數據結構自考2012年10月真題及答案解析

本試卷為單選題型，填空題，算法閱讀，算法設計等題型。

一、單項選擇題(本大題共15小題，每小題2分，共30分) 在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。

1.一個算法的時間耗費的數量級稱為該算法的(　　)

A.效率
B.難度
C.可實現性
D.時間復雜度

2.順序表便于(　　)

A.插入結點
B.刪除結點
C.按值查找結點
D.按序號查找結點

3.設帶頭結點的單循環鏈表的頭指針為head，指針變量P指向尾結點的條件是(　　)

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

4.設以數組A[0..m-1]存放循環隊列，front指向隊頭元素，rear指向隊尾元素的下一個位置，則當前隊列中的元素個數為(　　)

A.(rear-front+m)%m
B.rear-front+1
C.(front-rear+m)%m
D.(rear-front)%m

5.下列關于順序棧的敘述中，正確的是(　　)

A.入棧操作需要判斷棧滿，出棧操作需要判斷?？?br/>B.入棧操作不需要判斷棧滿，出棧操作需要判斷?？?br/>C.入棧操作需要判斷棧滿，出棧操作不需要判斷?？?br/>D.入棧操作不需要判斷棧滿，出棧操作不需要判斷?？?/p>

6.A是一個10×10的對稱矩陣，若采用行優先的下三角壓縮存儲，第一個元素,0的存儲地址為1，每個元素占一個存儲單元，則的地址為(　　)

A.25
B.26
C.33
D.34

7.樹的后序遍歷等價于該樹對應二叉樹的(　　)

A.層次遍歷
B.前序遍歷
C.中序遍歷
D.后序遍歷

8.使用二叉線索樹的目的是便于(　　)

A.二叉樹中結點的插入與刪除
B.在二叉樹中查找雙親
C.確定二叉樹的高度
D.查找一個結點的前趨和后繼

9.設無向圖的頂點個數為n，則該圖邊的數目最多為(　　)

A.n-1
B.n(n-1)/2
C.n(n+1)/2

D.

10.可進行拓撲排序的圖只能是(　　)

A.有向圖
B.無向圖
C.有向無環圖
D.無向連通圖

11.下列排序方法中穩定的是(　　)

A.直接插入排序
B.直接選擇排序
C.堆排序
D.快速排序

12.下列序列不為堆的是(　　)

A.75,45,65,30,15,25
B.75,65,45,30,25,15
C.75,65,30,15,25,45
D.75,45,65,25,30,15

13.對線性表進行二分查找時，要求線性表必須是(　　)

A.順序存儲
B.鏈式存儲
C.順序存儲且按關鍵字有序
D.鏈式存儲且按關鍵字有序

14.分別用以下序列生成二叉排序樹，其中三個序列生成的二叉排序樹是相同的，不同的序列是(　　)

A.(4,1,2,3,5)
B.(4,2,3,1,5)
C.(4,5,2,1,3)
D.(4,2,1,5,3)

15.下列關于m階B樹的敘述中，錯誤的是(　　)

A.每個結點至多有m個關鍵字
B.每個結點至多有m棵子樹
C.插入關鍵字時，通過結點分裂使樹高增加
D.刪除關鍵字時通過結點合并使樹高降低

二、填空題(本大題共10小題，每小題2分，共20分) 請在每小題的空格中填上正確答案。錯填、不填均無分。

11.數據元素之間的邏輯關系稱為數據的______結構。

12.在線性表中，表的長度定義為______。

13.用S表示入棧操作，X表示出棧操作，若元素入棧的順序為1、2、3、4，為了得到1、3、4、2的出棧順序，相應的S和X的操作序列為______。

14.在二叉樹中，帶權路徑長度最短的樹稱為______。

15.已知廣義表G，head(G)與tail(G)的深度分別為4和6，則G的深度是______。

16.一組字符(a,b,c,d)在文中出現的次數分別為(7，6，3，5)，字符"d"的哈夫曼編碼的長度為______。

17.在一個具有n個頂點的無向圖中，要連通全部頂點至少需要______條邊。

18.直接選擇排序算法的時間復雜度是______。

19.對于長度為81的表，若采用分塊查找，每塊的最佳長度為______。

110.用二叉鏈表保存有n個結點的二叉樹，則結點中有______個空指針域。

三、解答題(本大題共4小題，每小題5分，共20分)

21.假設Q是一個具有11個元素存儲空間的循環隊列(隊尾指針指向隊尾元素的下一 個位置，隊頭指針指向隊頭元素)，初始狀態Q.front=Q.rear=0;寫出依次執行 下列操作后頭、尾指針的當前值。a,b,c,d,e,f入隊，a,b,c,d出隊; (1) Q.front=______;Q.rear=______。g,h,i,j,k,l入隊，e,f,g,h出隊; (2) Q.front=______;Q.rear=______。M,n,o,P入隊，i,j,k,l,m出隊; (3) Q.front=______;Q.rear=______。

22.已知一個無向圖如題27圖所示，以①為起點，用普里姆(Prim)算法求其最小生成樹，畫出最小生成樹的構造過程。

23.用歸并排序法對序列 (98,36,-9,0,47,23,1,8)進行排序，問：(1)一共需要幾趟歸并可完成排序。(2)寫出第一趟歸并后數據的排列次序。

24.一組記錄關鍵字(55,76,44,32,64,82,20,16,43)，用散列函數H(key)=key%11將記錄 散列到散列表HT[0..12]中去，用線性探測法解決沖突。 (1)畫出存入所有記錄后的散列表。 (2)求在等概率情況下，查找成功的平均查找長度。

四、算法閱讀題(本大題共4小題，每小題5分，共20分)

31.順序表類型定義如下：# define ListSize 100typedef struct {int data[ListSize];int length; }SeqList;閱讀下列算法，并回答問題：(1)若L->data 中的數據為(22,4,63,0,15,29,34,42,3),則執行上述算法后L->data中的數據以及L->length的值各是什么?(2)該算法的功能是什么?

32.有向圖的鄰接矩陣類型定義如下：#define MVN 100 ∥ 最大頂點數typedef int EType; ∥ 邊上權值類型typedef struct{EType edges[MVN][MVN]; ∥ 鄰接矩陣，即邊表int n; ∥ 圖的頂點數｝MGraph; ∥ 圖類型例如，一個有向圖的鄰接矩陣如下所示：閱讀下列算法，并回答問題：(1)step1到step2之間的二重循環語句的功能是什么?(2)step2之后的二重循環語句的功能是什么?

33.閱讀下列算法，并回答問題：(1)這是哪一種插入排序算法?該算法是否穩定?(2)設置r[0]的作用是什么?

34.順序表類型定義如下：(1)給出該算法的功能;(2)給出該算法的時間復雜度。

五、算法設計題(本大題共1小題，共10分)

41.二叉樹的存儲結構類型定義如下typedef struct node{int data;struct node *lchild， *rchild;} BinNode;typedef BinNode *BinTree;編寫遞歸算法，求只有一個孩子結點的結點總數，并計算這些結點的數據值的和。 函數的原型為：void f34(BinTree T, int *count, int *sum) *count和*sum的初值為0。