깊이가 k인 포화이진트리(full binary tree)의 비단말노드의… | [7급 국가직 자료구조론] 13년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 13년 1회차
깊이가 k인 포화이진트리(full binary tree)의 비단말노드의 개수에서 단말노드의 개수를 뺀 값으로 옳은 것은? (단, k > 0)
1
-1
2
0
3
1
4
k - 1
해설

포화이진트리에서는 항상 비단말노드 수 = 단말노드 수 − 1이므로 차이는 −1이다.

깊이가 k이면 단말노드는 2k−12^{k-1}개, 비단말노드는 1+2+⋯+2k−2=2k−1−11+2+\cdots+2^{k-2}=2^{k-1}-1개다.

따라서 (2k−1−1)−2k−1=−1(2^{k-1}-1)-2^{k-1}=-1로, 깊이와 무관하게 일정하다.

  • 0: 두 개수가 같아야 하는데, 비단말노드가 항상 하나 적다.
  • 1: 부호가 반대다. 단말노드 쪽이 하나 더 많다.
  • k − 1: 차이는 깊이 k와 무관한 상수다.

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

이어서 풀어보기

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