第五章数组和广义表。
一、选择题
二、判断题。
部分答案解释如下。
1. 错误。对于完全二叉树，用一维数组作存储结构是效率高的（存储密度大）。
4. 错误。数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。因此，可以说数祖是元素值和下标构成的偶对的有穷集合。
5. 错误。数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。
6. 错误。稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。
8. 错误。广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是原子。
9. 错误。广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。
10. 错误。广义表中元素可以是原子，也可以是表（包括空表和非空表）。
11. 错误。广义表的表尾，指去掉表头元素后，剩余元素所组成的表。
三、填空题。
1. 顺序存储结构 2.（1）9572（2）1228 3.（1）9174（2）8788 4. 1100
5. 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) (1<=i,j<=n)
15. 非零元很少(t<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. 9319. i(i-1)/2+j20. 线性表21. 其余元素组成的表。
22. （1） 原子（单元素）是结构上不可再分的，可以是一个数或一个结构；而表带结构，本质就是广义表，因作为广义表的元素故称为子表。
2）大写字母 （3）小写字母 （4）表中元素的个数（5）表展开后所含括号的层数。
23. 深度24.（1）（）2）（（3）2 （4）2
25. head（head（tail（tail（head（tail（tail（a）））
26. 表展开后所含括号的层数 27.（1）5 （2）3
28. 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<=m
36.（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，则在low到i-1间去找，直到找到i=k为止。
37.逆置广义表的递归模型如下。
f(ls)=
上面append(a,b)功能是将广义表a和b作为元素的广义表连接起来。
1）(p->tag==0处理原子。
2）h=reverse(p-> 处理表头。
3）(p->产生表尾的逆置广义表。
4）s->连接。
5）q->头结点指向广义表。
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) mod i //计算出圈人s1
2）s1:=i若s1=0,说明是第i个人出圈（i%i=0）
3）s1 to i-1 //从s1到i依次前移，使人数减1，并将出圈人放到当前最后一个位置a[i]=w。
40. 若第n件物品能放入背包，则问题变为能否再从n-1件物品中选出若干件放入背包（这时背包可放入物品的重量变为s-w[n]）。若第n件物品不能放入背包，则考虑从n-1件物品选若干件放入背包（这时背包可放入物品仍为s）。
若最终s=0,则有一解；否则，若s<0或虽然s>0但物品数n<1,则无解。
1）s-w[n],n-1 //knap(s-w[n],n-1)=true
2）s,n-1knap←knap(s,n-1)
四、应用题。
三维数组以行为主序存储，其元素地址公式为：
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=3．每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。
1）242 （2）22 （3）s+182 （4）s+142
4．1784 (公式：loc(aijkl)=100(基地址)+[i-c1)v2v3v4+(j-c2)v3v4+(k-c3)v4+(l-c4)]*4
5. 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=1184
7. 五对角矩阵按行存储，元素在一维数组中下标（从1开始）k与i,j的关系如下：
k=a[15,16]是第71个元素，在向量[-10:m]中的存储位置是60 。
8．（1）540 （2）108 （3）i=3,j=10，即a[3,109． k=i(i-1)/2+j
10. 稀疏矩阵a有t个非零元素，加上行数mu、列数nu和非零元素个数tu(也算一个三元组)，共占用三元组表ltma的3(t+1)个存储单元，用二维数组存储时占用m*n个单元，只有当3(t+1) 安全教育作为一种专业知识，最初以师承传授形式出现，后来发展进入有关大学专业的课堂成为一门课程。在生产企业则成为新工人入门的教育，后来也成为企业领导培训的内容，甚至为此设立专门的培训班，在有关操作培训中也加进了此内容，其目的是提高有关人员的安全意识，增加其安全技术知识，强化其安全操作技能。所有这些均应... 新东方考研英语高分写作 作文模板很不错。2.2 复习计划。暑假前做基础版的阅读部分，重点不在做题，而是把每篇文章的单词，长句都弄明白，在文章中记单词，避免直接背单词书，暑假期间也就是7，8月份，做是珍藏版，根据各个题型重点突击，主要还是阅读和新题型，得阅读着得天下。9,10月份重点是真题的模拟，规定... 感谢凯程罗老师对本文的有益指导。辅导书很重要，英语是个积累的过程，关键在于单词量够不够，可以说单词不过关，其他都是免谈，想拿高分，真的很难。迈西背单词软件 5.1号开始做英语真题的，每做完一套都会把这套题的阅读理解背下来，说出来很多人可能不大相信，但我确实都背了！考前2周根据一些写作的模板，一篇一篇...广义安全教育的概念和目的 x
考研参考和计划
2019北大考研计划和考研心得