サンプル問題(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,5 | 1,2,3,4,5,4,5 | 3,2,2,1,2,3,1 |
| イ | 1,2,2,3,3,4,5 | 1,2,3,4,5,4,5 | 3,2,2,1,3,2,1 |
| ウ | 1,2,3,4,5,4,5 | 1,2,2,3,3,4,5 | 3,2,2,1,2,3,1 |
| エ | 1,2,3,4,5,4,5 | 1,2,2,3,3,4,5 | 3,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 手を表示)。「真・偽」は、その行の条件の判定です。
| 手 | 実行した行 | 変わった値 |
|---|---|---|
| 1 | 1行目○整数型配列の配列: 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}} |
| 2 | 2行目整数型: i, j | |
| 3 | 3行目整数型配列の配列: sparseMatrix | |
| 4 | 4行目sparseMatrix ← {{}, {}, {}} /* 要素数0の配列を三つ要素にもつ配列 */ | sparseMatrix = {{}, {}, {}} |
| 5 | 5行目for (i を 1 から matrixの行数 まで 1 ずつ増やす) | 真 i = 1 |
| 6 | 6行目for (j を 1 から matrixの列数 まで 1 ずつ増やす) | 真 j = 1 |
| 7 | 7行目if (matrix[i, j] が 0 でない) | 真 |
| 8 | 8行目sparseMatrix[1]の末尾 に iの値 を追加する | sparseMatrix = {{1}, {}, {}} |
| 9 | 9行目sparseMatrix[2]の末尾 に jの値 を追加する | sparseMatrix = {{1}, {1}, {}} |
| 10 | 10行目sparseMatrix[3]の末尾 に matrix[i, j]の値 を追加する | sparseMatrix = {{1}, {1}, {3}} |
| 11 | 6行目for (j を 1 から matrixの列数 まで 1 ずつ増やす) | 真 j = 2 |
| 12 | 7行目if (matrix[i, j] が 0 でない) | 偽 |
| 13 | 6行目for (j を 1 から matrixの列数 まで 1 ずつ増やす) | 真 j = 3 |
| 14 | 7行目if (matrix[i, j] が 0 でない) | 偽 |
| 15 | 6行目for (j を 1 から matrixの列数 まで 1 ずつ増やす) | 真 j = 4 |
| 16 | 7行目if (matrix[i, j] が 0 でない) | 偽 |
| 17 | 6行目for (j を 1 から matrixの列数 まで 1 ずつ増やす) | 真 j = 5 |
| 18 | 7行目if (matrix[i, j] が 0 でない) | 偽 |
| 19 | 6行目for (j を 1 から matrixの列数 まで 1 ずつ増やす) | 偽 j = 6 |
| 20 | 5行目for (i を 1 から matrixの行数 まで 1 ずつ増やす) | 真 i = 2 |
| 21 | 6行目for (j を 1 から matrixの列数 まで 1 ずつ増やす) | 真 j = 1 |
| 22 | 7行目if (matrix[i, j] が 0 でない) | 偽 |
| 23 | 6行目for (j を 1 から matrixの列数 まで 1 ずつ増やす) | 真 j = 2 |
| 24 | 7行目if (matrix[i, j] が 0 でない) | 真 |
| 25 | 8行目sparseMatrix[1]の末尾 に iの値 を追加する | sparseMatrix = {{1, 2}, {1}, {3}} |
| 26 | 9行目sparseMatrix[2]の末尾 に jの値 を追加する | sparseMatrix = {{1, 2}, {1, 2}, {3}} |
| 27 | 10行目sparseMatrix[3]の末尾 に matrix[i, j]の値 を追加する | sparseMatrix = {{1, 2}, {1, 2}, {3, 2}} |
| 28 | 6行目for (j を 1 から matrixの列数 まで 1 ずつ増やす) | 真 j = 3 |
| 29 | 7行目if (matrix[i, j] が 0 でない) | 真 |
| 30 | 8行目sparseMatrix[1]の末尾 に iの値 を追加する | sparseMatrix = {{1, 2, 2}, {1, 2}, {3, 2}} |
| 31 | 9行目sparseMatrix[2]の末尾 に jの値 を追加する | sparseMatrix = {{1, 2, 2}, {1, 2, 3}, {3, 2}} |
| 32 | 10行目sparseMatrix[3]の末尾 に matrix[i, j]の値 を追加する | sparseMatrix = {{1, 2, 2}, {1, 2, 3}, {3, 2, 2}} |
| 33 | 6行目for (j を 1 から matrixの列数 まで 1 ずつ増やす) | 真 j = 4 |
| 34 | 7行目if (matrix[i, j] が 0 でない) | 偽 |
| 35 | 6行目for (j を 1 から matrixの列数 まで 1 ずつ増やす) | 真 j = 5 |
| 36 | 7行目if (matrix[i, j] が 0 でない) | 偽 |
| 37 | 6行目for (j を 1 から matrixの列数 まで 1 ずつ増やす) | 偽 j = 6 |
| 38 | 5行目for (i を 1 から matrixの行数 まで 1 ずつ増やす) | 真 i = 3 |
| 39 | 6行目for (j を 1 から matrixの列数 まで 1 ずつ増やす) | 真 j = 1 |
| 40 | 7行目if (matrix[i, j] が 0 でない) | 偽 |
| 41 | 6行目for (j を 1 から matrixの列数 まで 1 ずつ増やす) | 真 j = 2 |
| 42 | 7行目if (matrix[i, j] が 0 でない) | 偽 |
| 43 | 6行目for (j を 1 から matrixの列数 まで 1 ずつ増やす) | 真 j = 3 |
| 44 | 7行目if (matrix[i, j] が 0 でない) | 偽 |
| 45 | 6行目for (j を 1 から matrixの列数 まで 1 ずつ増やす) | 真 j = 4 |
| 46 | 7行目if (matrix[i, j] が 0 でない) | 真 |
| 47 | 8行目sparseMatrix[1]の末尾 に iの値 を追加する | sparseMatrix = {{1, 2, 2, 3}, {1, 2, 3}, {3, 2, 2}} |
| 48 | 9行目sparseMatrix[2]の末尾 に jの値 を追加する | sparseMatrix = {{1, 2, 2, 3}, {1, 2, 3, 4}, {3, 2, 2}} |
| 49 | 10行目sparseMatrix[3]の末尾 に matrix[i, j]の値 を追加する | sparseMatrix = {{1, 2, 2, 3}, {1, 2, 3, 4}, {3, 2, 2, 1}} |
| 50 | 6行目for (j を 1 から matrixの列数 まで 1 ずつ増やす) | 真 j = 5 |
| 51 | 7行目if (matrix[i, j] が 0 でない) | 真 |
| 52 | 8行目sparseMatrix[1]の末尾 に iの値 を追加する | sparseMatrix = {{1, 2, 2, 3, 3}, {1, 2, 3, 4}, {3, 2, 2, 1}} |
| 53 | 9行目sparseMatrix[2]の末尾 に jの値 を追加する | sparseMatrix = {{1, 2, 2, 3, 3}, {1, 2, 3, 4, 5}, {3, 2, 2, 1}} |
| 54 | 10行目sparseMatrix[3]の末尾 に matrix[i, j]の値 を追加する | sparseMatrix = {{1, 2, 2, 3, 3}, {1, 2, 3, 4, 5}, {3, 2, 2, 1, 3}} |
| 55 | 6行目for (j を 1 から matrixの列数 まで 1 ずつ増やす) | 偽 j = 6 |
| 56 | 5行目for (i を 1 から matrixの行数 まで 1 ずつ増やす) | 真 i = 4 |
| 57 | 6行目for (j を 1 から matrixの列数 まで 1 ずつ増やす) | 真 j = 1 |
| 58 | 7行目if (matrix[i, j] が 0 でない) | 偽 |
| 59 | 6行目for (j を 1 から matrixの列数 まで 1 ずつ増やす) | 真 j = 2 |
| 60 | 7行目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}}