다음에 주어진 최대 힙(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개이므로 여섯째 위치부터 끝까지가 리프이다.
42+3+2+30+14+17=10842+3+2+30+14+17=108

  • 63 — 최종 리프 여섯 개의 합보다 작아, 리프 일부가 빠진 값이다.
  • 73 — 상향 조정 결과와 다른 리프 구성에서 나오는 값이다.
  • 113 — 최종 리프 합보다 커서, 리프가 아닌 노드의 키가 섞인 값이다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 20년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기