北京邮电大学C语言程序设计2003年硕士研究生入学考试试题.docxVIP

PAGE PAGE 1 北京邮电大学C语言程序设计 2003年硕士研究生入学考试试题 填空（20分，每空2分）： 1、5 个圆盘的Hanoi 塔，次小圆盘移到位时的步骤是第( )步； A. 16 B. 30 C. 31 D. 32 2、中缀表达式A*（B+C）/（D-E+F）的后缀表达式是( ) ； A. A*B+C/D-E+F B. AB*C+D/E-F+ C. ABC+*DE-+/ D . ABCDEF*+/-+ 3、广义表G=（a,b,(c,d,(e,f)),G）的长度为( ) ； A. 3 B. 4 C. 7 D. ∞ 4、对于有n个顶点e条边的连通图，其生成子图顶点和边的最小数目分别为_______ 和_________; A. 0 B. n C. n-1 D. e 5、含有4个元素值均不相同的结点的二叉排序树有_______ 种； A. 4 B. 6 C. 10 D. 14 6、有345个元素的有序表，等概率顺序查找成功的平均查找长度为________； A. 86 B. 172 C. 173 D. 345 7、一棵m阶非空B-树，每个结点最多有________棵子树；除根结点外，所有非终端结点最少有__________棵子树； A.┌m/2┐ B. m-1 C. m D. m +1 8、就平均时间而言，下列排序方法中_________最好。 A. 直接插入排序 B. 快速排序 C. 堆排序 D. 归并排序 判断对错（10分，每题1分）： 数据的逻辑结构与数据元素本身的形式和内容无关； 线性表的逻辑顺序总与其物理顺序一致； 字符串‘ababaab’的改进的失败函数nextval的值是‘0101011’； （10，21，43，39，22，45，48，201，49,46，99）是堆； 任何一个关键活动提前完成，则整个工程也会提前完成； 霍夫曼树的所有子树也均是霍夫曼树； 平衡二叉树（AVL树）的中序遍历值是递增的； 折半查找适用于所有的有序表； 理想情况下散列表等概率查找成功的平均查找长度是O（1）； 求n个数中最大的k（kn）个数，起泡排序比直接选择排序要好。 以下表顺序建立平衡二叉排序树，并求在等概率情况下查找成功的平均查找长度。（10分） (90,60,20,50,40,30,10,110,100,70,120,80) 用迪杰斯特拉（Dijkstra）算法求下图中V1顶点到其它各顶点的最短距离和最短路径，请写出求解过程。（5分） V1 5 1 V1 V5V2 V5 V2 1 1 3 1 2 3 2 V4V3 V4 V3 1 算法（30分，每题10分）： 现有算法如下，求给定输入时的输出： TYPE list=↑node; node=Record data :integer; next:list End; PROC RDWRT; H:=nil; Read(a); While a0 Do Begin New(P); P↑.data:=a; P↑.next:=H; H:=P; Read(a) End; Q:= P↑.next; While Q≠nil Do Begin R:=Q↑.next; IF R≠nil Then Begin Q↑.next:= R↑.next; R↑.next:=Q; P↑.next:=R; P:=Q; Q:= P↑.next; End Else Q:=nil End; P:=H; While P≠nil Do Begin Write(P↑.data,’ ’); P:=P↑.next End Endp; 输入为：1 2 3 4 5 6 7 8 9 10 0 2、已知以二叉链表表示的二叉树中有值为e、e1、e2的三个结点，下面的算法是判断e是否为e1和e2的共同祖先，请在空格处填上相应的语句或表达式。