1999年上半年北京數(shù)據(jù)結(jié)構(gòu)試卷

　　一、判斷題（正確的在題后括號內(nèi)劃“√”，錯誤的劃“×”。每小題1分，共 5分）

　　1. AVL樹的任何子樹都是AVL樹。（ ）

　　2. 用相鄰矩陣表示圖所用的存儲空間大小與圖的邊數(shù)成正比。（ ）

　　3. 霍夫曼樹一定是滿二叉樹。（ ）

　　4. 棧是一種線性結(jié)構(gòu)。（ ）

　　5. B＋樹既適于隨機檢索，也適于順序檢索。（ ）

　　二、 單項選擇題（在每小題的四個備選答案中，選出一個正確的答案，并將其號碼填在題干后的括號內(nèi)。每小題2分，共10分）

　　1. 一個二叉樹的前序周游序列為ABCDEFG，它的對稱序周游序列可能是（ ）

　　A. CABDEFG
　　B. ABCDEFG
　　C. DACEFBG
　　D. EABCDFG

　　2. 高度為h的滿二叉樹（僅含根結(jié)點的二叉樹高度為零）的結(jié)點最少是多少（ ）

　　A. h＋1
　　B. 2h＋1
　　C. 2h+1－1
　　D. 2h

　　3. 對包含n個關(guān)鍵碼的散列表進行檢索，平均檢索長度是（ ）

　　A. O( log2n )
　　B. O( n )
　　C. O(n log2n )
　　D. 不直接依賴于n

　　4. 設(shè)有關(guān)鍵碼初始序列{ Q,H,C,Y,P,A,M,S,R,D,F,X}，新序列{F,H,C,D,P,A,M,Q,R,S,Y,X}是采用下列哪種排序方法對初始序列進行第一趟掃描的結(jié)果？

　　A. 直接插入排序
　　B. 二路歸并排序
　　C. 以第一元素為分界元素的快速排序
　　D. 基數(shù)排序

　　5. 下列說法中錯誤的是

　　A. n個結(jié)點的樹的各結(jié)點度數(shù)之和為n-1
　　B. n個結(jié)點的無向圖最多有n*(n-1)條邊
　　C. 用相鄰矩陣存儲圖時所需存儲空間大小與圖的結(jié)點數(shù)有關(guān)，而與邊數(shù)無關(guān)
　　D. 散列表中碰撞的可能性大小與負載因子有關(guān)

　　三、填空題（每空2分，共16分）

　　1. 下面字符樹包含___________個關(guān)鍵字。
　　　　　　
　　2. 用可擴充散列組織文件時，若目錄深度為d，指向某葉頁的指針為n個，則該葉頁的局部深度為_________。

　　3. 含有3個2度結(jié)點和4個葉結(jié)點的二叉樹可含___________個1度結(jié)點。

　　4. 含有2的n次方個結(jié)點的二叉樹高度至少是________，至多是________（僅含根結(jié)點的二叉樹高度為零）。

　　5. 用起泡法對n個關(guān)鍵碼排序，在最好情況下，只需做___次比較和___次移動；在最壞的情況下要做____次比較。

　　四、求解下列問題（每小題9分，共45分）

　　1. 在一個空AVL樹內(nèi)，依次插入關(guān)鍵字10，20，30，40，50，60分別畫出10，20，30插入完和所有關(guān)鍵字都插入完的AVL樹。

　　2. 設(shè)有3階B＋樹如下所示：
　　　　　　　　　
　　畫出插入關(guān)鍵字50后的B＋樹。

　　3. 設(shè)有6*6的稀疏矩陣如下所示，若用帶輔助行向量的二元組表示法存儲該矩陣，請給出輔助行向量及二元組，并說明如何確定A[ i, j ]的值（1≤i, j≤6）。
　　　　　　　

　　4. 請畫出下面廣義表相應(yīng)的加入表頭結(jié)點的單鏈表表示，D(A(x,y,L(a,b))，B(z,A(x,y,L(a,b))))。

　　5. 試給出下面事件結(jié)點網(wǎng)絡(luò)中的所有關(guān)鍵路徑和關(guān)鍵活動，并指出哪些關(guān)鍵活動提前完成可導(dǎo)致整個工程提前完成？
　　
　　五、算法題（10分）

　　設(shè)有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實現(xiàn)了對二叉排序樹的一種運算；
　　（1） 試說明unknown的功能
　�。�2） 若root是pointer型變量，且root指向如下二叉樹的根結(jié)點，試畫出執(zhí)行完unknown(root,‘X’);后root指向的二叉樹。
　　　　　　　　

　　六、算法填空和分析（共14分）

　　下面是用PASCAL語言描述的拓撲排序算法，圖用相鄰矩陣表示，存儲在adj內(nèi)；過程degree用于計算出各結(jié)點的入度（用負數(shù)表示，如用-2表示入度為2）并存于indegree內(nèi)。
　　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分）