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

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

　　1.一個棧的輸入序列為1，2，3，4，下面哪一個序列不可能是這個棧的輸出序列？（ ）
　　A. 1，3，2，4　　B. 2，3，4，1 　　C. 4，3，1，2 　　D. 3，4，2，1

　　2.下列排序方法中，哪一種方法的比較次數(shù)與紀錄的初始排列狀態(tài)無關？（ ）
　　A. 直接插入排序 　　B. 起泡排序 　　C. 快速排序 　　D. 直接選擇排序

　　3.對n個記錄的文件進行二路歸并排序，總的時間代價為
　　A. O（nlog2n） 　　B. O（n2） 　　C. O（log2n） 　　D. O（n）

　　4.若一棵二叉樹具有10個度為2的結(jié)點，則該二叉樹的度為0的結(jié)點個數(shù)是（ ）
　　A. 9 　B. 11 　　C. 12　　D. 不確定

　　5.下面關于B樹和B+樹的敘述中，不正確的是
　　A. B樹和B+樹都是平衡的多分樹　　 　　B. B樹和B+樹都是可用于文件的索引結(jié)構(gòu)
　　C. B樹和B+樹都能有效地支持順序檢索 　D. B樹和B+樹都能有效地支持隨機檢索

　　二、 填空題（每空2分，共20分）

　　1.從邏輯結(jié)構(gòu)看，線性表是典型的 ，樹是典型的 。

　　2.設有二維數(shù)組A[0..9,0..19]，其每個元素占兩個字節(jié)，第一個元素的存儲地址為100，若按行優(yōu)先順序存儲，則元素A[6,6]的存儲地址為 ，按列優(yōu)順序存儲，元素A[6,6]的存儲地址為 。

　　3.若按層次順序?qū)⒁豢糜衝個結(jié)點的完全二叉樹的所有結(jié)點從1到n編號，那么當i為 且小于n時，結(jié)點I的右兄弟是結(jié)點 ，否則結(jié)點i沒有右兄弟。

　　4.求具有最小帶權外部路徑長度的擴充二叉樹的算法稱為 算法。堆排序中建堆的方法稱作 。

　　5.6階B樹中，每個結(jié)點至多包含 個關鍵碼，除根和葉結(jié)點外，每個結(jié)點至少包含 個關鍵碼。

　　三、 簡答題（每小題6分，共18分）

　　1.請簡述散列函數(shù)在散列法存儲中的作用，并舉出一個散列函數(shù)的例子。

　　2.請簡述散列法存儲中處理碰撞（沖突）的兩類基本方法。

　　3.請簡述負載因子的定義，為什么說負載因子是散列法存儲的一個重要參數(shù)？

　　四、 求解下列問題（每小題6分，共30分）

　　1.設待排序文件的關鍵碼為（512,275,908,677,503,765,612,897,154,170）以第一元素為分界元素進行快速排序（按關鍵碼值遞增順序），請給出一趟掃描后的結(jié)果。

　　2.請畫出下面的樹所對應的二叉樹。

　　3.從一棵空的二叉排序樹開始，將以下關鍵碼值依次插入：25,13,15,31,7,20,37，請畫出插入全部完成后的二叉排序樹。

　　4.請畫出下面帶權圖的一棵最小生成樹。

　　5.對于下面的稀疏矩陣

　　1）畫出其三元組法存儲表示。
　　2）畫出其行—列法（十字鏈表法）存儲表示。
　　　　　　　　　
　　五、 算法題（6分）
　　有一個鏈接方式存儲的線性表，表中每個結(jié)點包括兩個指針，其結(jié)點用PASCAL語言描述如下：
　　TYPE pointer=↑node;
　　node=RECORD
　　info:datatype;
　　link1,link2:pointer
　　END;
　　其中l(wèi)ink1是指向結(jié)點的下一個結(jié)點的指針，link2是指向結(jié)點的前一個結(jié)點的指針,如圖所示。
　　　　　　
　　p和q都是pointer類型的變量，現(xiàn)要將q所指的新結(jié)點插入表中p所指結(jié)點的前面（說明：p所指的不是鏈表的第一個結(jié)點）。請用PASCAL語句寫出該插入的關鍵步驟。（部要求寫完整的算法，只要求用幾個語句寫出關鍵步驟。）
　　
　　六、 算法填空和分析（共16分）
　　下面是用PASCAL語言編寫的二分值插入排序算法，該算法對排序碼為整數(shù)的線性表進行升序排序。
　　TYPE node=RECORD
　　key:integer;
　　info:datatype
　　End;
　　list=ARRAY[1..max] OF node;
　　PROCEDURE binarysort (VAR R: list; n: integer);
　　VAR temp :node ;
　　low,m,high,I,j: integer;
　　BEGIN
nteger;
　　BEGIN
nteger;
　　BEGIN
nteger;
　　BEGIN
　　FOR I:=2 TO n DO
　　BEGIN
　　temp := R[ i ];
　　low :=1; high := i-1;
　　WHILE ① DO
　　BEGIN
　　m :=(low+high) DIV 2;
　　IF ②
　　THEN high :=m-1
　　ELSE ③
　　END;
　　FOR j := i-1 DOWNTO ④ DO
　　R[j+1] := R[j];
　�、�
　　END;
　　END;

　　1.請將算法的空缺處應填入的正確內(nèi)容寫在下面。（10分）
　�、�
　�、�
　�、�
　�、�
　　⑤

　　2.設待排序的記錄數(shù)n=7，當排序碼的初始排列順序分別為（15,25,35,45,55,65,75）和（75,65,55,45,35,25,15）時，請說出排序過程中對排序碼所進行的總的比較次數(shù)分別是多少？（假定算法中取中項的整數(shù)除法采用小數(shù)截斷的方法。）（6分）