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

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

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

解説

正解は「エ」です。

すべての葉の深さが等しく,葉以外の節点がすべて二つの子をもつ木は,完全二分木(perfect binary tree)と呼ばれます。この木では,葉以外の各節点がちょうど二つの子をもつことから,節点の総数は「葉の個数 × 2 − 1」,葉以外の節点は「葉の個数 − 1」となります。したがって,「エ」が正解です。

  • ア: 節点の個数は枝の個数より 1 多くなります(枝+1=節点\text{枝} + 1 = \text{節点})。
  • イ: 深さ nn の完全二分木の葉の個数は 2n2^{n} です。
  • ウ: 節点の個数が nn のとき,深さは log⁡2(n+1)−1\log_2 (n+1) - 1 となり,log⁡2n\log_2 n ではありません。

関連問題

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