基本情報技術者試験「木構造」の問題
空の 2 分探索木に対して、50, 30, 70, 20, 60 の順に値を挿入した。次の擬似言語に従ってさらに値 65 を挿入したとき、65 を子としてもつ親ノードの値はどれか。挿入規則は「値が現ノードより小さければ左、大きければ右へ進み、進んだ先が空ならそこに挿入する」である。
○手続: 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ア50
イ70
ウ30
エ60
正解
エ．60
挿入経路は 50→（65>50 で右）70→（65<70 で左）60→（65>60 で右、空）となる。最後に止まった 60 の右に挿入されるため親は 60 であり エが正しい。
?選択肢ごとの解説
ア ×根 50 でいきなり挿入されると誤認したもので、50 の右はすでに 70 が存在するため空ではない。
イ ×70 の左がすでに 60 で埋まっていることを見落とし、70 を親とした誤りである。
ウ ×65>50 で右へ進むべきところを左（30 側）へ進んだ、比較の向きを取り違えた誤りである。
エ ○挿入経路は 50→（65>50 で右）70→（65<70 で左）60→（65>60 で右、空）となる。最後に止まった 60 の右に挿入されるため親は 60 であり エが正しい。
✎くわしく
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-0040