다음에 주어진 최대 힙(max heap)에 키 값이 2, 14, 49,… | [7급 국가직 자료구조론] 20년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 20년 1회차
다음에 주어진 최대 힙(max heap)에 키 값이 2, 14, 49, 3, 30, 41, 27, 17인 8개의 데이터를 순서대로 삽입하여 최대 힙을 구성하였다. 구성된 최대 힙에서 모든 리프(leaf) 노드의 키 값의 합은?
1
63
2
73
3
108
4
113
해설
구성된 최대 힙의 리프 키 합은 108이다.
초기 힙 72, 35, 42에 각 키를 맨 끝에 넣고 부모보다 크면 교환하는 상향 조정을 반복한다. 49는 42와, 30은 2와, 41은 30·35와, 27은 14와 교환된다.
최종 배열은 72, 41, 49, 35, 27, 42, 3, 2, 30, 14, 17이고, 노드가 11개이므로 여섯째 위치부터 끝까지가 리프이다.
- 63 — 최종 리프 여섯 개의 합보다 작아, 리프 일부가 빠진 값이다.
- 73 — 상향 조정 결과와 다른 리프 구성에서 나오는 값이다.
- 113 — 최종 리프 합보다 커서, 리프가 아닌 노드의 키가 섞인 값이다.
오류나 개정된 내용이 보이면 알려주세요
