노드의 개수가 177인 완전 이진 트리(complete binary t… | [7급 국가직 자료구조론] 16년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 16년 1회차
노드의 개수가 177인 완전 이진 트리(complete binary tree)에서 마지막 레벨(level)에 위치한 노드의 개수는? (단, 루트 노드는 첫 번째 레벨에 위치한다)
1
49
2
50
3
78
4
127
해설

마지막 레벨에는 50개의 노드가 있다.

완전 이진 트리는 마지막 레벨 직전까지 꽉 차 있다. 레벨 k까지의 노드 수는 2k−12^k - 1이고 27−1=127≤177<28−1=2552^7 - 1 = 127 \le 177 \lt 2^8 - 1 = 255이므로, 레벨 1~7이 포화 상태이고 레벨 8이 마지막 레벨이다.
177−127=50177 - 127 = 50

  • 49는 177−27177 - 2^7로, 레벨 7까지의 노드 수를 128로 잘못 센 값이다.
  • 78은 레벨 8의 최대 노드 수 128에서 50을 뺀 값, 즉 마지막 레벨의 빈 자리 수이다.
  • 127은 레벨 7까지 포화된 노드 수로, 마지막 레벨 위쪽 전체의 노드 수이다.

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

이어서 풀어보기

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