アルゴリズムとプログラミング
平成23年度 特別試験 基本情報技術者試験 午前 問5
空の 2 分探索木に，8, 12, 5, 3, 10, 7, 6 の順にデータを与えたときにできる 2 分探索木はどれか。
選択肢ア～エはいずれも2分木の図（節点は丸囲みの数字）。
- ア [図] 根8。左子5（左子3，右子6），右子10（左子7，右子12）
- イ [図] 根8。左子5（左子3，右子7（左子6）），右子10（右子12）
- ウ [図] 根8。左子5（左子3（右子7），右子6），右子12（左子10）
- エ [図] 根8。左子5（左子3，右子7（左子6）），右子12（左子10）
出典：平成23年度 特別試験 基本情報技術者試験 午前 問5
答えと解説を見る
正解：エ
覚える知識
2分探索木へのデータ挿入順による形状
2分探索木は、各節点で左部分木が節点値より小さく右部分木が大きくなるよう、挿入順に根から比較して構築する木構造である。
この問題で必要なこと
データを順に根から比較し、小さければ左・大きければ右へ辿って葉に挿入する。8,12,5,3,10,7,6では12は8の右、10は12の左、7は5の右、6は7の左になる。
ひっかけ
12と10の位置関係(10が8の右ではなく12の左)や6の位置を取り違えさせる。
この知識の出題：本試験系 1 回・免除試験 2 回（公開問題での観測値）