《考研数组和广义表答案》由会员分享，可在线阅读，更多相关《考研数组和广义表答案（22页珍藏版）》请在金锄头文库上搜索。
1、第五章 数组和广义表一、选择题 1.B2.1L2.2J2.3C2.4I2.5C3.B4.B5.A6.1H6.2C6.3E6.4A6.5F7.B8.1E8.2A8.3B9.B10.B11.B12.B13.A14.B15.B16.A17.C18.D19.C20.D21.F22.C23.D24.C25.A26.C27.A二、判断题1. 2.3.4.5.6. 7.8.9.10.11.12.13.14.部分答案解释如下。1. 错误。对于完全二叉树，用一维数组作存储结构是效率高的（存储密度大）。4. 错误。数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。因此，可以说数祖是元素值和下标构成的
2、偶对的有穷集合。5. 错误。数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。6. 错误。稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。 8. 错误。广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是原子。9. 错误。广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。10. 错误。广义表中元素可以是原子，也可以是表（包括空表和非空表）。11. 错误。广义表的表尾，指去掉表头元素后，剩余元素所组成的表。三、填空题1. 顺序存储结构 2.（1）9572（2）1228 3.（1）9174（2）8788 4. 1
3、1005. 1164 公式：LOC(aijk)=LOC(a000)+v2*v3*(i-c1)+v3*(j-c2)+(k-c3)*l (l为每个元素所占单元数)6. 232 7. 1340 8. 1196 9. 第1行第3列10. (1)270 (2)27 (3)2204 11. i(i-1)/2+j (1=i,j=n)12. (1)n(n+1)/2 (2)i(i+1)/2 (或j(j+1)/2) (3)i(i-1)/2+j (4)j(j-1)/2+i (1=i,j=n)13. 1038 三对角矩阵按行存储：k=2(i-1)+j (1=i,j=n) 14. 33 (k=i(i-1)/2+j) (
4、1=i,j=n) 15. 非零元很少(tm*n)且分布没有规律 16. 节省存储空间。 17. 上三角矩阵中，主对角线上第r(1rn) 行有n-r+1个元素，aij所在行的元素数是j-i+1。所以，元素在一维数组的下标k和二维数组下标关系:k=(i-1)*(2n-i+2)/2+(j-i+1)=(i-1)(2n-i)/2+j (ij)18. 93 19. i(i-1)/2+j 20. 线性表 21. 其余元素组成的表22. （1） 原子（单元素）是结构上不可再分的，可以是一个数或一个结构；而表带结构，本质就是广义表，因作为广义表的元素故称为子表。 （2）大写字母 （3）小写字母 （4）表中元素的
5、个数（5）表展开后所含括号的层数23. 深度 24.（1）（） （2）（） （3）2 （4）225. head（head（tail（tail（head（tail（tail（A）26. 表展开后所含括号的层数 27.（1）5 （2）328. head(head(tail(LS) 29. head(tail(tail(head(tail(head(A)30. head(tail(head(tail(H) 31. (b) 32. (x,y,z) 33. (d,e)34. GetHead(GetHead(GetTail(L)35. 本算法中，首先数组b中元素以逆置顺序放入d数组中，然后数组a和数组d的
6、元素比较，将大者拷贝到数组c。第一个WHILE循环到数组a或数组d结尾，第二个和第三个WHILE语句只能执行其中的一个。 （1）bm-i+1（2）x:=ai（3）i:=i+1（4）x:=dj（5）j:=j+1 （6）k:=k+1（7）i=l（8）j=m36.（1）(i=k) return（2）i+1（3）i-1（4）i!=k 本算法利用快速排序思想，找到第k个元素的位置（下标k-1因而开初有k-）。内层do循环以t(t=alow)为“枢轴”找到其应在i位置。这时若i等于k，则算法结束。（即第一个空格处if(i=k) return)。否则，若ik，则在low到i-1间去找，直到找到i=k为止。3
7、7.逆置广义表的递归模型如下 f(LS)=上面appEND(a,b)功能是将广义表a和b作为元素的广义表连接起来。（1）(p-tag=0) /处理原子（2）h=reverse(p-val.ptr.hp) /处理表头（3）(p-val.ptr.tp) /产生表尾的逆置广义表（4）s-val.ptr.tp=t; /连接（5）q-val.ptr.hp=h /头结点指向广义表38. 本题要求将1，2，.,n*n个自然数，按蛇型方式存放在二位数组Ann中。“蛇型”方式，即是按“副对角线”平行的各对角线，从左下到右上，再从右上到左下，存放n2个整数。对角线共2n-1条，在副对角线上方的对角线，题目中用k表
8、示第k条对角线（最左上角k=1），数组元素x和y方向坐标之和为k+1（即题目中的i+j=k+1）。副对角线下方第k条对角线与第2n-k条对角线对称，其元素的下标等于其对称元素的相应坐标各加(k-n)。（1）k=n /修改副对角线下方的下标i和j。（5）m+；或m=m+1 /为填下个数作准备，m变化范围1.n*n。本题解法的另一种思路见本章算法设计题第9题。39.本题难点有二：一是如何求下一出圈人的位置，二是某人出圈后对该人的位置如何处理。按题中要求，从第s个人开始报数，报到第m个人，此人出圈。n个人围成一圈，可看作环状，则下个出圈人，其位置是(s+m-1)%n。n是人数，是个变量，出圈一人减1
9、，算法中用i表示。对第二个问题，算法中用出圈人后面人的位置依次前移，并把出圈人的位置（下标）存放到当时最后一个人的位置（下标）。算法最后打印出圈人的顺序。（1）(s+m-1) MOD i /计算出圈人s1（2）s1:=i /若s1=0,说明是第i个人出圈（i%i=0）（3）s1 TO i-1 /从s1到i依次前移，使人数减1，并将出圈人放到当前最后一个位置Ai=w。40. 若第n件物品能放入背包，则问题变为能否再从n-1件物品中选出若干件放入背包（这时背包可放入物品的重量变为s-wn）。若第n件物品不能放入背包，则考虑从n-1件物品选若干件放入背包（这时背包可放入物品仍为s）。若最终s=0,则
10、有一解；否则，若s0但物品数n1,则无解。（1）s-wn,n-1 /Knap(s-wn,n-1)=true（2）s,n-1 / KnapKnap(s,n-1)四、应用题1、958 三维数组以行为主序存储，其元素地址公式为：LOC(Aijk)=LOC(Ac1c2c3)+(i-c1)V2V3+(j-c2)V3+(k-c3)*L+1其中ci,di是各维的下界和上界，Vi=di-ci+1是各维元素个数，L是一个元素所占的存储单元数。2. b对角矩阵的b条对角线，在主对角线上方和下方各有b/2条对角线(为叙述方便，下面设a=b/2)。从第1行至第a行，每行上的元素数依次是a+1,a+2,.,b-2,b-
11、1,最后的a行上的元素个数是 b-1，b-2,.,a+1。中间的(n-2a )行，每行元素个数都是b。故b条对角线上元素个数为 (n-2a)b+a*(a+b)。存放在一维数组V1.nb-a(b-a)中，其下标k与元素在二维数组中下标i和j的关系为： k=3每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。（1）242 （2）22 （3）s+182 （4）s+14241784 (公式：Loc(Aijkl)=100(基地址)+(i-c1)v2v3v4+(j-c2)v3v4+(k-c3)v4+(l-c4)*45. 1210+108L (LOC(A1,3,-2)=1
12、210+(k-c3)v2v1+(j-c2)v1+(i-c1)*L（设每个元素占L个存储单元）6. 数组占的存储字节数=10*9*7*4=2520；A5,0,7的存储地址=100+4*9*7+2*7+5*4=11847. 五对角矩阵按行存储，元素在一维数组中下标（从1开始）k与i,j的关系如下:k=A15,16是第71个元素，在向量-10:m中的存储位置是60 。8（1）540 （2）108 （3）i=3,j=10，即A3,10 9 k=i(i-1)/2+j10. 稀疏矩阵A有t个非零元素，加上行数mu、列数nu和非零元素个数tu(也算一个三元组)，共占用三元组表LTMA的3(t+1)个存储单元，用二维数组存储时占用m*n个单元，只有当3(t+1)m*n时，用LTMA表示A才有意义。解不等式得tm*n/3-1。11参见10。12. 题中矩阵非零元素用三元组表存储，查找某非零元素时，按常规要从第一个元素开始查找，属于顺序查找，时间复杂度为O(n)。若使查找时间得到改善，可以建立索引，将各行行号及各行第一个非零元素在数组B中的位置（下标）偶对放入一向量C中。若查找非零元素，可先在数组C中用折半查找到该非零元素的行号，并取出该行第一个非零元素在B中的位置，再到B中顺序（或折半）查找该元素，这时时间复杂度为O(logn)。13（1）176 （2）76和108 （3）28和1
