《数据结构》习题集第5章_数组与广义表

数据结构课后练习题第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，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为（B）。A、SA+141B、SA+180C、SA+222D、SA+2254.数组SA中，每个元素的长度为3个字节，行下标I从0到7，列下标J从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（C）。A、80B、100C、240D、2705.常对数组进行的两种基本操作是（B）。A、建立与删除B、索引和修改C、查找和修改D、查找和索引6.将一个A[15][15]的下三角矩阵（第一个元素为A[0][0]），按行优先存入一维数组B[120]中，A中元素A[6][5]在B数组中的位置K为（B）。A、19B、26C、21D、157.若广义表A满足Head(A)=Tail(A)，则A为（B）。A、（）B、（（））C、（（），（））D、（（），（），（））8.广义表（（a）,a）的表头是（C），表尾是（C）。A、aB、bC、(a)D、((a))9.广义表（（a,b）,c,d）的表头是（C），表尾是（D）。A、aB、bC、(a,b)D、(c,d)10.广义表（（a））的表头是（B），表尾是（C）。A、aB、(a)C、()D、((a))11.广义表（a,b,c,d）的表头是（A），表尾是（D）。A、aB、(a)C、(a,b)D、(b,c,d)12.广义表（（a,b,c,d））的表头是（C），表尾是（B）。A、aB、()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、CD、D数据结构课后练习题第5章数组与广义表2/5北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-115.已知广义表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.cD.d17.对矩阵压缩存储是为了（B）A、方便运算B、节省空间C、方便存储D、提高运算速度18.稀疏矩阵一般的压缩存储方法有两种，即（C）A、二元数组和三元数组B、三元组和散列C、三元组和十字链表D、散列和十字链表二、判断题(F/T)1.数组是同类型值的集合。(T)2.数组的存储结构是一组连续的内存单元。(T)3.数组是一种复杂的数据结构，数组元素之间的关系，即不是线性的也不是树形的。(T)4.插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也会经常使用。(F)5.使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。(F)6.广义表是由零个或多个原子或子表所组成的有限序列，所以广义表可能为空表。(T)7.线性表可以看成是广义表的特例，如果广义表中的每个元素是原子，则广义表便成为线性表。()8.广义表中原子个数即为广义表的长度。(F)9.广义表中元素的个数即为广义表的深度。(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中的存储位置是（）。数据结构课后练习题第5章数组与广义表3/5北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-112.已知一个稀疏矩阵为0000510000030200，则对应的三元组表表示为（（1，3，2），（2，1，3），（3，3，-1），（3，4，5））。13.一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为（n*（n+1）/2）。14.三维数组A[c1..d1,c2..d2..,c3..d3]共有（(d1-c1+1)*(d2-c2+1)*(d3-c3+1)）个元素。15.数组A[1..10,-2..6,2..8]以行优先顺序存储，设基地址为100，每个元素占3个存储单元，则元素A[5,0,7]的存储地址是（913）。=100+(4*7*9+2*7+5)*316.将一个下三角矩阵A[1..100,1..100]按行优先存入一维数组B[1..n]中，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=7992.假设二维数组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=12763.假设按低下标优先存储整数数组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）*44.按行优先顺序和按列优先顺序分别列出四维数组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，数据结构课后练习题第5章数组与广义表4/5北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-11]存于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为广义表的存储结构图，写出各图的广义表。六、设计题数据结构课后练习题第5章数组与广义表5/5北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-11.对于二维数组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的所有马鞍点，并分析算法的时间复杂度。