基本情報技術者試験「連結リスト」の問題
単方向連結リストの各ノードは val（整数）と next（参照、なければ NULL）をもつ。次の擬似言語は、値 target をもつ最初のノードを 1 つだけ削除する手続である。head→[600]→[755]→[755]→[900]→NULL に対し target=755 を与えて実行したあと、head から末尾までの val の並びはどれか。
○手続: deleteFirst(ノード: head, 整数型: target)
ノード: cur ← head
ノード: prev ← NULL
while (cur が NULL でない)
if (cur.val が target と等しい)
prev.next ← cur.next
return
endif
prev ← cur
cur ← cur.next
endwhileイ{600, 755, 900}
ア{600, 900}
ウ{755, 900}
エ{600, 755, 755, 900}
正解
イ．{600, 755, 900}
手続は最初に target と一致したノードを prev.next の付け替えで 1 つだけ外し、return で終了する。2 番目の 755 が外れて並びは {600, 755, 900} となるため イが正しい。
?選択肢ごとの解説
イ ○手続は最初に target と一致したノードを prev.next の付け替えで 1 つだけ外し、return で終了する。2 番目の 755 が外れて並びは {600, 755, 900} となるため イが正しい。
ア ×値が 755 のノードをすべて削除したと誤認し {600, 900} とした、return による 1 個限定の打ち切りを見落とした誤りである。
ウ ×先頭 600 と 755 の両方を削除したと取り違えて {755, 900} とした、削除対象を広げすぎた誤りである。
エ ×どのノードも削除されず元の並び {600, 755, 755, 900} のままとした、target 一致時の付け替えを行わなかった誤りである。
✎くわしく
単方向リストの削除は『削除ノードの直前 prev の next を削除ノードの next に付け替える』ことで実現する。return があるため一致が複数あっても最初の 1 個だけが対象となる。
✓本番での押さえどころ
試験のコツ
prev と cur のペアを 1 ノードずつずらし、最初に一致した瞬間の付け替え結果だけを書く。
覚え方
『前のノードの矢印を飛び越し先につなぐ』と覚え、return で 1 個限定と確認する。
よくある誤り
return を見落として全削除と考えたり、削除する 755 がどちらの位置かを取り違えるミスが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 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-0110