最新《数据结构》习题集：第5章-数组与广义表.doc

《最新《数据结构》习题集：第5章-数组与广义表.doc》由会员分享，可在线阅读，更多相关《最新《数据结构》习题集：第5章-数组与广义表.doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品资料数据结构习题集：第5章-数组与广义表.第5章 数组与广义表一、 选择题1. 在以下讲述中，正确的是（B ）。A、线性表的线性存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作方式是先进先出 D、队列的操作方式是先进后出2. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（ B ）。A、正确 B、错误3. 二维数组SA 中，每个元素的长度为3 个字节，行下标I 从0 到7，列下标J 从0 到9，从首地址SA 开始连续存放在存储器内，该数组按列存放时，元素A47的起始地址为（ B ）。A、SA+141

2、 B、SA+180 C、SA+222 D、SA+2254. 数组SA 中，每个元素的长度为3 个字节，行下标I 从0 到7，列下标J 从0 到9，从首地址SA 开始连续存放在存储器内，存放该数组至少需要的字节数是（ C ）。A、80 B、100 C、240 D、2705. 常对数组进行的两种基本操作是（ C ）。A、建立与删除 B、索引和修改C、查找和修改 D、查找和索引6. 将一个A1515的下三角矩阵（第一个元素为A00），按行优先存入一维数组B120中，A 中元素A65在B 数组中的位置K 为（ B ）。A、19 B、26 C、21 D、157. 若广义表A 满足Head(A)=Tail

