2024年2月23日发(作者：旗颐)
第5章 数组与广义表一、 选择题
1. 在以下讲述中，正确的是（ B ）。
A、线性表的线性存储结构优于链表存储结构
B、二维数组是其数据元素为线性表的线性表
C、栈的操作方式是先进先出
D、队列的操作方式是先进后出
2. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转
置运算，这种观点（ A ）。
A、正确 B、错误
3. 二维数组SA 中，每个元素的长度为3 个字节，行下标I 从0 到7，列下标J 从0 到9，从首地址SA 开始
连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为（ B）。
A、SA+141 B、SA+180 C、SA+222 D、SA+225
4. 数组SA 中，每个元素的长度为3 个字节，行下标I 从0 到7，列下标J 从0 到9，从首地址SA 开始连续
存放在存储器内，存放该数组至少需要的字节数是（ C ）。
A、80 B、100 C、240 D、270
5. 常对数组进行的两种基本操作是（ B ）。
A、建立与删除 B、索引和修改 C、查找和修改 D、查找和索引
6. 将一个A[15][15]的下三角矩阵（第一个元素为A[0][0]），按行优先存入一维数组B[120]中，A 中元素A[6][5]
在B 数组中的位置K 为（ B ）。
A、19 B、26 C、21 D、15
7. 若广义表A 满足Head(A)=Tail(A)，则A 为（ B ）。
A、（） B、（（）） C、（（），（）） D、（（），（），（））
8. 广义表（（a）,a）的表头是（ C ），表尾是（C ）。
A、a B、b C、(a) D、((a))
9. 广义表（（a,b）,c,d）的表头是（ C ），表尾是（ D ）。
A、a B、b C、(a,b) D、(c,d)
10. 广义表（（a））的表头是（ B ），表尾是（C ）。
A、a B、(a) C、() D、((a))
11. 广义表（a,b,c,d）的表头是（ A ），表尾是（ D ）。
A、a B、(a) C、(a,b) D、(b,c,d)
12. 广义表（（a,b,c,d））的表头是（ C ），表尾是（ B ）。
A、a B、() C、(a,b,c,d) D、((a,b,c,d))
13. 下面结论正确的是（ BC ）。
A、一个广义表的表头肯定不是一个广义表
B、一个广义表的表尾肯定是一个广义表
C、广义表L=（（），（A，B））的表头为空表
D、广义表中原子个数即为广义表的长度
14. 广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=( D )
A、(G) B、(D) C、C D、 D
15. 已知广义表L=((x,y,z),a,(u,t,w))，从L 表中取出原子项t 的操作是（ D ）。
A 、Head(Head(Tail(Tail(L)))) B 、Tail(Head(Head(Tail(L))))
C 、Head(Tail(Head(Tail(L)))) D 、Head(Tail(Head(Tail(Tail(L)))))
16. 16、设A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))=( D )
A. (g) B.(d) C.c D.d
17. 对矩阵压缩存储是为了（ B ）
A、方便运算 B、节省空间 C、方便存储
18. 稀疏矩阵一般的压缩存储方法有两种，即（ C ）
A、二元数组和三元数组 B、三元组和散列
C、三元组和十字链表 D、散列和十字链表
D、提高运算速度
二、 判断题(F/T)
1.
2.
3.
4.
5.
6.
7.
8.
9.
数组是同类型值的集合。(T)
数组的存储结构是一组连续的内存单元。(T)
数组是一种复杂的数据结构，数组元素之间的关系，即不是线性的也不是树形的。(T)
插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也会经常使用。(F)
使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。(F)
广义表是由零个或多个原子或子表所组成的有限序列，所以广义表可能为空表。(T)
线性表可以看成是广义表的特例，如果广义表中的每个元素是原子，则广义表便成为线性表。()
广义表中原子个数即为广义表的长度。(F)
广义表中元素的个数即为广义表的深度。(F)
三、 填空题
1. 设a 是含有N 个分量的整数数组，则求该数组中最大整数的递归定义为（ ），最小整数的递归定义为
（ ）。
2. 二维数组A[10][5]采用行序为主方式存储，每个元素占4 个存储单元，并且A[5][3]的存储地址是1000，则A[8][2]的地址是（ 1056 ）。
3. 二维数组A[m][n]采用行序为主方式存储，每个元素占k 个存储单元，并且第一个元素的存储地址是Loc(A[0][0])，则A[i][j]的地址是（Loc(A[0][0]+(i*n+m)*k ）。
4. 广义表的（深度 ）定义为广义表中括弧的重数。
5. 设广义表L=（（），（）），则Head(L)=（ () ）；Tail(L)=（(()) ）；L 的长度是（ 2 ）；L 的深度是（ 2 ）。
6. 广义表中的元素可以是（ 原子和字表），其描述宜采用程序设计语言中的（LISP语言 ）表示。
7. 广义表(((a)))的表头是（ ((a)) ），表尾是（() ）。
8. 广义表((a),((b),c),(((d))))的表头是（ (a) ），表尾是（(((b),c),(((d)))) ）。
9. 设广义表A=(x,((a,b),c,d))，则Head(Head(Tail(A)))=（ a ）。
10. 设广义表A=(a,b,c),B=(A,(c,d)),C=(a,(B,A),(e,f))，则
（1）Head(A)=( a ) （2） Tail(B)=( ((C,d)) )
（3）Head(Head(Head(Tail(C))))=( (a,b,c) )
11. 下三角矩阵A[1..N,1..N]的下三角元素已压缩到一维数组S[1..N*（N+1）/2+1]中，若按行序为主序存储，则A[I,j]对应的S 中的存储位置是 （ ）。
0312. 已知一个稀疏矩阵为0013.
14.
15.
16.
0200010000，则对应的三元组表表示为（ （1，3，2） ，（2，1，3），（3，3，-1），50（3，4，5） ） 。
一个n*n 的对称矩阵，如果以行或列为主序存入内存，则其容量为 （n*（n+1）/2 ）。
三维数组A[c1..d1,c2..d2..,c3..d3]共有（ (d1-c1+1)*(d2-c2+1)*(d3-c3+1) ）个元素。
数组A[1..10,-2..6,2..8]以行优先顺序存储，设基地址为100，每个元素占3 个存储单元，则元素A[5,0,7]的存储地址是（ 913 ）。=100+(4*7*9+2*7+5)*3
将一个下三角矩阵A[1..100,1..100]按行优先存入一维数组]中，A 中元素A[66,65]在B 数组中的位置为（ 2276 ）。
四、 计算题
1. 数组 A[8][6][9]以行主序存储，设第一个元素的首地址是54，每个元素的长度为5，求元素A[2][4][5]的存储地址。
答：LOCA[2][4][5]=54+（2*6*9+4*9+5）*5=799
2. 假设二维数组 A6x8，每个元素用相邻的6 个字节存储，存储器按字节编址，已知A 的基地址为1000，计算：
（1）数组A 的体积（存储量）
（2）A 的最后一个元素第一个字节的地址
（3）按行存储时，a14 的第一个字节的地址
（4）按列存储时，a47 的第一个字节的地址。
答：（1）数组A 的体积V=6*8*6=288
（2）1000+288-6=1282
（3）1000+（4+1*8）*6=1072
（4）1000+（4+7*6）*6=1276
3. 假设按低下标优先存储整数数组 A9x3x5x8 时，第一个元素的字节地址是100，每个整数占4 个字节。
问下列元素的存储地址是什么？
（1）a0000 =100
（2） a1111 =100+（1*3*5*8+1*5*8+1*8+1）*4
（3） a3125 =100+（3*3*5*8+1*5*8+2*8+5）*4
（4）a8247=100+（8*3*5*8+2*5*8+4*8+7）*4
4. 按行优先顺序和按列优先顺序分别列出四维数组 A[2][2][2][2]所有元素在内存中的存储顺序。
答：行优先顺序：A[0][0][0][0], A[0][1][0][0], A[1][0][0][0], A[1][1][0][0], A[0][0][1][0], A[0][1][1][0], A[1][0][1][0],
A[1][1][1][0], A[0][0][0][1], A[0][1][0][1], A[1][0][0][1], A[1][1][0][1], A[0][0][1][1], A[0][1][1][1], A[1][0][1][1],
A[1][1][1][1]
列优先顺序：A[0][0][0][0]，A[1][0][0][0]，A[0][1][0][0]，A[1][1][0][0]，A[0][0][1][0]，A[1][0][1][0]，A[0][1][1][0]，A[1][1][1][0]，A[0][0][0][1]，A[1][0][0][1]，A[0][1][0][1]，A[1][1][0][1]，A[0][0][1][1]，A[1][0][1][1]，A[0][1][1][1]，A[1][1][1][1]
5. 一个 n 阶对称矩阵A 采用一维数组S 按行序为主序存放其上三角各元素，写出S[k]与A[i,j]的关系公式。设A[1，1]存于S[1]中。
6. 写出下面稀疏矩阵对应的三元组表示，并画出十字链表表示法。
A=〔（0，0，2，0），（3，0，0，0），（0，0，-1，5），（0，0，0，0）〕
答：三元组表示：（（0,2,2），（1,0,3），（2,2，-1），（2,3,5））
十字链表表示法：
五、 简答题
1. 什么是广义表，简述广义表与线性表的主要区别？
2. 利用广义表的 Head 和Tail 运算把原子student 从下列广义表中分离出来。
（1） L1=（soldier,teacher,student,worker,farmer）
（2） L2=（soldier,(teacher,student),(worker,farmer)）
3. 画出下列广义表的存储结构图，并求它的深度。
（1）((( )),a,((b,c)),(((d)))) （2）((((a),(b))),((( ),d),(e,f)))
4. 已知图4.4 为广义表的存储结构图，写出各图的广义表。
六、 设计题
1. 对于二维数组 A[m][n]，分别编写相应函数实现如下功能：
（1）求数组 A 靠边元素之和；
（2）求从A[0][0]开始的互不相邻的各元素之和；（3）当m=n 时分别求两条对角线上的元素之和，否则打印出
m≠n 的信息。
倚窗远眺，目光目光尽处必有一座山，那影影绰绰的黛绿色的影，是春天的颜色。周遭流岚升腾，没露出那真实的面孔。面对那流转的薄雾，我会幻想，那里有一个世外桃源。在天阶夜色凉如水的夏夜，我会静静地，静静地，等待一场流星雨的来临…
许下一个愿望，不乞求去实现，至少，曾经，有那么一刻，我那还未枯萎的，青春的，诗意的心，在我最美的年华里，同星空做了一次灵魂的交流…
秋日里，阳光并不刺眼，天空是一碧如洗的蓝，点缀着飘逸的流云。偶尔，一片飞舞的落叶，会飘到我的窗前。斑驳的印迹里，携刻着深秋的颜色。在一个落雪的晨，这纷纷扬扬的雪，飘落着一如千年前的洁白。窗外，是未被污染的银白色世界。我会去迎接，这人间的圣洁。在这流转的岁月里，有着流转的四季，还有一颗流转的心，亘古不变的心。
2024年2月23日发(作者：旗颐)
第5章 数组与广义表一、 选择题
1. 在以下讲述中，正确的是（ B ）。
A、线性表的线性存储结构优于链表存储结构
B、二维数组是其数据元素为线性表的线性表
C、栈的操作方式是先进先出
D、队列的操作方式是先进后出
2. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转
置运算，这种观点（ A ）。
A、正确 B、错误
3. 二维数组SA 中，每个元素的长度为3 个字节，行下标I 从0 到7，列下标J 从0 到9，从首地址SA 开始
连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为（ B）。
A、SA+141 B、SA+180 C、SA+222 D、SA+225
4. 数组SA 中，每个元素的长度为3 个字节，行下标I 从0 到7，列下标J 从0 到9，从首地址SA 开始连续
存放在存储器内，存放该数组至少需要的字节数是（ C ）。
A、80 B、100 C、240 D、270
5. 常对数组进行的两种基本操作是（ B ）。
A、建立与删除 B、索引和修改 C、查找和修改 D、查找和索引
6. 将一个A[15][15]的下三角矩阵（第一个元素为A[0][0]），按行优先存入一维数组B[120]中，A 中元素A[6][5]
在B 数组中的位置K 为（ B ）。
A、19 B、26 C、21 D、15
7. 若广义表A 满足Head(A)=Tail(A)，则A 为（ B ）。
A、（） B、（（）） C、（（），（）） D、（（），（），（））
8. 广义表（（a）,a）的表头是（ C ），表尾是（C ）。
A、a B、b C、(a) D、((a))
9. 广义表（（a,b）,c,d）的表头是（ C ），表尾是（ D ）。
A、a B、b C、(a,b) D、(c,d)
10. 广义表（（a））的表头是（ B ），表尾是（C ）。
A、a B、(a) C、() D、((a))
11. 广义表（a,b,c,d）的表头是（ A ），表尾是（ D ）。
A、a B、(a) C、(a,b) D、(b,c,d)
12. 广义表（（a,b,c,d））的表头是（ C ），表尾是（ B ）。
A、a B、() C、(a,b,c,d) D、((a,b,c,d))
13. 下面结论正确的是（ BC ）。
A、一个广义表的表头肯定不是一个广义表
B、一个广义表的表尾肯定是一个广义表
C、广义表L=（（），（A，B））的表头为空表
D、广义表中原子个数即为广义表的长度
14. 广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=( D )
A、(G) B、(D) C、C D、 D
15. 已知广义表L=((x,y,z),a,(u,t,w))，从L 表中取出原子项t 的操作是（ D ）。
A 、Head(Head(Tail(Tail(L)))) B 、Tail(Head(Head(Tail(L))))
C 、Head(Tail(Head(Tail(L)))) D 、Head(Tail(Head(Tail(Tail(L)))))
16. 16、设A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))=( D )
A. (g) B.(d) C.c D.d
17. 对矩阵压缩存储是为了（ B ）
A、方便运算 B、节省空间 C、方便存储
18. 稀疏矩阵一般的压缩存储方法有两种，即（ C ）
A、二元数组和三元数组 B、三元组和散列
C、三元组和十字链表 D、散列和十字链表
D、提高运算速度
二、 判断题(F/T)
1.
2.
3.
4.
5.
6.
7.
8.
9.
数组是同类型值的集合。(T)
数组的存储结构是一组连续的内存单元。(T)
数组是一种复杂的数据结构，数组元素之间的关系，即不是线性的也不是树形的。(T)
插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也会经常使用。(F)
使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。(F)
广义表是由零个或多个原子或子表所组成的有限序列，所以广义表可能为空表。(T)
线性表可以看成是广义表的特例，如果广义表中的每个元素是原子，则广义表便成为线性表。()
广义表中原子个数即为广义表的长度。(F)
广义表中元素的个数即为广义表的深度。(F)
三、 填空题
1. 设a 是含有N 个分量的整数数组，则求该数组中最大整数的递归定义为（ ），最小整数的递归定义为
（ ）。
2. 二维数组A[10][5]采用行序为主方式存储，每个元素占4 个存储单元，并且A[5][3]的存储地址是1000，则A[8][2]的地址是（ 1056 ）。
3. 二维数组A[m][n]采用行序为主方式存储，每个元素占k 个存储单元，并且第一个元素的存储地址是Loc(A[0][0])，则A[i][j]的地址是（Loc(A[0][0]+(i*n+m)*k ）。
4. 广义表的（深度 ）定义为广义表中括弧的重数。
5. 设广义表L=（（），（）），则Head(L)=（ () ）；Tail(L)=（(()) ）；L 的长度是（ 2 ）；L 的深度是（ 2 ）。
6. 广义表中的元素可以是（ 原子和字表），其描述宜采用程序设计语言中的（LISP语言 ）表示。
7. 广义表(((a)))的表头是（ ((a)) ），表尾是（() ）。
8. 广义表((a),((b),c),(((d))))的表头是（ (a) ），表尾是（(((b),c),(((d)))) ）。
9. 设广义表A=(x,((a,b),c,d))，则Head(Head(Tail(A)))=（ a ）。
10. 设广义表A=(a,b,c),B=(A,(c,d)),C=(a,(B,A),(e,f))，则
（1）Head(A)=( a ) （2） Tail(B)=( ((C,d)) )
（3）Head(Head(Head(Tail(C))))=( (a,b,c) )
11. 下三角矩阵A[1..N,1..N]的下三角元素已压缩到一维数组S[1..N*（N+1）/2+1]中，若按行序为主序存储，则A[I,j]对应的S 中的存储位置是 （ ）。
0312. 已知一个稀疏矩阵为0013.
14.
15.
16.
0200010000，则对应的三元组表表示为（ （1，3，2） ，（2，1，3），（3，3，-1），50（3，4，5） ） 。
一个n*n 的对称矩阵，如果以行或列为主序存入内存，则其容量为 （n*（n+1）/2 ）。
三维数组A[c1..d1,c2..d2..,c3..d3]共有（ (d1-c1+1)*(d2-c2+1)*(d3-c3+1) ）个元素。
数组A[1..10,-2..6,2..8]以行优先顺序存储，设基地址为100，每个元素占3 个存储单元，则元素A[5,0,7]的存储地址是（ 913 ）。=100+(4*7*9+2*7+5)*3
将一个下三角矩阵A[1..100,1..100]按行优先存入一维数组]中，A 中元素A[66,65]在B 数组中的位置为（ 2276 ）。
四、 计算题
1. 数组 A[8][6][9]以行主序存储，设第一个元素的首地址是54，每个元素的长度为5，求元素A[2][4][5]的存储地址。
答：LOCA[2][4][5]=54+（2*6*9+4*9+5）*5=799
2. 假设二维数组 A6x8，每个元素用相邻的6 个字节存储，存储器按字节编址，已知A 的基地址为1000，计算：
（1）数组A 的体积（存储量）
（2）A 的最后一个元素第一个字节的地址
（3）按行存储时，a14 的第一个字节的地址
（4）按列存储时，a47 的第一个字节的地址。
答：（1）数组A 的体积V=6*8*6=288
（2）1000+288-6=1282
（3）1000+（4+1*8）*6=1072
（4）1000+（4+7*6）*6=1276
3. 假设按低下标优先存储整数数组 A9x3x5x8 时，第一个元素的字节地址是100，每个整数占4 个字节。
问下列元素的存储地址是什么？
（1）a0000 =100
（2） a1111 =100+（1*3*5*8+1*5*8+1*8+1）*4
（3） a3125 =100+（3*3*5*8+1*5*8+2*8+5）*4
（4）a8247=100+（8*3*5*8+2*5*8+4*8+7）*4
4. 按行优先顺序和按列优先顺序分别列出四维数组 A[2][2][2][2]所有元素在内存中的存储顺序。
答：行优先顺序：A[0][0][0][0], A[0][1][0][0], A[1][0][0][0], A[1][1][0][0], A[0][0][1][0], A[0][1][1][0], A[1][0][1][0],
A[1][1][1][0], A[0][0][0][1], A[0][1][0][1], A[1][0][0][1], A[1][1][0][1], A[0][0][1][1], A[0][1][1][1], A[1][0][1][1],
A[1][1][1][1]
列优先顺序：A[0][0][0][0]，A[1][0][0][0]，A[0][1][0][0]，A[1][1][0][0]，A[0][0][1][0]，A[1][0][1][0]，A[0][1][1][0]，A[1][1][1][0]，A[0][0][0][1]，A[1][0][0][1]，A[0][1][0][1]，A[1][1][0][1]，A[0][0][1][1]，A[1][0][1][1]，A[0][1][1][1]，A[1][1][1][1]
5. 一个 n 阶对称矩阵A 采用一维数组S 按行序为主序存放其上三角各元素，写出S[k]与A[i,j]的关系公式。设A[1，1]存于S[1]中。
6. 写出下面稀疏矩阵对应的三元组表示，并画出十字链表表示法。
A=〔（0，0，2，0），（3，0，0，0），（0，0，-1，5），（0，0，0，0）〕
答：三元组表示：（（0,2,2），（1,0,3），（2,2，-1），（2,3,5））
十字链表表示法：
五、 简答题
1. 什么是广义表，简述广义表与线性表的主要区别？
2. 利用广义表的 Head 和Tail 运算把原子student 从下列广义表中分离出来。
（1） L1=（soldier,teacher,student,worker,farmer）
（2） L2=（soldier,(teacher,student),(worker,farmer)）
3. 画出下列广义表的存储结构图，并求它的深度。
（1）((( )),a,((b,c)),(((d)))) （2）((((a),(b))),((( ),d),(e,f)))
4. 已知图4.4 为广义表的存储结构图，写出各图的广义表。
六、 设计题
1. 对于二维数组 A[m][n]，分别编写相应函数实现如下功能：
（1）求数组 A 靠边元素之和；
（2）求从A[0][0]开始的互不相邻的各元素之和；（3）当m=n 时分别求两条对角线上的元素之和，否则打印出
m≠n 的信息。
倚窗远眺，目光目光尽处必有一座山，那影影绰绰的黛绿色的影，是春天的颜色。周遭流岚升腾，没露出那真实的面孔。面对那流转的薄雾，我会幻想，那里有一个世外桃源。在天阶夜色凉如水的夏夜，我会静静地，静静地，等待一场流星雨的来临…
许下一个愿望，不乞求去实现，至少，曾经，有那么一刻，我那还未枯萎的，青春的，诗意的心，在我最美的年华里，同星空做了一次灵魂的交流…
秋日里，阳光并不刺眼，天空是一碧如洗的蓝，点缀着飘逸的流云。偶尔，一片飞舞的落叶，会飘到我的窗前。斑驳的印迹里，携刻着深秋的颜色。在一个落雪的晨，这纷纷扬扬的雪，飘落着一如千年前的洁白。窗外，是未被污染的银白色世界。我会去迎接，这人间的圣洁。在这流转的岁月里，有着流转的四季，还有一颗流转的心，亘古不变的心。