數據結構自考2014年4月真題及答案解析

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

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

1.與數據存儲結構無關的概念是(　　)

A.棧
B.鏈表
C.順序表
D.二叉鏈表

2.順序表中有10個數據元素，若第一個元素的存儲地址是1000，則最后一個元素地址是1036，第5個元素的地址是(　　)

A.1010
B.1016
C.1018
D.1019

3.設棧的初始狀態為空，元素1、2、3、4、5、6依次入棧，得到的出棧序列是(2,4,3,6,5,1),則棧的容量至少是(　　)

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

4.下列關于隊列的敘述中,錯誤的是(　　)

A.隊列是一種先進先出的線性表
B.隊列是一種后進后出的線性表
C.循環隊列中進行出隊操作時要判斷隊列是否為空
D.在鏈隊列中進行入隊操作時要判斷隊列是否為滿

5.對稀疏矩陣進行壓縮存儲的目的是(　　)

A.便于運算
B.節省存儲空間
C.便于輸入輸出
D.降低時間復雜度

6.一棵二叉樹的第7層上最多含有的結點數為(　　)

A.14
B.64
C.127
D.128

7.下列選項為完全二叉樹的是(　　)

8.用鄰接表表示n個頂點e條邊的無向圖,其邊表結點的總數是(　　)

A.n×e
B.e
C.2e
D.n+e

9.無向圖中所有頂點的度數之和與所有邊數之比是(　　)

A.1/2
B.1
C.2
D.4

10.采用鄰接矩陣存儲圖時，廣度優先搜索遍歷算法的時間復雜度為(　　)

A.O(n)
B.O(n+e)

C.

D.

11.對序列(15,9,7,8,20,-1,4)進行排序，若一趟排序后的結果為(-1,15,9,7,8,20,4),則采用的排序方法是(　　)

A.歸并排序
B.快速排序
C.直接選擇排序
D.冒泡排序

12.比較次數與待排序列初始狀態無關的排序方法是(　　)

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

13.查找較快，且插入和刪除操作也比較方便的查找方法是(　　)

A.分塊查找
B.二分查找
C.順序查找
D.折半查找

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

A.根結點至多有m棵子樹
B.所有葉子都在同一層次上
C.每個非根內部結點至少有 棵子樹
D.結點內部的關鍵字可以是無序的

15.在散列查找中處理沖突時,可以采用開放定址法。下列不是開放定址法的是(　　)

A.線性探查法
B.二次探查法
C.雙重散列法
D.拉鏈法

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

11.數據結構研究的內容包括數據的邏輯結構、________和數據的運算。

12.頭指針為L的帶頭結點的雙循環鏈表,結點的前趨指針域為prior,后繼指針域為next,判斷該鏈表為空的條件是________。

13.普里姆(Prim)算法完成的功能是求圖的________。

14.若三維數組a[4][5][6]的基地址是100,每個元素占用2個存儲單元,則數組a中最后一個元素的存儲地址是________。

15.二叉樹的線索鏈表利用________存放遍歷時得到的前趨或后繼結點的指針。

16.采用鄰接矩陣存儲n個頂點e條邊的無向圖,其鄰接矩陣的大小為________。

17.若無向圖中任意兩個不同的頂點間都有路徑,則稱該圖為________。

18.在直接插入排序、冒泡排序和快速排序中,平均時間性能最佳的是________。

19.假設m個關鍵字互為同義詞,若用線性探查法把這m個關鍵字存入散列表中,至少要進行的探查次數是________。

110.順序查找算法的平均時間復雜度為________。

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

21.用X代表進棧操作,S代表出棧操作。給出利用棧將字符串"a*b-c"改變為"ab*c-"的操作步驟。例如：將"ABC"改變為"BCA",則其操作步驟為XXSXSS。

22.假定電文字符集為{A,B,C,D,E,F,G,H},它們在電文中出現的次數分別為{19,6,12,5,38,3,13,4),為這8個字符設計哈夫曼編碼。畫出哈夫曼樹并給出編碼。要求在構造哈夫曼樹的過程中,權值較小結點放在左側,編碼時左分支生成代碼0,右分支生成代碼1。

23.設圖以鄰接表存儲,如題28圖所示。(1)寫出從頂點v1出發圖的深度優先搜索遍歷序列。(2)寫出從頂點v1出發圖的廣度優先搜索遍歷序列。

24.(1)一個排序方法穩定的含義是什么?(2)快速排序是穩定的嗎?舉例說明。

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

31.閱讀下列算法,并回答問題：void f30(SeqStack S){     int k=0;      CirQueue Q;      SeqStack T;      InitQueue(&Q); //初始化隊列Q       InitStack(&T); //初始化棧T       while (!StackEmpty(&S))     {       k++;         if (k%2!=0) Push(&T, Pop(&S));         else EnQueue(&Q, Pop(&S));    } //第一個循環      while (!QueueEmpty(&Q)) //第二個循環       Push(&S, DeQueue(&Q));        while(!StackEmpty(&T)) //第三個循環         Push(&S,Pop(&T)); }設棧S=(1,2,3,4,5,6,7),其中7為棧頂元素。調用函數f30(S)后,(1)第一個循環結束后,棧T和隊列Q中的內容各是什么?(2)第三個循環語句結束后,棧S中的內容是什么?

32.二叉樹的二叉鏈表類型定義如下：typedef struct node {      DataType data;       struct node *lchild, *rchild;} BinNode;typedef BinNode *BinTree;閱讀下列算法,并回答問題：

33.單鏈表類型定義如下：typedef struct node {     int data;     struct node *next;} ListNode;typedef ListNode *LinkList;用不帶頭結點的單鏈表存儲待排數據,鏈表頭指針為head。下列直接選擇排序算法對鏈表按升序進行排序,請在答題紙相應位置填寫適當內容使算法完整。

34.實現二分查找的遞歸章法如下,在答題紙相應位置填寫適當的內容使算法完整。

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

41.單鏈表類型定義如下：typedef struct node {       int data;       struct node *next;  } ListNode;typedef ListNode *LinkList;設計算法在帶頭結點的單鏈表L中刪除數據值最小的結點(設鏈表中各結點數據值 均不相同)。函數的原型為：void f34(LinkList L)