高等教育自學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料

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

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

A、單鏈表

B、僅有頭指針的單循環(huán)鏈表

C、僅有尾指針的單循環(huán)鏈表

D、雙鏈表

2、哈夫曼樹的帶權(quán)路徑長度WPL等于___________.

A、除根以外的所有結(jié)點的權(quán)植之和

B、所有結(jié)點權(quán)值之和

C、各葉子結(jié)點的帶權(quán)路徑長度之和

D、根結(jié)點的值

3、設(shè)輸入序列為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、對于下面二叉樹，按后序遍歷所得的結(jié)點序列為___________.

A、1234567

B、1245367

C、4251637

D、4526731

5、棧和隊列都是___________.

A、順序存儲的線性結(jié)構(gòu)

B、鏈式存儲的線性結(jié)構(gòu)

C、限制存儲點的線性結(jié)構(gòu)

D、限制存儲點的非線性結(jié)構(gòu)

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

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、基數(shù)排序

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

A、直接插入排序

B、冒泡排序

C、直接選擇排序

D、快速排序

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

A、選擇排序

B、歸并排序

C、快速排序

D、直接插入排序

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

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

（ ）2、雙循環(huán)鏈表中，任一結(jié)點的后繼指針均指向其邏輯后繼。

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

（ ）4、樹（或森林）轉(zhuǎn)化為對應(yīng)的二叉樹后，兩者的分支數(shù)相等。

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

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

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

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

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

（ ）10、存在有偶數(shù)個結(jié)點的滿二叉樹。

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

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

2、設(shè)有一個鏈隊列，結(jié)點結(jié)構(gòu)為：隊尾指針為Ls（≠nil），則執(zhí)行入隊操作時， S↑。next：=Ls↑。next；___________；___________.

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

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

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

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

1、 以數(shù)據(jù)集{3，4，5，8，12，18，20，30}為葉子結(jié)點的權(quán)值，（1）構(gòu)造一棵哈夫曼樹 （4分）

（2）計算其帶權(quán)路徑長度（2分）。

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

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

3、如圖所示

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

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

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

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

5、有一個數(shù)據(jù)序列：25，50，70，100，43，7，12.現(xiàn)采用堆排序算法進行排序，寫出每趟的結(jié)果。

五、算法設(shè)計題：（共20分）

1、設(shè)計一個用帶頭結(jié)點的單鏈表表示的直接插入排序算法，各結(jié)點結(jié)構(gòu)如圖：

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

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