基本情報技術者試験科目B サンプル問題（2022年4月公表）問4

次の記述中のa～cに入れる正しい答えの組合せを，解答群の中から選べ。ここで，配列の要素番号は 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}})として呼び出したときの戻り値は，{{a}, {b}, {c}} である。〔プログラム〕

○整数型配列の配列: 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

答えを選ぶ

出典：基本情報技術者試験科目B サンプル問題（2022年4月公表）問4（問題文は IPA の公開問題。図・数式・下線などはテキストに直して掲載。解説は当サイト作成）

科目Bの解き方と全問の一覧

解説に誤りを見つけたら、解説の誤りを報告してください。

答えと解説を見る

正解：イ

覚える知識

疎行列の格納(行番号・列番号・値の3配列)

要素の多くが 0 の行列は、0 でない要素だけを行番号・列番号・値の 3 つの配列に並べて持つと、データ量を減らせる。

この問題で必要なこと

二重ループは行 i が外側、列 j が内側なので、0 でない要素は行の順に、同じ行の中では列の順に取り出される。取り出される順は (1,1)=3、(2,2)=2、(2,3)=2、(3,4)=1、(3,5)=3、(4,4)=2、(5,5)=1。よって a=行 1,2,2,3,3,4,5、b=列 1,2,3,4,5,4,5、c=値 3,2,2,1,3,2,1 となり、正解はイ。

ひっかけ

ウ・エは sparseMatrix[1] と [2]（行と列）を取り違えている。アの値の並びは列の順に読んだもので、3 行目の 1,3 と 4 行目の 2 の順番が崩れている（行優先のループ順を読み落とす）。

← 問3

問5 →

基本情報技術者試験 科目B サンプル問題（2022年4月公表） 問4

基本情報技術者試験科目B サンプル問題（2022年4月公表）問4