北京邮电大学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分）：
1、数据的逻辑结构与数据元素本身的形式和内容无关；
2、线性表的逻辑顺序总与其物理顺序一致；
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<<n）个数，起泡排序比直接选择排序要好。
三、以下表顺序建立平衡二叉排序树，并求在等概率情况下查找成功的平均查找长度。（10分）
(90,60,20,50,40,30,10,110,100,70,120,80)
四、用迪杰斯特拉（Dijkstra）算法求下图中V1顶点到其它各顶点的最短距离和最短路径，请写出求解过程。（5分）
</IMG>
五、算法（30分，每题10分）：
1、现有算法如下，求给定输入时的输出：
TYPE list=↑node;
node=Record
data :integer;
next:list
End;
PROC RDWRT;
H:=nil; Read(a);
While a>0 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的共同祖先，请在空格处填上相应的语句或表达式。
TYPE biptr=↑node;
node=Record
data :datatype;
lc，rc:biptr
End;
FUNC Forefather(t:biptr: e,e1,e2:integer):boolean;
f:=p1:=p2:=nil;
</IMG>
End
ENDP;
3、求以二叉链表表示的二叉树中叶子结点的个数，在求值过程中，将树中所有结点的左右子树重新调换：结点值大的子树作为右子树，空结点值最小，试写出算法。