問題プレビューID: b75e8e81応用情報技術者試験 2018年(平成30年度)秋期 午前

問 6
応用情報技術者試験 2018年(平成30年度)秋期 午前

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

解説

正解は「エ」です。

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

  • 葉の個数は 2d2^d
  • 葉以外(内部)の節点の個数は 1+2+⋯+2d−1=2d−11 + 2 + \cdots + 2^{d-1} = 2^d - 1
  • 節点の総数は 2d+1−12^{d+1} - 1
  • ア: 一般に木では「節点の個数 = 枝の個数 + 1」であり,両者が等しくなることはありません。
  • イ: 深さが nn のときの葉の個数は 2n2^n です。2n−12^{n-1} は誤りです。
  • ウ: 節点の総数が nn のとき,n=2d+1−1n = 2^{d+1} - 1 より深さは log⁡2(n+1)−1\log_2 (n+1) - 1 となり,log⁡2n\log_2 n ではありません。
  • エ: 葉の個数が n=2dn = 2^d のとき,葉以外の節点の個数は 2d−1=n−12^d - 1 = n - 1 となります。正しい記述です。

関連問題

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