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