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 · 目视转录

对 nn 阶对称矩阵压缩存储时,需要表长为( )的顺序表。

A. n/2n/2

B. n×n/2n\times n/2

C. n(n+1)/2n(n+1)/2

D. n(n−1)/2n(n-1)/2

查看答案与解析

答案:C。

只需存储其上三角或下三角部分(含对角线),元素个数为 n+(n−1)+⋯+1=n(n+1)/2n+(n-1)+\cdots+1=n(n+1)/2。

单项选择题 03

原书题目P104 · 解析P106 · 目视转录

有一个 n×nn\times n 的对称矩阵 AA,将其下三角部分按行存放在一维数组 BB 中,而 A[0][0] 存放于 B[0] 中,则元素 A[i][i] 存放于 BB 中的( )处。

A. (i+3)i/2(i+3)i/2

B. (i+1)i/2(i+1)i/2

C. (2n−i+1)i/2(2n-i+1)i/2

D. (2n−i−1)i/2(2n-i-1)i/2

查看答案与解析

答案:A。

此题要注意 3 个细节:矩阵的最小下标为 0;数组下标也是从 0 开始的;矩阵按行优先存在数组中。注意到此三点,答案不难得到为选项 A。此外,本类题建议采用特殊值代入法求解,例如,A[1][1] 对应的下标为 2,代入后只有选项 A 满足条件。

技巧:对于特殊三角矩阵压缩存储的题,心中应有“平移”挪动的思想,并结合画图,这样会比较形象,在计算时再注意矩阵和数组的起始下标,就不容易出错。

单项选择题 04

原书题目P104 · 解析P106 · 目视转录

在二维数组 AA 中,假设每个数组元素的长度为 3 个存储单元,行下标 ii 为 0~8,列下标 jj 为 0~9,从首地址 SA 开始连续存放。在这种情况下,元素 A[8][5] 的起始地址为( )。

A. SA+141

B. SA+144

C. SA+222

D. SA+255

查看答案与解析

答案:D。

二维数组计算地址(按行优先顺序)的公式为

LOC⁡(i,j)=LOC⁡(0,0)+(i×m+j)×L.\operatorname{LOC}(i,j)=\operatorname{LOC}(0,0)+(i\times m+j)\times L.

其中,LOC⁡(0,0)=SA\operatorname{LOC}(0,0)=\mathrm{SA},是数组存放的首地址;L=3L=3 是每个数组元素的长度;m=9−0+1=10m=9-0+1=10 是数组的列数。因此 LOC⁡(8,5)=SA+(8×10+5)×3=SA+255\operatorname{LOC}(8,5)=\mathrm{SA}+(8\times10+5)\times3=\mathrm{SA}+255,所以选择选项 D。

单项选择题 05

原书题目P104 · 解析P106 · 目视转录

二维数组 AA 按行优先存储,其中每个元素占 1 个存储单元。若 A[1][1] 的存储地址为 420,A[3][3] 的存储地址为 446,则 A[5][5] 的存储地址为( )。

A. 472

B. 471

C. 458

D. 457

查看答案与解析

答案:A。

本题未直接给出数组 AA 的行数和列数,因此需要根据题目中的信息来推理。因为该二维数组按行优先存储,且 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] 的存储地址是 446+24+2=472446+24+2=472。

单项选择题 06

原书题目P105 · 解析P106 · 目视转录

将三对角矩阵即数组 A[1…100][1…100] 按行优先存入一维数组 B[1…298] 中,数组 AA 中元素 A[66][65] 在数组 BB 中的位置 kk 为( )。

A. 198

B. 195

C. 197

D. 196

查看答案与解析

答案:B。

对于三对角矩阵,将 A[1…n][1…n] 压缩至 B[1…3n-2] 时,ai,ja_{i,j} 与 bkb_k 的对应关系为 k=2i+j−2k=2i+j-2。则 AA 中的元素 A[66][65] 在数组 BB 中的位置 k=2×66+65−2=195k=2\times66+65-2=195。

单项选择题 07

原书题目P105 · 解析P106 · 目视转录

若将 nn 阶上三角矩阵 AA 按列优先级压缩存放在一维数组 B[1…n(n+1)/2+1] 中,则存放到 B[k] 中的非零元素 ai,ja_{i,j}(1≤i,j≤n1\le i,j\le n)的下标 ii、jj 与 kk 的对应关系是( )。

A. i(i+1)/2+ji(i+1)/2+j

B. i(i−1)/2+j−1i(i-1)/2+j-1

C. j(j−1)/2+ij(j-1)/2+i

D. j(j−1)/2+i−1j(j-1)/2+i-1

查看答案与解析

答案:C。

