問題
葉以外の節点は全て二つの子をもち、根から葉までの深さが全て等しい木を考える。この木に関する記述のうち、適切なものはどれか。ここで、深さとは根から葉に至るまでの枝の個数を表す。また、節点には根及び葉も含まれる。
選択肢
- 1枝の個数が n ならば、節点の個数も n である。
- 2木の深さが n ならば、葉の個数は 2ⁿ⁻¹ である。
- 3節点の個数が n ならば、深さは log₂n である。
- 4葉の個数が n ならば、葉以外の節点の個数は n−1 である。
正解
4. 葉の個数が n ならば、葉以外の節点の個数は n−1 である。
詳しい解説を見る解説を閉じる
解説
葉以外の節点が全て二つの子をもつ完全二分木では、葉の個数を n とすると、葉以外（内部）の節点の個数は n−1 になるという性質が成り立つ。これは二分木で「内部節点数＝葉の数−1」となる一般的な定理であり、エが正解。深さ k の木では葉の数は 2ᵏ、全節点数は 2ᵏ⁺¹−1 であり、他の選択肢は指数の式が合わない。（出典: 平成25年度 秋期 応用情報技術者試験 午前 問6）
一問一答
全400問を繰り返し学習