?數(shù)據(jù)結(jié)構(gòu)自考2016年4月真題

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

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

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

1.下列選項(xiàng)中，屬于非線性數(shù)據(jù)結(jié)構(gòu)的是(　　)

A.隊列
B.棧
C.二叉排序樹
D.線性表

2.瑞士計算機(jī)科學(xué)家沃思教授曾指出：算法+數(shù)據(jù)結(jié)構(gòu)=程序。這里的數(shù)據(jù)結(jié)構(gòu)指的是(　　)

A.數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)
B.數(shù)據(jù)的線性結(jié)構(gòu)和非線性結(jié)構(gòu).
C.數(shù)據(jù)的緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)
D.數(shù)據(jù)的順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)

3.線性表順序存儲時，邏輯上相鄰的兩個數(shù)據(jù)元素，其存儲地址 (　　)

A.—定相鄰
B.—定不相鄰
C.不一定相鄰
D.可能不相鄰

4.數(shù)據(jù)元素1,2,3,4,5依次入棧，則不可能得到的出棧序列是(　　)

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

5.設(shè)順序表首元素A[0]的存儲地址是4000,每個數(shù)據(jù)元素占5個存儲單元,則元素 A[20]的起始存儲地址是(　　)

A.4005
B.4020
C.4100
D.4105

6.廣義表A=(a,(b,c, (e,f)))，函數(shù)head(head(tail(A)))的運(yùn)算結(jié)果是(　　)

A.a
B.b
C.c
D.e

7.設(shè)髙度為h的二叉樹中， 只有度為0和2的結(jié)點(diǎn)， 則此類二叉樹包含的結(jié)點(diǎn)數(shù)至少 是(　　)

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

8.一棵非空二叉樹T的前序遍歷和后序遍歷序列正好相反,則T—定滿足(　　)

A.所有結(jié)點(diǎn)均無左孩子
B.所有結(jié)點(diǎn)均無右孩子
C.只有一個葉子結(jié)點(diǎn)
D.是一棵滿二叉樹

9.設(shè)圖的鄰接矩陣A如下所示。各頂點(diǎn)的度依次是(　　)

A.1,2,1,2
B.2,2,1, 1
C.3,4,2,3
D.4,4,2,2

10.無向圖G如題10圖所示，從頂點(diǎn)a開始進(jìn)行深度優(yōu)先遍歷，下列遍歷序列中，正確的是(　　)

A.a, b, e, c, d, f
B.a, c, f,e,d, b
C.a,c,b, e,f,d
D.a, e,d, f,c,b

11.設(shè)帶權(quán)連通圖G中含有n(≥1)個頂點(diǎn)，下列關(guān)于g的最小生成樹T的敘述中， 正確的是(　　)

A.T中可能含有回路
B.T中含有圖g的所有邊
C.T是唯一的，且含有n-1條邊
D.T可能不唯一，但權(quán)一定相等

12.若要求對序列進(jìn)行穩(wěn)定的排序，則在下列選項(xiàng)中應(yīng)選擇(　　)

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

13.下列排序算法中，空間復(fù)雜度最差的是(　　)

A.歸并排序
B.希爾排序
C.冒泡排序
D.堆排序

14.下列排序算法中，初始數(shù)據(jù)有序時，花費(fèi)的時間反而更多的算法是(　　)

A.插入排序
B.冒泡排序
C.快速排序
D.希東排序

15.對線性表L進(jìn)行二分查找時,要求L必須滿足(　　)

A.以順序方式存儲
B.以順序方式存儲，且數(shù)據(jù)元素有序
C.以鏈接方式存儲
D.以鏈接方式存儲，且數(shù)據(jù)元素有序

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

11.下面程序段的時間復(fù)雜度是________。i=1;while(i<n)i=i*2

12.在單鏈表的p結(jié)點(diǎn)之后插入s結(jié)點(diǎn)的操作是________。

13.只能在線性表的兩端進(jìn)行插入或刪除操作的兩種邏輯結(jié)構(gòu)分別是________。

14.廣義表A=(x,(y,z,(u,v,w)))的長度是________。

15.一棵樹的后序遍歷序列與其對應(yīng)的二叉樹的________序遍歷序列相同

16.在有向圖、無向圖中,其鄰接矩陣一定對稱的是________。

17.要計算圖中從某一頂點(diǎn)出發(fā)到其余各頂點(diǎn)的最短路徑,可選用________算法。

18.設(shè)關(guān)鍵字序列為28,72,97,63,4,53,84,使用希爾排序法將其排成升序序列,若第一趟采用的間隔是3,則該趟排序的結(jié)果是________。

19. 對具有15個關(guān)鍵字的關(guān)鍵字序列進(jìn)行順序查找時,查找成功的平均查找長度為_______。

110.在二又排序樹的查找過程中,若當(dāng)前結(jié)點(diǎn)的關(guān)鍵字值大于待查找關(guān)鍵字,則應(yīng)在該________結(jié)點(diǎn)的子樹上繼續(xù)查找。

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

21.設(shè)Q是有N個存儲空間的循環(huán)隊列,初始狀態(tài)font=rear=0,約定指針rear指向的單元始終為空。定義如下：#define N 100typedef struct {        char data[N];         int front, rear;}CQ:CQ*Q:(1)寫出清空隊列的語句序列;(2)寫出判斷隊列為滿的表達(dá)式;(3)給出計算隊列長度L的表達(dá)式。

22.已知4×5稀疏矩陣M按行優(yōu)先順序存儲的三元組表如下：(1)寫出矩陣M;(2)給出矩陣M的轉(zhuǎn)置矩陣T按行優(yōu)先順序存儲的三元組表。

23.給定一組權(quán)值數(shù)據(jù){3,8,9,11,4},回答下列問題。(1)畫出基于所給數(shù)據(jù)的一棵哈夫曼樹;(2)計算所得哈夫曼樹的帶權(quán)路徑長度WPL。

24.已知有向圖G=(V,E)，其中={v1,v2,v3,v4,v5,v6,v7}，E={<v1,v2>,<v1,v3>,<v1,v4>,<v2,v5>,<v3,v5>,<v3,v6>,<v4,v6>,<v5,v7>,<v6,v7>}。(1)畫出有向圖G:(2)判斷圖G是否存在拓?fù)渑判蛐蛄?若不存在請說明理由;若存在請給出一個拓?fù)渑判蛐蛄小?/p>

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

31.閱讀程序f0。int f30( int A[], int n){    int m;     if (n<=0) return=-1;      if(n==0 )retum=0      m=f30(A,n-1);"    if(A[m]>A[n-1]) return m;else return n-1;}已知線性表A={25,34,256,9,38,47,128,256,64}。(1)若主函數(shù)調(diào)用語句為f30(A,5),f30的返回值是多少?(2)若主函數(shù)調(diào)用語句為f30(A,9),f30的返回值是多少?(3)給出算法f30的功能。

32.已知棧的基本操作定義如下,請在空白處填寫適當(dāng)內(nèi)容,完成相應(yīng)的功能。  typedef struct { //棧定義       char data[ Stack Size];        int top;} SeqStack;SeqStack s;void InitStack( SeqStack *s)    //棧初始化  {         s->top=-1;}int StackEmpty( SeqStack *s)    //判棧是否為空{(diào)      retum ____(1)_____;}    int StackFull( SeqStack *s)   //棧是否為滿{        retum s->top== StackSize-1; }  char push( SeqStack*s, char c)      //入棧操作{       if( Stack Full( s ))          return ‘