令和6年度 公開問題 科目B 問4
次の記述中の[ ]に入れる正しい答えを,解答群の中から選べ。ここで,配列の要素番号は 1 から始まる。
関数 merge は,昇順に整列された整数型の配列 data1 及び data2 を受け取り,これらを併合してできる昇順に整列された整数型の配列を返す。
関数 merge を merge({2, 3}, {1, 4}) として呼び出すと,/*** α ***/ の行は。
○整数型の配列: 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
| 答え | |
|---|---|
| ア | 0 |
| イ | 1 |
| ウ | 2 |
| エ | 3 |
出典:令和6年度 基本情報技術者試験 科目B 公開問題 問4
正解と解説を見る
正解:イ
ポイント:マージ(併合)は、2つの列の先頭を比べて小さい方から取る。片方が尽きたら、残りをそのまま写す。
整列済みの2つの配列 data1={2, 3}、data2={1, 4} を1つの整列済みの配列にまとめ、αの行(data2 の残りを写す行)が何回実行されるかを数えます。
最初の while(両方に残りがある間):
・2 と 1 を比べる → 1 を取る(j=2)。work={1}
・2 と 4 を比べる → 2 を取る(i=2)。work={1, 2}
・3 と 4 を比べる → 3 を取る(i=3)。work={1, 2, 3}
i=3 で data1 が尽きたので、ループを抜けます。
2つ目の while(data1 の残り):i=3 > 2 なので実行しません。
3つ目の while(data2 の残り):j=2 ≦ 2 なので、4 を写すαの行が1回だけ実行されます。
よって 1 回(イ)。最終的な work は {1, 2, 3, 4} です。
解説と下の表はこのサイトが作成したものです(表は、正解の選択肢を入れたプログラムを実際に実行した結果です)。
正解のプログラムを動かしてみる
merge({2, 3}, {1, 4}) を呼び出したときに、1行ずつ何が起きるかの表です(全部で 30 手)。「真・偽」は、その行の条件の判定です。
| 手 | 実行した行 | 変わった値 |
|---|---|---|
| 1 | 1行目○整数型の配列: merge(整数型の配列: data1, 整数型の配列: data2) | data1 = {2, 3} data2 = {1, 4} |
| 2 | 2行目整数型: n1 ← data1の要素数 | n1 = 2 |
| 3 | 3行目整数型: n2 ← data2の要素数 | n2 = 2 |
| 4 | 4行目整数型の配列: work ← {(n1 + n2)個の 未定義の値} | work = {未定義, 未定義, 未定義, 未定義} |
| 5 | 5行目整数型: i ← 1 | i = 1 |
| 6 | 6行目整数型: j ← 1 | j = 1 |
| 7 | 7行目整数型: k ← 1 | k = 1 |
| 8 | 8行目while ((i ≦ n1) and (j ≦ n2)) | 真 |
| 9 | 9行目if (data1[i] ≦ data2[j]) | 偽 |
| 10 | 13行目work[k] ← data2[j] | work = {1, 未定義, 未定義, 未定義} |
| 11 | 14行目j ← j + 1 | j = 2 |
| 12 | 16行目k ← k + 1 | k = 2 |
| 13 | 8行目while ((i ≦ n1) and (j ≦ n2)) | 真 |
| 14 | 9行目if (data1[i] ≦ data2[j]) | 真 |
| 15 | 10行目work[k] ← data1[i] | work = {1, 2, 未定義, 未定義} |
| 16 | 11行目i ← i + 1 | i = 2 |
| 17 | 16行目k ← k + 1 | k = 3 |
| 18 | 8行目while ((i ≦ n1) and (j ≦ n2)) | 真 |
| 19 | 9行目if (data1[i] ≦ data2[j]) | 真 |
| 20 | 10行目work[k] ← data1[i] | work = {1, 2, 3, 未定義} |
| 21 | 11行目i ← i + 1 | i = 3 |
| 22 | 16行目k ← k + 1 | k = 4 |
| 23 | 8行目while ((i ≦ n1) and (j ≦ n2)) | 偽 |
| 24 | 18行目while (i ≦ n1) | 偽 |
| 25 | 23行目while (j ≦ n2) | 真 |
| 26 | 24行目work[k] ← data2[j] /*** α ***/ | work = {1, 2, 3, 4} |
| 27 | 25行目j ← j + 1 | j = 3 |
| 28 | 26行目k ← k + 1 | k = 5 |
| 29 | 23行目while (j ≦ n2) | 偽 |
| 30 | 28行目return work |
戻り値:{1, 2, 3, 4}