2013 년 알 리 바 바 여름 인턴 필기시험 문제 - 2013 년 5 월 5 일 시험
어제 북 대 필기시험 을 보 러 가 려 고 했 는데 결국에는 패 필 을 주지 않 겠 다 고 했 어 요. 니 마, 그래 요. 형 이 또 순 순 히 돌 아 왔 어. 지금 인터넷 에 문제 가 생 겼 어 요. 가 져 와 서 해 봐 요. 19 번 필기시험 을 잘 준비 하 세 요!
--------------------------------------------------------------------------------------------------------------
문제 풀이:
1. 문제 풀이 시간 90 분, 시간 파악 에 주의 하 세 요.
2. 시험 문 제 는 네 가지 부분 으로 나 뉜 다. 한 가지 선택 문제 (10 문제, 20 점), 부정 방향 선택 문제 (4 문제, 20 점), 빈 칸 채 우기 문답 (5 문제, 40 점), 종합 체 (1 문제, 20 점) 이다.
--------------------------------------------------------------------------------------------------------------
1. 단일 선택 문제
1. 다음 의 잘못된 표현 은:
A.SATA 500Mbps/s
B. 18XDVD 1Gbps
C. 1Gpbs
D. DDR3 100Gbps분석: A 와 B 에 비해 어떻게 CD 의 속도 가 하 드 디스크 보다 빠 릅 니까?B. 틀림 없어 요.기 가 이 더 넷 의 속 도 는 1000 Mbps 이 고 1Gbps 라 고 쓸 수도 있다.DDR3 - 1600 의 극한 전송 속 도 는 12.8GBp / s 이다.
2. () Linux 의 프로 세 스 통신 에 사용 할 수 없습니다.
A.
B.
C.
D. 분석: Linux 의 프로 세 스 통신 방식 은 파이프, 메시지 큐, 공유 메모리, 소켓 이 있 습 니 다.
3. 메모리 에 P1, P2, P3 세 개의 프로그램 이 설치 되 어 있 고 P1, P2, P3 의 우선 순위 에 따라 실 행 됩 니 다. 그 중에서 내부 계산 과 IO 작업 시간 은 다음 표 에서 제 시 됩 니 다 (CPU 계산 과 IO 자원 은 한 프로그램 에서 만 사용 할 수 있 습 니 다).
P1: 60ms---》IO 80ms---》 20ms
P2: 120ms---》IO 40ms---》 40ms
P3: 40ms---》IO 80ms---》 40ms세 개의 프로그램 을 완성 하 는 것 이 한 개의 실행 보다 절약 하 는 시간 은 () 이다.
A.80ms
B.120ms
C.160ms
D.200ms4. 두 개의 등가 스 레 드 가 동시에 다음 프로그램 을 실행 합 니 다. a 는 전체 변수 이 고 초기 에는 0 입 니 다. printf, +, - 작업 이 모두 원자 적 이 라 고 가정 하면 출력 은 () 일 수 없습니다.
[cpp] view plain copy print ?
void foo() {
if(a <= 0) {
a++;
}
else{
a--;
}
printf("%d", a);
}
A.01
B.10
C.12
D.225. fun 함 수 를 다음 과 같이 지정 합 니 다. 그러면 fun (10) 의 출력 결 과 는 () 입 니 다.
[cpp] view plain copy print ?
int fun(intx)
{
return(x==1)? 1 : (x + fun(x-1));
}
A.0
B.10
C.55
D.36288006. c + 프로그램 에서 정형 변수 가 자주 사용 된다 면 그 를 () 로 정의 하 는 것 이 좋 습 니 다.
A.auto
B.extern
C.static
D.register7. n 길이 의 문자열 중 m 길이 의 하위 문자열 과 일치 하 는 복잡 도 는 () 입 니 다.
A.O(N)
B.O(M+N)
C.O(N+logM)
D.O(M+logN)8. n 개의 정수 a [] 에 i, j, k 만족 a [i] + a [j] = a [k] 가 존재 하 는 지 판단 하 는 시간 복잡 도 최소 값 은 ()
A.O(n^2) B. O(n^2*logn) C. O(n^3) D. O(nlogn)9. 다음 정렬 알고리즘 중 최 악의 경우 시간 복잡 도 는 n (n - 1) / 2 가 아 닙 니 다.
A. B. C. D. 10. 포탄 을 세 번 발사 하고 목 표를 명중 시 킬 확률 은 0.95 입 니 다. 한 번 발사 하면 목 표를 명중 시 킬 확률 은 얼마 입 니까?
A0.63
B0.50
C.0.32
D.0.862. 부정 방향 선택 문제
1. 기억 이 안 난다
2. 한 스 택 의 스 택 수 는 1, 2, 3, 4, 5, 6 입 니 다. 다음 중 어느 것 이 가능 한 스 택 순서 입 니까? (옵션 은 기억 나 지 않 습 니 다)
3. 다음 중 어떤 코드 가 a 와 b 의 수 치 를 교환 할 수 있 습 니까? (옵션 은 기억 나 지 않 습 니 다)
4. A 와 B 는 밤 에 심심 하면 별 을 세 기 시작한다. 매번 K 개 (20 & lt; = k & gt; = 30) 만 셀 수 있다. A 와 B 는 돌아 가면 서 세 어 본다. 마지막 에 누가 별 을 다 세 면 이 기 는 것 이다. 그러면 별 수가 얼마 일 때 A 가 반드시 이 기 는 것 일 까? (옵션 은 기억 나 지 않 는 다)
3. 빈 칸 채 우기 문답 문제
1. 전체 배열 A [N] 을 드 리 고 작은 프로그램 코드 (20 줄 이내) 를 완성 하여 A [N] 을 역방향 으로 합 니 다. 즉, 원래 배열 은 1, 2, 3, 4 이 고 역방향 은 4, 3, 2, 1 입 니 다.
[cpp] view plain copy print ?
void revense(int * a,int n) {
int begin = 0, end = n-1;
int tmp;
while(begin < end)
{
tmp = a[begin];
a[begin] = a[end];
a[end] = tmp;
++begin;
--end;
}
}
2. 스 케 쥴 링 에 관 한 문 제 는 제목 이 매우 길 습 니 다. 바로 세 개의 스 레 드 를 드 리 는 것 입 니 다. 먼저 분 배 된 전략 과 가장 짧 은 실행 간 의 스 케 쥴 링 전략 을 사용 한 다음 에 모든 스 레 드 가 제출 에서 실행 까지 의 시간 을 계산 하 는 것 입 니 다. 문제 가 너무 길 고 표 가 몇 개 있 습 니 다. 운영 체제 에서 작업 스 케 쥴 링 알고리즘 이 먼저 나 오고 가장 짧 은 작업 이 우선 입 니 다.
3. 한 고 된 직장 인 이 매일 알 람 을 맞 추 는 것 을 잊 어 버 릴 확률 은 0.2, 출근 시간 에 차 가 막 힐 확률 은 0.5 이다. 만약 에 알 람 을 맞 추 지 않 고 출근 하고 차 가 막 히 면 지각 할 확률 은 1.0 이다. 만약 에 알 람 을 맞 추 었 는데 출근 시간 에 차 가 막 히 면 지각 할 확률 은 0.8 이다. 만약 에 그 가 알 람 을 맞 추 지 않 았 는데 출근 시간 에 차 가 막 히 지 않 으 면 지각 할 확률 은 0.9 이다. 만약 에 그 가 알 람 을 맞 추고 출근 해도 막 히 지 않 으 면차 는 그 가 늦 을 확률 이 0. 0 이 라면 60 일 동안 출근 에 늦 을 것 이라는 기 대 를 구 했다.
정 답: 30.6 일
4. 전보 교류: 전장 에 위치 가 다른 N 개 전사 (n > 4)모든 전사 들 은 현재 의 전황 을 알 고 있 습 니 다. 지금 은 이 n 명의 전사 가 통 화 를 통 해 교 류 를 하고 자신 이 알 고 있 는 전황 정 보 를 전달 해 야 합 니 다. 매번 통 화 를 할 때마다 통화 하 는 쌍방 이 상대방 의 모든 정 보 를 알 게 할 수 있 습 니 다. 알고리즘 을 설계 하고 최소 의 통화 횟수 를 사용 해 야 합 니 다. 예, 전쟁터 의 n 명의 병사 들 은 모든 전황 정 보 를 알 고 프로그램 코드 를 쓰 지 않 아 도 됩 니 다. 가장 적은 것 을 얻 을 수통화 횟수.
5. N 명 이 있 습 니 다. 그 중의 한 스타 와 n - 1 명의 대중 은 모두 스타 를 알 고 있 습 니 다. 스타 는 그 어떠한 대중 도 모 릅 니 다. 대중 과 대중 간 의 인식 관 계 는 모 릅 니 다. 지금 만약 에 로봇 R2T 2 라면 한 사람 에 게 다른 사람 을 아 는 대가 가 O (1) 인지 물 어 볼 때마다 알고리즘 을 설계 하여 스타 를 찾아내 고 시간 복잡 도 (복잡 도 없 이 득점 하지 않 음) 를 제시 합 니 다.
정 답: 1 ~ n 이 n 명 을 옮 겨 다 니 며 1 번 과 2 번 을 먼저 꺼 내 고 1 번 이 2 를 안다 면 1 을 빼 고 1 번 이 2 를 모른다 면 2 를 빼 도 된다. 비교 할 때마다 하 나 를 빼 고 이렇게 순환 한다. n - 1 번 이후 에 한 사람 만 시간 복잡 도: O (n - 1)
종합 문제
타 오 바 오 상점 이 있 습 니 다. 한 도시 에 n 개의 창고 가 있 습 니 다. 창고 마다 저장량 이 다 릅 니 다. 지금 은 화물 운송 을 통 해 매번 창고 의 저장량 을 일치 시 켜 야 합 니 다. n 개 창고 간 의 운송 노선 은 도시 한 바퀴, 즉 1 - > 2 - > 3 - > 4 - >... - > n - > 1 - >... 화물 은 연 결 된 창고 로 만 운송 할 수 있 고 가장 작은 운송 원가 (수송량 * 거리) 를 설계 할 수 있 습 니 다.타 오 바 오 상점 의 요구 에 도달 하고 코드 를 작성 합 니 다.
해답: 이 문제 와 유사 한 문 제 는 다음 과 같다.
제목:http://www.lydsy.com/JudgeOnline/problem.php?id=1045 n 명의 어린이 가 한 바퀴 를 돌 고 있 습 니 다. 한 사람 에 게 ai 개의 사탕 이 있 습 니 다. 한 사람 은 좌우 두 사람 에 게 만 사탕 을 전달 할 수 있 습 니 다. 한 사람 에 게 한 개의 사탕 대 가 를 1 로 전달 하고 모든 사람 에 게 균등 한 사탕 의 최소 대 가 를 받 도록 합 니 다. 분석: a1 이 an 에 게 나 누 어 준 사탕 수 를 k 로 가정 하면 다음 과 같은 정 보 를 얻 을 수 있 습 니 다. a1 a2 a3 an - 1 an 현재 수량: a1 - k a2 a3 an - 1 an + k 에 필요 한 대가: | a1 - k - ave | a1 + a2 - k - 2 * ave | | a1 + a2 + a3 - k - 3 * ave | a1 +.. + a (n - 1) - k - (n - 1) * ave | |k | sum [i] 로 a1 에서 ai 로 i * ave 의 합 치 를 줄 이 는 것 을 표시 합 니 다. 이 이상 은 총 대가 = | s1 - k | + | s2 - k | +... + | s (n - 1) - k | + | k | 로 간략화 할 수 있 습 니 다. k 가 s1.. s (n - 1) 의 중위 일 때 필요 한 대 가 는 최소 입 니 다.
코드 를 네트워크 에 전송:
[cpp] view plain copy print ?
#include
#include
#include
using namespace std;
const int X = 1000005;
typedef longlong ll;
ll sum[X],a[X];
ll n;
ll Abs(ll x){
return max(x,-x);
}
int main(){
//freopen("sum.in","r",stdin);
while(cin>>n){
ll x;
ll tot = 0;
for(inti=1;i<=n;i++){
scanf("%lld",&a[i]);
tot += a[i];
}
ll ave = tot/n;
for(inti=1;i
sum[i] = a[i]+sum[i-1]-ave;
sort(sum+1,sum+n);
ll mid = sum[n/2];
ll ans = Abs(mid);
for(inti=1;i
ans += Abs(sum[i]-mid);
cout<
}
return0;
}
좋은 웹페이지 즐겨찾기
