數(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ì)解析。

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

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

A.O(nlog₂n)

B.O(n²)

D.O(2ⁿ)

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

A.正確性
B.易讀性
C.健壯性
D.時空性

3.設(shè)順序表的長度為100，則在第40個元素之后插入一個元素所需移動元素的個數(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.求鏈棧的元素個數(shù)

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

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

7.以行序為主序的二維數(shù)組a[3][5]中，第一個元素a[0][0]的存儲地址是100，每個元素占2個存儲單元，則a[1][2]的存儲地址是(　　)

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

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

A.4
B.5
C.6
D.無法確定

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

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

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

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

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

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

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

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

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

A.O(n²)

B.O(nlog₂n)

D.O(log₂n)

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

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

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

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

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

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

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

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

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

15.在棧結(jié)構(gòu)中，允許插入和刪除的一端稱為________。

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

17.具有64個結(jié)點(diǎn)的完全二叉樹的深度為________。

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

19.三個頂點(diǎn)v₁，v₂，v₃的圖的鄰接矩陣為，則該圖中頂點(diǎn)v₂的出度為________。

110.除第一個頂點(diǎn)和最后一個頂點(diǎn)相同外，其余頂點(diǎn)不重復(fù)的回路，稱為________。

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

112.堆排序算法的時間復(fù)雜度為________。

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

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

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

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

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

24.題32圖所示二叉排序樹的各結(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，用鏈地址法解決沖突，試畫出相應(yīng)的散列表，并計算在等概率情況下查找成功時的平均查找長度。

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

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

32.寫出直接選擇排序算法。