?數據結構自考2015年4月真題

數據結構自考2015年4月真題及答案解析

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

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

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

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

C.

D.

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

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

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

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的數組實現循環隊列，若當前rear=0，front=3。當從隊列中出隊一個元素，再入隊兩個元素后，rear和front的值分別是(　　)

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

5.二維數組a[10][20]按行優先順序存放在連續的存儲空間中，元素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.以二叉鏈表作為二叉樹的存儲結構，在有n(n>0)個結點的二叉鏈表中，空指針域的個數是(　　)

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

8.構造一棵含n個葉結點的哈夫曼樹，樹中結點總數是(　　)

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

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

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

10. 下列關于有向無環圖G的拓撲排序序列的敘述中，正確的是(　　)

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

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

A.

B.

C.

D.

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

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

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

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

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

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

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

A.根結點可以只有一個關鍵字
B.所有葉結點都必須在同一層上
C.每個結點內最多有m棵子樹
D.每個結點內最多有m個關鍵字

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

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

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

13.一個線性表如果需要頻繁地增刪元素，則存儲結構應該選擇_________。

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

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

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

17.用矩陣作為圖的存儲結構，該矩陣稱為圖的_________。

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

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

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

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

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

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

23.已知散列函數為H(key)=key%11，現將關鍵字序列{23，27，34，56，58，10，18，120)散列到散列表HT(0…10)中，利用線性探查法解決沖突。回答下列問題。(1)畫出最后的散列表;(2)求在等概率情況下查找成功時的平均查找長度。

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

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

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

32.下列函數的功能是在帶頭結點的單鏈表head中刪除所有數據域值為X的結點，請 在空白處填上適當的語句，使其完成指定功能。

33.下列函數的功能是：在帶頭結點的單鏈表上進行選擇排序。請在空白處填上適當內 容將函數補充完整，并說明該算法是否是穩定的。

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

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

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