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