IPA FE Subject B first sample Question 4

Topic: Math & Data Science

A question IPA Japan published in 基本情報技術者試験 科目Bのサンプル問題 問4, translated into English. ITPEC is based on the same exams.

From the answer group below, select the correct combination of answers to be inserted into A through C in the description. Here, the array index starts at 1.

A matrix in which most of the elements are 0 is called a sparse matrix. The following program converts a matrix stored in a two-dimensional array into a data structure suitable for storing a sparse matrix, in order to reduce the amount of data of the matrix.
The function transformSparseMatrix converts the matrix given as a two-dimensional array in the argument matrix into an array of integer-type arrays, and returns it. When the function transformSparseMatrix is called as 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}}), the return value is {{A}, {B}, {C}}.

[Program]
○ integer [][]: transformSparseMatrix(integer [,]: matrix)
integer: i, j
integer [][]: sparseMatrix
sparseMatrix ← {{}, {}, {}} /* an array that has three arrays with 0 elements as its elements */
for (increase i from 1 to the number of rows of matrix by 1)
for (increase j from 1 to the number of columns of matrix by 1)
if (matrix[i, j] is not equal to 0)
add the value of i to the end of sparseMatrix[1]
add the value of j to the end of sparseMatrix[2]
add the value of matrix[i, j] to the end of sparseMatrix[3]
endif
endfor
endfor
return sparseMatrix

Answer group

OptionABC

Explanation

A: 1, 2, 2, 3, 3, 4, 5, B: 1, 2, 3, 4, 5, 4, 5, C: 3, 2, 2, 1, 3, 2, 1 — the program scans the matrix row by row and, for each nonzero element, appends its row number, column number and value to the three arrays.

The outer loop runs over the rows i and the inner one over the columns j, so row 1 is scanned from left to right, then row 2, and so on. The nonzero elements in that order:

Row iColumn jValue
113
222
232
341
353
442
551

Reading the columns down gives the three arrays: sparseMatrix[1] holds the row numbers (A), sparseMatrix[2] the column numbers (B) and sparseMatrix[3] the values (C). Three arrays of seven replace the 25 elements of the matrix.

Answer (b)

Why not others:

  • •(a) — A and B are right, but C lists the values column by column (column 4's 1 and 2 before column 5's 3 and 1), so its fifth value, 2, no longer belongs to element [3, 5], which is 3
  • •(c) and (d) — swap A and B, but sparseMatrix[1] receives i, the row number; (c) also has the column-by-column values of (a)

Key rule: This sparse-matrix format keeps three parallel arrays (row, column, value) with one entry per nonzero element, so the same position in each array describes the same element.

Math & Data Science · AI-written, may contain errors

Practice this exam

This question comes from the past questions IPA Japan publishes, translated into English by ITPEC Practice. ITPEC Practice is an independent study tool and is not affiliated with IPA or ITPEC. See the original paper (PDF) or Report an issue.