基本情報技術者平成17年秋期 午前問12

午前問12

すべての葉が同じ深さをもち,葉以外のすべての節点が二つの子をもつ2分木に関して,節点数と深さの関係を表す式はどれか。ここで,nは節点数,kは根から葉までの深さを表す。例に示す2分木の深さkは2である。
12.gif/image-size:218×126
  • 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」になります。
© 2010-2020 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop