基本情報技術者試験「連結リスト」の問題
単方向連結リストの各ノードは val と next（参照、末尾は NULL）をもつ。次の擬似言語は、リスト a の末尾にリスト b をつなげ、連結後の先頭を返す手続である。a=headA→[110]→[220]→[330]→NULL、b=headB→[440]→[550]→NULL を与えて実行したとき、返された先頭から末尾までの val の並びはどれか。
○ノード: concat(ノード: a, ノード: b)
if (a が NULL)
return b
endif
ノード: cur ← a
while (cur.next が NULL でない)
cur ← cur.next
endwhile
cur.next ← b
return aウ{110, 220, 330, 440, 550}
ア{110, 440, 220, 550, 330, 110}
イ{440, 550, 110}
エ{110, 220, 330}
正解
ウ．{110, 220, 330, 440, 550}
while で a の末尾（next が NULL のノード 330）まで進み、その next に b の先頭 440 を接続する。先頭 a を返すので並びは {110, 220, 330, 440, 550} となり ウが正しい。
?選択肢ごとの解説
ウ ○while で a の末尾（next が NULL のノード 330）まで進み、その next に b の先頭 440 を接続する。先頭 a を返すので並びは {110, 220, 330, 440, 550} となり ウが正しい。
ア ×2 つのリストを交互に併合したうえ先頭 110 を重複させて {110, 440, 220, 550, 330, 110} とした、連結をマージと取り違えた誤りである。
イ ×b を a の前に置いたうえ末尾を取りこぼして {440, 550, 110} とした、接続の向きを逆にし要素も落とした誤りである。
エ ×b を接続せず a の元の並び {110, 220, 330} のままとした、末尾への接続を行わなかった誤りである。
✎くわしく
リスト連結は『a の末尾を探し、その next に b の先頭を付ける』だけで、b 側は再構築しない。末尾探索の while 条件 cur.next≠NULL を正しく置くことが核心である。
✓本番での押さえどころ
試験のコツ
末尾ノードは『next が NULL のノード』と定義し、そこへ b の先頭をつなぐと整理する。
覚え方
『a の最後の矢印を b の先頭へ伸ばす』と覚える。
よくある誤り
while 条件を cur≠NULL とすると末尾を通り越して NULL を参照し、接続に失敗するミスが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 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-0111