北邮数据结构1996.docVIP

北京邮电大学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. 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 (in) THEN [top := ;stack[top] :=i;{第i件物品装入背包} T:=T-w[i]]; IF T=0 THEN RETURN ( ) {背包问题有解} ELSE [IF (i=n ) and (top0) THEN [i:= ;{取出栈顶物品} top:= ; T:= ]; {恢复T值} i:=i+1 {准备挑选下一件物品} ]; ]; RETURN( ) {背包无解} END; 五．按下面要求解图2中二叉树的有关问题：（10分） 对此二叉树进行后续后继线索化 ，（3分） 将此二叉树变换为森林（4分）