다음 최대힙(Max Heap) 트리를 일차원 배열에 표현할 경우, 배열… | [7급 국가직 자료구조론] 15년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 15년 1회차
다음 최대힙(Max Heap) 트리를 일차원 배열에 표현할 경우, 배열에서 최댓값을 두 번 삭제한 후 남아있는 배열의 상태로 옳은 것은? (단, 최대힙 배열에서 첫 번째 요소는 비어있다)
최대힙의 배열 표현:
| - | 9 | 7 | 8 | 3 | 6 | 4 | 5 | 1 | 2 |

1
| - | 7 | 3 | 6 | 4 | 5 | 1 | 2 |
2
| - | 7 | 6 | 5 | 3 | 4 | 1 | 2 |
3
| - | 7 | 6 | 5 | 3 | 1 | 4 | 2 |
4
| - | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
해설
최댓값을 두 번 삭제한 뒤의 배열은 7, 6, 5, 3, 1, 4, 2이다.
첫 번째 삭제: 루트 9를 빼고 마지막 원소 2를 루트로 올린 뒤 더 큰 자식과 교환하며 내린다(2↔8, 2↔5).
결과: 8, 7, 5, 3, 6, 4, 2, 1두 번째 삭제: 루트 8을 빼고 마지막 원소 1을 루트로 올린 뒤 더 큰 자식과 교환하며 내린다(1↔7, 1↔6).
결과: 7, 6, 5, 3, 1, 4, 2
- 7, 3, 6, 4, 5, 1, 2: 루트 7의 자식 3이 그 자식 4·5보다 작아 힙 조건을 어긴다.
- 7, 6, 5, 3, 4, 1, 2: 1이 내려간 자리에 4가 와 있어 삭제 과정의 교환 결과와 다르다.
- 7, 6, 5, 4, 3, 2, 1: 내림차순 정렬 상태로, 재힙화(sift-down) 결과가 아니다.
오류나 개정된 내용이 보이면 알려주세요
이어서 풀어보기
[7급 국가직 자료구조론] 15년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요비슷한 기출
- java에서힙(heap)에남아있으나변수가가지고있던참조값을잃거나변수자체가없어짐으로써더이상사용되지않는객체를제거해주는역할을하는모듈은? {"answer":2,21년-3회차-정보처리기사-필기
- 힙정렬(heapsort)에대한설명으로틀린것은? {"answer":4,"content":[{"content":"정렬할입력레코드들로힙을구성하고가장큰키값을갖21년-2회차-정보처리기사-필기
- 폭15[m]도로양쪽에간격20[m]로대칭배열된가로등이점등되어있다.한등의전광속8000[lm],조명률45[%]일때도로의조도를계산하시오. 양쪽대칭배열에서가로등1등이담당하전기기사 실기 2022년 2회 기출유형문제