?數據結構導論2012年10月真題（02142）

數據結構導論2012年10月真題及答案解析（02142）

數據結構導論2012年10月真題及答案（02142），該試卷為數據結構導論自考歷年真題試卷，包含答案及詳細解析。

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

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

A.O(nlog₂n)

B.O(n²)

D.O(2ⁿ)

2.即使輸入非法數據，算法也能適當地做出反應或進行處理，不會產生預料不到的運行結果，這種算法好壞的評價因素稱為(　　)

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

3.設順序表的長度為100，則在第40個元素之后插入一個元素所需移動元素的個數為(　　)

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

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

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

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

A.出棧
B.進棧
C.取棧頂元素
D.求鏈棧的元素個數

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

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

8.對任何一棵二叉樹T，若葉結點數為5個，則度為2的結點個數為(　　)

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

9.m個葉結點的哈夫曼樹中，其結點總數為(　　)

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

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

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

11.有10個頂點的無向完全圖的邊數是(　　)

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

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

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

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

A.O(n²)

B.O(nlog₂n)

D.O(log₂n)

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

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

15.快速排序屬于(　　)

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

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

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

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

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

14.在帶有頭結點的單鏈表head中，首結點的指針為________。

15.在棧結構中，允許插入和刪除的一端稱為________。

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

17.具有64個結點的完全二叉樹的深度為________。

18.某二叉樹的先序遍歷序列為AJKLMNO，中序遍歷序列為JLKANMO，則根結點A的右子樹中的結點個數為________。

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

110.除第一個頂點和最后一個頂點相同外，其余頂點不重復的回路，稱為________。

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

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

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

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

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

22.將題30圖所示的一棵樹轉換為對應的二叉樹。題30圖

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

24.題32圖所示二叉排序樹的各結點的值為1~10中的數，試標出各結點的數值。題32圖

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

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

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

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