3.4 数组和特殊矩阵·习题
复习入口
3.4 数组和特殊矩阵 · 3.4.1 数组的定义 · 3.4.2 数组的存储结构 · 3.4.3 特殊矩阵的压缩存储 · 3.4.3.1 对称矩阵 · 3.4.3.2 三角矩阵 · 3.4.3.3 三对角矩阵 · 3.4.4 稀疏矩阵
本节共16题:选择题16题,综合应用题0题。每题答案紧接题目折叠显示。
文字转录进度:16/16题。已转录题目的题干、选项和解析可编辑;示意图按需保留。
单项选择题
单项选择题 01
原书题目P104 · 解析P106 · 目视转录
对特殊矩阵采用压缩存储的主要目的是( )。
A. 表达变得简单
B. 对矩阵元素的存取变得简单
C. 去掉矩阵中的多余元素
D. 减少不必要的存储空间
查看答案与解析
答案:D。
特殊矩阵中含有很多相同元素或零元素,所以可采用压缩存储,以节省存储空间。
单项选择题 02
原书题目P104 · 解析P106 · 目视转录
对 阶对称矩阵压缩存储时,需要表长为( )的顺序表。
A.
B.
C.
D.
查看答案与解析
答案:C。
只需存储其上三角或下三角部分(含对角线),元素个数为 。
单项选择题 03
原书题目P104 · 解析P106 · 目视转录
有一个 的对称矩阵 ,将其下三角部分按行存放在一维数组 中,而 A[0][0] 存放于 B[0] 中,则元素 A[i][i] 存放于 中的( )处。
A.
B.
C.
D.
查看答案与解析
答案:A。
此题要注意 3 个细节:矩阵的最小下标为 0;数组下标也是从 0 开始的;矩阵按行优先存在数组中。注意到此三点,答案不难得到为选项 A。此外,本类题建议采用特殊值代入法求解,例如,A[1][1] 对应的下标为 2,代入后只有选项 A 满足条件。
技巧:对于特殊三角矩阵压缩存储的题,心中应有“平移”挪动的思想,并结合画图,这样会比较形象,在计算时再注意矩阵和数组的起始下标,就不容易出错。
单项选择题 04
原书题目P104 · 解析P106 · 目视转录
在二维数组 中,假设每个数组元素的长度为 3 个存储单元,行下标 为 0~8,列下标 为 0~9,从首地址 SA 开始连续存放。在这种情况下,元素 A[8][5] 的起始地址为( )。
A. SA+141
B. SA+144
C. SA+222
D. SA+255
查看答案与解析
答案:D。
二维数组计算地址(按行优先顺序)的公式为
其中,,是数组存放的首地址; 是每个数组元素的长度; 是数组的列数。因此 ,所以选择选项 D。
单项选择题 05
原书题目P104 · 解析P106 · 目视转录
二维数组 按行优先存储,其中每个元素占 1 个存储单元。若 A[1][1] 的存储地址为 420,A[3][3] 的存储地址为 446,则 A[5][5] 的存储地址为( )。
A. 472
B. 471
C. 458
D. 457
查看答案与解析
答案:A。
本题未直接给出数组 的行数和列数,因此需要根据题目中的信息来推理。因为该二维数组按行优先存储,且 A[3][3] 的存储地址为 446,所以 A[3][1] 的存储地址为 444,又 A[1][1] 的存储地址为 420,显然 A[1][1] 和 A[3][1] 正好相差 2 行,所以该矩阵的列数为 12。而 A[5][3] 和 A[3][3] 正好相差 2 行,A[5][5] 和 A[5][3] 又相差 2 个元素,所以 A[5][5] 的存储地址是 。
单项选择题 06
原书题目P105 · 解析P106 · 目视转录
将三对角矩阵即数组 A[1…100][1…100] 按行优先存入一维数组 B[1…298] 中,数组 中元素 A[66][65] 在数组 中的位置 为( )。
A. 198
B. 195
C. 197
D. 196
查看答案与解析
答案:B。
对于三对角矩阵,将 A[1…n][1…n] 压缩至 B[1…3n-2] 时, 与 的对应关系为 。则 中的元素 A[66][65] 在数组 中的位置 。
单项选择题 07
原书题目P105 · 解析P106 · 目视转录
若将 阶上三角矩阵 按列优先级压缩存放在一维数组 B[1…n(n+1)/2+1] 中,则存放到 B[k] 中的非零元素 ()的下标 、 与 的对应关系是( )。
A.
B.
C.
D.
查看答案与解析
答案:C。
按列优先存储,所以元素 前面有 列,共有 个元素,元素 在第 列上是第 个元素,数组 的下标是从 1 开始,因此 。
单项选择题 08
原书题目P105 · 解析P106 · 目视转录
若将 阶下三角矩阵 按列优先顺序压缩存放在一维数组 B[1…n(n+1)/2+1] 中,则存放到 B[k] 中的非零元素 ()的下标 、 与 的对应关系是( )。
A.
B.
C.
D.
查看答案与解析
答案:B。
按列优先存储,所以元素 之前有 列,共有 个元素。元素 是第 列上第 个元素,数组 的下标从 1 开始,。
单项选择题 09
原书题目P105 · 解析P106 · 目视转录
稀疏矩阵采用压缩存储后的缺点主要是( )。
A. 无法判断矩阵的行列数
B. 丧失随机存取的特性
C. 无法由行、列值查找某个矩阵元素
D. 使矩阵元素之间的逻辑关系更复杂
查看答案与解析
答案:B。
稀疏矩阵通常采用三元组来压缩存储,存储矩阵元素的行列下标和相应的值,因此不能根据矩阵元素的行列下标快速定位矩阵元素,失去了随机存取的特性。
单项选择题 10
原书题目P105 · 解析P106 · 目视转录
下列关于矩阵的说法中,正确的是( )。
Ⅰ. 在 ()阶三对角矩阵中,每行都有 3 个非零元素
Ⅱ. 稀疏矩阵的特点是矩阵中的元素少
A. 仅Ⅰ
B. 仅Ⅱ
C. Ⅰ和Ⅱ
D. 无正确项
查看答案与解析
答案:D。
在三对角矩阵中,第 1 行和最后 1 行只有 2 个非零元,其余各行均有 3 个非零元。稀疏矩阵的特点是矩阵中非零元的个数较少。
单项选择题 11
原书题目P105 · 解析P107 · 目视转录
【2016 统考真题】有一个 100 阶的三对角矩阵 ,其元素 ()按行优先依次压缩存入下标从 0 开始的一维数组 中,元素 在 中的下标是( )。
A. 86
B. 87
C. 88
D. 89
查看答案与解析
答案:B。
三对角矩阵的非零元集中在主对角线及两条相邻对角线上:首行含 ,中间第 行含 ,末行含 ,其余位置为 0。
采用压缩存储,将 3 条对角线上的元素按行优先方式存放在一维数组 中,且 存放于 B[0] 中,其存储形式如下:
[a11, a12, a21, a22, a23, …, a(n-1,n), a(n,n-1), a(n,n)]
可以计算矩阵 中 3 条对角线上的元素 ()在一维数组 中存放的下标为 ,公式很难记忆,我们通常采用解法 2。
解法 1:针对该题,仅需将数字逐一代入公式:,结果为 87。
解法 2:观察上述三对角矩阵不难发现,第一行有两个元素,剩下的在元素 所在行之前的 28 行(注意下标 )中,每行都有 3 个元素,而 之前仅有一个元素 ,不难发现元素 在数组 中的下标是 。
注意:矩阵和数组的下标从 0 或 1 开始(如矩阵可能从 或 开始,数组可能从 B[0] 或 B[1] 开始),这时就需要适时调整计算方法(无非是多计算 1 或少计算 1 的问题)。
单项选择题 12
原书题目P105 · 解析P107 · 目视转录
【2017 统考真题】适用于压缩存储稀疏矩阵的两种存储结构是( )。
A. 三元组表和十字链表
B. 三元组表和邻接矩阵
C. 十字链表和二叉链表
D. 邻接矩阵和十字链表
查看答案与解析
答案:A。
三元组表的结点存储了行(row)、列(col)、值(value)三种信息,是主要用来存储稀疏矩阵的一种数据结构。十字链表将行单链表和列单链表结合起来存储稀疏矩阵。邻接矩阵空间复杂度达 ,不适合于存储稀疏矩阵。二叉链表又名左孩子右兄弟表示法,可用于表示树或森林。
单项选择题 13
原书题目P105 · 解析P107 · 目视转录
【2018 统考真题】设有一个 阶对称矩阵 ,将其上三角部分的元素 ()按行优先存入 C 语言的一维数组 中,元素 在 中的下标是( )。
A. 50
B. 51
C. 55
D. 66
查看答案与解析
答案:A。
在 C 语言中,数组 的下标从 0 开始。第一个元素 对应存入 ,矩阵 的第一行有 12 个元素,第二行有 11 个,第三行有 10 个,第四行有 9 个,第五行有 8 个,所以 是第 个元素,下标应为 50。
单项选择题 14
原书题目P105 · 解析P107 · 目视转录
【2020 统考真题】将一个 阶对称矩阵 的上三角部分的元素 ()按列优先存入 C 语言的一维数组 中,元素 在 中的下标是( )。
A. 15
B. 16
C. 22
D. 23
查看答案与解析
答案:C。
上三角矩阵按列优先存储,先存储只有 1 个元素的第一列,再存储有 2 个元素的第二列,以此类推。 位于左下角,对应右上的元素为 ,在 之前存储有:
| 列 | 元素个数 |
|---|---|
| 第 1 列 | 1 |
| 第 2 列 | 2 |
| 第 6 列 | 6 |
| 第 7 列 | 1 |
前面共存储有 个元素(数组下标范围为 0~21),注意数组下标从 0 开始,所以 在数组 中的下标为 22,即 在数组 中的下标为 22。
单项选择题 15
原书题目P105 · 解析P108 · 目视转录
【2021 统考真题】二维数组 按行优先方式存储,每个元素占用 1 个存储单元。若元素 A[0][0] 的存储地址是 100,A[3][3] 的存储地址是 220,则元素 A[5][5] 的存储地址是( )。
A. 295
B. 300
C. 301
D. 306
查看答案与解析
答案:B。
二维数组 按行优先存储,每个元素占用 1 个存储单元,由 A[0][0] 和 A[3][3] 的存储地址可知 A[3][3] 是一维数组的第 121 个元素,假设一维数组 的每行有 个元素,则 ,求得 ,所以元素 A[5][5] 的存储地址为 。
单项选择题 16
原书题目P105 · 解析P108 · 目视转录
【2023 统考真题】若采用三元组表存储结构存储稀疏矩阵 ,则除三元组表外,下列数据中还需要保存的是( )。
Ⅰ. 的行数
Ⅱ. 中含非零元素的行数
Ⅲ. 的列数
Ⅳ. 中含非零元素的列数
A. 仅Ⅰ、Ⅲ
B. 仅Ⅰ、Ⅳ
C. 仅Ⅱ、Ⅳ
D. Ⅰ、Ⅱ、Ⅲ、Ⅳ
查看答案与解析
答案:A。
用三元组表存储结构存储稀疏矩阵 时,每个非零元素都由三元组(行标、列标、关键字值)组成。但是,仅通过三元组表中的元素无法判断稀疏矩阵 的大小,因此还要保存 的行数和列数。此外,还可以保存 的非零元素个数。例如,如下两个稀疏矩阵的三元组表是相同的,若不保存行数和列数,则无法判断两个稀疏矩阵的大小。