第5章数组和广义表答案

第五章数组和广义表一、选择题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.错误。数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。因此，可以说数祖是元素值和下标构成的偶对的有穷集合。5.错误。数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。6.错误。稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。8.错误。广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是原子。9.错误。广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。10.错误。广义表中元素可以是原子，也可以是表（包括空表和非空表）。11.错误。广义表的表尾，指去掉表头元素后，剩余元素所组成的表。三、填空题1.顺序存储结构2.（1）9572（2）12283.（1）9174（2）87884.11005.1164公式：LOC(aijk)=LOC(a000)+[v2*v3*(i-c1)+v3*(j-c2)+(k-c3)]*l(l为每个元素所占单元数)6.2327.13408.11969.第1行第3列10.(1)270(2)27(3)220411.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)(1=i,j=n)15.非零元很少(tm*n)且分布没有规律16.节省存储空间。17.上三角矩阵中，主对角线上第r(1rn)行有n-r+1个元素，aij所在行的元素数是j-i+1。所以，元素在一维数组的下标k和二维数组下标关系:k=((i-1)*(2n-i+2))/2+(j-i+1)=(i-1)(2n-i)/2+j(ij)18.9319.i(i-1)/2+j20.线性表21.其余元素组成的表22.（1）原子（单元素）是结构上不可再分的，可以是一个数或一个结构；而表带结构，本质就是广义表，因作为广义表的元素故称为子表。（2）大写字母（3）小写字母（4）表中元素的个数（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的元素比较，将大者拷贝到数组c。第一个WHILE循环到数组a或数组d结尾，第二个和第三个WHILE语句只能执行其中的一个。（1）b[m-i+1]（2）x:=a[i]（3）i:=i+1（4）x:=d[j]（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=a[low])为“枢轴”找到其应在i位置。这时若i等于k，则算法结束。（即第一个空格处if(i==k)return)。否则，若ik，就在i+1至high中间去查；若ik，则在low到i-1间去找，直到找到i=k为止。37.逆置广义表的递归模型如下f(LS)=1tagS-))f(head(LS)ail(LS)),append(f(tnull)!val.ptr.tpLS-0tagS-head(LS))ail(LS)),append(f(ttail(LS)LSLSnullLLLS若，且若为空为原子，且若为空若上面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个自然数，按蛇型方式存放在二位数组A[n][n]中。“蛇型”方式，即是按“副对角线”平行的各对角线，从左下到右上，再从右上到左下，存放n2个整数。对角线共2n-1条，在副对角线上方的对角线，题目中用k表示第k条对角线（最左上角k=1），数组元素x和y方向坐标之和为k+1（即题目中的i+j=k+1）。副对角线下方第k条对角线与第2n-k条对角线对称，其元素的下标等于其对称元素的相应坐标各加(k-n)。（1）k=2*n-1//共填2*n-1条对角线（2）q=2*n-k//副对角线以下的各条对角线上的元素数（3）k%2！=0//k为偶数时从右上到左下，否则从左下向右上填数。（本处计算下标i和j）（4）k=n//修改副对角线下方的下标i和j。（5）m++；或m=m+1//为填下个数作准备，m变化范围1..n*n。本题解法的另一种思路见本章算法设计题第9题。39.本题难点有二：一是如何求下一出圈人的位置，二是某人出圈后对该人的位置如何处理。按题中要求，从第s个人开始报数，报到第m个人，此人出圈。n个人围成一圈，可看作环状，则下个出圈人，其位置是(s+m-1)%n。n是人数，是个变量，出圈一人减1，算法中用i表示。对第二个问题，算法中用出圈人后面人的位置依次前移，并把出圈人的位置（下标）存放到当时最后一个人的位置（下标）。算法最后打印出圈人的顺序。（1）(s+m-1)MODi//计算出圈人s1（2）s1:=i//若s1=0,说明是第i个人出圈（i%i=0）（3）s1TOi-1//从s1到i依次前移，使人数减1，并将出圈人放到当前最后一个位置A[i]=w。40.若第n件物品能放入背包，则问题变为能否再从n-1件物品中选出若干件放入背包（这时背包可放入物品的重量变为s-w[n]）。若第n件物品不能放入背包，则考虑从n-1件物品选若干件放入背包（这时背包可放入物品仍为s）。若最终s=0,则有一解；否则，若s0或虽然s0但物品数n1,则无解。（1）s-w[n],n-1//Knap(s-w[n],n-1)=true（2）s,n-1//Knap←Knap(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-1,最后的a行上的元素个数是b-1，b-2,...,a+1。中间的(n-2a)行，每行元素个数都是b。故b条对角线上元素个数为(n-2a)b+a*(a+b)。存放在一维数组V[1..nb-a(b-a)]中，其下标k与元素在二维数组中下标i和j的关系为：k=nianjanianiaiaaniajaiaaijaii12)1)(()2(11)2(112)2)(1当当当（3．每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。（1）242（2）22（3）s+182（4）s+1424．1784(公式：Loc(Aijkl)=100(基地址)+[(i-c1)v2v3v4+(j-c2)v3v4+(k-c3)v4+(l-c4)]*45.1210+108L(LOC(A[1,3,-2])=1210+[(k-c3)v2v1+(j-c2)v1+(i-c1)]*L（设每个元素占L个存储单元）6.数组占的存储字节数=10*9*7*4=2520；A[5,0,7]的存储地址=100+[4*9*7+2*7+5]*4=11847.五对角矩阵按行存储，元素在一维数组中下标（从1开始）k与i,j的关系如下:k=)ni(2j)1i(4)ni1(1j)1i(4)1i(j)1i(4时当时当时当A[15,16]是第71个元素，在向量[-10:m]中的存储位置是60。8．（1）540（2）108（3）i=3,j=10，即A[3,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和116。14．（1）k=3(i-1)(主对角线左下角，即i=j+1)k=3(i-1)+1(主对角线上，即i=j)k=3(i-1)+2(主对角线上，即i=j-1)由以上三式，得k=2(i-1)+j(1i,jn;1k3n-2)（2）103*103-(3*103-2)15.稀疏矩阵A采用二维数组存储时，需要n*n个存储单元，完成求Σaii(1=i=n)时，由于a[i][i]随机存取，速度快。但采用三元组表时，若非零元素个数为t，需3(t+1)个存储单元（第一个分量中存稀疏矩阵A的行数，列数和非零元素个数，以后t个分量存各非零元素的行值、列值、元素值），比二维数组节省存储单元；但在求Σaii(1=i=n)时，要扫描整个三元组表，以便找到行列值相等的非零元素求和，其时间性能比采用二维数组时差。16.特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元素分配单元（对值相同元素只分配一个单元），将非零元素存储在向量中，元素的下标i和j和该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小（tm*n），且分布没有规律。用十字链表作存储结构自然失去了随机存取的功能。即使用三元组表的顺序存储结构，存取下标为i和j的元素时，要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为O(1)，最差情况下是O(n)，因此也失去了随机存取的功能。17．一维数组属于特殊的顺序表，和有序表的差别主要在于有序表中元素按值排序（非递增或非递减），而一维数组中元素没有按元素值排列顺序的要求。18．n(