按列优先存储,所以元素 ai,ja_{i,j} 前面有 j−1j-1 列,共有 1+2+3+⋯+(j−1)=j(j−1)/21+2+3+\cdots+(j-1)=j(j-1)/2 个元素,元素 ai,ja_{i,j} 在第 jj 列上是第 ii 个元素,数组 BB 的下标是从 1 开始,因此 k=j(j−1)/2+ik=j(j-1)/2+i。

单项选择题 08

原书题目P105 · 解析P106 · 目视转录

若将 nn 阶下三角矩阵 AA 按列优先顺序压缩存放在一维数组 B[1…n(n+1)/2+1] 中,则存放到 B[k] 中的非零元素 ai,ja_{i,j}(1≤i,j≤n1\le i,j\le n)的下标 ii、jj 与 kk 的对应关系是( )。

A. (j−1)(2n−j+1)/2+i−j(j-1)(2n-j+1)/2+i-j

B. (j−1)(2n−j+2)/2+i−j+1(j-1)(2n-j+2)/2+i-j+1

C. (j−1)(2n−j+2)/2+i−j(j-1)(2n-j+2)/2+i-j

D. (j−1)(2n−j+1)/2+i−j−1(j-1)(2n-j+1)/2+i-j-1

查看答案与解析

答案:B。

按列优先存储,所以元素 ai,ja_{i,j} 之前有 j−1j-1 列,共有 n+(n−1)+⋯+(n−j+2)=(j−1)(2n−j+2)/2n+(n-1)+\cdots+(n-j+2)=(j-1)(2n-j+2)/2 个元素。元素 ai,ja_{i,j} 是第 jj 列上第 i−j+1i-j+1 个元素,数组 BB 的下标从 1 开始,k=(j−1)(2n−j+2)/2+i−j+1k=(j-1)(2n-j+2)/2+i-j+1。

单项选择题 09

原书题目P105 · 解析P106 · 目视转录

稀疏矩阵采用压缩存储后的缺点主要是( )。

A. 无法判断矩阵的行列数

B. 丧失随机存取的特性

C. 无法由行、列值查找某个矩阵元素

D. 使矩阵元素之间的逻辑关系更复杂

查看答案与解析

答案:B。

稀疏矩阵通常采用三元组来压缩存储,存储矩阵元素的行列下标和相应的值,因此不能根据矩阵元素的行列下标快速定位矩阵元素,失去了随机存取的特性。

单项选择题 10

原书题目P105 · 解析P106 · 目视转录

下列关于矩阵的说法中,正确的是( )。

Ⅰ. 在 nn(n>3n>3)阶三对角矩阵中,每行都有 3 个非零元素

Ⅱ. 稀疏矩阵的特点是矩阵中的元素少

A. 仅Ⅰ

B. 仅Ⅱ

C. Ⅰ和Ⅱ

D. 无正确项

查看答案与解析

答案:D。

在三对角矩阵中,第 1 行和最后 1 行只有 2 个非零元,其余各行均有 3 个非零元。稀疏矩阵的特点是矩阵中非零元的个数较少。

单项选择题 11

原书题目P105 · 解析P107 · 目视转录

【2016 统考真题】有一个 100 阶的三对角矩阵 MM,其元素 mi,jm_{i,j}(1≤i,j≤1001\le i,j\le100)按行优先依次压缩存入下标从 0 开始的一维数组 NN 中,元素 m30,30m_{30,30} 在 NN 中的下标是( )。

A. 86

B. 87

C. 88

D. 89

查看答案与解析

答案:B。

三对角矩阵的非零元集中在主对角线及两条相邻对角线上:首行含 a1,1,a1,2a_{1,1},a_{1,2},中间第 ii 行含 ai,i−1,ai,i,ai,i+1a_{i,i-1},a_{i,i},a_{i,i+1},末行含 an,n−1,an,na_{n,n-1},a_{n,n},其余位置为 0。

采用压缩存储,将 3 条对角线上的元素按行优先方式存放在一维数组 BB 中,且 a1,1a_{1,1} 存放于 B[0] 中,其存储形式如下:

[a11, a12, a21, a22, a23, …, a(n-1,n), a(n,n-1), a(n,n)]

可以计算矩阵 AA 中 3 条对角线上的元素 ai,ja_{i,j}(1≤i,j≤n,∣i−j∣≤11\le i,j\le n,|i-j|\le1)在一维数组 BB 中存放的下标为 k=2i+j−3k=2i+j-3,公式很难记忆,我们通常采用解法 2。

解法 1:针对该题,仅需将数字逐一代入公式:k=2×30+30−3=87k=2\times30+30-3=87,结果为 87。

解法 2:观察上述三对角矩阵不难发现,第一行有两个元素,剩下的在元素 m30,30m_{30,30} 所在行之前的 28 行(注意下标 1≤i,j≤1001\le i,j\le100)中,每行都有 3 个元素,而 m30,30m_{30,30} 之前仅有一个元素 m30,29m_{30,29},不难发现元素 m30,30m_{30,30} 在数组 NN 中的下标是 2+28×3+2−1=872+28\times3+2-1=87。

