北邮数据结构1997.doc

文档介绍：北京邮电大学97考研题
注意事项:
解答试卷应字迹清楚,语以确切画图工整;
算法题应写明算法思想并对主要数据的类型、变量加以说明,算法力求结构清晰简明易懂,并加必要的注释;
算法用类PASCAL语言编写,也可用你熟悉的语言编写,但要注明语种;
答题纸上。
一、有递归算法如下: (10分)
FUNCION sum (n:integer):intger;
BEGIN
IF n=0 THEN sum:=0
ELSE BEGIN
READ (x);
sum:=sum(n-1)+x
END;
END;
设初值n=4,读入 x=4,9,6,2
问:1 若为局部变量时;该函数递归结束后返回调用程序的并画出在递归过程中栈状态的变化过程;
2 若x为全程变量递归结束时返回调用程序的sum=?
二、写出下面算法中带标号语句的频度。(10分)
TYPE AR=ARRY[1…n] OF datatype;
PROCEDURE perm ( a: AR; k, n: integer);
var x: datatype; i:integer;
begin
① if k=n
then begin
② for i:=1 to n do
③ write (a[i])
writeln;
end;
else begin
④ for i:=k to n do’
⑤ a[i]:=a[i]+i*i;
⑥ perm (a, k+1, n);
end
end;
设k的初值等于1。
三、已知模式串t=’a b c a a b b a b c a b’写出用KMP法求得的每个字符对应的next和
nextval函数值。(10分)
四、写出或画出下面两题的结果:(10分)
归并段长度为9,4,7,3,8,6,15试画出3路平衡最佳归并树。
有二叉树中序序列为:A B C E F G H D
后序序列为:A B F H G E D C
请画出此二叉树。
五、求解下面有向图的有关问题:(15分)
1 判断此有向图是否有强连通分量?若有请画出;
data
firstin
firstout
2 画出此有向图的十字链表存储结构;其顶点表结点为:

data ------顶点的有关信息;
firstin------指向一该顶点为弧头的第一条边的指针;
firstout-------指向一该顶点为弧尾的第一条边的指针,
其表结点的结构为:
tailvex
headvex
weight
hlink
tlink
tailvex,headvex-------分别为弧尾和弧头在图中的序号;
weight---------弧上的权值;
hlink,tlink--------分别为指向弧头相同和弧尾相同的下一条边的指针。
3 设其顶点a, b, c, d, e表示一个乡的5个村庄,弧上的权值表示为两村之间的距离;
求每个村庄到其他村庄的最短距离;
乡内要建立一所医院,问医院设在哪个村庄才能使各村离医院的距离较近。
六