問題プレビューID: a349cd96基本情報技術者試験 午前免除試験 2023年6月11日

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

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

解説

正解は「エ」です。

葉以外の節点がすべて二つの子をもつ木では,葉以外の節点の個数を m,葉の個数を n とすると,枝(辺)の本数は,各内部節点が 2 本ずつ枝を出すので「2m」であり,また「節点の総数 − 1 = (m + n) − 1」でもあります。したがって 2m = m + n − 1 より m = n − 1 となり,葉の個数が n ならば葉以外の節点の個数は n − 1 です。

  • ア: 枝の本数は節点の総数より 1 少ないため,両者が等しくなることはありません。
  • イ: すべての葉の深さが等しい完全二分木では,深さ n のときの葉の個数は 2n2^n です。2n−12^{n-1} ではありません。
  • ウ: 節点の個数と深さの関係は木の形によって変わるため,log⁡2n\log_2 n とは限りません。

関連問題

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