テクノロジ系
秋期
応用情報技術者 2018年 秋期 問6
6 / 80
葉以外の節点は全て二つの子をもち、根から葉までの深さが全て等しい木を考え る。この木に関する記述のうち、適切なものはどれか。ここで、木の深さとは根か ら葉に至るまでの枝の個数を表す。また、節点には根及び葉も含まれる。
正解と解説
表示する
正解 エ
葉の個数がnならば、葉以外の節点の個数は1ー1である。
完全2分木(葉以外は必ず2子、全葉の深さが等しい)では、葉の個数をnとすると葉以外(内部節点)の個数はn-1になります。よって正解はエです。深さnなら葉は2^n個、節点総数は2^(n+1)-1個であり、他の選択肢の関係式は成り立ちません。