問題プレビューID: bcd8ea12基本情報技術者試験 午前免除試験 2021年7月25日

問 7
基本情報技術者試験 午前免除試験 2021年7月25日

2 分探索木になっている 2 分木はどれか。

解説

正解は「イ」です。

2 分探索木とは,任意の節において,左部分木のすべての節の値がその節の値より小さく,右部分木のすべての節の値がその節の値より大きい 2 分木です。各選択肢の構造を確認します。

  • ア: 根 16 の左の子 15 に対し,その右の子が 14 です。右の子は親より大きくなければならないのに 14 < 15 なので不適切です。
  • イ: 根 17 に対し,左部分木 {14,10,16}\{14, 10, 16\} はすべて 17 より小さく,右部分木 {19,18}\{19, 18\} はすべて 17 より大きいです。節 14 は左の子 10 < 14,右の子 16 > 14 を満たし,節 19 は左の子 18 < 19 を満たします。すべての条件を満たすので適切です。
  • ウ: 根 18 の左の子 16 に対し,その右の子が 14 であり,14 < 16 なので不適切です。
  • エ: 根 20 の右の子が 19 であり,19 < 20 なので不適切です。

したがって「イ」が正解です。

関連問題

本文が同じ・似ている問題を表示しています