平成17年秋期試験問題 午前問12

すべての葉が同じ深さをもち,葉以外のすべての節点が二つの子をもつ2分木に関して,節点数と深さの関係を表す式はどれか。ここで,nは節点数,kは根から葉までの深さを表す。例に示す2分木の深さkは2である。
12.png

  • n=k(k+1)+1
  • n=2k+3
  • n=2k+1-1
  • n=(k-1)(k+1)+4
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:データ構造
解説
葉以外のすべての節点がすべての子を持ち、根から葉までの深さがすべて等しい2分木を完全2分木といいます。

この木構造において深さ(k)が増加すると節点数(n)は次のように変化していきます。
  • k=1→n=3
  • k=2→n=7
  • k=3→n=15
  • k=4→n=31
ここでは選択肢の式にk=3を代入して、nが15になるか否かで適切な式を導きます。
  • 3(3+1)+1=12+1=13(×)
  • 23+3=8+3=11(×)
  • 23+1-1=16-1=15()
  • (3-1)(3+1)+4=8+4=12(×)
したがって節点数と深さの関係を表す式は「n=2k+1-1」になります。

Pagetop