《数据结构》习题集：章-数组与广义表

1/6第5章数组与广义表一、选择题1.在以下讲述中，正确的是（B）。A、线性表的线性存储结构优于链表存储结构B、二维数组是其数据元素为线性表的线性表C、栈的操作方式是先进先出D、队列的操作方式是先进后出2.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（B）。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.常对数组进行的两种基本操作是（C）。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、D15.已知广义表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)))))2/616.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、散列和十字链表二、判断题1.数组是同类型值的集合。X2.数组的存储结构是一组连续的内存单元。V3.数组是一种复杂的数据结构，数组元素之间的关系，即不是线性的也不是树形的。X4.插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也会经常使用。X5.使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。V6.广义表是由零个或多个原子或子表所组成的有限序列，所以广义表可能为空表。V7.线性表可以看成是广义表的特例，如果广义表中的每个元素是原子，则广义表便成为线性表。V8.广义表中原子个数即为广义表的长度。X9.广义表中元素的个数即为广义表的深度。X三、填空题1.设a是含有N个分量的整数数组，则求该数组中最大整数的递归定义为（最大整数的递归定义为：f(k)=a[0](k=0时)||f(k)=max(f(k-1),a[k])(k0时)），最小整数的递归定义为（最小整数的递归定义为：f(k)=a[0](k=0时)||f(k)=min(f(k-1),a[k])(k0时)）。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])+(n*I+j)*k）。4.广义表的（深度）定义为广义表中括弧的重数。5.设广义表L=（（），（）），则Head(L)=（()）；Tail(L)=（(())）；L的长度是（2）；L的深度是（2）。6.广义表中的元素可以是（原子或子表），其描述宜采用程序设计语言中的（链表）表示。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.下三角矩阵A[1..N,1..N]的下三角元素已压缩到一维数组S[1..N*（N+1）/2+1]中，若按行序为主序存储，则A[I,j]对应的S中的存储位置是（）。3/612.已知一个稀疏矩阵为0000510000030200，则对应的三元组表表示为（）。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）。16.将一个下三角矩阵A[1..100,1..100]按行优先存入一维数组B[1..n]中，A中元素A[66,65]在B数组中的位置为（2210）。四、计算题1.数组A[8][6][9]以行主序存储，设第一个元素的首地址是54，每个元素的长度为5，求元素A[2][4][5]的存储地址。A[2][4][5]的存储地址为loc(2,4,5)=loc(0,0,0)+(2*6*9+4*9+5)*5=54+149*5=7992.假设二维数组A6x8，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的基地址为1000，计算：（1）数组A的体积（存储量）（2）A的最后一个元素第一个字节的地址（3）按行存储时，a14的第一个字节的地址（4）按列存储时，a47的第一个字节的地址。答案：（1）存储量=（6*8）*6=288（2）数组A的最后一个元素a57的地址：1000+288-6=1282（3）按行存储时，a14的地址：1000+（1*8+4）*6=1072（4）按列存储时，a47的地址：1000+（7*6+4）*6=12763.假设按低下标优先存储整数数组A9x3x5x8时，第一个元素的字节地址是100，每个整数占4个字节。问下列元素的存储地址是什么？（1）a0000100（2）a1111776（3）a31251784（4）a824744164.按行优先顺序和按列优先顺序分别列出四维数组A[2][2][2][2]所有元素在内存中的存储顺序。四维数组A的按行优先顺序在内存中的存储次序为：A0000、A0001、A0010、A0011、A0100、A0101、A0110、A0111、A1000、A1001、A1010、A1011、A1100、A1101、A1110、A1111；按列优先存储顺序为：A0000、A1000、A0100、A1100、A0010、A1010、A0110、A1110、A0001、A1001、A0101、A1101、A0011、A1011、A0111、A11115.一个n阶对称矩阵A采用一维数组S按行序为主序存放其上三角各元素，写出S[k]与A[i,j]的关系公式。设4/6A[1，1]存于S[1]中。k=(I-1)(2n-I+2)/2+j-I+1(I=j时)和k=(j-1)(2n-j+2)/2+I-j+1(Ij时)五、简答题1.什么是广义表，简述广义表与线性表的主要区别？广义表是线性表的推广，形式上定义为LS=(a1,a2,…,an)，ai可以是单个元素，也可以是广义表，并分别称为广义表的原子和子表。主要区别是：线性表中元素只能是单个元素，而广义表中元素可以是单个元素，也可以是广义表；线性表中各元素是独立的，而广义表中元素可以为其他表或子表共享，特别地，广义表可以是一个递归的表，即广义表也可以是其本身的一个子表。2.利用广义表的Head和Tail运算把原子student从下列广义表中分离出来。（1）L1=（soldier,teacher,student,worker,farmer）（2）L2=（soldier,(teacher,student),(worker,farmer)）Head(Tail(Tail(L1)))=studentHead(Tail(Head(Tail(L2))))=student3.画出下列广义表的存储结构图，并求它的深度。（1）((()),a,((b,c)),(((d))))（2）((((a),(b))),(((),d),(e,f)))5/64.已知图4.4为广义表的存储结构图，写出各图的广义表。解答：（1）((x,(y)),(((())),(),(z)))（2）(((a,b,()),()),(a,(b)),())六、设计题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的所有马鞍点，并分析算法的时间复杂度。6/6