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

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

1、北京邮电大学2003年硕士研究生入学考试试题一、填空（20分，每空2分）：1、5个圆盘的Hanoi塔，次小圆盘移到位时的步骤是第()步；A.16B.30C.31D.322、中缀表达式A*（B+C）/（D-E+F）的后缀表达式是()；A.A*B+C/D-E+FB.AB*C+D/E-F+C.ABC+*DE-+/D.ABCDEF*+/-+3、广义表G=（a,b,(c,d,(e,f)),G）的长度为()；A.3B.4C.7D.∞4、对于有n个顶点e条边的连通图，其生成子图顶点和边的最小数目分别为_______和_________;A.0B.nC.n-1D.e5、含有4个元素值均不相同的结

2、点的二叉排序树有_______种；A.4B.6C.10D.146、有345个元素的有序表，等概率顺序查找成功的平均查找长度为________；A.86B.172C.173D.3457、一棵m阶非空B-树，每个结点最多有________棵子树；除根结点外，所有非终端结点最少有__________棵子树；A.┌m/2┐B.m-1C.mD.m+18、就平均时间而言，下列排序方法中_________最好。A.直接插入排序B.快速排序C.堆排序D.归并排序二、判断对错（10分，每题1分）：1、数据的逻辑结构与数据元素本身的形式和内容无关；2、线性表的逻辑顺序总与其物理顺序一致；3、字符串‘

3、ababaab’的改进的失败函数nextval的值是‘0101011’；4、（10，21，43，39，22，45，48，201，49,46，99）是堆；5、任何一个关键活动提前完成，则整个工程也会提前完成；6、霍夫曼树的所有子树也均是霍夫曼树；7、平衡二叉树（AVL树）的中序遍历值是递增的；8、折半查找适用于所有的有序表；9、理想情况下散列表等概率查找成功的平均查找长度是O（1）；10、求n个数中最大的k（k<

4、10,100,70,120,80)四、用迪杰斯特拉（Dijkstra）算法求下图中V1顶点到其它各顶点的最短距离和最短路径，请写出求解过程。（5分）V151V5V21131232V4V31一、算法（30分，每题10分）：1、现有算法如下，求给定输入时的输出：TYPElist=↑node;node=Recorddata:integer;next:listEnd;PROCRDWRT;H:=nil;Read(a);Whilea>0DoBeginNew(P);P↑.data:=a;P↑.next:=H;H:=P;Read(a)End;Q:=P↑.next;WhileQ≠nilDoBegi

5、nR:=Q↑.next;IFR≠nilThenBeginQ↑.next:=R↑.next;R↑.next:=Q;P↑.next:=R;P:=Q;Q:=P↑.next;EndElseQ:=nilEnd;P:=H;WhileP≠nilDoBeginWrite(P↑.data,’’);P:=P↑.nextEndEndp;输入为：1234567891002、已知以二叉链表表示的二叉树中有值为e、e1、e2的三个结点，下面的算法是判断e是否为e1和e2的共同祖先，请在空格处填上相应的语句或表达式。TYPEbiptr=↑node;node=Recorddata:datatype;lc，rc:

6、biptrEnd;FUNCForefather(t:biptr:e,e1,e2:integer):boolean;f:=p1:=p2:=nil;Search(t,f,e):S1;S2;S3IFS#ThenReturn(true);Return(false)ENDF;S4PROCSearch(t:biptr;Vars:biptr;e:datatype);IfAnd(s=nil)ThenBeginIft↑.data=eThens:=t;S5;Search(t↑.lc,s,e)EndENDP;3、求以二叉链表表示的二叉树中叶子结点的个数，在求值过程中，将树中所有结点的左右子树重新调换：

7、结点值大的子树作为右子树，空结点值最小，试写出算法。