考研数组和广义表答案.doc

《考研数组和广义表答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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.错误。对于完全二叉树，用一维数组作存储结构是效率高的（存储密度大）。

2、4.错误。数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。因此，可以说数祖是元素值和下标构成的偶对的有穷集合。5.错误。数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。6.错误。稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。8.错误。广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是原子。9.错误。广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。10.错误。广义表中元素可以是原子，也可以是表（

3、包括空表和非空表）。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(

4、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.非零元很少(t<

5、/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.表展开后所含括号

6、的层数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语句只能执行其

7、中的一个。（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，则在l

8、ow到i-1间去找，直到找到i=k为止。37.逆置广义表的递归模型如下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*