アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 200906 実施分 問5
葉以外の節点はすべて二つの子をもち，根から葉までの深さがすべて等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，深さとは根から葉に至るまでの枝の個数を表す。
答えを選ぶ
出典：基本情報技術者試験 科目A免除 修了試験 200906 実施分 問5（問題文は IPA の公開問題。解説は当サイト作成）
解説に誤りを見つけたら、解説の誤りを報告してください。
答えと解説を見る
正解：エ
覚える知識
完全2分木の節点数と葉の数の関係
全ての非葉節点が 2 つの子を持つ 2 分木では、葉の数は非葉節点の数より 1 多い。
この問題で必要なこと
完全2分木では葉が n 個なら葉以外の節点は n−1 個。深さ d なら葉は 2^d 個、節点は 2^(d+1)−1 個である。
ひっかけ
深さと葉の数の指数を 2^(n−1) と取り違えたり、節点数と枝数を同一視したりする。
この知識の出題：本試験系 0 回・免除試験 5 回（公開問題での観測値）。頻出知識ランキング860位（全1,254件中）。