FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次のマージ処理を途中まで実行したとき、戻り値はどれか。 整数…
問題
次のマージ処理を途中まで実行したとき、戻り値はどれか。
整数型の配列: a ← {1, 4, 6, 9}
整数型の配列: b ← {2, 4, 5, 8}
整数型: i ← 1, j ← 1
整数型の配列: out ← {}
while (i ≦ aの要素数 and j ≦ bの要素数 and outの要素数 ＜ 5)
if (a[i] ≦ b[j])
append(out, a[i])
i ← i ＋ 1
else
append(out, b[j])
j ← j ＋ 1
endif
endwhile
return out[5]- ア 4
- イ 5（正解）
- ウ 6
- エ 8
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：5
2つの整列済み配列の先頭候補を比べ、小さい方をoutへ追加します。同値のときは条件がa[i]≦b[j]なので、a側を先に追加します。
| 追加値 | i | j | out |
|---|---|---|---|
| 1 | 2 | 1 | {1} |
| 2 | 2 | 2 | {1,2} |
| 4(a) | 3 | 2 | {1,2,4} |
| 4(b) | 3 | 3 | {1,2,4,4} |
| 5 | 3 | 4 | {1,2,4,4,5} |
out[5]は5です。同じ4が2回出る点を落とすと答えがずれます。
選択肢の見分け方：4は同値4の片方だけを見た誤り、6や8は5個目で止めずに先へ進めた誤りです。outの要素数が5になった時点で処理を止めます。
このアルゴリズムの正体：これはマージソートの核となる「2つの整列済み配列を併合する処理」です。1回の繰返しで小さい側の要素を1個取り出しポインタを1つ進めるため、本来なら要素数の合計に比例するO(m＋n)で全要素を併合できます。本問は条件にoutの要素数＜5が加わっているので、5個目を入れた時点で残りを見ずに止まる途中打切りになっている点が要注意です。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。