問題プレビューID: 70f8a4c4基本情報技術者試験 午前免除試験 2009年6月

問 5
基本情報技術者試験 午前免除試験 2009年6月

葉以外の節点はすべて二つの子をもち,根から葉までの深さがすべて等しい木を考える。この木に関する記述のうち,適切なものはどれか。ここで,深さとは根から葉に至るまでの枝の個数を表す。

解説

正解は「エ」です。

問題文の木は,根から葉までの深さがすべて等しく,葉以外の節点がすべて二つの子をもつので,完全二分木(perfect binary tree)である。木の深さを dd とすると,各レベルの節点数は上から 1,2,4,…,2d1, 2, 4, \ldots, 2^d となり,次が成り立つ。

  • 葉の個数は 2d2^d
  • 節点の総数は 2d+1−12^{d+1} - 1
  • 葉以外の節点の個数は 2d−12^d - 1

葉の個数を nn とすると n=2dn = 2^d であり,葉以外の節点の個数は 2d−1=n−12^d - 1 = n - 1 となる。

  • ア: 枝の個数が nn のとき,節点の個数は n+1n + 1 であり誤り。
  • イ: 木の深さが nn ならば,葉の個数は 2n2^n であり誤り。
  • ウ: 節点の個数が nn ならば,深さは log⁡2(n+1)−1\log_2(n + 1) - 1 となり誤り。
  • エ: 葉の個数が nn のとき,葉以外の節点の個数は n−1n - 1 となり正しい。

したがって,正解は「エ」です。

関連問題

本文が同じ・似ている問題を表示しています