基本情報技術者試験「木構造」の問題
空の 2 分探索木に対し、次の擬似言語の挿入規則に従って 400, 200, 600, 100, 300, 500 をこの順に挿入した。挿入後の木において、根の右の子がさらにもつ左の子（根→右→左とたどったノード）の値はどれか。挿入規則は「値が現ノードより小さければ左、大きければ右へ進み、空の位置に達したらそこに挿入する」である。
○手続: insert(ノード: root, 整数型: v)
ノード: cur ← root
while (true)
if (v < cur.値)
if (cur.左 が 空)
cur.左 ← 新ノード(v); return
endif
cur ← cur.左
else
if (cur.右 が 空)
cur.右 ← 新ノード(v); return
endif
cur ← cur.右
endif
endwhileイ500
ア60
ウ右の子の左で500
エ100
正解
イ．500
400 が根、600 が根の右の子になる。500 は 500>400 で右へ、500<600 で左へ進み 600 の左の子となるため、根→右→左の値は 500 であり イが正しい。
?選択肢ごとの解説
イ ○400 が根、600 が根の右の子になる。500 は 500>400 で右へ、500<600 で左へ進み 600 の左の子となるため、根→右→左の値は 500 であり イが正しい。
ア ×根の右の子 600 自体を答えるつもりで桁を取り違え 60 とした、もう 1 段左へたどる指示の見落としと桁の誤りである。
ウ ×値だけでなく経路の説明を冗長に書いた『右の子の左で500』とした、簡潔な値の解答形式から外れた誤りである。
エ ×最小値 100（根→左→左）を答えた、たどる経路を左寄りに誤った誤りである。
✎くわしく
2 分探索木では各値が根から比較で一意の位置に決まる。挿入順が同じなら同じ形になり、根→右→左のような相対経路でノードを特定できる点が要点である。
✓本番での押さえどころ
試験のコツ
挿入のたびに木を一段ずつ描き足し、最後に問われた経路を矢印でたどる。
覚え方
『小さければ左、大きければ右』を各挿入で唱えながら木を更新する。
よくある誤り
挿入順を無視して値の大小だけで形を推測し、子の配置を取り違えるミスが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-b-algo-0113