?數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2012年10月真題（02142）

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2012年10月真題及答案解析（02142）

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2012年10月真題及答案（02142），該試卷為數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考?xì)v年真題試卷，包含答案及詳細(xì)解析。

一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的。錯(cuò)選、多選或未選均無(wú)分。

1.下面幾種算法時(shí)間復(fù)雜度階數(shù)中，值最大的是(　　)

A.O(nlog₂n)

B.O(n²)

D.O(2ⁿ)

2.即使輸入非法數(shù)據(jù)，算法也能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，不會(huì)產(chǎn)生預(yù)料不到的運(yùn)行結(jié)果，這種算法好壞的評(píng)價(jià)因素稱(chēng)為(　　)

A.正確性
B.易讀性
C.健壯性
D.時(shí)空性

3.設(shè)順序表的長(zhǎng)度為100，則在第40個(gè)元素之后插入一個(gè)元素所需移動(dòng)元素的個(gè)數(shù)為(　　)

A.40
B.60
C.61
D.100

4.設(shè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表的頭指針為head，則判斷該鏈表是否為空的條件是(　　)

A.head->next==head
B.head->next==NULL
C.head!=NULL
D.head==NULL

5.在鏈棧的運(yùn)算中，不需要判斷棧是否為空的是(　　)

A.出棧
B.進(jìn)棧
C.取棧頂元素
D.求鏈棧的元素個(gè)數(shù)

6.一個(gè)隊(duì)列的輸入序列是A，B，C，D，則該隊(duì)列的輸出序列是(　　)

A.A，B，C，D
B.B，C，D，A
C.D，C，B，A
D.C，D，B，A

7.以行序?yàn)橹餍虻亩S數(shù)組a[3][5]中，第一個(gè)元素a[0][0]的存儲(chǔ)地址是100，每個(gè)元素占2個(gè)存儲(chǔ)單元，則a[1][2]的存儲(chǔ)地址是(　　)

A.100
B.108
C.114
D.116

8.對(duì)任何一棵二叉樹(shù)T，若葉結(jié)點(diǎn)數(shù)為5個(gè)，則度為2的結(jié)點(diǎn)個(gè)數(shù)為(　　)

A.4
B.5
C.6
D.無(wú)法確定

9.m個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)中，其結(jié)點(diǎn)總數(shù)為(　　)

A.m
B.2m+1
C.2m
D.2m-1

10.二叉樹(shù)的中序遍歷序列中，結(jié)點(diǎn)P排在結(jié)點(diǎn)Q之前的條件是(　　)

A.在二叉樹(shù)中P在Q的左邊
B.在二叉樹(shù)中P在Q的右邊
C.在二叉樹(shù)中P是Q的祖先
D.在二叉樹(shù)中P是Q的子孫

11.有10個(gè)頂點(diǎn)的無(wú)向完全圖的邊數(shù)是(　　)

A.11
B.45
C.55
D.90

12.在帶權(quán)有向圖中求兩個(gè)結(jié)點(diǎn)之間的最短路徑可以采用的算法是(　　)

A.迪杰斯特拉(Dijkstra)算法
B.克魯斯卡爾(Kruskal)算法
C.普里姆(Prim)算法
D.深度優(yōu)先搜索(DFS)算法

13.二分查找(Binary Search)算法的時(shí)間復(fù)雜度是(　　)

A.O(n²)

B.O(nlog₂n)

D.O(log₂n)

14.在一棵初始時(shí)為空的二叉樹(shù)中，依次插入鍵值序列50，72，43，85，75，20，38，45，65，60，構(gòu)造對(duì)應(yīng)的二叉排序樹(shù)以后，查找元素60要進(jìn)行的比較次數(shù)是(　　)

A.2
B.3
C.4
D.5

15.快速排序?qū)儆?　　)

A.插入排序
B.交換排序
C.選擇排序
D.歸并排序

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

