基本情報技術者試験 基本情報技術者試験 令和7年度 科目A 公開問題 午前 問3: 図の木構造は２分探索木である。a〜g の値の大小関係として，適切なものはどれか。ここで，a〜g の値は重複しないものとする。

正解

イ. d＜b＜e＜a＜f＜c＜g

正答率 58.1%（1,258人中 731人が正解）

問題の解説

2分探索木は「任意のノードの左部分木の値 < 自ノードの値 < 右部分木の値」という大小関係を満たします。図の木はaが根で、左部分木にb（左子d・右子e）、右部分木にc（左子f・右子g）を持つので、左→自→右の順（中順走査）で訪問すると値は昇順に並びます。すなわち d＜b＜e＜a＜f＜c＜g となり、選択肢イが正解です。

選択肢ごとの解説

• ア根のaが先頭にきており、2分探索木の中順走査の順序になっていません。
• イ中順走査の結果 d＜b＜e＜a＜f＜c＜g と一致しており、2分探索木の大小関係を満たします。
• ウ葉ノードのd,e,f,gが連続しており、aが最大としていますが、これは2分探索木の構造と矛盾します。
• エ順序が逆（降順）になっており、aを最大としていますが、aは中央値であるため誤りです。