平成25年 秋期 応用情報技術者 午前 問6

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

　ア 　枝の個数がn ならば、葉を含む節点の個数もn である。
　イ 　木の深さがn ならば、葉の個数は2n -1である。
　ウ 　節点の個数がn ならば、深さはlog2n である。
　エ 　葉の個数がn ならば、葉以外の節点の個数はn -1である。

答え　エ

【解説】
完全二分木の図で確認しながら、選択肢を確認する。

　ア 　根以外のすべての節点には親とつながるための枝を持っているので、枝の個数がn ならば、節点の個数はn +1である。(+1は根。)
　イ 　木の深さが1(親と子のみ)ならば葉の数は2(=21)、木の深さが2(親と子、孫)ならば葉の数は4(=22)であり、木の深さがn ならば葉の数は2n である。
　ウ 　木の深さが1(親と子のみ)ならば節の数は3(=1+2)、木の深さが2(親と子、孫)ならば節の数は7(=1+2+4)、木の深さが3ならば節の数は15(=1+2+4+8)であり、木の深さがn ならば節の数は2n +1-1であり、選択肢の条件は成立しない。(なお、葉の個数がn ならば、木の深さはlog2n である。)
　エ 　葉の数が2(木の深さが1)のとき葉以外の節の個数は1(根のみ)であり、葉の数が4(木の深さが2)のとき葉以外の節の個数は3(=1+2)、葉の数が8(木の深さが3)のとき葉以外の節の個数は7(=1+2+4)であり、葉の数がn ならば葉以外の節の個数はn -1である。

【キーワード】
・二分木

【キーワードの解説】

戻る 一覧へ 次へ