基本情報技術者平成13年春期 午前問12

問12

2分探索木になっている2分木はどれか。
  • 12a.gif/image-size:185×102
  • 12i.gif/image-size:185×102
  • 12u.gif/image-size:185×102
  • 12e.gif/image-size:185×102
  • [出題歴]
  • 基本情報技術者 H28秋期 問6

分類

テクノロジ系 » アルゴリズムとプログラミング » データ構造

正解

解説

2分探索木は、2分木の各節にデータをもたせることで探索を行えるようにした木です。各節がもつデータは「その節から出る左部分木にあるどのデータよりも大きく、右部分木のどのデータよりも小さい」という条件があります。

要するにどの部分についても「左<中<右」の関係を満たしていれば2分探索木といえます。最も簡単に見分ける方法は図示されている木構造の各節点を左から順にならべて昇順になっているか否かを確認することです。
12.gif/image-size:292×203
  • 左から順に 10,15,14,16,18,19 となり、2分探索木の条件を満たすためには15と14の位置が逆だとわかります。
  • 左から順に 14,15,16,17,18,19,20 となり、昇順に整列されているため2分探索木だとわかります。
  • 左から順に 15,16,14,18,19,20 となり、15,16,14の順番が昇順になっていません。
  • 左から順に 10,18,14,20,15,19,16 となり、昇順ではありません。なお、この木構造は2分探索木ではありませんが、全ての葉が同じ「深さ」を持っているため完全2分木になります。
2分木
各節からでる枝の数が2本以下で構成される木
© 2010-2024 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop