APP
?數(shù)據(jù)結(jié)構(gòu)自考2016年4月真題
摘要：本試卷為單選題型，填空題，算法閱讀，算法設(shè)計(jì)等題型。
數(shù)據(jù)結(jié)構(gòu)自考2016年4月真題及答案解析
本試卷為單選題型，填空題，算法閱讀，算法設(shè)計(jì)等題型。
一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分) 在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。
1.下列選項(xiàng)中，屬于非線性數(shù)據(jù)結(jié)構(gòu)的是( )
A.隊(duì)列
B.棧
C.二叉排序樹
D.線性表
2.瑞士計(jì)算機(jī)科學(xué)家沃思教授曾指出：算法+數(shù)據(jù)結(jié)構(gòu)=程序。這里的數(shù)據(jù)結(jié)構(gòu)指的是( )
A.數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(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.線性表順序存儲(chǔ)時(shí)，邏輯上相鄰的兩個(gè)數(shù)據(jù)元素，其存儲(chǔ)地址 ( )
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]的存儲(chǔ)地址是4000,每個(gè)數(shù)據(jù)元素占5個(gè)存儲(chǔ)單元,則元素 A[20]的起始存儲(chǔ)地址是( )
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.只有一個(gè)葉子結(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)個(gè)頂點(diǎn)，下列關(guān)于g的最小生成樹T的敘述中， 正確的是( )
A.T中可能含有回路
B.T中含有圖g的所有邊
C.T是唯一的，且含有n-1條邊
D.T可能不唯一，但權(quán)一定相等
12.若要求對(duì)序列進(jìn)行穩(wěn)定的排序，則在下列選項(xiàng)中應(yīng)選擇( )
A.希爾排序
B.快速排序
C.直接插入排序
D.直接選擇排序
13.下列排序算法中，空間復(fù)雜度最差的是( )
A.歸并排序
B.希爾排序
C.冒泡排序
D.堆排序
14.下列排序算法中，初始數(shù)據(jù)有序時(shí)，花費(fèi)的時(shí)間反而更多的算法是( )
A.插入排序
B.冒泡排序
C.快速排序
D.希東排序
15.對(duì)線性表L進(jìn)行二分查找時(shí),要求L必須滿足( )
A.以順序方式存儲(chǔ)
B.以順序方式存儲(chǔ)，且數(shù)據(jù)元素有序
C.以鏈接方式存儲(chǔ)
D.以鏈接方式存儲(chǔ)，且數(shù)據(jù)元素有序
二、填空題(本大題共10小題，每小題2分，共20分) 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。
11.下面程序段的時(shí)間復(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)))的長(zhǎng)度是________。
15.一棵樹的后序遍歷序列與其對(duì)應(yīng)的二叉樹的________序遍歷序列相同
16.在有向圖、無向圖中,其鄰接矩陣一定對(duì)稱的是________。
17.要計(jì)算圖中從某一頂點(diǎn)出發(fā)到其余各頂點(diǎn)的最短路徑,可選用________算法。
18.設(shè)關(guān)鍵字序列為28,72,97,63,4,53,84,使用希爾排序法將其排成升序序列,若第一趟采用的間隔是3,則該趟排序的結(jié)果是________。
19. 對(duì)具有15個(gè)關(guān)鍵字的關(guān)鍵字序列進(jìn)行順序查找時(shí),查找成功的平均查找長(zhǎng)度為_______。
110.在二又排序樹的查找過程中,若當(dāng)前結(jié)點(diǎn)的關(guān)鍵字值大于待查找關(guān)鍵字,則應(yīng)在該________結(jié)點(diǎn)的子樹上繼續(xù)查找。
三、解答題(本大題共4小題，每小題5分，共20分)
21.設(shè)Q是有N個(gè)存儲(chǔ)空間的循環(huán)隊(duì)列,初始狀態(tài)font=rear=0,約定指針rear指向的單元始終為空。定義如下：#define N 100typedef struct { char data[N]; int front, rear;}CQ:CQ*Q:(1)寫出清空隊(duì)列的語句序列;(2)寫出判斷隊(duì)列為滿的表達(dá)式;(3)給出計(jì)算隊(duì)列長(zhǎng)度L的表達(dá)式。
22.已知4×5稀疏矩陣M按行優(yōu)先順序存儲(chǔ)的三元組表如下：
(1)寫出矩陣M;(2)給出矩陣M的轉(zhuǎn)置矩陣T按行優(yōu)先順序存儲(chǔ)的三元組表。
23.給定一組權(quán)值數(shù)據(jù){3,8,9,11,4},回答下列問題。(1)畫出基于所給數(shù)據(jù)的一棵哈夫曼樹;(2)計(jì)算所得哈夫曼樹的帶權(quán)路徑長(zhǎng)度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ù)渑判蛐蛄?若不存在請(qǐng)說明理由;若存在請(qǐng)給出一個(gè)拓?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.已知棧的基本操作定義如下,請(qǐng)?jiān)诳瞻滋幪顚戇m當(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 ‘