基本情報技術者試験「連結リスト」の問題
単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。次の擬似言語は、先頭 head から連なるリストの向きを逆転させ、新しい先頭ノードを返す手続である。head→[105]→[270]→[330]→[480]→NULL を与えて実行したとき、戻り値として返される新しい先頭ノードの val はどれか。
○ノード: reverse(ノード: head)
ノード: prev ← NULL
ノード: cur ← head
ノード: nxt
while (cur が NULL でない)
nxt ← cur.next
cur.next ← prev
prev ← cur
cur ← nxt
endwhile
return prevエ480
ア15
イ105480
ウ330
正解
エ．480
反転では各ノードの next を 1 つ前のノードへ付け替え、prev が逆順リストの先頭を保持する。最後に prev が指すのは元の末尾 480 であり、戻り値の val は 480 となるため エが正しい。
?選択肢ごとの解説
エ ○反転では各ノードの next を 1 つ前のノードへ付け替え、prev が逆順リストの先頭を保持する。最後に prev が指すのは元の末尾 480 であり、戻り値の val は 480 となるため エが正しい。
ア ×反転を行わず元の先頭 105 をそのまま返すつもりで桁を取り違え 15 とした、prev と head の取り違えと桁の誤りである。
イ ×先頭 105 と末尾 480 を連結して 105480 とした、val を数値結合と取り違えた桁の誤りである。
ウ ×中央付近のノード 330 を新先頭と誤った、付け替えの最終位置を見失った誤りである。
✎くわしく
単方向リストの反転は prev・cur・nxt の 3 ポインタで next を逆向きに付け替える定石である。next を退避する nxt を先に保存しないと後続ノードを失う点が核心である。
✓本番での押さえどころ
試験のコツ
反転は『退避→付け替え→prev 前進→cur 前進』の 4 行を 1 セットで追い、最後の prev を答える。
覚え方
『矢印を全部逆向きに描き直す』と唱え、末尾が新先頭になると覚える。
よくある誤り
nxt への退避を忘れて cur.next←prev の直後にリンクをたどれなくなるミスが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 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-0109