基本情報技術者試験 基本情報技術者試験 令和元年度 科目A 修了認定試験 午前 問7: 葉以外の節点は全て二つの子をもち、根から葉までの深さが全て等しい木を考える。この木に関する記述のうち、適切なものはどれか。ここで、木の深さとは根から葉に至るまで

正解

エ. 葉の個数が n ならば、葉以外の節点の個数は n − 1 である。

正答率 48.4%（1,606人中 778人が正解）

問題の解説

葉以外の節点が全て二つの子をもつ完全二分木（厳密 2 分木）では、葉の個数 n に対し、内部節点（葉以外の節点）の個数は n−1 となる。

選択肢ごとの解説

• ア完全二分木の節点数は枝数+1 なので n+1 となり、n と等しくない。
• イ深さ n の完全二分木の葉の個数は 2^n であり、2^(n−1) ではない。
• ウ節点数 n のとき、深さは必ずしも log₂ n にならない（n+1=2^(d+1)−1 の関係から d=log₂((n+1)/1)−1）。
• エ葉 n 個の完全二分木の内部節点は n−1 個=正解。