1999年上半年北京数据结构试卷

　　一、判断题（正确的在题后括号内划“√”，错误的划“×”。每小题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分）