깊이(depth)가 k인 이진트리(binary tree)가 가질 수 있… | [7급 국가직 자료구조론] 09년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 09년 1회차
깊이(depth)가 k인 이진트리(binary tree)가 가질 수 있는 최대 노드 수를 A라고 하고, 최소 노드 수를 B라고 할 때, A - B의 값은? (단, 루트노드의 레벨은 1로 한다)
1
2k−1+k+12^{k-1} + k + 1
2
2k−1+k−12^{k-1} + k - 1
3
2k−k−12^{k} - k - 1
4
2k−k+12^{k} - k + 1
해설

A − B 의 값은 2k−k−12^{k} - k - 1이다.

최대 노드 수는 모든 레벨이 꽉 찬 포화 이진트리일 때로, 레벨 i에 2i−12^{i-1}개씩 있으므로 A=2k−1A = 2^{k} - 1이다.
최소 노드 수는 레벨마다 노드가 하나뿐인 편향 이진트리일 때로 B=kB = k이다.
A−B=(2k−1)−k=2k−k−1A - B = (2^{k} - 1) - k = 2^{k} - k - 1

  • 2k−1+k+12^{k-1} + k + 1: 깊이 1이면 노드가 하나뿐이라 A − B 는 0이어야 하는데 3이 된다.
  • 2k−1+k−12^{k-1} + k - 1: 깊이 1에서 1이 되어 0이 아니므로 맞지 않는다.
  • 2k−k+12^{k} - k + 1: 깊이 1에서 2가 되어 상수항 부호가 틀렸다.

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

이어서 풀어보기

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