이진 트리로 구성하는 것이 불가능한 것은? (단, 루트(root) 노드… | [7급 국가직 자료구조론] 14년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 14년 1회차
이진 트리로 구성하는 것이 불가능한 것은? (단, 루트(root) 노드의 단계(level)는 1이라고 가정한다)
1
노드 개수가 23개이고 높이가 5인 이진 트리
2
높이가 5이고 노드 개수가 10개이며 단말 노드 개수가 6개인 이진 트리
3
노드 개수가 20개이고 간선이 19개인 이진 트리
4
높이가 6이고 노드 개수가 32개인 완전 이진 트리
해설

구성이 불가능한 것은 높이 5, 노드 10개, 단말 노드 6개인 이진 트리이다.

이진 트리에서는 단말 노드 수가 차수 2인 노드 수보다 항상 1 많다(n0=n2+1n_0=n_2+1).

n2=6−1=5n_2=6-1=5
n1=10−6−5=−1n_1=10-6-5=-1
차수 1인 노드 수가 음수가 되어 성립하지 않는다.

  • 노드 23개·높이 5: 높이 5의 노드 수는 5개부터 25−1=312^5-1=31개까지 가능하다.
  • 노드 20개·간선 19개: 모든 트리는 간선 수가 노드 수보다 1 적으므로 가능하다.
  • 높이 6·노드 32개인 완전 이진 트리: 5단계까지 31개를 채우고 6단계 맨 왼쪽에 1개를 두면 된다.

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

이어서 풀어보기

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