目标

辨析数组与线性表的关系、行优先与列优先的寻址换算，掌握对称、三角、三对角矩阵的压缩下标公式，以及稀疏矩阵的三元组表、十字链表与转置算法的取舍。

前置知识

建议先阅读 3.3 数组寻址与特殊矩阵正文，掌握行优先/列优先的地址公式，以及对称、三角、三对角矩阵的压缩存储下标换算。

答题进度已答 0/12正确 0

第 1 题

难度★考点数组、基本概念

关于数组，下列说法正确的是（ ）。

请选择一个答案

A数组是线性表的推广，一旦建立，元素个数与元素间的关系不再变化，一般只做存取、不做插入删除

B数组建立后，元素个数可以动态增减

C二维数组可以看作元素是标量的一维数组

D数组采用链式存储，以便实现 O(1) 的随机访问

第 2 题

难度★考点数组、寻址、行优先

设二维数组 $A[m][n]$，首地址为 $base$，每个元素占 $size$ 字节，行优先存储时 $A[i][j]$ 的地址为（ ）。

请选择一个答案

A$base+(i\times n+j)\times size$

B$base+(j\times m+i)\times size$

C$base+(i\times m+j)\times size$

D$base+(i+j)\times size$

第 3 题

难度★★考点数组、寻址、列优先

设有数组 $A[i][j]$，每个元素占 3 字节，$i$ 从 1 到 8、$j$ 从 1 到 10，数组从内存首地址 $BA$ 开始顺序存放。按列为主存放时，元素 $A[5][8]$ 的存储首地址为（ ）。

请选择一个答案

A$BA+141$

B$BA+180$

C$BA+222$

D$BA+225$

第 4 题

难度★★考点矩阵、对称矩阵、压缩存储

设 $n$ 阶对称矩阵 $A$ 的下三角（含对角线）按行优先压缩存储到一维数组 $B[1..n(n+1)/2]$ 中，则元素 $a_{ij}$（$i\ge j$）在 $B$ 中的下标是（ ）。

请选择一个答案

A$i(i-1)/2+j$

B$j(j-1)/2+i$

C$i(i+1)/2+j$

D$j(j+1)/2+i$

第 5 题

难度★★考点矩阵、对称矩阵、压缩存储

设有一个 10 阶的对称矩阵 $A$，采用压缩存储方式，以行序为主存储，$a_{11}$ 为第一个元素，其存储地址为 1，每个元素占一个地址空间，则 $a_{85}$ 的地址为（ ）。

请选择一个答案

A13

B33

C18

D40

第 6 题

难度★★考点矩阵、对称矩阵、压缩存储、408真题

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

请选择一个答案

A50

B51

C55

D66

第 7 题

难度★★考点矩阵、对称矩阵、压缩存储、408真题

将一个 10×10 对称矩阵 M 的上三角部分的元素 $m_{i,j}$（$1\le i\le j\le 10$）按列优先存入 C 语言的一维数组 N 中，元素 $m_{7,2}$ 在 N 中的下标是（ ）。

请选择一个答案

A15

B16

C22

D23

第 8 题

难度★★考点矩阵、三对角矩阵、压缩存储、408真题

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

请选择一个答案

A86

B87

C88

D89

第 9 题

难度★考点矩阵、三对角矩阵、压缩存储

三对角矩阵按行优先压缩存储，下标从 0 开始时，元素 $A[i][j]$（$|i-j|\le 1$）在一维数组中的下标是（ ）。

请选择一个答案

A$2i+j$

B$3i+j$

C$i+2j$

D$i(i+1)/2+j$

第 10 题

难度★考点稀疏矩阵、三元组、十字链表、408真题

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

请选择一个答案

A三元组表和十字链表

B三元组表和邻接矩阵

C十字链表和二叉链表

D邻接矩阵和十字链表

第 11 题

难度★★考点稀疏矩阵、转置

稀疏矩阵的普通转置与快速转置相比，快速转置快在（ ）。

请选择一个答案

A先统计每列非零元个数并求出起始位置，一趟扫描直接定位，避免逐列重复扫描

B不需要重排三元组的行优先次序

C把时间复杂度降到 $O(t)$

D用链表代替顺序表

第 12 题

难度★★考点稀疏矩阵、十字链表

当稀疏矩阵的非零元个数与位置在运算中变化较大（如矩阵相加）时，宜采用的存储结构及其原因分别是（ ）。

请选择一个答案

A十字链表；插入删除只需改指针，无需移动大量元素

B三元组表；随机访问是 O(1)

C二维数组；实现最简单

D邻接矩阵；可表示任意矩阵

答案总览（建议完成全部题目后查看）

1. 第 1 题：A
2. 第 2 题：A
3. 第 3 题：B
4. 第 4 题：A
5. 第 5 题：B
6. 第 6 题：A
7. 第 7 题：C
8. 第 8 题：B
9. 第 9 题：A
10. 第 10 题：A
11. 第 11 题：A
12. 第 12 题：A

思考题

1. 为什么数组被称为随机存取结构？它的 $O(1)$ 访问靠什么保证？
2. 对称矩阵压缩后访问 $A[j][i]$（$j<i$）时下标如何换算？
3. 三对角矩阵中 $|i-j|>1$ 的元素值一定是什么？为什么能直接跳过存储？