다음 다섯 개의 숫자를 갖는 최소 힙(min-heap)을 만들려고 한다… | [7급 국가직 자료구조론] 14년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 14년 1회차
다음 다섯 개의 숫자를 갖는 최소 힙(min-heap)을 만들려고 한다. 구성할 수 있는 서로 다른 최소 힙의 경우의 수는?
1, 2, 3, 4, 5
1
1개
2
6개
3
8개
4
10개
해설

구성할 수 있는 서로 다른 최소 힙은 8개이다.

힙은 완전 이진 트리이므로 노드 5개의 모양은 하나로 고정되고, 루트는 최솟값 1이다. 루트의 왼쪽 서브트리는 노드 3개, 오른쪽 서브트리는 노드 1개이다.

남은 2~5 중 왼쪽에 들어갈 3개 선택: (43)=4\binom{4}{3}=4
3노드 서브트리는 루트가 최솟값으로 고정되고 두 자식 배치가 2가지
4×2=84\times 2=8

  • 1개: 루트만 고정될 뿐 나머지 원소의 배치는 여러 가지이다.
  • 6개: 왼쪽 원소 조합 4가지마다 두 배치가 모두 힙 조건을 만족하므로 8보다 적지 않다.
  • 10개: 3노드 서브트리 내부 배치는 2가지뿐이므로 8을 넘을 수 없다.

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

이어서 풀어보기

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