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

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】
次の2分探索木から要素12を削除したとき,その位置に別の要素を移動するだけで2分探索木を再構成するには,削除された要素の位置にどの要素を移動すればよいか。
12.gif

  • 9
  • 10
  • 13
  • 14
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:データ構造
解説
2分探索木は、2分木の各節にデータをもたせることで探索を行えるようにした木です。各節がもつデータは「その節から出る左部分木にあるどのデータよりも大きく、右部分木のどのデータよりも小さい」という条件があり、これを利用して効率的なデータ探索を可能にしています。
問題文の2分探索木から要素12を削除すると、2分探索木の性質(要素同士の大小関係)を保つために12に最も近い値である「要素11」または「要素13」を新たな節点として再構成が行われます。
  • 12a.gif
    節点となる要素9の左部分木に要素10と要素11が存在することになるので不適切です。
  • 12i.gif
    節点となる要素10の左部分木に要素11が存在することになるので不適切です。
  • 12u.gif
    正しい。節点となる要素13の左部分木に要素9,要素10,要素11、右部分木に要素14,要素15が配置されることになるので適切です。
  • 12e.gif
    節点となる要素14の右部分木に要素13が存在することになるので不適切です。

この問題の出題歴


Pagetop