絕密★考試結(jié)束前

全國2013年10月高等教育自學(xué)考試

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題

課程代碼：02142

請考生按規(guī)定用筆將所有試題的答案涂、寫在答題紙上。

選擇題部分

注意事項：

1. 答題前，考生務(wù)必將自己的考試課程名稱、姓名、準(zhǔn)考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規(guī)定的位置上。

2. 每小題選出答案后，用2B鉛筆把答題紙上對應(yīng)題目的答案標(biāo)號涂黑。如需改動，用橡皮擦干凈后，再選涂其他答案標(biāo)號。不能答在試題卷上。

一、單項選擇題(本大題共15小題，每小題2分，共30分)

在每小題列出的四個備選項中只有一個是符合題目要求的，請將其選出并將“答題紙”的相應(yīng)代碼涂黑。錯涂、多涂或未涂均無分。

1．下列幾種算法時間復(fù)雜度中，最大的是

A.O（1） 

B.O（n）

C.O（nlog2n）

D.O（n2）

2．?dāng)?shù)據(jù)結(jié)構(gòu)中結(jié)點按邏輯關(guān)系依次排列形成一條“鏈”的結(jié)構(gòu)是

A．集合 B.圖結(jié)構(gòu)

C.樹形結(jié)構(gòu)

D.線性結(jié)構(gòu)

3．在表長為100的順序表中做插入運(yùn)算，平均移動元素的次數(shù)為

A．25 B.33

C.50

D.100

4．已知尾指針的單向循環(huán)鏈表中，在第一個結(jié)點后面插入一個新結(jié)點，該算法的時間復(fù)雜度為

A．O（1） B.O（log2n）

C.O（n）

D.O(n2)

5．下列表述正確的是

A．?？諘r出棧產(chǎn)生“上溢”，棧滿時進(jìn)棧產(chǎn)生“下溢”

B.?？諘r出棧產(chǎn)生“下溢”，棧滿時進(jìn)棧產(chǎn)生“上溢”

C.棧空時出棧和棧滿時進(jìn)棧均產(chǎn)生“上溢”

D.?？諘r出棧和棧滿時進(jìn)棧均產(chǎn)生“下溢”

6.隊列操作的原則是

A.先進(jìn)先出

B.后進(jìn)先出

C.先進(jìn)后出

D.只進(jìn)不出

7．一棵深度為6的滿二叉樹有

A．63個結(jié)點 B.64個結(jié)點

C.127個結(jié)點

D.128個結(jié)點

8.在一棵度為3的樹中，度為3的結(jié)點有4個，度為2的結(jié)點有2個，度為1的結(jié)點有3個，則度為0的結(jié)點有

A.8個

B.10個

C.11個

D.12個

9．一棵二叉樹T，度為2的結(jié)點數(shù)為20個，則葉子結(jié)點數(shù)為

A．19個 B.20個

C.21個

D.22個

10．有10個葉結(jié)點的哈夫曼樹中共有

A．10個結(jié)點 B.11個結(jié)點

C.19個結(jié)點

D.21個結(jié)點

11．求圖中兩個結(jié)點之間的最短路徑采用的算法是

A．廣度優(yōu)先搜索（BFS）算法 B.克魯斯卡爾（Kruskal）算法

C.普里姆（Prim）算法

D.迪杰斯特拉（Dijkstra）算法

12．順序查找算法的平均查找長度為

A．log2n B.（n-1）/2

C.n/2

D.（n+1）/2

13．二叉排序樹中，根的

A．左子樹是二叉排序樹、右子樹不一定是二叉排序樹

B.左子樹是二叉排序樹、右子樹也是二叉排序樹

C.左子樹不一定是二叉排序樹、右子樹是二叉排序樹

D.左子樹不一定是二叉排序樹、右子樹也不一定是二叉排序樹

14．冒泡排序的時間復(fù)雜度為

A．O(n) B.O(nlog2n)

C.O(n2)

D.O(log2n)

15．關(guān)于穩(wěn)定性的表述，正確的是

A．穩(wěn)定性是排序方法本身的特性，與數(shù)據(jù)無關(guān)

B.穩(wěn)定性不是排序方法本身的特性，與數(shù)據(jù)有關(guān)

