基本情報技術者試験「連結リスト」の問題
単方向連結リスト head→[10]→[20]→[30]→NULL がある。各ノードは val と next をもつ。次の擬似言語は、値 target をもつノードの直後に値 v の新ノードを挿入する手続である。target=20, v=25 を与えて実行したあと、head から末尾までの val の並びはどれか。
○手続: insertAfter(ノード: head, 整数型: target, 整数型: v)
ノード: cur ← head
while (cur が NULL でない)
if (cur.val が target と等しい)
ノード: node ← 新ノード(v)
node.next ← cur.next
cur.next ← node
return
endif
cur ← cur.next
endwhileア{10, 20, 25, 30}
イ{10, 25, 20, 30}
ウ{25, 10, 20, 30}
エ{10, 20, 30, 25}
正解
ア．{10, 20, 25, 30}
target=20 のノードを走査で見つけ、新ノード 25 の next を元の cur.next（30）に向け、cur.next を 25 に付け替える。順序を保って 25 が 20 と 30 の間に入り {10,20,25,30} となるため アが正しい。
?選択肢ごとの解説
ア ○target=20 のノードを走査で見つけ、新ノード 25 の next を元の cur.next（30）に向け、cur.next を 25 に付け替える。順序を保って 25 が 20 と 30 の間に入り {10,20,25,30} となるため アが正しい。
イ ×挿入位置を 1 つ手前にずらし 10 の直後に入れた {10,25,20,30} であり、target の一致判定をずらした誤りである。
ウ ×先頭に挿入した {25,10,20,30} であり、直後挿入ではなく先頭追加と取り違えた誤りである。
エ ×末尾に追加した {10,20,30,25} であり、target の直後ではなくリスト末尾へ付けた誤りである。
✎くわしく
連結リストへの直後挿入は『新ノードの next を先につなぎ、それから前ノードの next を新ノードに張り替える』順序が要である。順序を逆にすると後続ノードへの参照を失う。
✓本番での押さえどころ
試験のコツ
挿入は『new.next ← cur.next』を先に、『cur.next ← new』を後に、の順で 2 本の矢印を描いて確認する。
覚え方
『新しい人の手を後ろの人につないでから、前の人の手をつなぎ替える』と順序を覚える。
よくある誤り
張り替えの順序を逆にして後続を切り離すミス、挿入位置を 1 つずらすミスが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 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-0041