《《数据结构》习题集第5章数组与广义表.pdf》由会员分享，可在线阅读，更多相关《《数据结构》习题集第5章数组与广义表.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构课后练习题 第 5 章 数组与广义表 1/5 北京理工大学珠海学院计算机学院“数据结构”课程组编制 2011-3-1 第 5 章 数组与广义表 一、选择题 1.在以下讲述中，正确的是（B ）。A、线性表的线性存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作方式是先进先出 D、队列的操作方式是先进后出 2.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转 置运算，这种观点（A ）。A、正确 B、错误 3.二维数组 SA 中，每个元素的长度为 3 个字节，行下标 I 从 0 到 7，列下标 J 从 0 到 9，从首地
2、址 SA 开始 连续存放在存储器内，该数组按列存放时，元素 A47的起始地址为（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.将一个 A1515的下三角矩阵（第一个元素为 A00），按行优先存入一维数组 B120中，A 中元素
3、A65 在 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
4、,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 数据结构课后练习题 第 5 章 数组与广义表 2/5 北京理工大学珠海学院计算机学院“数据结构”课程组编制 2
5、011-3-1 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、方便存储 D、提高运算速度 18.稀疏矩阵一般的
6、压缩存储方法有两种，即（C ）A、二元数组和三元数组 B、三元组和散列 C、三元组和十字链表 D、散列和十字链表 二、判断题(F/T)1.数组是同类型值的集合。(T)2.数组的存储结构是一组连续的内存单元。(T)3.数组是一种复杂的数据结构，数组元素之间的关系，即不是线性的也不是树形的。(T)4.插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也会经常使用。(F)5.使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。(F)6.广义表是由零个或多个原子或子表所组成的有限序列，所以广义表可能为空表。(T)7.线性表可以看成是广义表的特例，如果广义表中的每个元素是原子，则广义
7、表便成为线性表。()8.广义表中原子个数即为广义表的长度。(F)9.广义表中元素的个数即为广义表的深度。(F)三、填空题 1.设 a 是含有 N 个分量的整数数组，则求该数组中最大整数的递归定义为（），最小整数的递归定义为（）。2.二维数组 A105采用行序为主方式存储，每个元素占 4 个存储单元，并且 A53的存储地址是 1000，则 A82的地址是（1056 ）。3.二维数组Amn采用行序为主方式存储，每个元素占k 个存储单元，并且第一个元素的存储地址是Loc(A00)，则 Aij的地址是（Loc(A00+(i*n+m)*k ）。4.广义表的（深度 ）定义为广义表中括弧的重数。5.设广义表
8、 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,
9、d)（3）Head(Head(Head(Tail(C)=(a,b,c)11.下三角矩阵 A1.N,1.N的下三角元素已压缩到一维数组 S1.N*（N+1）/2+1中，若按行序为主序存储，则 AI,j对应的 S 中的存储位置是（）。数据结构课后练习题 第 5 章 数组与广义表 3/5 北京理工大学珠海学院计算机学院“数据结构”课程组编制 2011-3-1 12.已知一个稀疏矩阵为0000510000030200，则对应的三元组表表示为（1，3，2），（2，1，3），（3，3，-1），（3，4，5）。13.一个 n*n 的对称矩阵，如果以行或列为主序存入内存，则其容量为（n*（n+1）/2 ）。1
10、4.三维数组 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 ）。=100+(4*7*9+2*7+5)*3 16.将一个下三角矩阵 A1.100,1.100按行优先存入一维数组 B1.n中，A 中元素 A66,65在 B 数组中的位置为（2276 ）。四、计算题 1.数组 A869以行主序存储，设第一个元素的首地址是 54，每个元素的长度为 5，求元素 A245的存储地址。答：LOCA
11、245=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，每
12、个整数占 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.按行优先顺序和按列优先顺序分别列出四维数组 A2222所有元素在内存中的存储顺序。答：行优先顺序：A0000,A0100,A1000,A1100,A0010,A0110,A1010,A1110,A0001,A0101,A1001,A1101,A0011,A0111,A1011,A1111 列优先顺序：A
13、0000，A1000，A0100，A1100，A0010，A1010，A0110，A1110，A0001，A1001，A0101，A1101，A0011，A1011，A0111，A1111 5.一个 n 阶对称矩阵A 采用一维数组S 按行序为主序存放其上三角各元素，写出Sk与Ai,j的关系公式。设A1，数据结构课后练习题 第 5 章 数组与广义表 4/5 北京理工大学珠海学院计算机学院“数据结构”课程组编制 2011-3-1 1存于 S1中。6.写出下面稀疏矩阵对应的三元组表示，并画出十字链表表示法。A=（0，0，2，0），（3，0，0，0），（0，0，-1，5），（0，0，0，0）答：三元组
14、表示：（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.对于二维数组 Amn，分别编写相应函数实现如下功能：（1）求数组 A 靠边元素之和；数据结构课后练习题 第 5 章 数组与广义表 5/5 北京理工大学珠海学院计算机学院“数据结构”课程组编制 2011-3-1（2）求从 A00开始的互不相邻的各元素之和；（3）当 m=n 时分别求两条对角线上的元素之和，否则打印出 mn 的信息。2.如果矩阵 A 中的一个元素 Aij满足下列条件：Aij是第 I 行中最小的元素，又是第 j 列中值最大的元素，则称之为该矩阵的一个马鞍点。编写函数计算 mn 的矩阵 A 的所有马鞍点，并分析算法的时间复杂度。