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

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

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

課程代碼：02142

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

選擇題部分

注意事項(xiàng)：

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

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

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

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

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

A.O（1） 

B.O（n）

C.O（nlog2n）

D.O（n2）

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

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

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

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

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

A．25 B.33

C.50

D.100

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

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

C.O（n）

D.O(n2)

5．下列表述正確的是

A．棧空時(shí)出棧產(chǎn)生“上溢”，棧滿時(shí)進(jìn)棧產(chǎn)生“下溢”

B.棧空時(shí)出棧產(chǎn)生“下溢”，棧滿時(shí)進(jìn)棧產(chǎn)生“上溢”

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

D.棧空時(shí)出棧和棧滿時(shí)進(jìn)棧均產(chǎn)生“下溢”

6.隊(duì)列操作的原則是

A.先進(jìn)先出

B.后進(jìn)先出

C.先進(jìn)后出

D.只進(jìn)不出

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

A．63個(gè)結(jié)點(diǎn) B.64個(gè)結(jié)點(diǎn)

C.127個(gè)結(jié)點(diǎn)

D.128個(gè)結(jié)點(diǎn)

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

A.8個(gè)

B.10個(gè)

C.11個(gè)

D.12個(gè)

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

A．19個(gè) B.20個(gè)

C.21個(gè)

D.22個(gè)

10．有10個(gè)葉結(jié)點(diǎn)的哈夫曼樹中共有

A．10個(gè)結(jié)點(diǎn) B.11個(gè)結(jié)點(diǎn)

C.19個(gè)結(jié)點(diǎn)

D.21個(gè)結(jié)點(diǎn)

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

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

C.普里姆（Prim）算法

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

12．順序查找算法的平均查找長(zhǎng)度為

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

C.n/2

D.（n+1）/2

13．二叉排序樹中，根的

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

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

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

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

14．冒泡排序的時(shí)間復(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)

非選擇題部分

注意事項(xiàng)：

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

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

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

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

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

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

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

21．100個(gè)結(jié)點(diǎn)的二叉樹采用三叉鏈表存儲(chǔ)時(shí)，空指針域NULL 有___102_______個(gè)。

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

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

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

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

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

27．若在線性表中采用二分查找法查找元素，則該線性表必須按值有序，并且采用___順序_______存儲(chǔ)結(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 個(gè)鍵值序列{k 1,k 2,…，k n }是___最大堆_______。

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

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

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

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

題31圖

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

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

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

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

typedef struct node

{ int data;

struct node *next;

}Node, *LinkList;

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

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

typedef struct tnode

{ DataType data;

struct tnode *son, *brother;

}*Tree;

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