第五章 数组和广义
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
一、选择
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
1.B
2.1L
2.2J
2.3C
2.4I
2.5C
3.B
4.B
5.A
6.1H
6.2C
6.3E
6.4A
6.5F
7.B
8.1E
8.2A
8.3B
9.B
10.B
11.B
12.B
13.A
14.B
15.B
16.A
17.C
18.D
19.C
20.D
21.F
22.C
23.D
24.C
25.A
26.C
27.A
二、判断题
1. ×
2.√
3.√
4.×
5.×
6. ×
7.√
8.×
9.×
10.×
11.×
12.√
13.√
14.√
部分
答案
八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案
解释如下。
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<
k，则在low到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*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。
本题解法的另一种思路见本章算法
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
题第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-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=
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,10] 9． k=i(i-1)/2+j
10. 稀疏矩阵A有t个非零元素，加上行数mu、列数nu和非零元素个数tu(也算一个三元组)，共占用三元组表LTMA的3(t+1)个存储单元，用二维数组存储时占用m*n个单元，只有当3(t+1)=j）。第1列有n个元素，第j列有n-j+1个元素，第1列到第j-1列是等腰梯形，元素数为(n+(n-j+2)(j-1)/2，而aij在第j列上的位置是为i-j+1。所以n阶下三角矩阵A按列存储，其元素aij在一维数组B中的存储位置k与i和j的关系为：
k=(n+(n-(j-1)+1)(j-1)/2+(i-j+1)=(2n-j)(j-1)/2+i
21．三对角矩阵第一行和最后一行各有两个非零元素，其余每行均有三个非零元素，所以共有3n-2个元素。
（1）主对角线左下对角线上的元素下标间有i=j+1关系，k与i和j的关系为k=3(i-1);主对角线上元素下标间有关系i=j，k与i和j的关系为k=3(i-1)+1; 主对角线右上那条对角线上元素下标间有关系i=j-1，k与i和j的关系为k=3(i-1)+2。综合以上三等式，有k=2(i-1)+j (1<=i,j<=n, |i-j|<=1)
（2）i=k/3+1；（1≤k≤3n-2） // k/3取小于k/3的最大整数。下同
j=k-2(i-1)=k-2(k/3)=k%3+k/3
22．这是一个递归调用问题，运行结果为：DBHEAIFJCKGL
23.（1）FOR循环中，每次执行PerfectShuffle(A,N)和CompareExchange(A,N)的结果：
第1次：A[1..8]=[90,30,85,65,50,80,10,100]
A[1..8]=[30,90,65,85,50,80,10,100]
第2次：A[1..8]=[30,50,90,80,65,10,85,100]
A[1..8]=[30,50,80,90,10,65,85,100]
第3次：A[1..8]=[30,10,50,65,80,85,90,100]
A[1..8]=[10,30,50,65,80,85,90,100]
（2）Demo的功能是将数组A中元素按递增顺序排序。
（3）PerfectShuffle 中WHILE循环内是赋值语句，共2N次，WHILE外成组赋值语句，相当2N个简单赋值语句；CompareExchange中WHILE循环内是交换语句，最好情况下不发生交换，最差情况下发生N次交换，相当于3N个赋值语句；Demo中FOR循环循环次数log22N，故按赋值语句次数计算Demo的时间复杂度为：最好情况：O(4N*log22N)≈O(Nlog(2*N))；最差情况：O((4N+3N)*log22N)≈O(Nlog(2*N))。
24. 这是一个排序程序。运行后B数组存放A数组各数在排序后的位置。结果是：
A={121,22,323,212,636,939,828,424,55,262}
B={3,1,6,4,8,10,9,7,2,5}
C={22,55,121,212,262,323,424,639,828,939}
25.（1）c=
（2）a=
26.（1）同上面26题（1）
（2）对c数组的赋值同所选择的下标i和j的次序（指外层循环用j内层用i）没有关系
（3）同上题26（2）
（4）对i,j下标取反序后，重复执行第（3）步，A数组所有元素均变为2。（在机器上验证，反复循环3次后，所有元素均变为2）
27．错误有以下几处：
（1）过程参数没有类型说明； （2）出错条件判断：缺少OR（i+k>last+1）；
（3）删除元素时FOR循环应正向，不应用反向DOWNTO； （4）count没定义；
低效体现在两处：
（1）删除k个元素时，不必一个一个元素前移，而应一次前移k个位置；
（2）last指针不应一次减1，而应最后一次减k。
正确的高效算法如下：
const m=64；
TYPE ARR=ARRAY[1..m] OF integer；
PROCEDURE delk（VAR A:ARR；VAR last:integer;i,k：integer）；
{从数组A[1..last]中删除第i个元素起的k个元素，m为A的上限}
VAR count：integer；
BEGIN
IF（i<0）OR（i>last）OR（k<0）OR（last>m）OR（i+k>last+1）
THEN write（’error’）
ELSE[FOR count：= i+k TO last DO A[count-k]：=A[count]；
last：=last-k；]
END；
28. 这是计数排序程序。
（a）c[i](1<=i<=n)中存放A数组中值为i的元素个数。
（b）c[i](1<=i<=n)中存放A数组中小于等于i的个数。
（c）B中存放排序结果，B[1..n]已经有序。
（d）算法中有4个并列for循环语句，算法的时间复杂度为O(n)。
29．上三角矩阵第一行有n个元素，第i-1行有n-（i-1）+1个元素，第一行到第i-1行是等腰梯形，而第i行上第j个元素（即aij）是第i行上第j-i+1个元素，故元素Aij在一维数组中的存储位置（下标k）为：
k=(n+(n-(i-1)+1))(i-1)/2+(j-i+1)=(2n-i+2)(i-1)/2+j-i+1
30．将上面29题的等式进一步整理为：
k=（n+1/2）i-i2/2+j-n，
则得f1（i）=（n+1/2）i-i2/2，f2（j）=j，c=-n。
31.（1）将对称矩阵对角线及以下元素按行序存入一维数组中，结果如下：
（2）因行列表头的“行列域”值用了0和0，下面十字链表中行和列下标均从1开始。
注：上侧列表头Hi和左侧行表头Hi是一个（即H1、H2、H3和H4），为了清楚，画成了两个。
32.（1）k=(2n-j+2)(j-1)/2+i-j+1 （当i≥j时，本题n=4）
k=(2n-i+2)(i-1)/2+j-i+1 （当ij, 1≤i，j≤n/2)；在中心元素后，其下标是k=2(i-1)(i<>j，n/2+1≤i，j≤n, 1<=k<=2n-1)。
（3）aij在B中的位置K=
36. 由于对称矩阵采用压缩存储，上三角矩阵第一列一个元素，第二列两个元素，第j列j个元素。上三角矩阵共有n (n+1)/2个元素。我们将这些元素存储到一个向量B[n(n+1)/2+1]中。可以看到B[k]和矩阵中的元素aij之间存在着一一对应关系：
则其对应关系可表示为：k=( 1<=i,j<=n, 1<=k<=n(n+1)/2)
int MAX(int x,int y)
{ return(x>y?x:y);
}
int MIN(int x,int y)
{ return(x
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
，第1列到第1个非零元素一定是转置后矩阵的三元组表中的第1个元素，第1列非零元素在第2列非零元素的前面。这种方法时间复杂度是O(n*P)，其中p是非零元素个数，当p和m*n同量级时，时间复杂度为O(n3)。
另一种转置方法称作快速转置，使时间复杂度降为O(m*n)。它是按稀疏矩阵三元组表中元素的顺序进行。按顺序取出一个元素，放到转置矩阵三元组表的相应位置。这就要求出每列非零元素个数和每列第一个非零元素在转置矩阵三元组表中的位置，设置了两个附加向量。
38. 广义表中的元素，可以是原子，也可以是子表，即广义表是原子或子表的有限序列，满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个成为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构。
39. 数组是具有相同性质的数据元素的集合，同时每个元素又有唯一下标限定，可以说数组是值和下标偶对的有限集合。n维数组中的每个元素，处于n个关系之中，每个关系都是线性的，且n维数组可以看作其元素是n-1维数组的一个线性表。而广义表与线性表的关系，见上面38题的解释。
40．线性表中的元素可以是各种各样的，但必须具有相同性质，属于同一数据对象。广义表中的元素可以是原子，也可以是子表。其它请参见38
41.（1）（c,d） （2）（b） （3）b （4）（f） （5）（）
42. Head（Tail（Head（Head（L1））））
Head（Head（Head（Tail（Head（Tail（L2））））））
类似本题的另外叙述的几个题解答如下：
（1）head（head（tail（tail（L）））），设L=（a，（c），b），（（（e））））
（2）head（head（head（head（tail（tail（L））））））
（3）head（tail（head（tail（A））））
（4）H（H（T（H（T（H（T（L）））））））
（5）tail（L）=（（（c,d）），（e,f））
head（tail（L））=（（c,d））
head（head（tail（L）））=（c,d）
tail（head（head（tail（L））））=（d）
head（tail（head（head（tail（L）））））=d
（6）head（tail（head（head（tail（tail（A））））））
43. 广义表的第一种存储结构的理论基础是，非空广义表可唯一分解成表头和表尾两部分，而由表头和表尾可唯一构成一个广义表。这种存储结构中，原子和表采用不同的结点结构（“异构”，即结点域个数不同）。
原子结点两个域：标志域tag=0表示原子结点，域DATA表示原子的值；子表结点三个域：tag=1表示子表，hp和tp分别是指向表头和表尾的指针。在画存储结构时，对非空广义表不断进行表头和表尾的分解，表头可以是原子，也可以是子表，而表尾一定是表（包括空表）。上面是本题的第一种存储结构图。
广义表的第二种存储结构的理论基础是，非空广义表最高层元素间具有逻辑关系：第一个元素无前驱有后继，最后一个元素无后继有前驱，其余元素有唯一前驱和唯一后继。有人将这种结构看作扩充线性结构。这种存储结构中，原子和表均采用三个域的结点结构（“同构”）。结点中都有一个指针域指向后继结点。原子结点中还包括标志域tag=0和原子值域DATA；子表结点还包括标志域tag=1和指向子表的指针hp。在画存储结构时，从左往右一个元素一个元素的画，直至最后一个元素。下面是本题的第二种存储结构图。
由于存储结构图占篇幅较大，下面这类题均不再解答。
44.深度为5，长度为2
45.（1）略
（2）表的长度为5，深度为4
（3）head（tail（head（head（head（tail（tail（tail（tail（A）））））））））
46.共享结构广义表A=（（（b,c），d），（a），（（a），（（b,c），d）），e，（））的存储表示：
47.（1）算法A的功能是逆置广义表p（即广义表由p指针所指）。逆置后的广义表由t指向。
（2）逆置后的广义表由t指向，这时p=nil。
48.（a,b） 49.（d）
50.否。广义表的长度不是广义表中原子个数，而是指广义表中所含元素的个数，广义表中的元素可以是原子，也可以是子表。广义表元素多于1个时，元素间用逗号分开。
51. p（x1 x2 x3）=2 x15 x22 x34+5 x15 x23 x33+3 x1 x24 x32+（x15 x23+ x2）x3+6
52.（1）H(A(a1,a2）,B(b1）,C(c1，c2）,x）
HEAD(TAIL(HEAD(H）））=a2
（2）略
五.算法设计题
1.[题目分析]本题是在向量D内插入元素问题。首先要查找插入位置，数据x插入到第i个数据组的末尾，即是第i+1个数据组的开始，而第i（1≤i≤n）个数据组的首地址由数组s（即数组元素s[i]）给出。其次，数据x插入后，还要维护数组s，以保持空间区D和数组s的正确的相互关系。
void Insert（int s[]，datatype D[]，x，int i,m）
//在m个元素的D数据区的第i个数据组末尾，插入新数据x，第i个数据组的首址由数组s给出。
｛if（i<１|| i>n）｛printf（“参数错误”）；exit（０）；｝
if（i==n） D[m]=x； // 在第n个数据组末尾插入元素。
else｛for（j=m-1;j>=s[i+1];j--）D[j+1]=D[j]; // 第i＋１个数据组及以后元素后移
D[s[i+1]]=x; // 将新数据x插入
for(j=i+1;j<=n;j++) s[j]++; // 维护空间区D和数组s的的关系。
} //结束元素插入
m++; //空间区D的数据元素个数增1。
}// 算法Insert结束
[算法讨论] 数据在空间区从下标0开始，最后一个元素的下标是m-1。设空间区容量足够大，未考虑空间溢出问题。数组s随机存数，而向量D数据插入，引起数组元素移动，时间复杂度是O（n）。
2. [题目分析]设稀疏矩阵的非零元素的三元组以行序为主存储在三元组表中。矩阵的相加是对应元素的相加。对两非零元素相加，若行号不等，则行号大者是结果矩阵中的非零元素。若行号相同，则列号大者是结果中一非零元素；若行号列号相同，若对应元素值之和为零，不予存储，否则，作为新三元组存到三元组表中。题目中要求时间复杂度为O（m+n）。因此需从两个三元组表的最后一个元素开始相加。第一个非零元素放在A矩阵三元组表的第m+n位置上。结果的三元组至多是m+n个非零元素。最后若发生对应元素相加和为零的情况，对三元组表中元素要进行整理，以便使第一个三元组存放在下标1的位置上。
CONST maxnum=大于非零元素数的某个常量
TYPE tuple=RECORD
i,j：integer； v：elemtp；
END；
sparmattp=RECORD
mu，nu，tu：integer；
data: ARRAY[1..maxnum] OF tuple；
END；
PROC AddMatrix（VAR A：sparmattp；B：sparmattp）；
// 稀疏矩阵A和B各有m和n个非零元素，以三元组表存储。A的空间足够大，本算法实现两个稀疏矩阵相加，结果放到A中。
L:=m；p:=n；k:=m+n；// L,p为A，B三元组表指针，k为结果三元组表指针（下标）。
A.tu:=m+n；// 暂存结果矩阵非零元素个数
WHILE（L≥1）AND（p≥1）DO
[CASE // 行号不等时，行号大者的三元组为结果三元组表中一项。
A.data[L].i>B.data[p].i：A.data[k]:=A.data[L]；L:=L-1；// A中当前项为结果项
A.data[L].iB.data[p].j：A.data[k]:=A.data[L]；L:=L-1；
A.data[L].j0 DO[A.data[k]:=B.data[p]；k:=k-1；p:=p-1；] //处理B的剩余部分。
WHILE L>1 DO[A.data[k]:=A.data[L]；k:=k-1；L:=L-1；] //处理A的剩余部分。
IF k>1 THEN //稀疏矩阵相应元素相加时，有和为零的元素，因而元素总数A[i][j]) min[i]=j; //修改第i行最小元素的列号.
}
for (i=0;il) {l=i-j+1;k=j;} //局部最长平台
i++; j=i; } //新平台起点
printf(“最长平台长度%d，在b数组中起始下标为%d”，l，k)；
}// Platform
8．[题目分析]矩阵中元素按行和按列都已排序，要求查找时间复杂度为O（m+n），因此不能采用常规的二层循环的查找。可以先从右上角（i=a,j=d）元素与x比较，只有三种情况：一是A[i,j]>x， 这情况下向j 小的方向继续查找；二是A[i,j]=c)
if(A[i][j]==x) {flag=1;break;}
else if (A[i][j]>x) j--; else i++;
if(flag) printf(“A[%d][%d]=%d”,i,j,x); //假定x为整型.
else printf(“矩阵A中无%d 元素”，x)；
}算法search结束。
[算法讨论]算法中查找x的路线从右上角开始，向下（当x>A[i,j]）或向左（当xn-1时，j=j+2，开始从左下向右上填数；而当j>n-1时i=i+2，开始从右上向左下的填数，直到n*n个数填完为止。
void Snake_Number(int A[n][n],int n)
//将自然数1..n*n,按”蛇形”填入n阶方阵A中.
{i=0; j=0; k=1; //i,j是矩阵元素的下标,k是要填入的自然数.
while(i-1) //从右上向左下填数,
{A[i][j]=k++; i++ ;j--;}
if((j<0)&&(i-1 && j=n) {printf(“参数错误\n ”);exit(0);}
if(k==0 || k==n) return(1);
浙公网安备 33021202002483