3、(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、

4、() 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、 D15. 已知广义表L=(x,y,z),a,(u,t,w)，从L 表中取出原子项t 的操作是（D ）。A 、Head(Head(Tail(Tail(L) B 、Tail(Head(Head

5、(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.d17. 对矩阵压缩存储是为了（ B ）A、方便运算 B、节省空间 C、方便存储 D、提高运算速度18. 稀疏矩阵一般的压缩存储方法有两种，即（ C ）A、二元数组和三元数组 B、三元组和散列C、三元组和十字链表 D、散列和十字链表二、 判断题1. 数组是同类型值的集合。X2. 数组的存储结构是一组连续

6、的内存单元。V3. 数组是一种复杂的数据结构，数组元素之间的关系，即不是线性的也不是树形的。X4. 插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也会经常使用。X5. 使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。V6. 广义表是由零个或多个原子或子表所组成的有限序列，所以广义表可能为空表。V7. 线性表可以看成是广义表的特例，如果广义表中的每个元素是原子，则广义表便成为线性表。V8. 广义表中原子个数即为广义表的长度。X9. 广义表中元素的个数即为广义表的深度。X三、 填空题1. 设a 是含有N 个分量的整数数组，则求该数组中最大整数的递归定义为（ ），最小整数

7、的递归定义为（ ）。2. 二维数组A105采用行序为主方式存储，每个元素占4 个存储单元，并且A53的存储地址是1000，则A82的地址是（ 1056 ）。3. 二维数组Amn采用行序为主方式存储，每个元素占k 个存储单元，并且第一个元素的存储地址是Loc(A00)，则Aij的地址是（ (i*n+j)*k+Loc(A00) ）。4. 广义表的（ 深度 ）定义为广义表中括弧的重数。5. 设广义表L=（），（），则Head(L)=（ () ）；Tail(L)=（ () ）；L 的长度是（ 2 ）；L 的深度是（ 2 ）。6. 广义表中的元素可以是（ 原子或字表 ），其描述宜采用程序设计语言中的（

8、链表 ）表示。7. 广义表(a)的表头是（ (a) ），表尾是（ () ）。8. 广义表(a),(b),c),(d)的表头是（ (a) ），表尾是（ (b),c),(d) ）。9. 设广义表A=(x,(a,b),c,d)，则Head(Head(Tail(A)=（(a,b) ）。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 )11. 下三角矩阵A1.N,1.N的下三角元素已压缩到一维数组S1.N*（N+1）/2+1

9、中，若按行序为主序存储，则AI,j对应的S 中的存储位置是 （ ）。12. 已知一个稀疏矩阵为，则对应的三元组表表示为（ a(0,2,2),a(1,0,3),a(2,2,-1),a(2,3,5) ） 。13. 一个n*n 的对称矩阵，如果以行或列为主序存入内存，则其容量为 （ (n+1)*n/2 ）。14. 三维数组Ac1.d1,c2.d2.,c3.d3共有（(d1-c1+1)*(d2+c2+1)*(d3-c3+1) ）个元素。15. 数组A1.10,-2.6,2.8以行优先顺序存储，设基地址为100，每个元素占3 个存储单元，则元素A5,0,7的存储地址是（913 ）。16. 将一个下三角矩

10、阵A1.100,1.100按行优先存入一维数组B1.n中，A 中元素A66,65在B 数组中的位置为（ 2210=(65+1)*(66)/2+65 ）。四、 计算题1. 数组 A869以行主序存储，设第一个元素的首地址是54，每个元素的长度为5，求元素A245的存储地址。 答: (2*6*9+4*9+5)*5+54=7992. 假设二维数组 A6x8，每个元素用相邻的6 个字节存储，存储器按字节编址，已知A 的基地址为1000，计算：（1）数组A 的体积（存储量） 288字节（2）A 的最后一个元素第一个字节的地址 1282（3）按行存储时，a14 的第一个字节的地址 1072（4）按列存储时

11、，a47 的第一个字节的地址。 12763. 假设按低下标优先存储整数数组 A9x3x5x8 时，第一个元素的字节地址是100，每个整数占4 个字节。问下列元素的存储地址是什么？（1）a0000 100（2） a1111 (1*3*5*8+1*5*8+1*8+1)*4+100=776（3） a3125 (3*3*5*8+40+16+5)*4+100=1784（4）a8247 (8*3*5*8+2*5*8+4*8+7)*4+100=44164. 按行优先顺序和按列优先顺序分别列出四维数组 A2222所有元素在内存中的存储顺序。按行:A0000A0001A0010A0011A0100A0101A0

12、110A0111A1000A1001A1010A1011A1100A1101A1110A1111按列:A0000A1000A0100A1100A0010A1010A0110A1110A0001A1001A0101A1101A0011A1011A0111A11115. 一个 n 阶对称矩阵A 采用一维数组S 按行序为主序存放其上三角各元素，写出Sk与Ai,j的关系公式。设A1，1存于S1中。6. 写出下面稀疏矩阵对应的三元组表示，并画出十字链表表示法。A=（0，0，2，0），（3，0，0，0），（0，0，-1，5），（0，0，0，0）五、 简答题1. 什么是广义表，简述广义表与线性表的主要区别？

13、答:广义表是一种非线性的数据结构，它是线性表的一种推广 广义表中的数据元素既可以是单个元素，也可以是子表，因此对于广义表，我们难以用顺序存储结构来表示它.2. 利用广义表的 Head 和Tail 运算把原子student 从下列广义表中分离出来。（1） L1=（soldier,teacher,student,worker,farmer） Head(Tail(Tail(L1)（2） L2=（soldier,(teacher,student),(worker,farmer)） Head(Tail(Head(Tail(L2)3. 画出下列广义表的存储结构图，并求它的深度。（1）( ),a,(b,c),(d) （2）(a),(b),( ),d),(e,f)(1) 深度4 结构未知(2) 深度4 结构未知4. 已知图4.4 为广义表的存储结构图，写出各图的广义表。六、 设计题1. 对于二维数组 Amn，分别编写相应函数实现如下功能：（1）求数组 A 靠边元素之和；（2）求从A00开始的互不相邻的各元素之和；（3）当m=n 时分别求两条对角线上的元素之和，否则打印出mn 的信息。2. 如果矩阵 A 中的一个元素Aij满足下列条件：Aij是第I 行中最小的元素，又是第j 列中值最大的元素，则称之为该矩阵的一个马鞍点。编写函数计算mn 的矩阵A 的所有马鞍点，并分析算法的时间复杂度。