うごく基本情報

サンプル問題(2022年4月公開) 科目B 問4

二次元配列 ・ 二重ループ ・ トレース

次の記述中の[ ]~[ ]に入れる正しい答えの組合せを,解答群の中から選べ。ここで,配列の要素番号は 1 から始まる。
要素の多くが 0 の行列を疎行列という。次のプログラムは,二次元配列に格納された行列のデータ量を削減するために,疎行列の格納に適したデータ構造に変換する。
関数 transformSparseMatrix は,引数 matrix で二次元配列として与えられた行列を,整数型配列の配列に変換して返す。関数 transformSparseMatrix をtransformSparseMatrix({{3, 0, 0, 0, 0}, {0, 2, 2, 0, 0}, {0, 0, 0, 1, 3}, {0, 0,0, 2, 0}, {0, 0, 0, 0, 1 }})として呼び出したときの戻り値は, {{[ ]},{[ ]}, {[ ]}} である。

○整数型配列の配列: transformSparseMatrix(整数型の二次元配列: matrix)
  整数型: i, j
  整数型配列の配列: sparseMatrix
  sparseMatrix ← {{}, {}, {}}  /* 要素数0の配列を三つ要素にもつ配列 */
  for (i を 1 から matrixの行数 まで 1 ずつ増やす)
    for (j を 1 から matrixの列数 まで 1 ずつ増やす)
      if (matrix[i, j] が 0 でない)
        sparseMatrix[1]の末尾 に iの値 を追加する
        sparseMatrix[2]の末尾 に jの値 を追加する
        sparseMatrix[3]の末尾 に matrix[i, j]の値 を追加する
      endif
    endfor
  endfor
  return sparseMatrix
答え答え答え
ア1,2,2,3,3,4,51,2,3,4,5,4,53,2,2,1,2,3,1
イ1,2,2,3,3,4,51,2,3,4,5,4,53,2,2,1,3,2,1
ウ1,2,3,4,5,4,51,2,2,3,3,4,53,2,2,1,2,3,1
エ1,2,3,4,5,4,51,2,2,3,3,4,53,2,2,1,3,2,1

出典:基本情報技術者試験 科目B試験 サンプル問題(2022年4月公開) 問4

正解と解説を見る

正解:イ

ポイント:二重ループは「行ごとに、左から右へ」。0 でない要素の行番号・列番号・値を見つけた順に並べる。

行列を1行目から順に、各行を左から右へ調べ、0 でない要素を見つけるたびに、行番号、列番号、値をそれぞれの配列に追加します。
問題の行列で 0 でない要素を、見つかる順に書くと:
1行1列=3、2行2列=2、2行3列=2、3行4列=1、3行5列=3、4行4列=2、5行5列=1
よって
行番号:1, 2, 2, 3, 3, 4, 5
列番号:1, 2, 3, 4, 5, 4, 5
値:3, 2, 2, 1, 3, 2, 1
で(イ)。
アは値の5番目と6番目(3, 2)の順が逆です。ウ・エは行番号と列番号が逆です。
外側のループが行、内側のループが列なので、同じ行の中では列番号の小さい順に見つかります。

解説と下の表はこのサイトが作成したものです(表は、正解の選択肢を入れたプログラムを実際に実行した結果です)。

正解のプログラムを動かしてみる

transformSparseMatrix({{3, 0, 0, 0, 0}, {0, 2, 2, 0, 0}, {0, 0, 0, 1, 3}, {0, 0, 0, 2, 0}, {0, 0, 0, 0, 1}}) を呼び出したときに、1行ずつ何が起きるかの表です(全部で 87 手、最初の 60 手を表示)。「真・偽」は、その行の条件の判定です。

