一、單項選擇（每空2分，共20分）

　　1、若某線性表中更常用的操作是在更后一個元素之前插入和刪除元素，則采用___________更節省運算時間。

　　A、單鏈表

　　B、僅有頭指針的單循環鏈表

　　C、僅有尾指針的單循環鏈表

　　D、雙鏈表

　　2、哈夫曼樹的帶權路徑長度WPL等于___________.

　　A、除根以外的所有結點的權植之和

　　B、所有結點權值之和

　　C、各葉子結點的帶權路徑長度之和

　　D、根結點的值

　　3、設輸入序列為1，2，3，4，5，借助一個棧不可能得到的輸出序列是___________.

　　A、1，2，3，4，5

　　B、1，4，3，2，5

　　C、4，1，3，2，5

　　D、1，3，2，5，4

　　4、對于下面二叉樹，按后序遍歷所得的結點序列為___________.

　　A、1234567

　　B、1245367

　　C、4251637

　　D、4526731

　　5、棧和隊列都是___________.

　　A、順序存儲的線性結構

　　B、鏈式存儲的線性結構

　　C、限制存儲點的線性結構

　　D、限制存儲點的非線性結構

　　6、已知完全二叉樹有30個結點，則整個二叉樹有___________個度為1的結點。

　　A、0

　　B、1

　　C、2

　　D、不確定

　　7、對下圖，不能得到的拓撲序列是___________.

　　A、1，2，3，4，5，6，7，8

　　B、1，5，2，6，3，7，4，8

　　C、1，2，5，6，3，4，7，8

　　D、1，2，3，4，8，7，6，5

　　8、下列排序算法中，第一趟排序完畢后，其更大或更小元一定在其更終位置上的算法是___________.

　　A、歸并排序

　　B、直接選擇排序

　　C、快速排序

　　D、基數排序

　　9、下列排序方法中，排序所花費時間不受數據初始排列特性影響的算法是___________.

　　A、直接插入排序

　　B、冒泡排序

　　C、直接選擇排序

　　D、快速排序

　　10、下列排序方法中，更好情況下，時間復雜度為O（N）的算法是___________.

　　A、選擇排序

　　B、歸并排序

　　C、快速排序

　　D、直接插入排序

　　二、判斷題（每小題1分，共10分）

　　（ ）1、線性表的長度是線性表占用的存儲空間的大小。

　　（ ）2、雙循環鏈表中，任一結點的后繼指針均指向其邏輯后繼。

　　（ ）3、隊列只能采用鏈式存儲方式。

　　（ ）4、樹（或森林）轉化為對應的二叉樹后，兩者的分支數相等。

　　（ ）5、由二叉樹的先序序列和中序序列能唯一確定一棵二叉樹。

　　（ ）6、圖中一個頂點i的出度等于其鄰接矩陣中第i列的非0元個數。

　　（ ）7、在用線性探查法解決沖突所構造的閉散列表中，每組同義詞中至少有一個元素的地址正好等于其散列地址。

　　（ ）8、所謂沖突即是兩個關鍵字的值相同的元素，其散列地址相同。

　　（ ）9、對n個元素的有序表用快速排序方法進行排序，時間復雜是O（n2）。

　　（ ）10、存在有偶數個結點的滿二叉樹。

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

　　1、在單鏈表中，若要刪除指針P所指結點的后繼結點，則需執行下列三條語句： U：=P↑。next；P↑。next：=U↑。next；___________.

　　2、設有一個鏈隊列，結點結構為：隊尾指針為Ls（≠nil），則執行入隊操作時， S↑。next：=Ls↑。next；___________；___________.

　　3、單鏈表中指針P所指結點不為尾結點的條件是___________. 4、設數組B[1……4，1……5]中的任一元素均占3個單元，從首地址SA開始把數組B按行優先存儲， 則元素B[3，4]的地址為___________. 5、在有n（n>0）個結點的二叉鏈表中，非空鏈域的個數為___________. 6、深度為6（根的層次號為i）的完全二叉樹至多有___________個結點。

　　7、一個具有n個頂點的連通有向圖至多有___________條邊。

　　8、一棵二叉排序樹中若存在30個結點其成功的查找長度≤6，則有___________個結點其成功的查找長度=4. 9、在對有10個數據的有序表作二分查找時，有___________個結點的查找長度是4. 10、在完全二叉樹中，編號為i的結點的左孩子結點的編號為___________.

　　四、解答下列各題（共30分）

　　1、 以數據集{3，4，5，8，12，18，20，30}為葉子結點的權值，（1）構造一棵哈夫曼樹　（4分）

　　（2）計算其帶權路徑長度（2分）。

　　2、已知二叉樹的先序、中序和后序序列分別如下，但其中有一些已模糊不清，構造出該二叉樹（6分）

　　先序序列　_BC_EF__中序序列　BDE_AG_H后序序列　_DC_GH_A

　　3、如圖所示

　　（1）寫出鄰接矩陣（2分）

　　（2）求出其更小生成樹（4分）

　　4、設散列函數H（X）=K MOD 7，若輸入序列為 {100，90，120，60，78，35，42，31，15，20，22，12，16，27}，求：（1）構造出開散列表。

　　（2）求出在等概率查找情況下查找成功的平均查找長度。

　　5、有一個數據序列：25，50，70，100，43，7，12.現采用堆排序算法進行排序，寫出每趟的結果。

　　五、算法設計題：（共20分）

　　1、設計一個用帶頭結點的單鏈表表示的直接插入排序算法，各結點結構如圖：

　　要求：用類PASCAL語言寫出算法（10分）

　　2、設二叉樹采用二叉鏈表表示，各結點結構為：其中data為整數型字段。設計算法判別一棵二叉樹是否是二叉排序樹。（10分）