北京邮电大学 1996-1999年硕士研究生入学考试试题.doc

《北京邮电大学 1996-1999年硕士研究生入学考试试题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、北京邮电大学96考研题解题要求：1试卷回答应字迹清楚，语意正确。2算法题应说明算法的基本思想，并对主要数据类型及变量加以说明，算法力求结构清析，简明易懂，应加以必要的注释。3算法可用类pascal语言编写，也可用你熟悉的高级语言编写，但应说明是哪一种语言。一．回答下列问题。（共15分）⑴假设高度为H的二叉树上只有度为0和度为2的结点，问此类二叉树的结点数可能达到的最大值和最小值各为多少？（4分）⑵分析下面排序算法中各带标号语句的频度及此算法的时间复杂度，并指出此算法是属于哪一种排序法。（7分）PROCEDUREsort(VARa:ARRAY[1..n]OFinteger)

2、;BEGIN1FORi:=1TOn-1DO[2j:=i;3FORk:=j+1TOnDO4IFa[k]

3、n=0THENsum:=0ELSE[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分）FUNCTIONkaup---stack(varstack

4、,w:ARRAY[1…n]ofreal;vartop:integer;T:real):boolean;{w[1..n]存放n件物品的重量，依次从中取出物品放入背包中检查背包的重量，若不超过T，则弃之，取下一个物品试之。若有解则返回函数之true,否则返回false}BEGINtop:=0;i:=1;{i指示待选物品}WHILEanedo[IForand(i0)THEN[i:=;{取出栈

5、顶物品}top:=;T:=];{恢复T值}i:=i+1{准备挑选下一件物品}];];RETURN(){背包无解}END;五．按下面要求解图2中二叉树的有关问题：（10分）（1）对此二叉树进行后续后继线索化，（3分）（2）将此二叉树变换为森林（4分）（1）用后根序遍历该森林，写出遍历的结点序列。（3分）六．已知有向网络的带权邻接矩阵如下：（共15分）1234561∞2015∞∞∞22∞∞∞10303∞4∞∞∞104∞∞∞∞∞∞5∞∞∞15∞∞6∞∞∞510∞（1）画出此有向网络（5分）；（2）以该邻接矩阵为存储结构，分别画出用深度优先和广度优先搜索法得到的生成树或生成森林。

6、（5分）（3）用DIJKSTRAL法求顶点到其它各顶点的最短路径及其长度，填入下表中（请找出路径长度递增的次序填入）。路始始点终点路径路径长度七.现有待查记录关键字序列为：（40，25，53，17，48，98，87，90）求（1）建立二叉排序树，并求出在等概率的情况下查找成功时的平均查找长度。（5分）（2）此树是否为二叉平衡树？若不是，请调整为二叉平衡树。（5分）八．写出算法，求出中序线索二叉树中结合给定值为x的结点之后继结点，返回该后继结点的指针。（20分）线索树中结点结构如图3所示‘Ltaglcdatarcrtag（图3）图中data——存放结点的值lc，rc——为指

7、向左，右孩子或该结点前驱或后继的指针lyag，rtag——为标志域，各值为：0，则lc，rc为指向左，右孩子的指针;1，则lc，rc为指向某前驱后继结点的指针.北京邮电大学97考研题注意事项：1、解答试卷应字迹清楚，语以确切画图工整；2、算法题应写明算法思想并对主要数据的类型、变量加以说明，算法力求结构清晰简明易懂，并加必要的注释；3、算法用类PASCAL语言编写，也可用你熟悉的语言编写，但要注明语种；4、答题纸上。一、有递归算法如下：（10分）FUNCIONsum(n:integer):intger;BEGINIFn=0TH