그림과 같은 최대 힙(max heap)을 구성하기 위한 삽입 순서로 옳… | [7급 국가직 자료구조론] 17년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 17년 1회차
그림과 같은 최대 힙(max heap)을 구성하기 위한 삽입 순서로 옳은 것은?
1
50, 30, 40, 70, 60, 10, 20
2
10, 60, 50, 70, 20, 30, 40
3
10, 20, 40, 30, 60, 50, 70
4
50, 60, 30, 10, 20, 70, 40
해설
그림의 최대 힙(배열 70, 50, 60, 10, 20, 30, 40)을 만드는 삽입 순서는 50, 60, 30, 10, 20, 70, 40이다.
50 다음 60이 들어오면 위로 교환되어 [60, 50]이 되고, 30·10·20은 부모보다 작아 그대로 붙어 [60, 50, 30, 10, 20]이 된다. 70은 30의 자식 자리에 들어가 30, 60과 차례로 교환되어 루트가 되고, 마지막 40은 부모 60보다 작아 그대로 남아 그림과 같아진다.
- 50, 30, 40, 70, 60, 10, 20 순서는 70, 60이 왼쪽으로 올라가 [70, 60, 40, 30, 50, 10, 20]이 되어 다르다.
- 10, 60, 50, 70, 20, 30, 40 순서는 [70, 60, 50, 10, 20, 30, 40]이 되어 루트의 왼쪽 자식이 60이므로 다르다.
- 10, 20, 40, 30, 60, 50, 70 순서는 [70, 40, 60, 10, 30, 20, 50]이 되어 다르다.
오류나 개정된 내용이 보이면 알려주세요