手実行した行変わった値
11行目○整数型配列の配列: transformSparseMatrix(整数型の二次元配列: matrix)matrix = {{3, 0, 0, 0, 0}, {0, 2, 2, 0, 0}, {0, 0, 0, 1, 3}, {0, 0, 0, 2, 0}, {0, 0, 0, 0, 1}}
22行目整数型: i, j
33行目整数型配列の配列: sparseMatrix
44行目sparseMatrix ← {{}, {}, {}} /* 要素数0の配列を三つ要素にもつ配列 */sparseMatrix = {{}, {}, {}}
55行目for (i を 1 から matrixの行数 まで 1 ずつ増やす)真
i = 1
66行目for (j を 1 から matrixの列数 まで 1 ずつ増やす)真
j = 1
77行目if (matrix[i, j] が 0 でない)真
88行目sparseMatrix[1]の末尾 に iの値 を追加するsparseMatrix = {{1}, {}, {}}
99行目sparseMatrix[2]の末尾 に jの値 を追加するsparseMatrix = {{1}, {1}, {}}
1010行目sparseMatrix[3]の末尾 に matrix[i, j]の値 を追加するsparseMatrix = {{1}, {1}, {3}}
116行目for (j を 1 から matrixの列数 まで 1 ずつ増やす)真
j = 2
127行目if (matrix[i, j] が 0 でない)偽
136行目for (j を 1 から matrixの列数 まで 1 ずつ増やす)真
j = 3
147行目if (matrix[i, j] が 0 でない)偽
156行目for (j を 1 から matrixの列数 まで 1 ずつ増やす)真
j = 4
167行目if (matrix[i, j] が 0 でない)偽
176行目for (j を 1 から matrixの列数 まで 1 ずつ増やす)真
j = 5
187行目if (matrix[i, j] が 0 でない)偽
196行目for (j を 1 から matrixの列数 まで 1 ずつ増やす)偽
j = 6
205行目for (i を 1 から matrixの行数 まで 1 ずつ増やす)真
i = 2
216行目for (j を 1 から matrixの列数 まで 1 ずつ増やす)真
j = 1
227行目if (matrix[i, j] が 0 でない)偽
236行目for (j を 1 から matrixの列数 まで 1 ずつ増やす)真
j = 2
247行目if (matrix[i, j] が 0 でない)真
258行目sparseMatrix[1]の末尾 に iの値 を追加するsparseMatrix = {{1, 2}, {1}, {3}}
269行目sparseMatrix[2]の末尾 に jの値 を追加するsparseMatrix = {{1, 2}, {1, 2}, {3}}
2710行目sparseMatrix[3]の末尾 に matrix[i, j]の値 を追加するsparseMatrix = {{1, 2}, {1, 2}, {3, 2}}
286行目for (j を 1 から matrixの列数 まで 1 ずつ増やす)真
j = 3
297行目if (matrix[i, j] が 0 でない)真
308行目sparseMatrix[1]の末尾 に iの値 を追加するsparseMatrix = {{1, 2, 2}, {1, 2}, {3, 2}}
319行目sparseMatrix[2]の末尾 に jの値 を追加するsparseMatrix = {{1, 2, 2}, {1, 2, 3}, {3, 2}}
3210行目sparseMatrix[3]の末尾 に matrix[i, j]の値 を追加するsparseMatrix = {{1, 2, 2}, {1, 2, 3}, {3, 2, 2}}
336行目for (j を 1 から matrixの列数 まで 1 ずつ増やす)真
j = 4
347行目if (matrix[i, j] が 0 でない)偽
356行目for (j を 1 から matrixの列数 まで 1 ずつ増やす)真
j = 5
367行目if (matrix[i, j] が 0 でない)偽
376行目for (j を 1 から matrixの列数 まで 1 ずつ増やす)偽
j = 6
385行目for (i を 1 から matrixの行数 まで 1 ずつ増やす)真
i = 3
396行目for (j を 1 から matrixの列数 まで 1 ずつ増やす)真
j = 1
407行目if (matrix[i, j] が 0 でない)偽
416行目for (j を 1 から matrixの列数 まで 1 ずつ増やす)真
j = 2
427行目if (matrix[i, j] が 0 でない)偽
436行目for (j を 1 から matrixの列数 まで 1 ずつ増やす)真
j = 3
447行目if (matrix[i, j] が 0 でない)偽
456行目for (j を 1 から matrixの列数 まで 1 ずつ増やす)真
j = 4
467行目if (matrix[i, j] が 0 でない)真
478行目sparseMatrix[1]の末尾 に iの値 を追加するsparseMatrix = {{1, 2, 2, 3}, {1, 2, 3}, {3, 2, 2}}
489行目sparseMatrix[2]の末尾 に jの値 を追加するsparseMatrix = {{1, 2, 2, 3}, {1, 2, 3, 4}, {3, 2, 2}}
4910行目sparseMatrix[3]の末尾 に matrix[i, j]の値 を追加するsparseMatrix = {{1, 2, 2, 3}, {1, 2, 3, 4}, {3, 2, 2, 1}}
506行目for (j を 1 から matrixの列数 まで 1 ずつ増やす)真
j = 5
517行目if (matrix[i, j] が 0 でない)真
528行目sparseMatrix[1]の末尾 に iの値 を追加するsparseMatrix = {{1, 2, 2, 3, 3}, {1, 2, 3, 4}, {3, 2, 2, 1}}
539行目sparseMatrix[2]の末尾 に jの値 を追加するsparseMatrix = {{1, 2, 2, 3, 3}, {1, 2, 3, 4, 5}, {3, 2, 2, 1}}
5410行目sparseMatrix[3]の末尾 に matrix[i, j]の値 を追加するsparseMatrix = {{1, 2, 2, 3, 3}, {1, 2, 3, 4, 5}, {3, 2, 2, 1, 3}}
556行目for (j を 1 から matrixの列数 まで 1 ずつ増やす)偽
j = 6
565行目for (i を 1 から matrixの行数 まで 1 ずつ増やす)真
i = 4
576行目for (j を 1 から matrixの列数 まで 1 ずつ増やす)真
j = 1
587行目if (matrix[i, j] が 0 でない)偽
596行目for (j を 1 から matrixの列数 まで 1 ずつ増やす)真
j = 2
607行目if (matrix[i, j] が 0 でない)偽

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

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