数据结构课后练习题 第5章 数组和广义表
第5章 数组和广义表
一、 选择题
1. 在以下讲述中，正确的是（ ）。【＊】
A、线性表的线性存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作方式是先进先出 D、队列的操作方式是先进后出
2. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转
置运算，这种观点（ ）。【＊，★】 A、正确 B、错误
3. 二维数组SA 中，每个元素的长度为3 个字节，行下标I 从0 到7，列下标J 从0 到9，从首地址SA 开始
连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为（ ）。【＊，★】 A、SA+141 B、SA+180 C、SA+222 D、SA+225
4. 数组SA 中，每个元素的长度为3 个字节，行下标I 从0 到7，列下标J 从0 到9，从首地址SA 开始连续
存放在存储器内，存放该数组至少需要的字节数是（ ）。【＊】 A、80 B、100 C、240 D、270 5. 常对数组进行的两种基本操作是（ ）。【＊】
A、建立与删除 B、索引和修改 C、查找和修改 D、查找和索引
6. 将一个A[15][15]的下三角矩阵（第一个元素为A[0][0]），按行优先存入一维数组B[120]中，A 中元素A[6][5]
在B 数组中的位置K 为（ ）。【＊＊，★】 A、19 B、26 C、21 D、15 7. 若广义表A 满足Head(A)=Tail(A)，则A 为（ ）。【＊】
A、（） B、（（）） C、（（），（）） D、（（），（），（）） 8. 广义表（（a）,a）的表头是（ ），表尾是（ ）。【＊】
A、a B、b C、(a) D、((a)) 9. 广义表（（a,b）,c,d）的表头是（ ），表尾是（ ）。【＊】
A、a B、b C、(a,b) D、(c,d) 10. 广义表（（a））的表头是（ ），表尾是（ ）。【＊】
A、a B、(a) C、() D、((a)) 11. 广义表（a,b,c,d）的表头是（ ），表尾是（ ）。【＊】
A、a B、(a) C、(a,b) D、(b,c,d) 12. 广义表（（a,b,c,d））的表头是（ ），表尾是（ ）。【＊】
A、a B、() C、(a,b,c,d) D、((a,b,c,d)) 13. 下面结论正确的是（ ）。（注：多项选择）【＊，★】
A、一个广义表的表头肯定不是一个广义表 B、一个广义表的表尾肯定是一个广义表
C、广义表L=（（），（A，B））的表头为空表 D、广义表中原子个数即为广义表的长度
14. 广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=( ) 【＊，★】
A、(G) B、(D) C、C D、 D
15. 已知广义表L=((x,y,z),a,(u,t,w))，从L 表中取出原子项t 的操作是（ ）。【＊，★】
1/4
北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1
数据结构课后练习题 第5章 数组和广义表
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. 设A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))=( )（注：与14题重复）
A. (g) B.(d) C.c D.d 17. 对矩阵压缩存储是为了（ ）【＊】 A、方便运算 B、节省空间 C、方便存储 18. 稀疏矩阵一般的压缩存储方法有两种，即（ ）【＊】
A、二元数组和三元数组 B、三元组和散列 C、三元组和十字链表 D、散列和十字链表
D、提高运算速度
二、 判断题
1. 2. 3. 4. 5. 6. 7. 8. 9.
数组是同类型值的集合。【＊】
数组的存储结构是一组连续的内存单元。【＊】
数组是一种复杂的数据结构，数组元素之间的关系，即不是线性的也不是树形的。【＊】
插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也会经常使用。【＊】 使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。【＊】
广义表是由零个或多个原子或子表所组成的有限序列，所以广义表可能为空表。【＊】
线性表可以看成是广义表的特例，如果广义表中的每个元素是原子，则广义表便成为线性表。【＊】 广义表中原子个数即为广义表的长度。【＊】 广义表中元素的个数即为广义表的深度。【＊】
三、 填空题
1. 设a 是含有N 个分量的整数数组，则求该数组中最大整数的递归定义为（ ），最小整数的递归定义为
（ ）。（注：有函数max(p1,p2)和min(p1,p2)）【＊＊，★】 2. 二维数组A[10][5]采用行序为主方式存储，每个元素占4 个存储单元，并且A[5][3]的存储地址是1000，则A[8][2]
的地址是（ ）。【＊＊，★】
3. 二维数组A[m][n]采用行序为主方式存储，每个元素占k 个存储单元，并且第一个元素的存储地址是Loc(A[0][0])，
则A[i][j]的地址是（ ）。【＊＊】
4. 广义表的（ ）定义为广义表中括弧的重数。【＊】
5. 设广义表L=（（），（）），则Head(L)=（ ）；Tail(L)=（ ）；L 的长度是（ ）；L 的深度是（ ）。
【＊】
6. 广义表中的元素可以是（ ），其描述宜采用程序设计语言中的（ ）表示。【＊，？】 7. 广义表(((a)))的表头是（ ），表尾是（ ）。【＊】
8. 广义表((a),((b),c),(((d))))的表头是（ ），表尾是（ ）。【＊】 9. 设广义表A=(x,((a,b),c,d))，则Head(Head(Tail(A)))=（ ）。【＊】 10. 设广义表A=(a,b,c),B=(A,(c,d)),C=(a,(B,A),(e,f))，则【＊】
（1）Head(A)=( ) （2） Tail(B)=( ) （3）Head(Head(Head(Tail(C))))=( )
11. 下三角矩阵A[1..N,1..N]的下三角元素已压缩到一维数组S[1..N*（N+1）/2+1]中，若按行序为主序存储，则A[I,j]
对应的S 中的存储位置是 （ ）。【＊＊，★】
2/4
北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1
数据结构课后练习题 第5章 数组和广义表
?0?312. 已知一个稀疏矩阵为??0??002000?1000?0??，则对应的三元组表表示为（ ） 。【＊】 5??0?13. 一个n*n 的对称矩阵，如果以行或列为主序存入内存，则其容量为 （ ）。【＊】 14. 三维数组A[c1..d1,c2..d2..,c3..d3]共有（ ）个元素。【＊】
15. 数组A[1..10,-2..6,2..8]以行优先顺序存储，设基地址为100，每个元素占3 个存储单元，则元素A[5,0,7]的存储
地址是（ ）。【＊＊，★】
16. 将一个下三角矩阵A[1..100,1..100]按行优先存入一维数组B[1..n]中，A 中元素A[66,65]在B 数组中的位置为
（ ）。【＊＊，★】
四、 计算题
1. 数组 A[8][6][9]以行主序存储，设第一个元素的首地址是54，每个元素的长度为5，求元素A[2][4][5]的存储地
址。【＊＊】
2. 假设二维数组 A6x8，每个元素用相邻的6 个字节存储，存储器按字节编址，已知A 的基地址为1000，计算：
（1）数组A 的体积（存储量）【＊＊，★】 （2）A 的最后一个元素第一个字节的地址 （3）按行存储时，a14 的第一个字节的地址 （4）按列存储时，a47 的第一个字节的地址。
3. 假设按低下标优先存储整数数组 A9x3x5x8 时，第一个元素的字节地址是100，每个整数占4 个字节。
问下列元素的存储地址是什么？【＊＊，★】 （1）a0000 （2）a1111 （3）a3125 （4）a8247
4. 按行优先顺序和按列优先顺序分别列出四维数组 A[2][2][2][2]所有元素在内存中的存储顺序。【＊＊】 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）〕
五、 简答题
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 为广义表的存储结构图，写出各图的广义表。【＊＊，★】
3/4
北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1
数据结构课后练习题 第5章 数组和广义表
六、 设计题
1. 对于二维数组 A[m][n]，分别编写相应函数实现如下功能：【＊＊＊，★】
（1）求数组 A 靠边元素之和；
（2）求从A[0][0]开始的互不相邻的各元素之和；（3）当m=n 时分别求两条对角线上的元素之和，否则打印出 m≠n 的信息。
2. 如果矩阵 A 中的一个元素A[i][j]满足下列条件：A[i][j]是第I 行中最小的元素，又是第j 列中值最大的元素，
则称之为该矩阵的一个马鞍点。编写函数计算m×n 的矩阵A 的所有马鞍点，并分析算法的时间复杂度。【＊＊＊，★】
4/4
北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1