11.下面算法程序段的時(shí)間復(fù)雜度為_(kāi)_______。for (i=1; i<=n; i++)       for (j=1; j<=n; j++)            for (k=1;k<=n;k++)                  x++;

12.所有存儲(chǔ)結(jié)點(diǎn)存放在一個(gè)連續(xù)的存儲(chǔ)區(qū)里，利用結(jié)點(diǎn)在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。這種存儲(chǔ)方式是________。

13.單鏈表中指針p指向結(jié)點(diǎn)A，若要?jiǎng)h除A之后的結(jié)點(diǎn)(存在且不釋放存儲(chǔ)空間)，則需要修改指針的操作為p->next=________。

14.在帶有頭結(jié)點(diǎn)的單鏈表head中，首結(jié)點(diǎn)的指針為_(kāi)_______。

15.在棧結(jié)構(gòu)中，允許插入和刪除的一端稱(chēng)為_(kāi)_______。

16.C程序中，將對(duì)稱(chēng)矩陣A[n][n]的下三角元素壓縮存儲(chǔ)到n(n+1)/2個(gè)元素的一維數(shù)組M中，設(shè)a[i][j](i≥j)存放在數(shù)組M[k]中，則k的值(用i，j表示)為_(kāi)_______。

17.具有64個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為_(kāi)_______。

18.某二叉樹(shù)的先序遍歷序列為AJKLMNO，中序遍歷序列為JLKANMO，則根結(jié)點(diǎn)A的右子樹(shù)中的結(jié)點(diǎn)個(gè)數(shù)為_(kāi)_______。

19.三個(gè)頂點(diǎn)v₁，v₂，v₃的圖的鄰接矩陣為，則該圖中頂點(diǎn)v₂的出度為_(kāi)_______。

110.除第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同外，其余頂點(diǎn)不重復(fù)的回路，稱(chēng)為_(kāi)_______。

111.在順序查找、二分查找、散列查找和索引順序查找四種查找方法中，平均查找長(zhǎng)度與元素個(gè)數(shù)沒(méi)有關(guān)系的查找方法是________。

112.堆排序算法的時(shí)間復(fù)雜度為_(kāi)_______。

113.如果要將序列{60，18，28，69，99，75，78}建成堆，則只需把60與________相互交換。

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

21.如題29圖所示，在棧的輸入端依次輸入元素A，B，C，試寫(xiě)出在棧的輸出端可以得到的所有輸出序列，并給出每個(gè)序列的操作過(guò)程(用push(A)表示A進(jìn)棧，pop(A)表示A出棧)。題29圖

22.將題30圖所示的一棵樹(shù)轉(zhuǎn)換為對(duì)應(yīng)的二叉樹(shù)。題30圖

23.已知含五個(gè)頂點(diǎn)A，B，C，D，E的連通帶權(quán)圖的鄰接矩陣如題31圖所示，試畫(huà)出它所表示的連通帶權(quán)圖及該連通帶權(quán)圖的最小生成樹(shù)。           題31圖

24.題32圖所示二叉排序樹(shù)的各結(jié)點(diǎn)的值為1~10中的數(shù)，試標(biāo)出各結(jié)點(diǎn)的數(shù)值。題32圖

25.設(shè)散列函數(shù)H(key)=key mod 11(mod表示求余運(yùn)算)，給出鍵值序列為66，13，41，15，44，6，68，17，26，31，39，46，用鏈地址法解決沖突，試畫(huà)出相應(yīng)的散列表，并計(jì)算在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。

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

31.帶頭結(jié)點(diǎn)的單鏈表的結(jié)點(diǎn)結(jié)構(gòu)如下：typedef struct node{   int data;    struct node *next;}Node, *LinkList;試編寫(xiě)單鏈表的刪除運(yùn)算算法void DeleteLinklist( LinkList head，int i)

32.寫(xiě)出直接選擇排序算法。