うごく基本情報

令和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 手)。「真・偽」は、その行の条件の判定です。

手実行した行変わった値
11行目○整数型の配列: merge(整数型の配列: data1, 整数型の配列: data2)data1 = {2, 3}
data2 = {1, 4}
22行目整数型: n1 ← data1の要素数n1 = 2
33行目整数型: n2 ← data2の要素数n2 = 2
44行目整数型の配列: work ← {(n1 + n2)個の 未定義の値}work = {未定義, 未定義, 未定義, 未定義}
55行目整数型: i ← 1i = 1
66行目整数型: j ← 1j = 1
77行目整数型: k ← 1k = 1
88行目while ((i ≦ n1) and (j ≦ n2))真
99行目if (data1[i] ≦ data2[j])偽
1013行目work[k] ← data2[j]work = {1, 未定義, 未定義, 未定義}
1114行目j ← j + 1j = 2
1216行目k ← k + 1k = 2
138行目while ((i ≦ n1) and (j ≦ n2))真
149行目if (data1[i] ≦ data2[j])真
1510行目work[k] ← data1[i]work = {1, 2, 未定義, 未定義}
1611行目i ← i + 1i = 2
1716行目k ← k + 1k = 3
188行目while ((i ≦ n1) and (j ≦ n2))真
199行目if (data1[i] ≦ data2[j])真
2010行目work[k] ← data1[i]work = {1, 2, 3, 未定義}
2111行目i ← i + 1i = 3
2216行目k ← k + 1k = 4
238行目while ((i ≦ n1) and (j ≦ n2))偽
2418行目while (i ≦ n1)偽
2523行目while (j ≦ n2)真
2624行目work[k] ← data2[j] /*** α ***/work = {1, 2, 3, 4}
2725行目j ← j + 1j = 3
2826行目k ← k + 1k = 5
2923行目while (j ≦ n2)偽
3028行目return work

戻り値:{1, 2, 3, 4}

サイトで、1行ずつ予想しながら動かす →