問題プレビューID: 38e297c0基本情報技術者試験 午前免除試験 2025年6月8日

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

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

解説

正解は「エ」です。

この木は,葉以外のすべての節点が二つの子をもつ完全二分木です。完全二分木では,葉の個数は葉以外(内部)の節点の個数より必ず 1 つ多くなります。したがって,葉の個数が n ならば,葉以外の節点の個数は n−1 個となります。

  • ア: 木では枝(辺)の個数は節点の個数より 1 少ないので,枝が n ならば節点は n+1 個です。
  • イ: 深さ n の完全二分木の葉の個数は 2 の n 乗です。2 の (n−1) 乗ではありません。
  • ウ: 節点の総数は 2 の (深さ+1) 乗から 1 を引いた値なので,深さは log2 (n+1) − 1 となり,log2 n ではありません。

関連問題

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