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

問題本文

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

選択肢

• ア.枝の個数が n ならば、節点の個数も n である。
• イ.木の深さが n ならば、葉の個数は 2^(n−1) である。
• ウ.節点の個数が n ならば、木の深さは log₂ n である。
• エ.葉の個数が n ならば、葉以外の節点の個数は n − 1 である。

正解

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

解説

葉以外の節点が全て二つの子をもつ完全二分木（厳密 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 個=正解。