注意:矩阵和数组的下标从 0 或 1 开始(如矩阵可能从 a0,0a_{0,0} 或 a1,1a_{1,1} 开始,数组可能从 B[0] 或 B[1] 开始),这时就需要适时调整计算方法(无非是多计算 1 或少计算 1 的问题)。

单项选择题 12

原书题目P105 · 解析P107 · 目视转录

【2017 统考真题】适用于压缩存储稀疏矩阵的两种存储结构是( )。

A. 三元组表和十字链表

B. 三元组表和邻接矩阵

C. 十字链表和二叉链表

D. 邻接矩阵和十字链表

查看答案与解析

答案:A。

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

单项选择题 13

原书题目P105 · 解析P107 · 目视转录

【2018 统考真题】设有一个 12×1212\times12 阶对称矩阵 MM,将其上三角部分的元素 mi,jm_{i,j}(1≤i≤j≤121\le i\le j\le12)按行优先存入 C 语言的一维数组 NN 中,元素 m6,6m_{6,6} 在 NN 中的下标是( )。

A. 50

B. 51

C. 55

D. 66

查看答案与解析

答案:A。

在 C 语言中,数组 NN 的下标从 0 开始。第一个元素 m1,1m_{1,1} 对应存入 n0n_0,矩阵 MM 的第一行有 12 个元素,第二行有 11 个,第三行有 10 个,第四行有 9 个,第五行有 8 个,所以 m6,6m_{6,6} 是第 12+11+10+9+8+1=5112+11+10+9+8+1=51 个元素,下标应为 50。

单项选择题 14

原书题目P105 · 解析P107 · 目视转录

【2020 统考真题】将一个 10×1010\times10 阶对称矩阵 MM 的上三角部分的元素 mi,jm_{i,j}(1≤i≤j≤101\le i\le j\le10)按列优先存入 C 语言的一维数组 NN 中,元素 m7,2m_{7,2} 在 NN 中的下标是( )。

A. 15

B. 16

C. 22

D. 23

查看答案与解析

答案:C。

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

列元素个数
第 1 列1
第 2 列2
⋯\cdots⋯\cdots
第 6 列6
第 7 列1

前面共存储有 1+2+3+4+5+6+1=221+2+3+4+5+6+1=22 个元素(数组下标范围为 0~21),注意数组下标从 0 开始,所以 m2,7m_{2,7} 在数组 NN 中的下标为 22,即 m7,2m_{7,2} 在数组 NN 中的下标为 22。

单项选择题 15

原书题目P105 · 解析P108 · 目视转录

【2021 统考真题】二维数组 AA 按行优先方式存储,每个元素占用 1 个存储单元。若元素 A[0][0] 的存储地址是 100,A[3][3] 的存储地址是 220,则元素 A[5][5] 的存储地址是( )。

A. 295

B. 300

C. 301

D. 306

查看答案与解析

答案:B。

二维数组 AA 按行优先存储,每个元素占用 1 个存储单元,由 A[0][0] 和 A[3][3] 的存储地址可知 A[3][3] 是一维数组的第 121 个元素,假设一维数组 AA 的每行有 nn 个元素,则 n×3+4=121n\times3+4=121,求得 n=39n=39,所以元素 A[5][5] 的存储地址为 100+39×5+6−1=300100+39\times5+6-1=300。

单项选择题 16

原书题目P105 · 解析P108 · 目视转录

【2023 统考真题】若采用三元组表存储结构存储稀疏矩阵 MM,则除三元组表外,下列数据中还需要保存的是( )。

Ⅰ. MM 的行数

Ⅱ. MM 中含非零元素的行数

Ⅲ. MM 的列数

Ⅳ. MM 中含非零元素的列数

A. 仅Ⅰ、Ⅲ

B. 仅Ⅰ、Ⅳ

C. 仅Ⅱ、Ⅳ

D. Ⅰ、Ⅱ、Ⅲ、Ⅳ

查看答案与解析

答案:A。

用三元组表存储结构存储稀疏矩阵 MM 时,每个非零元素都由三元组(行标、列标、关键字值)组成。但是,仅通过三元组表中的元素无法判断稀疏矩阵 MM 的大小,因此还要保存 MM 的行数和列数。此外,还可以保存 MM 的非零元素个数。例如,如下两个稀疏矩阵的三元组表是相同的,若不保存行数和列数,则无法判断两个稀疏矩阵的大小。

[0200005000000000][020005000]\begin{bmatrix}0&2&0&0\\0&0&5&0\\0&0&0&0\\0&0&0&0\end{bmatrix}\qquad\begin{bmatrix}0&2&0\\0&0&5\\0&0&0\end{bmatrix}