文档介绍：北京邮电大学2002考研题
注意事项:
;
;
3 .算法应说明基本思路,应对主要数据类型, 变量出说明,所写算法应思路清晰简明易懂,应加必要注释。
,c语言等你所熟悉的高级语言编写,但要注明语种。
判断对错(10分,每题1分)
数据的逻辑结构是数据的各数据项之间的逻辑关系;
顺序存储方式插入和删除时效率太低,因此不如链式存储方式好;
栈和队列都是线性表,只是在插入和删除时受到了一些限制;
KMP算法的特点是在模式匹配时指示主串的指针不会变小;
二维以上的数组其实是一种特殊的广义表;
二叉树是树的特殊情形;
强连通分量是无向图的极大强连通子图;
查找相同结点的效率折半查找]总比顺序查找高;
归并排序在任何情况下都比所有简单排序速度快;
直接访问文件也能顺序访问,只是一般效率不高。
简答(10分,每题5分)
现有12个初始归并段,其记录数分别为:{30,44,8,6,3,20,60,18,9,62,68,85},现用3路平衡归并,画出最佳归并树;
长度为12的表{Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oxt,Nov,Dec},按此顺序建立一阶B_树,画出此B_树;
证明(10分)
对有向图的顶点适当的编号,可使其邻接矩阵为下三角形且组对角线为全0的充要条件使该图是无环图。
应用(2分,每题10)
已知一有向网的邻接矩阵如下,如需在其中一个结点建立娱乐中心,要求该结点距其它各结点的最长往返路程最短,相同条件下总的往返路程越短越好,问娱乐中心应选址何处?给出解题过程;v1 0 2 ∞∞∞ 3
v2 ∞ 0 3 2 ∞∞
v3 4 ∞ 0 ∞ 4 ∞
v4 1 ∞∞ 0 1 ∞
v5 ∞ 1 ∞∞ 0 3
v6 ∞∞ 2 5 ∞ 0
有一组关键字序列{15,92,124,5,27,28,18,6,36,34,30,26,32,259},将它们用散列函数H(key)=key mod 10 按顺序散列到哈希表HT(0:9)中,用链地址法解决冲突,画出最终的哈希表,并求在等概率情况下查找成功和不成功时的平均查找长度。
算法(50分,前两题各10分,后两题各15分)
现有算法及整数n和数组A如下,求数组C的值;
Var
A,B,C:Array[1..100] of integer;
FUNC AAA(s,t:integer):integer;
If s=t Then If B[s]=0 Then AAA:=r;Else AAA:=-s Else
Begin
L :=AAA(s,(s+t) Div 2);
R:=AAA((s+t) Div 2+1,t);
If i>0 Rhen AAA:=l Else AAA:=r;
If (r>0) And (A[l]>A[r]) Then AAA:=r
END
ENDF;
PROC BBB;
For I:=1 To n Do B[i]:=0;
For I:=1 To n Do B[AAA(1,n)]:=i;
For I:=1 To n Do C[B[i]]:=A[i];
ENDP;
初始值:n=