全國2014年4月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題

課程代碼：02331

請(qǐng)考生按規(guī)定用筆將所有試題的答案涂、寫在答題紙上。

選擇題部分

注意事項(xiàng)：

1.答題前，考生務(wù)必將自己的考試課程名稱、姓名、準(zhǔn)考證號(hào)用黑色字跡的簽字筆或鋼筆填寫在答題紙規(guī)定的位置上。

2.每小題選出答案后，用2B鉛筆把答題紙上對(duì)應(yīng)題目的答案標(biāo)號(hào)涂黑。如需改動(dòng)，用橡皮擦干凈后，再選涂其他答案標(biāo)號(hào)。不能答在試題卷上。

一、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）

在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其選出并將“答題紙”的相應(yīng)代碼涂黑。錯(cuò)涂、多涂或未涂均無分。

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

A.棧 B.鏈表

C.順序表 D.二叉鏈表

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

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)于隊(duì)列的敘述中,錯(cuò)誤的是

A.隊(duì)列是一種先進(jìn)先出的線性表

B.隊(duì)列是一種后進(jìn)后出的線性表

C.循環(huán)隊(duì)列中進(jìn)行出隊(duì)操作時(shí)要判斷隊(duì)列是否為空

D.在鏈隊(duì)列中進(jìn)行入隊(duì)操作時(shí)要判斷隊(duì)列是否為滿

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

A.便于運(yùn)算 B.節(jié)省存儲(chǔ)空間

C.便于輸入輸出 D.降低時(shí)間復(fù)雜度

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

A.14 B.64

C.127 D.128

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

8.用鄰接表表示n個(gè)頂點(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.采用鄰接矩陣存儲(chǔ)圖時(shí),廣度優(yōu)先搜索遍歷算法的時(shí)間復(fù)雜度為

A. O（n） B. O（n+e）

C. O（n2） D. O（n3）

11.對(duì)序列（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樹的敘述中,錯(cuò)誤的是

A.根結(jié)點(diǎn)至多有m棵子樹

B.所有葉子都在同一層次上

C.每個(gè)非根內(nèi)部結(jié)點(diǎn)至少有[m/2]棵子樹

D.結(jié)點(diǎn)內(nèi)部的關(guān)鍵字可以是無序的

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

A.線性探查法 B.二次探查法

C.雙重散列法 D.拉鏈法

非選擇題部分

注意事項(xiàng)：

用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上,不能答在試題卷上。

二、填空題（本大題共10小題,每小題2分,共20分）

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

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

18.普里姆（Prim）算法完成的功能是求圖的________。

19.若三維數(shù)組a［4］［5］［6］的基地址是100,每個(gè)元素占用2個(gè)存儲(chǔ)單元,則數(shù)組a中最后一個(gè)元素的存儲(chǔ)地址是________。

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

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

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

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

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

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

三、解答題（本大題共4小題,每小題5分,共20分）

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

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

28.設(shè)圖以鄰接表存儲(chǔ),如題28圖所示。

（1）寫出從頂點(diǎn)v1出發(fā)圖的深度優(yōu)先搜索遍歷序列。

（2）寫出從頂點(diǎn)v1出發(fā)圖的廣度優(yōu)先搜索遍歷序列。

29.（1）一個(gè)排序方法穩(wěn)定的含義是什么？

（2）快速排序是穩(wěn)定的嗎？舉例說明。

四、算法閱讀題（本大題共4小題,每小題5分,共20分）

30.閱讀下列算法,并回答問題：

void f30（SeqStack S）

{ int k=0；

CirQueue Q；

SeqStack T；

InitQueue（&Q）； //初始化隊(duì)列Q

InitStack（&T）； //初始化棧T

while （!StackEmpty（&S））

{ k++;

if （k%2!=0） Push（&T, Pop（&S））;

else EnQueue（&Q, Pop（&S））;

} //第一個(gè)循環(huán)

while （!QueueEmpty（&Q）） //第二個(gè)循環(huán)

Push（&S, DeQueue（&Q））;

while（!StackEmpty（&T）） //第三個(gè)循環(huán)

Push（&S,Pop（&T））；

}

設(shè)棧S=（1,2,3,4,5,6,7）,其中7為棧頂元素。調(diào)用函數(shù)f30（S）后,

（1）第一個(gè)循環(huán)結(jié)束后,棧T和隊(duì)列Q中的內(nèi)容各是什么？

（2）第三個(gè)循環(huán)語句結(jié)束后,棧S中的內(nèi)容是什么？

31.二叉樹的二叉鏈表類型定義如下：

typedef struct node {

DataType data；

struct node *lchild, *rchild;

} BinNode;

typedef BinNode *BinTree；

閱讀下列算法,并回答問題：

void f31（BinTree BT）

{ BinNode *s;

if （BT）

{ s=BT->lchild；

BT->lchild=BT->rchild;

BT->rchild=s；

f31（BT->lchild）；

f31（BT->rchild）；

}

}

（1）該算法的功能是什么？

（2）以下算法功能是否等價(jià)于上面的算法？

void f3la（BinTree BT）

{ BinNode *s;

if（BT）

{ f31a（BT->lchild）；

f31a（BT->rchild）；

s=BT->lchild;

BT->lchild=BT->rchild;

BT->rchild=s；

}

}

32.單鏈表類型定義如下：

typedef struct node {

int data;

struct node *next;

} ListNode;

typedef ListNode *LinkList;

用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)待排數(shù)據(jù),鏈表頭指針為head。下列直接選擇排序算法對(duì)鏈表按升序進(jìn)行排序,請(qǐng)?jiān)诖痤}紙相應(yīng)位置填寫適當(dāng)內(nèi)容使算法完整。

void f32（LinkList head）

{ ListNode *p, *q, *r;

int tmp;

p=head;

while（p）

{ q=p；

r=->next;

while（ (1) ）

{ if（ (2) ） q=r；

r=r->next;

}

tmp=q->data;

q->data=p->data;

p->data=tmp;

p= (3) ；

}

}

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

typedef struct{

KeyType key;

InfoType otherinfo;

}NodeType;

typedef NodeType SeqList［n+l］;

int f33（SeqList R, int low, int high, KeyType K）

{ int mid;

if（low>high）

return 0；

mid= （1） ；

if（R［mid］.key==K）

return （2） ；

if（R［mid］.key<K）

f33（R, mid+l, high, K）；

else

(3) ；

}

五、算法設(shè)計(jì)題（本題10分）

34.單鏈表類型定義如下：

typedef struct node {

int data;

struct node *next;

} ListNode;

typedef ListNode *LinkList;

設(shè)計(jì)算法在帶頭結(jié)點(diǎn)的單鏈表L中刪除數(shù)據(jù)值最小的結(jié)點(diǎn)（設(shè)鏈表中各結(jié)點(diǎn)數(shù)據(jù)值

均不相同）。函數(shù)的原型為：void f34（LinkList L）