C.穩(wěn)定性是排序方法本身的特性，與數(shù)據(jù)有關(guān)

D.穩(wěn)定性不是排序方法本身的特性，與數(shù)據(jù)無關(guān)

非選擇題部分

注意事項：

用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。

二、填空題(本大題共13小題，每小題2分，共26分)

16．?dāng)?shù)據(jù)中不可分割的最小標(biāo)識單位是___數(shù)據(jù)項_______。

17．雙向循環(huán)鏈表中，在p 所指結(jié)點的后面插入一個新結(jié)點*t ，需要修改四個指針，分別為：t->prior=p ；__t->next=p->next________；p->next->prior=t ；p->next=t ；。

18.在帶有頭結(jié)點的循環(huán)鏈表中，頭指針為head ，判斷指針p 所指結(jié)點為首結(jié)點的條件是_p==head->next;_________。

19．元素的進(jìn)棧次序為1，2，3，…，n ，出棧的第一個元素是n ，則第k 個出棧的元素是__n-k+1________。

20．在棧結(jié)構(gòu)中，允許插入和刪除的一端稱為___棧頂_______。

21．100個結(jié)點的二叉樹采用三叉鏈表存儲時，空指針域NULL 有___102_______個。

22.某二叉樹的先序遍歷序列為ABKLMNO ，中序遍歷序列為BLKANMO ，則該二叉樹中結(jié)點A 的右孩子為結(jié)點__m______。

23．一個二叉樹的最少結(jié)點個數(shù)為_____0_____。

24．圖中第一個頂點和最后一個頂點相同的路徑稱為回路。除第一個頂點和最后一個頂點相同外，其余頂點不重復(fù)的回路，稱為_____簡單回路____。

25．設(shè)查找表有n 個數(shù)據(jù)元素，則二分查找算法的平均查找長度為___(n+1)/2 log2(n+1) -1 _______。

26．用鍵值通過散列函數(shù)獲取存儲位置的這種存儲方式構(gòu)造的存儲結(jié)構(gòu)稱為___散列表_______。

27．若在線性表中采用二分查找法查找元素，則該線性表必須按值有序，并且采用___順序_______存儲結(jié)構(gòu)。

28．堆分為最小堆和最大堆，若鍵值序列{k 1,k 2,…，k n }，滿足i 2i i 2i 1

k k n (i 1,2,,)k k 2+≥???=???≥??? ，則這n 個鍵值序列{k 1,k 2,…，k n }是___最大堆_______。

三、應(yīng)用題(本大題共5小題，每小題6分，共30分)

29．設(shè)一個鏈棧的輸入序列為X ，Y ，Z ，試寫出出棧的所有可能的輸出序列及其操作步驟。

30．設(shè)二叉樹的先序遍歷序列為DCBAHEIFG ，中序遍歷序列為ABCHDIEFG ，試畫出該二叉樹并寫出后序遍歷序列。

31．已知連通帶權(quán)圖如題31圖所示，試?yán)闷绽锬罚≒rim ）算法，從頂點A 出發(fā)，構(gòu)造它的最小生成樹，畫出構(gòu)造過程。

題31圖

32．給定表（28，15，55，3，71，75，10，22，56），試按元素在表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r為空的二叉排序樹，畫出插入完成后的二叉排序樹。

33．應(yīng)用直接選擇排序算法，對初始關(guān)鍵字序列為48，35，61，98，82，18，29，48的記錄進(jìn)行從小到大排序，寫出排序過程和結(jié)果。

四、算法設(shè)計題(本大題共2小題，每小題7分，共14分)

34.單鏈表的結(jié)點結(jié)構(gòu)定義如下：

typedef struct node

{ int data;

struct node *next;

}Node, *LinkList;

試編寫在帶頭結(jié)點的單鏈表head中查找第1個元素值小于x的結(jié)點的實現(xiàn)算法Node *GetLinklist(LinkList head，int x)，若找到，則返回指向該結(jié)點的指針，否則返回NULL。

35．假設(shè)樹采用孩子兄弟鏈表表示法，其結(jié)構(gòu)定義如下：

typedef struct tnode

{ DataType data;

struct tnode *son, *brother;

}*Tree;

試編寫算法void leveltree(Tree root)實現(xiàn)樹的按層次遍歷。