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

1[7급 국가직 자료구조론] 11년 1회차
N개의 노드를 가진 완전 이진 트리(complete binary tree)에 대한 설명으로 옳지 않은 것은? (단, 루트 노드의 높이는 1로 한다)
1
단말(terminal) 노드의 개수는 비단말(non-terminal) 노드의 개수와 같거나 하나가 더 많다.
2
높이가 K라면 노드 개수 N의 범위는 2K−1≤N≤2K−12^{K-1} \le N \le 2^{K}-1이다.
3
포화 이진 트리(full binary tree)는 완전 이진 트리의 일종이다.
4
완전 이진 트리를 최악으로 구성할 경우 높이는 N이다.
해설

완전 이진 트리는 왼쪽부터 빈틈없이 채우므로 높이가 ⌊log⁡2N⌋+1\lfloor \log_2 N \rfloor + 1로 제한되며, 높이가 N이 된다는 설명이 옳지 않다.

높이가 N이 되는 경우는 노드가 한쪽으로만 이어진 편향 이진 트리로, 완전 이진 트리가 될 수 없다.

  • 완전 이진 트리의 단말 노드 수는 N/2의 올림, 비단말 노드 수는 내림이므로 같거나 하나 더 많다.
  • 높이 K일 때 최소는 마지막 레벨에 노드가 하나인 경우, 최대는 모든 레벨이 꽉 찬 경우이므로 제시된 범위가 성립한다.
  • 포화 이진 트리는 모든 레벨이 꽉 찬 트리로 완전 이진 트리의 조건을 만족한다.

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

이어서 풀어보기

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