數(shù)據(jù)結(jié)構(gòu)自考2014年4月真題及答案解析

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

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

1.與數(shù)據(jù)存儲結(jié)構(gòu)無關(guān)的概念是(　　)

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

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

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

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

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

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

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

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

A.便于運(yùn)算
B.節(jié)省存儲空間
C.便于輸入輸出
D.降低時間復(fù)雜度

6.一棵二叉樹的第7層上最多含有的結(jié)點(diǎn)數(shù)為(　　)

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

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

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

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

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

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

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

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

C.

D.

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

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

12.比較次數(shù)與待排序列初始狀態(tài)無關(guān)的排序方法是(　　)

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

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

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

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

A.根結(jié)點(diǎn)至多有m棵子樹
B.所有葉子都在同一層次上
C.每個非根內(nèi)部結(jié)點(diǎn)至少有 棵子樹
D.結(jié)點(diǎn)內(nèi)部的關(guān)鍵字可以是無序的

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

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

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

11.數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容包括數(shù)據(jù)的邏輯結(jié)構(gòu)、________和數(shù)據(jù)的運(yùn)算。

12.頭指針為L的帶頭結(jié)點(diǎn)的雙循環(huán)鏈表,結(jié)點(diǎn)的前趨指針域?yàn)閜rior,后繼指針域?yàn)閚ext,判斷該鏈表為空的條件是________。

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

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

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

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

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

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

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

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

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

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

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

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

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

四、算法閱讀題(本大題共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));    } //第一個循環(huán)      while (!QueueEmpty(&Q)) //第二個循環(huán)       Push(&S, DeQueue(&Q));        while(!StackEmpty(&T)) //第三個循環(huán)         Push(&S,Pop(&T)); }設(shè)棧S=(1,2,3,4,5,6,7),其中7為棧頂元素。調(diào)用函數(shù)f30(S)后,(1)第一個循環(huán)結(jié)束后,棧T和隊列Q中的內(nèi)容各是什么?(2)第三個循環(huán)語句結(jié)束后,棧S中的內(nèi)容是什么?

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;用不帶頭結(jié)點(diǎn)的單鏈表存儲待排數(shù)據(jù),鏈表頭指針為head。下列直接選擇排序算法對鏈表按升序進(jìn)行排序,請在答題紙相應(yīng)位置填寫適當(dāng)內(nèi)容使算法完整。

34.實(shí)現(xiàn)二分查找的遞歸章法如下,在答題紙相應(yīng)位置填寫適當(dāng)?shù)膬?nèi)容使算法完整。

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

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