アルゴリズムとプログラミング
平成31年度 春期 基本情報技術者試験 午前 問5
2 分探索木として適切なものはどれか。ここで，数字 1～9 は，各ノード（節）の値を表す。
ア〜エ各々が 2 分木の図。
ア: 1 ─ 左2(左4, 右5), 右3(左6(左8, 右9), 右7)
イ: 4 ─ 左2(左1, 右3), 右8(左6(左5, 右7), 右9)
ウ: 7 ─ 左6(左4, 右5), 右8(左3(左1, 右2), 右9)
エ: 9 ─ 左7(左1, 右2), 右8(左5(左3, 右4), 右6)
- ア [図] 根1，左の子2（子: 4, 5），右の子3（子: 6, 7。6 の子: 8, 9）
- イ [図] 根4，左の子2（子: 1, 3），右の子8（子: 6, 9。6 の子: 5, 7）
- ウ [図] 根7，左の子6（子: 4, 5），右の子8（子: 3, 9。3 の子: 1, 2）
- エ [図] 根9，左の子7（子: 1, 2），右の子8（子: 5, 6。5 の子: 3, 4）
出典：平成31年度 春期 基本情報技術者試験 午前 問5
答えと解説を見る
正解：イ
覚える知識
2分探索木の大小関係
2分探索木は、各ノードで左部分木の値が小さく、右部分木の値が大きい2分木である。
この問題で必要なこと
各ノードの左部分木は全てそのノードより小さく、右部分木は全て大きい。これを満たす図を選ぶ。
ひっかけ
ヒープ状の配置や、一部だけ大小関係を満たす図を正しい木に見せかける。
この知識の出題：本試験系 4 回・免除試験 8 回（公開問題での観測値）