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

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

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

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

1.數(shù)據(jù)的四種存儲結(jié)構(gòu)是( )

A.順序存儲結(jié)構(gòu)、鏈接存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)和散列存儲結(jié)構(gòu)
B.線性存儲結(jié)構(gòu)、非線性存儲結(jié)構(gòu)、樹型存儲結(jié)構(gòu)和圖型存儲結(jié)構(gòu)
C.集合存儲結(jié)構(gòu)、一對一存儲結(jié)構(gòu)、一對多存儲結(jié)構(gòu)和多對多存儲結(jié)構(gòu)
D.順序存儲結(jié)構(gòu)、樹型存儲結(jié)構(gòu)、圖型存儲結(jié)構(gòu)和散列存儲結(jié)構(gòu)

2.若對某線性表最常用的操作是在最后一個結(jié)點之后插入一個新結(jié)點或刪除最后一個結(jié)點，要使操作時間最少，下列選項中，應選擇的存儲結(jié)構(gòu)是( )

A.無頭結(jié)點的單向鏈表
B.帶頭結(jié)點的單向鏈表
C.帶頭結(jié)點的雙循環(huán)鏈表
D.帶頭結(jié)點的單循環(huán)鏈表

3.若帶頭結(jié)點的單鏈表的頭指針為head，則判斷鏈表是否為空的條件是( )

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

4.若元素的入棧順序為1，2，3....，n，如果第2個出棧的元素是n，則輸出的第i(1<=i<=n)個元素是( )

A.n-i
B.n-i+1
C.n-i+2
D.無法確定

5.串匹配算法的本質(zhì)是( )

A.串復制
B.串比較
C.子串定位
D.子串鏈接

6.設有一個10階的對稱矩陣A，采用行優(yōu)先壓縮存儲方式，a11為第一個元素，其存儲地址為1，每個元素占一個字節(jié)空間，則a85的地址為( )

A.13
B.18
C.33
D.40

7.若一棵二叉樹的前序遍歷序列與后序遍歷序列相同，則該二叉樹可能的形狀是( )

A.樹中沒有度為2的結(jié)點
B.樹中只有一個根結(jié)點
C.樹中非葉結(jié)點均只有左子樹
D.樹中非葉結(jié)點均只有右子樹

8.若根結(jié)點的層數(shù)為1，則具有n個結(jié)點的二叉樹的最大高度是( )

A.n

B.

C.

9.在圖G中求兩個結(jié)點之間的最短路徑可以采用的算法是( )

A.迪杰斯特拉(Dijkstra)算法
B.克魯斯卡爾(Kruskal)算法
C.普里姆(Prim)算法
D.廣度優(yōu)先遍歷(BFS)算法

10.下圖G=(V,E)是一個帶權連通圖，G的最小生成樹的權為( )

A.15
B.16
C.17
D.18

11.在下圖中，從頂點1出發(fā)進行深度優(yōu)先遍歷可得到的序列是( )

A.1 2 3 4 5 6 7
B.1 4 2 6 3 7 5
C.1 4 2 5 3 6 7
D.1 2 4 6 5 3 7

12.如果在排序過程中不改變關鍵字相同元素的相對位置，則認為該排序方法是( )

A.不穩(wěn)定的
B.穩(wěn)定的
C.基于交換的
D.基于選擇的

13.設有一組關鍵字(19, 14, 23, 1，6，20, 4，27, 5，11, 10, 9)，用散列函數(shù)H(key)=key%13構(gòu)造散列表，用拉鏈法解決沖突，散列地址為1的鏈中記錄個數(shù)為( )

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

14.已知二叉樹結(jié)點關鍵字類型為字符，下列二叉樹中符合二叉排序樹性質(zhì)的是( )

15.若需高效地查詢多關鍵字文件，可以采用的文件組織方式為( )

A.順序文件
B.索引文件
C.散列文件
D.倒排文件

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

11.下面程序段的時間復雜度為___________。sum=1;for(i=0;sum <n;i++)sum+=1;

12.已知鏈表結(jié)點定義如下：typedef struct node{char data[16];struct node *next;} LinkStrNode;如果每個字符占1個字節(jié)，指針占4個字節(jié)，則該鏈表的存儲密度是___________。

13.使用一個100個元素的數(shù)組存儲循環(huán)隊列，如果采取少用一個元素空間的方法來區(qū)別循環(huán)隊列的隊空和隊滿，約定隊頭指針front等于隊尾指針rear時表示隊空。若為front=8，rear=7，則隊列中的元素個數(shù)為___________。

14.3個結(jié)點可以組成___________種不同樹型的二叉樹。

15.用5個權值{3, 2，4，5，1}構(gòu)造的哈夫曼(Huffman)樹的帶權路徑長度是___________。

16.若無向圖G中有n個頂點m條邊，采用鄰接矩陣存儲，則該矩陣中非0元素的個數(shù)為___________。

17.影響排序效率的兩個因素是關鍵字的___________次數(shù)和記錄的移動次數(shù)。

18.對任一m階的B樹，每個結(jié)點中最多包含___________個關鍵字。

19.若兩個關鍵字通過散列函數(shù)映射到同一個散列地址，這種現(xiàn)象稱為___________。

110.如果要為文件中的每個記錄建立一個索引項，則這樣建立的索引表稱為___________。

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

21.要在[0..n-1]的向量空間中建立兩個棧stack1和stack2，請回答：(1)應該如何設計這兩個棧才能充分利用整個向量空間?(2)若stack1的棧頂指針為top1,stack2的棧頂指針為top2，如果需要充分利用整個向量空間，則： 棧stack1空的條件是：___________; 棧stack2空的條件是：___________; 棧stackl和棧stack2滿的條件是：___________。

22.已知廣義表如下：A=(B,y)B=(x，L)L=(a，b)要求：(1)寫出下列操作的結(jié)果 tail(A)=_______________. head(B)=______________。(2)請畫出廣義表A對應的圖形表示。

23.已知二叉樹如下：請畫出該二叉樹對應的森林。

24.請回答下列問題：(1)英文縮寫DAG的中文含義是什么?(2)請給出下面DAG圖的全部拓撲排序。

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

1.已知線性表(a1,a2,a3...，an)按順序存放在數(shù)組a中，每個元素均為整數(shù)，下列程序的功能是將所有小于0的元素移到全部大于等于0的元素之前。例如，有7個整數(shù)的原始序列為(x,x,-x,-x,x,x,-x)，變換后數(shù)組中保存的序列是(-x,-x,-x,x,x,x,x)。請在程序處填入合適的內(nèi)容，使其成為完整的算法。

2.閱讀下列程序，并回答問題：(1)寫出執(zhí)行該程序后的輸出結(jié)果;(2)簡述函數(shù)f31的功能。

3.下面程序?qū)崿F(xiàn)插入排序算法。在空白處填寫適當?shù)膬?nèi)容，使該程序功能完整。

4.設有單鏈表類型定義如下：typedef struct node{int data;struct node *next;} *LinkList;閱讀下列算法，并回答問題：

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

11.已知二叉樹的定義如下：typedef struct node{int data;struct node *lchild, *rchild;}*Bitptr;編寫遞歸算法求二叉樹的高度。函數(shù)原型為：int f34(Bitptr t);