問題
葉以外の節点は全て二つの子をもち，根から葉までの深さが全て等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，木の深さとは根から葉に至るまでの枝の個数を表す。また，節点には根及び葉も含まれる。
選択肢
- 1枝の個数が n ならば，節点の個数も n である。
- 2木の深さが n ならば，葉の個数は 2^(n-1) である。
- 3節点の個数が n ならば，木の深さは log2 n である。
- 4葉の個数が n ならば，葉以外の節点の個数は n-1 である。
正解
4. 葉の個数が n ならば，葉以外の節点の個数は n-1 である。
詳しい解説を見る解説を閉じる
解説
完全二分木では，葉の個数をnとすると葉以外の節点（内部節点）の個数はn−1になる。例えば葉4個なら内部節点は3個。アは節点数=枝数+1，イは葉の個数は2^n，ウは深さがlog2(節点数+1)−1程度であり，いずれも誤り。（出典: 平成30年度 秋期 応用情報技術者試験 午前 問6）
一問一答
全400問を繰り返し学習