疎行列への格納処理【基本情報技術者試験 科目B サンプル問題】

← 科目Bの公開問題一覧へ戻る

　基本情報技術者試験の科目Bのサンプル問題を題材に，疎行列への格納処理について学習します。この問題では，行列の0でない要素を取り出し，行番号，列番号，値を配列に格納する処理を確認します。

（令和4年度4月公開） 基本情報技術者試験 サンプル問題 科目B 問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

解答群

	a	b	c
ア	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

【参考】	「極限値・グラフ理論・待ち行列理論の基礎まとめ（グラフ理論とは）」

この問題のポイント

　この問題から学べることは，

• 疎行列とは何か
• 行列の0でない要素を取り出す処理
• 行番号，列番号，値を別々の配列に格納する方法
• 二重ループと条件分岐による行列の走査

です。特に，行列の0でない要素を見つけたときに，行番号，列番号，値をそれぞれ対応する配列に格納する処理を理解しておきましょう。

基本情報技術者試験の学習におすすめの参考書

基本情報技術者試験の合格を目指す方におすすめの参考書です。