一、判断题（正确的在题后括号内划“√”，错误的划“×”。每小题1分，共 5分）
1. AVL树的任何子树都是AVL树。（ ）
2. 用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（ ）
3. 霍夫曼树一定是满二叉树。（ ）
4. 栈是一种线性结构。（ ）
5. B＋树既适于随机检索，也适于顺序检索。（ ）
二、 单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在题干后的括号内。每小题2分，共10分）
1. 一个二叉树的前序周游序列为ABCDEFG，它的对称序周游序列可能是（ ）
A. CABDEFG
B. ABCDEFG
C. DACEFBG
D. EABCDFG
2. 高度为h的满二叉树（仅含根结点的二叉树高度为零）的结点最少是多少（ ）
A. h＋1
B. 2h＋1
C. 2h+1－1
D. 2h
3. 对包含n个关键码的散列表进行检索，平均检索长度是（ ）
A. O( log2n )
B. O( n )
C. O(n log2n )
D. 不直接依赖于n
4. 设有关键码初始序列{ Q,H,C,Y,P,A,M,S,R,D,F,X}，新序列{F,H,C,D,P,A,M,Q,R,S,Y,X}是采用下列哪种排序方法对初始序列进行第一趟扫描的结果？
A. 直接插入排序
B. 二路归并排序
C. 以第一元素为分界元素的快速排序
D. 基数排序
5. 下列说法中错误的是
A. n个结点的树的各结点度数之和为n-1
B. n个结点的无向图最多有n*(n-1)条边
C. 用相邻矩阵存储图时所需存储空间大小与图的结点数有关，而与边数无关
D. 散列表中碰撞的可能性大小与负载因子有关
三、填空题（每空2分，共16分）
1. 下面字符树包含___________个关键字。
2. 用可扩充散列组织文件时，若目录深度为d，指向某叶页的指针为n个，则该叶页的局部深度为_________。
3. 含有3个2度结点和4个叶结点的二叉树可含___________个1度结点。
4. 含有2的n次方个结点的二叉树高度至少是________，至多是________（仅含根结点的二叉树高度为零）。
5. 用起泡法对n个关键码排序，在最好情况下，只需做___次比较和___次移动；在最坏的情况下要做____次比较。
四、求解下列问题（每小题9分，共45分）
1. 在一个空AVL树内，依次插入关键字10，20，30，40，50，60分别画出10，20，30插入完和所有关键字都插入完的AVL树。
2. 设有3阶B＋树如下所示：
画出插入关键字50后的B＋树。
3. 设有6*6的稀疏矩阵如下所示，若用带辅助行向量的二元组表示法存储该矩阵，请给出辅助行向量及二元组，并说明如何确定A[ i, j ]的值（1≤i, j≤6）。
4. 请画出下面广义表相应的加入表头结点的单链表表示，D(A(x,y,L(a,b))，B(z,A(x,y,L(a,b))))。
5. 试给出下面事件结点网络中的所有关键路径和关键活动，并指出哪些关键活动提前完成可导致整个工程提前完成？
五、算法题（10分）
设有PASCAL说明如下：
type pointer =↑node;
node = record
info: char;
left, right: pointer
end;
procedure unknown (var p: pointer; ch: char);
begin
if p= nil then
begin
new (p);
p↑.info :=ch;
p↑.left :=nil;
p↑.right:=nil
end
else
if ch = p↑.info then
writeln (ch, ‘Exists in the binary tree!’)
else
if ord(ch) < ord(p↑.info) then
unknown (p↑.left, ch)
else
unknown (p↑.right, ch)
end;
过程unknown实现了对二叉排序树的一种运算；
（1） 试说明unknown的功能
（2） 若root是pointer型变量，且root指向如下二叉树的根结点，试画出执行完unknown(root,‘X’);后root指向的二叉树。
六、算法填空和分析（共14分）
下面是用PASCAL语言描述的拓扑排序算法，图用相邻矩阵表示，存储在adj内；过程degree用于计算出各结点的入度（用负数表示，如用-2表示入度为2）并存于indegree内。
const M =100;
var adj: array [1..M, 1..M] of integer;
n: integer;
indegree: array [1..M] of integer;
procedure degree (n: integer);
var i,j: integer;
begin
for i:=1 to n do
indegree [i] := 0 ;
for i:=1 to n do
for j :=1 to n do
if__________(1) then
indegree [j] := indegree [j] – 1;
end;
procedure sort (n: integer);
var count,i,s,sp,width: integer;
begin
sp :=0;
for i:=1 to n do
if___________（2）__________then
begin
ind
ind
ind
ind
indegree [i] :=sp;
end;
count :=0;
while sp>0 do
begin
s :=sp;
sp:=indegree[s];
count;=count+1;
if s<10 then width :=1
else
if s<100 then width :=2
else width :=3;
write (‘v’,s,‘ ’: 5-width);
for i:=1 to n do
if adj [s,i] =1 then
if indegree [i]<0 then
begin
___________(3)__________ ;
if indegree [i]=0 then
begin
indegree [i]:=sp;
____________(4)__________
end
end
end;
if_________(5)__________then
writeln( ‘The graph contains a cycle!’)
end;
(1)填写算法中空缺的语句或表达式；（10分）
(2)给出下图的所有拓扑序列。（4分）
