文档介绍：北京邮电大学96考研题
解题要求:
1试卷回答应字迹清楚,语意正确。
2 算法题应说明算法的基本思想,并对主要数据类型及变量加以说明,算法力求结构清析,简明易懂,应加以必要的注释。
3 算法可用类pascal语言编写,也可用你熟悉的高级语言编写,但应说明是哪一种语言。
。(共15分)
⑴假设高度为H的二叉树上只有度为0和度为2的结点,问此类二叉树的结点数可能达到的最大值和最小值各为多少? (4分)
⑵分析下面排序算法中各带标号语句的频度及此算法的时间复杂度,并指出此算法是属于哪一种排序法。(7分)
PROCEDURE sort (VAR a: ARRAY [1..n] OF integer);
BEGIN
1 FOR i:=1 TO n-1 DO
[2 j:=i;
3 FOR k:=j+1 TO n DO
4 IF a[k]<a[j] THEN j:=k;
4 t:=a[i]; a[i]:=a[j]; a[j];=t
]
END;
⑶全国有10000人参加物理竞赛,只录取成绩优异的前10名,并将他们从高分到低分输出。而对落选的其他考生,不须排出名次,问此种情况下,用何种排序方法速度最快?为什(4分)
二. 下图所示的伙伴系统中,回收两块首地址分别为768及128,大小为的存储块,
请画出回收后该伙伴系统的状态图。(10分)
三. 有如下递归算法:
FUNCTION sum( n:integer):integer;
BEGIN
IF n=0 THEN sum:=0
ELSE [read(x); {x为整型变量}
sum:=sum(n-1)+x
]
END;
设n初值为4,读入x=4, 9, 6, 2.
问:(1)若x为局部变量时,该函数递归结束后返回调用程序的sum=?
(2)若x为全局变量时,该函数递归结束后返回调用程序的sum=?
,用适当的语句填入下面算法的中:
问题:设有n件物品,重量分别为w1,w2,w3,…wn和一个能装载总重量为T的背包。能否从n件物品中选择若干件恰好使它们的重量之和等于T。若能,则背包问题有解,否则无解解此问题的算法如下: (10分)
FUNCTION kaup---stack(var stack, w :ARRAY[1…n] of real;
var top:integer; T:real):boolean;
{w[1..n] 存放n件物品的重量,依次从中取出物品放入背包中检查背包的重量,若不超过T,则弃之,取下一个物品试之。若有解则返回函数之true,否则返回false}
BEGIN
top:=0; i:=1; { i指示待选物品}
WHILE ane do
[IF or and (i<n)
THEN [top := ;stack[top] :=i;{第i件物品装入背包}
T:=T-w[i]];
IF T=0
THEN RETURN ( ) {背包问题有解}
ELSE [IF (i=n ) and (top>0)
THEN [i:= ;{取出栈顶物品}
top:= ;
T:= ]; {恢复T值}
i:=i+1 {准备挑选下一件物品}