🏷️ 知识点：特殊矩阵

将一个 10*10 对称矩阵 M 的上三角部分的元素mi,j (1≤i≤j≤10)，按列优先存入 C 语言的一维数组 N 中，元素m7,2在 N 中的下标是（ ）

特殊矩阵

A. 15 B. 16 C. 22 D. 23

[tag_link]

正确答案：C

上三角矩阵 按列优先存储，先存储仅 1 个元素的第一列，再存储有 2 个元素的第二列，以此类推。加 7,2 位于左下角，对应右上角的元素为加 2, 7 , 在加 2,7 之前存有

• 第 1 列：1
• 第 2 列：2
• ……
• 第 6 列：6
• 第 7 列：1前面共存有 1 + 2 + 3 + 4 + 5 + 6 + 1 = 2 2 个 元 素（数组下标范围为 0〜21）, 注意数组下标从 0 开始，故加工 7 在数组 N 中的下标为 2 2 , 即加 7,2 在数组 N 中的下标为 22。

设有一个 10 阶对称矩阵 A，采用压缩存储方式，以行序为主存储，a₁₁为第一个元素，其存储地址为 1，每个元素占一个地址空间，则 a₆₅ 的地址可能是（ ）。

A. 13 B. 33 C. 18 D. 40

特殊矩阵

[tag_link]

正确答案：B

对于对称矩阵的压缩存储，通常采用下三角部分（包括对角线）以行序为主存储。 在此方式下，元素

$a_{ij}$ （其中 $i\ge j$ ）的地址计算公式为：

$$=\frac{i(i-1)}{2}+j$$

其中，第一个元素 $a_{11}$ 的地址为 1，每个元素占一个地址空间。

对于

$a_{65}$ ，即 $i=6,j=5$ ，代入公式计算：

$$=\frac{6\times 5}{2}+5=15+5=20$$

但 20 不在选项中。

若考虑元素

$a_{85}$ （即 $i=8,j=5$ ），则：

$$=\frac{8\times 7}{2}+5=28+5=33$$

33 对应选项 B。

由于 20 不在选项，且常见考题中类似问题常涉及

$a_{85}$ 的地址计算，结合选项判断，本题中 $a_{65}$ 可能为笔误，实际应为 $a_{85}$ ，故正确答案为 B.33。

适用于压缩存储稀疏矩阵的两种存储结构是（）

特殊矩阵

A. 三元组表和十字链表 B. 三元组表和邻接矩阵 C. 十字链表和二叉链表 D. 邻接矩阵和十字链表

[tag_link]

正确答案：A

三元组表 的结点存储了行 row、列 col、值 value 三种信息，是主要用来存储稀疏矩阵的一种 数据结构。十字链表将行单链表和列单链表结合起来存储稀疏矩阵。邻接矩阵空间复杂度达O(n2), 不适用于存储稀疏矩阵。二叉链表又名左孩子右兄弟表示法，可用于表示树或森林。因此 A 正确。

设有一个12×12的对称矩阵M，将其上三角部分的元素mi,j (1≤i≤j≤12)按行优先存入 C 语言的一维数组N中，元素m6,6在N中的下标是（ ）。

特殊矩阵

A. 50 B. 51 C. 55 D. 66

[tag_link]

正确答案：A

数组N的下标从0开始，第一个元素m1,1对应存入n0，矩阵M的第一行有 12 个元素，第二行有 11 个，第三行有 10 个，第四行有 9 个，第五行有 8 个，所以m6,6是第 12 + 11 + 10 + 9 + 8 + 1 = 51 个元素，下标应为 50, 故选 A。

若采用三元组表存储结构存储系数矩阵 M。则除三元组外，下列数据中还需要保存的是（ ）。

I. M 的行数

II. M 中包含非零元素的行数

III. M 的列数

IV. M 中包含非零元素的列数

特殊矩阵 三元组表

A. 仅 I 和 III B. 仅 I 和 IV C. 仅 II 和 IV D. I, II, III, IV

[tag_link]

正确答案：A

存储稀疏矩阵 M， 三元组表 的表项存储了行 row、列 col、值 value 三种信息，除此之外，我们还需要知道矩阵 M 的规模 rows × cols，即 M 的行数 rows 和 M 的列数 cols，这个信息应该直接给出。当我们需要某个位置的元素，可以先根据 M 的行数和列数判断是否越界，如果没有越界，在三元组进行查找，如果三元组没有保存对应位置的值代表矩阵中该位置的值为 0。本题答案选 A。

有一个 100 阶的三对角矩阵M，其元素mi,j(1≤i≤100,1≤j≤100)按行优先依次压缩存入下标从 0 开始的一维数组 N 中。元素m30,30在数组 N 中的下标是（ ）。

特殊矩阵 三对角矩阵

A. 86 B. 87 C. 88 D. 89

[tag_link]

正确答案：B

参考三对角矩阵，采用压缩存储，将 3 条对角线上的元素按行优先方式存放在一 维数组 B 中，且a1,1存放于 B[0] 中，其存储形式如下所示： 可以计算矩阵 A 中 3 条对角线上的元素ai,j(1≤i,j≤n,∣i−j∣≤1) 在一维数组 B 中存放的下标为k=2i+j−3。 解法一：针对该题，仅需将数字逐一代入公式里面即可：k=2x30+30-3 = 87, 结果为 87。 解法二：观察上图的三对角矩阵不难发现，第一行有两个元素，剩下的在元素m30,30所在行之前的 28 行（注意下标1≤i≤100、1≤j≤100）中每行都有 3 个元素，而m30,30之前仅有一个元素m30,29, 那么不难发现元素m30,30在数组 N 中的下标是：2+28x3+2-1 = 87。