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

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

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

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

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

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

2.若對(duì)某線性表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，要使操作時(shí)間最少，下列選項(xiàng)中，應(yīng)選擇的存儲(chǔ)結(jié)構(gòu)是( )

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

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

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

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

A.n-i
B.n-i+1
C.n-i+2
D.無(wú)法確定

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

A.串復(fù)制
B.串比較
C.子串定位
D.子串鏈接

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

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

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

A.樹(shù)中沒(méi)有度為2的結(jié)點(diǎn)
B.樹(shù)中只有一個(gè)根結(jié)點(diǎn)
C.樹(shù)中非葉結(jié)點(diǎn)均只有左子樹(shù)
D.樹(shù)中非葉結(jié)點(diǎn)均只有右子樹(shù)

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

A.n

B.

C.

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

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

10.下圖G=(V,E)是一個(gè)帶權(quán)連通圖，G的最小生成樹(shù)的權(quán)為( )

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

11.在下圖中，從頂點(diǎn)1出發(fā)進(jìn)行深度優(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.如果在排序過(guò)程中不改變關(guān)鍵字相同元素的相對(duì)位置，則認(rèn)為該排序方法是( )

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

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

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

14.已知二叉樹(shù)結(jié)點(diǎn)關(guān)鍵字類(lèi)型為字符，下列二叉樹(shù)中符合二叉排序樹(shù)性質(zhì)的是( )

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

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

二、填空題(本大題共10小題，每小題2分，共20分) 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。

11.下面程序段的時(shí)間復(fù)雜度為_(kāi)__________。sum=1;for(i=0;sum <n;i++)sum+=1;

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

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

14.3個(gè)結(jié)點(diǎn)可以組成___________種不同樹(shù)型的二叉樹(shù)。

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

16.若無(wú)向圖G中有n個(gè)頂點(diǎn)m條邊，采用鄰接矩陣存儲(chǔ)，則該矩陣中非0元素的個(gè)數(shù)為_(kāi)__________。

17.影響排序效率的兩個(gè)因素是關(guān)鍵字的___________次數(shù)和記錄的移動(dòng)次數(shù)。

18.對(duì)任一m階的B樹(shù)，每個(gè)結(jié)點(diǎn)中最多包含___________個(gè)關(guān)鍵字。

19.若兩個(gè)關(guān)鍵字通過(guò)散列函數(shù)映射到同一個(gè)散列地址，這種現(xiàn)象稱(chēng)為_(kāi)__________。

110.如果要為文件中的每個(gè)記錄建立一個(gè)索引項(xiàng)，則這樣建立的索引表稱(chēng)為_(kāi)__________。

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

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

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

23.已知二叉樹(shù)如下：請(qǐng)畫(huà)出該二叉樹(shù)對(duì)應(yīng)的森林。

24.請(qǐng)回答下列問(wèn)題：(1)英文縮寫(xiě)DAG的中文含義是什么?(2)請(qǐng)給出下面DAG圖的全部拓?fù)渑判颉?img src="https://status.shangxueba.com/exam/2019-03-21/922009207811804.png" width="475" height="115"/>

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

1.已知線性表(a1,a2,a3...，an)按順序存放在數(shù)組a中，每個(gè)元素均為整數(shù)，下列程序的功能是將所有小于0的元素移到全部大于等于0的元素之前。例如，有7個(gè)整數(shù)的原始序列為(x,x,-x,-x,x,x,-x)，變換后數(shù)組中保存的序列是(-x,-x,-x,x,x,x,x)。請(qǐng)?jiān)诔绦蛱幪钊牒线m的內(nèi)容，使其成為完整的算法。

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

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

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

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

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