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

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

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

1.以下各階時間復(fù)雜度中，性能最優(yōu)的是(　　)

A.O(log2n)
B.O(n)

C.

D.

2.頭指針head指向帶頭結(jié)點的單循環(huán)鏈表。鏈表為空時下列選項為真的是(　　)

A.head!=Null
B.head==Null
C.head->next==Null
D.head->next==head

3.設(shè)棧的進(jìn)棧序列為a，b，c，d，e，經(jīng)過合理的出入棧操作后， 不能得到的出棧序列是(　　)

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

4.使用大小為6的數(shù)組實現(xiàn)循環(huán)隊列，若當(dāng)前rear=0，front=3。當(dāng)從隊列中出隊一個元素，再入隊兩個元素后，rear和front的值分別是(　　)

A.1和5
B.4和2
C.2和4
D.5和1

5.二維數(shù)組a[10][20]按行優(yōu)先順序存放在連續(xù)的存儲空間中，元素a[0] [0]的存儲地址為200，若每個元素占1個存儲空間，則元素a[6][2]的存儲地址是(　　)

A.226
B.322
C.341
D.342

6.廣義表A=(a(b，c，(e，f, g，h)))的深度是(　　)

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

7.以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，在有n(n>0)個結(jié)點的二叉鏈表中，空指針域的個數(shù)是(　　)

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

8.構(gòu)造一棵含n個葉結(jié)點的哈夫曼樹，樹中結(jié)點總數(shù)是(　　)

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

9.若圖G的鄰接表中有奇數(shù)個表結(jié)點，下列選項中，正確的是(　　)

A.G中必有奇數(shù)個頂點
B.G中必有偶數(shù)個頂點
C.G為無向圖
D.G為有向圖

10. 下列關(guān)于有向無環(huán)圖G的拓?fù)渑判蛐蛄械臄⑹鲋校_的是(　　)

A.存在且唯一
B.存在且不唯一
C.存在但可能不唯一
D.無法確定是否存在

11.對下圖進(jìn)行廣度優(yōu)先搜索遍歷，不能得到的遍歷序列是(　　)

A.

B.

C.

D.

12.下列排序方法中，效率較高且使用輔助空間最少的方法是(　　)

A.冒泡排序
B.快速排序
C.堆排序
D.歸并排序

13.下列排序方法中，平均比較次數(shù)最少的方法是(　　)

A.插入排序
B.快速排序
C.簡單選擇排序
D.歸并排序

14.對含有16個元素的有序表進(jìn)行二分查找，關(guān)鍵字比較次數(shù)最多是(　　)

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

15.下列敘述中，不符合m階B樹定義的是(　　)

A.根結(jié)點可以只有一個關(guān)鍵字
B.所有葉結(jié)點都必須在同一層上
C.每個結(jié)點內(nèi)最多有m棵子樹
D.每個結(jié)點內(nèi)最多有m個關(guān)鍵字

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

11.算法必須滿足可行性等五個準(zhǔn)則，其中_________的含義是：算法中每條指令的含義都必須明確，無二義性。

12.采用大0表示法時，常數(shù)階算法的時間復(fù)雜度記為_________。

13.一個線性表如果需要頻繁地增刪元素，則存儲結(jié)構(gòu)應(yīng)該選擇_________。

14.隊列Q中已有元素l，3，5，數(shù)據(jù)序列2，4，6，8，10依次入隊，再連續(xù)執(zhí)行6次出隊操作，得到的出隊序列是_________。

15.廣義表A=(a，(b，C，(e，f，g，h)))，head(tail(A))= _________。

16.一棵右子樹為空的二叉樹在后序線索化后，其空指針域的個數(shù)為_________。

17.用矩陣作為圖的存儲結(jié)構(gòu)，該矩陣稱為圖的_________。

18.普里姆(Prim)算法得到的是帶權(quán)連通圖的_________。

19.希爾排序方法使用的增量序列中，最后一個增量必須是_________。

110. 若待排序序列中的關(guān)鍵字基本有序，采用快速排序或直接插入排序時，效率較高的是_________。

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

21.順序棧的類型定義如下：typedef struct{      DataType data[MaxSize];         int top;}SeqStack;SeqStack S;規(guī)定棧底位置在MaxSize-1，請回答下列問題。(1)若要求?？諘r條件為真，則判斷?？盏臈l件表達(dá)式是什么?(2)若要求棧滿時條件為真，則判斷棧滿的條件表達(dá)式是什么?(3)用語句表示將X入棧的操作。

22.已知廣義表及結(jié)點類型結(jié)構(gòu)如下：typedef enum{ATOM, LIST}NodeTag;       //ATOM=0,表示原子;LIST=1,表示子表typedef struct GLNode{ NodeTag tag;     //區(qū)分原子結(jié)點和表結(jié)點     union{     DataType data;      //存放原子結(jié)點的值     GLNode *slink;       //指向子表的指針};GLNode *next;    //指向下一個表結(jié)點}*Glist; //廣義表類型請回答下列問題。(1)若廣義表A為空表，應(yīng)如何表示?(2)若廣義表A=(a，(b，c))，畫出A的存儲結(jié)構(gòu)。

23.已知散列函數(shù)為H(key)=key%11，現(xiàn)將關(guān)鍵字序列{23，27，34，56，58，10，18，120)散列到散列表HT(0…10)中，利用線性探查法解決沖突?；卮鹣铝袉栴}。(1)畫出最后的散列表;(2)求在等概率情況下查找成功時的平均查找長度。

24.給定帶權(quán)圖G如題29圖所示，使用迪杰斯特拉(Dijkstra)算法，求頂點vl到其他 各頂點的最短路徑，列出每條路徑上的各頂點及路徑長度。

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

31.設(shè)下列程序段中的數(shù)據(jù)皆為int型，請指出該程序段的功能是什么。

32.下列函數(shù)的功能是在帶頭結(jié)點的單鏈表head中刪除所有數(shù)據(jù)域值為X的結(jié)點，請 在空白處填上適當(dāng)?shù)恼Z句，使其完成指定功能。

33.下列函數(shù)的功能是：在帶頭結(jié)點的單鏈表上進(jìn)行選擇排序。請在空白處填上適當(dāng)內(nèi) 容將函數(shù)補(bǔ)充完整，并說明該算法是否是穩(wěn)定的。

34.閱讀程序，并回答下列問題。 假設(shè)順序表R的元素存放在下標(biāo)為l～8的數(shù)組元素中，K=7，low=1，high=8。(1)R的關(guān)鍵字依次為{1，2，3，4，5，6，7，8)，函數(shù)f33的返回值是多少?(2)R的關(guān)鍵字依次為{7，7，7，7，7，7，7，7)，函數(shù)f33的返回值是多少?(3)簡述函數(shù)的功能。

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

41.存儲二叉樹的二叉鏈表定義如下：ypedef struct node {       char data;       struct node *lchild, *rchild;} BinTNode;typedef BinTNode *BinTree;請編寫一個后序遍歷二叉樹的遞歸程序void PostOrder(BinTree root)，并輸出遍歷序列。其中root指向二叉樹根結(jié)點。