アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20240609 実施分 問5
葉以外の節点は全て二つの子をもち，根から葉までの深さが全て等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，木の深さとは根から葉に至るまでの枝の個数を表す。また，節点には根及び葉も含まれる。
- ア 枝の個数が n ならば，節点の個数も n である。
- イ 木の深さが n ならば，葉の個数は 2^(n-1) である。
- ウ 節点の個数が n ならば，木の深さは log_2 n である。
- エ 葉の個数が n ならば，葉以外の節点の個数は n－1 である。
出典：基本情報技術者試験 科目A免除 修了試験 20240609 実施分 問5
答えと解説を見る
正解：エ
覚える知識
完全2分木の節点数と葉の数の関係
葉以外の節点が全て2つの子をもつ2分木では、内部節点数は葉の数-1である。
この問題で必要なこと
完全2分木で葉がn個なら内部節点はn-1個。
ひっかけ
深さnの葉数を2^(n-1)と誤る(正しくは2^n)など。
この知識の出題：本試験系 0 回・免除試験 5 回（公開問題での観測値）