다음 C 코드에서 heapify(a, 7)을 수행한 후 배열 a[]의 … | [7급 국가직 자료구조론] 24년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 24년 1회차
다음 C 코드에서 heapify(a, 7)을 수행한 후 배열 a[]의 내용은? (단, 모든 배열 원소값은 양의 정수로 한정하고, －1은 연산 대상이 아니며, 0은 삭제된 값을 나타낸다)int a[8]={-1, 1, 2, 3, 6, 4, 7, 5};
int heapify(int *a, int n) {
int item=a[1], temp=a[n];
int i=1, j=2;
a[n]=0, n=n-1;
while(j<=n) {
if(j<n && a[j]>a[j+1]) j++;
if(temp<a[j]) break;
else {
a[i]=a[j];
i=j;
j=j*2;
}
}
a[i]=temp;
return item;
}
1
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| －1 | 2 | 3 | 4 | 6 | 5 | 7 | 0 |
2
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| －1 | 2 | 4 | 3 | 6 | 5 | 7 | 0 |
3
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| －1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 |
4
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| －1 | 2 | 4 | 3 | 5 | 6 | 7 | 0 |
해설
heapify(a, 7) 수행 후 배열은 -1, 2, 4, 3, 6, 5, 7, 0이다.
이 함수는 최소 힙의 루트 삭제이다. 루트 1을 item에 보관하고 마지막 원소 5를 temp로 꺼낸 뒤 a[7]=0, n=6으로 만들고, 루트 자리에서 더 작은 자식과 temp를 비교하며 내려간다.
i=1: 자식 a[2]=2, a[3]=3 중 작은 2가 temp 5보다 작으므로 a[1]=2, i=2
i=2: 자식 a[4]=6, a[5]=4 중 작은 4가 5보다 작으므로 a[2]=4, i=5
j=10 > n이므로 종료하고 a[5]=5를 저장한다.
- -1, 2, 3, 4, 6, 5, 7, 0은 a[2] 자리에 3이 올라가 있어, i=2에서 자식 6, 4 중 작은 4를 끌어올리는 과정과 맞지 않는다.
- -1, 2, 3, 4, 5, 6, 7, 0은 완전히 정렬된 상태로, 한 경로만 따라 내려가는 삭제 연산의 결과가 아니다.
- -1, 2, 4, 3, 5, 6, 7, 0은 temp 5가 a[4]에 들어간 형태로, 더 작은 자식 a[5]=4 쪽으로 내려가야 한다는 점과 맞지 않는다.
오류나 개정된 내용이 보이면 알려주세요