基本情報技術者試験「整列」の問題
次の擬似言語は、ともに昇順整列済みの 2 つの配列 L と R を 1 つの昇順配列にマージする手続である。L = {11, 27, 38}、R = {9, 25, 40}（どちらも添字は 1 から）を与えて実行したとき、戻り値の配列 res の内容はどれか。
○配列: merge(整数型の配列: L, 整数型の配列: R)
整数型の配列: res ← {}（空）
整数型: i ← 1, j ← 1
while (i <= Lの要素数 かつ j <= Rの要素数)
if (L[i] <= R[j])
res の末尾に L[i] を追加; i ← i + 1
else
res の末尾に R[j] を追加; j ← j + 1
endif
endwhile
i <= Lの要素数 の間 L[i] を res に追加し i を進める
j <= Rの要素数 の間 R[j] を res に追加し j を進める
return resア{11, 27, 38, 9, 25, 40}
イ{9, 11, 25, 38, 27, 40}
ウ{9, 11, 25, 27, 38, 40}
エ{40, 38, 27, 25, 11, 9}
正解
ウ．{9, 11, 25, 27, 38, 40}
マージは L と R の先頭同士を比較し小さい方を res に移す操作の繰り返しである。9→11→25→27→38 と取り、最後に R の 40 が残って追加され {9,11,25,27,38,40} となるため ウが正しい。
?選択肢ごとの解説
ア ×比較を行わず L を全部出してから R を全部出した {11,27,38,9,25,40} であり、while の比較を無視した誤りである。
イ ×途中で比較対象を取り違え 38 と 27 の順序が逆になった {9,11,25,38,27,40} であり、添字 i,j の更新ミスによる誤りである。
ウ ○マージは L と R の先頭同士を比較し小さい方を res に移す操作の繰り返しである。9→11→25→27→38 と取り、最後に R の 40 が残って追加され {9,11,25,27,38,40} となるため ウが正しい。
エ ×昇順ではなく降順に並べた {40,…,9} であり、比較演算子の向きを逆にした誤りである。
✎くわしく
マージは 2 つの整列済み列を線形時間で 1 つに統合する分割統治の要である。先頭比較と添字前進、そして片方が尽きたあとの残り要素の後処理という 3 段構成を漏れなく追う。
✓本番での押さえどころ
試験のコツ
L と R に指（添字）を 1 本ずつ置き、小さい方を取って指を 1 つ進める動作を 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-0039