基本情報技術者試験の公開問題を解こう！（令和６年度・科目B）（4）「マージソート」

基本情報技術者試験の令和6年度の公開問題（科目B）を解いてみよう。

〔プログラム〕

○整数型の配列: merge(整数型の配列: data1, 整数型の配列: data2)
整数型: n1 ← data1の要素数
整数型: n2 ← data2の要素数
整数型の配列: work ← {(n1 + n2)個の 未定義の値}
整数型: i ← 1
整数型: j ← 1
整数型: k ← 1
while ((i ≦ n1) and (j ≦ n2))
if (data1[i] ≦ data2[j])
work[k] ← data1[i]
i ← i + 1
else
work[k] ← data2[j]
j ← j + 1
endif
k ← k + 1
endwhile

while (i ≦ n1)
work[k] ← data1[i]
i ← i + 1
k ← k + 1
endwhile

while (j ≦ n2)
work[k] ← data2[j] /*** α ***/
j ← j + 1
k ← k + 1
endwhile
return work

解答群
ア 　実行されない
イ 　1 回実行される
ウ 　2 回実行される
エ 　3 回実行される

この問題は、マージソートの「マージ処理」部分に関する理解を問うものである。

問題の概要

関数 merge(data1, data2) は、昇順に整列された2つの配列を受け取り、それらを1つの昇順配列にマージして返す関数である。

呼び出しは以下の通り

merge({2, 3}, {1, 4})

このとき、プログラム中の /*** α ***/ の行（work[k] ← data2[j]）が何回実行されるかを問うものである。。

処理の流れを追ってみよう

初期状態

• data1 = {2, 3}（要素数2）
• data2 = {1, 4}（要素数2）
• i = 1, j = 1, k = 1

1回目の比較

• data1[1] = 2, data2[1] = 1
• 1 < 2 → work[1] = 1（data2の要素を追加）
• j = 2, k = 2

2回目の比較

• data1[1] = 2, data2[2] = 4
• 2 < 4 → work[2] = 2（data1の要素を追加）
• i = 2, k = 3

3回目の比較

• data1[2] = 3, data2[2] = 4
• 3 < 4 → work[3] = 3（data1の要素を追加）
• i = 3, k = 4

ループ終了

• i > n1（data1の要素はすべて処理済み）
• j = 2（data2の2番目の要素が残っている）

最後の while ループ（αの行）

while (j ≦ n2)
  work[k] ← data2[j]  ← ★この行が α
  j ← j ＋ 1
  k ← k ＋ 1
endwhile

このループは j = 2 から始まり、n2 = 2 なので、1回だけ実行されます。
したがって、正解は、「イ：1回実行される」となる。