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

數(shù)據(jù)結(jié)構(gòu)年月真題

02331201710

1、【單選題】下列選項(xiàng)中，與數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)直接相關(guān)的是

線性表

雙向鏈表

A:

二叉樹

B:

有向圖

C:

答D:案：B

解析：雙向鏈表的每個(gè)節(jié)點(diǎn)中儲(chǔ)存有兩個(gè)指針，這兩個(gè)指針分別指向前一個(gè)節(jié)點(diǎn)的地址和

后一個(gè)節(jié)點(diǎn)的地址，這樣無論通過那個(gè)節(jié)點(diǎn)都能夠?qū)ふ业狡渌墓?jié)點(diǎn)。線性表、二叉樹和

有向圖需要查找某一個(gè)元素時(shí)，都必須從第一個(gè)元素開始進(jìn)行查找。

2、【單選題】將12個(gè)數(shù)據(jù)元素保存在順序表中，若第一個(gè)元素的存儲(chǔ)地址是100，第二個(gè)

元素的存儲(chǔ)地址是105，則該順序表最后一個(gè)元素的存儲(chǔ)地址是

111

144

A:

155

B:

156

C:

答D:案：C

解析：線性表的第i個(gè)元素ai的存儲(chǔ)位置LOC(ai)=LOC(ai)+(i-1)*d,所以第12個(gè)元素

的地址=100+（12-1）*5=155

3、【單選題】設(shè)棧的初始狀態(tài)為空,元素1,2,3,4,5,6依次入棧,棧的容量是3,能夠得

到的出棧序列是

1,2,6,4,3,5

2,4,3,6,5,1

A:

3,1,2,5,4,6

B:

3,2,6,5,1,4

C:

答D:案：B

解析：棧的特點(diǎn)：后進(jìn)先出，且容量為3.答案B的順序?yàn)椋?進(jìn)，2進(jìn)，2出，3進(jìn)，4

進(jìn)，4出，3出，5進(jìn)，6進(jìn)，6出，5出，1出。

4、【單選題】設(shè)指針變量head指向非空單循環(huán)鏈表的頭結(jié)點(diǎn),指針變量p指向終端結(jié)點(diǎn),

next是結(jié)點(diǎn)的指針域,則下列邏輯表達(dá)式中,值為真的是

p->next->next==head

p->next==head

A:

p->next->next==NULL

B:

p->next==NULL

C:

答D:案：B

解析：循環(huán)單鏈表的特點(diǎn)就是最后一個(gè)結(jié)點(diǎn)的指針不為空，而是指向鏈表的頭結(jié)點(diǎn)。

5、【單選題】已知廣義表LS=(((a,b)),((c,(d))）,(e,f))),(g,h)),LS的深度是

2

3

A:

4

B:

5

C:

答D:案：C

解析：一個(gè)表展開后所含括號(hào)的層數(shù)稱為廣義表的深度。即表中每個(gè)元素的括號(hào)匹配數(shù)加

1

6、【單選題】已知一棵高度為4的完全二叉樹T共有5個(gè)葉結(jié)點(diǎn),則T中結(jié)點(diǎn)個(gè)數(shù)最少是

9

10

A:

11

B:

12

C:

答D:案：A

解析：深度為4的二叉樹，其前3層是一棵滿二叉樹，至少得有7個(gè)結(jié)點(diǎn)，而題目中結(jié)出

有5個(gè)是葉子結(jié)點(diǎn)，那么第三層的結(jié)點(diǎn)中得有一個(gè)得有左右子結(jié)點(diǎn)，這要T中結(jié)點(diǎn)個(gè)數(shù)至

少是9個(gè)。

7、【單選題】在一棵非空二叉樹的中序遍歷序列中，所有列在根結(jié)點(diǎn)前面的是

左子樹中的部分結(jié)點(diǎn)

左子樹中的全部結(jié)點(diǎn)

A:

右子樹中的部分結(jié)點(diǎn)

B:

右子樹中的全部結(jié)點(diǎn)

C:

答D:案：B

解析：中序遍歷二叉樹的操作：1.中序遍歷左子樹2.訪問根結(jié)點(diǎn)3.中序遍歷右子樹。

8、【單選題】用鄰接矩陣表示有n個(gè)頂點(diǎn)和e條邊的無向圖，采用壓縮方式存儲(chǔ)，矩陣中零

元素的個(gè)數(shù)是

n(n+1)/2-e

n(n+1)/2—2e

A:

n×n-e

B:

n×n一2e

C:

答D:案：A

解析：有n個(gè)頂點(diǎn)的無向圖的鄰接矩陣一共有n*n個(gè)元素，由于是對(duì)稱矩陣，采用壓縮存

儲(chǔ)，共存儲(chǔ)n(n+1)/2個(gè)元素，其中只有e個(gè)元素是非零元素，其他都是零元素，共

n(n+1)/2-e個(gè)。

9、【單選題】無向圖G中所有頂點(diǎn)的度數(shù)之和是20，則G中的邊數(shù)是

10

20

A:

30

B:

40

C:

答D:案：A

解析：一條邊是2度，20除以2等于10條邊。

10、【單選題】設(shè)有向圖G含有n個(gè)頂點(diǎn)、e條邊，使用鄰接表存儲(chǔ)。對(duì)G進(jìn)行廣度優(yōu)先遍

歷的算法的時(shí)間復(fù)雜度是

O(n)

O(e)

A:

O(n+e)

B:

O(n×e)

C:

答D:案：C

解析：鄰接表存儲(chǔ)的有向圖進(jìn)行廣度優(yōu)先遍歷的時(shí)間復(fù)雜度與圖中的頂點(diǎn)個(gè)數(shù)以及邊數(shù)都

相關(guān)

11、【單選題】對(duì)數(shù)據(jù)序列（25，15，7，18，10，0，4）采用直接插入排序進(jìn)行升序排

序，兩趟排序后，得到的排序結(jié)果為

0，4，7，18，10，25，15

A:

O，4，25，15，7，18，10

7，15，10，O，4，18，25

B:

7，15，25，18，10，O，4

C:

答D:案：D

解析：初始【25】【15，7，18，10，0，4】第一趟【15，25】【7，18，10，0，4】第二

趟【7，15，25】【18，10，0，4】

12、【單選題】下列排序方法中，穩(wěn)定的排序方法是

希爾排序

歸并排序

A:

堆排序

B:

快速排序

C:

答D:案：B

解析：這個(gè)題考查各種排序方法的穩(wěn)定性，教材190頁(yè)內(nèi)部排序方法的分析與比較中總結(jié)

到，直接插入、冒泡、歸并、基數(shù)排序算法是穩(wěn)定的，直接選擇、希爾、快速、堆排序算

法是不穩(wěn)定的

13、【單選題】一組記錄的關(guān)鍵碼為(45，68，57，13，24，89)，利用堆排序算法進(jìn)行升序

排序，建立的初始堆為

68，45，57，13，24，89

89，68，57，13，24，45

A:

89，68，57，45，24，13

B:

89，57，68，24，45，13

C:

答D:案：B

解析：

根據(jù)教材183頁(yè)堆排序定義，建堆過程如下：

14、【單選題】一棵二叉排序樹中，關(guān)鍵字n所在結(jié)點(diǎn)是關(guān)鍵字m所在結(jié)點(diǎn)的祖先，則

n一定大于m

n一定小于m

A:

n一定等于m

B:

C:

n與m的大小關(guān)系不確定

答D:案：D

解析：由二叉排序樹定義可知，其右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值，則左子樹上

所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值，因?yàn)轭}目中m和n并沒有給出是左子樹還是右子樹，所

以大小關(guān)系不確定。

15、【單選題】設(shè)散列表長(zhǎng)m=14，散列函數(shù)H（key）=key％11。表中己保存4個(gè)關(guān)鍵字：

addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址均為空。保存關(guān)鍵字49時(shí)存

在沖突，采用線性探查法來處理。則查找關(guān)鍵字49時(shí)的探查次數(shù)是

1

2

A:

4

B:

8

C:

答D:案：C

解析：h(49)=5,散列地址5已經(jīng)被占，因此探查h1=(5+1)%11=6,但散列地址6也已經(jīng)被

占，再探查h2=(6+1)%11=7,散列地址7也被占了，再探查h3=(7+1)%11=8,此地址是開放

的，可將49插入。

16、【問答題】設(shè)電文字符集是{e1，e2，e3，e4，e5}，它們出現(xiàn)的次數(shù)分別為：{50，

10，16，8，12}。現(xiàn)要為該字符集設(shè)計(jì)哈夫曼編碼。請(qǐng)回答下列問題。（1）畫出得到的哈夫

曼樹。（2）給出各符號(hào)的哈夫曼編碼。

答案：

解析：

（1）哈夫曼樹構(gòu)造過程：（2）哈夫曼樹左分支表示0，右分支表示1.以

根結(jié)點(diǎn)到葉結(jié)點(diǎn)路徑上的分支字符組成的串作為該葉結(jié)點(diǎn)的字符編碼。

17、【問答題】己知圖G采用鄰接矩陣存儲(chǔ)，鄰接矩陣如題27圖所示。

（1）寫出從頂點(diǎn)A開始圖G

的3個(gè)不同的深度優(yōu)先搜索遍歷序列。（2）寫出從頂點(diǎn)A開始圖G的2個(gè)不同的廣度優(yōu)

先搜索遍歷序列。

答案：(1)ABCEGDFACEGBDFADFGBCE(2)ABCDEFGADCBFEG

解析：

根據(jù)鄰接矩陣可以畫出這個(gè)有向圖（因?yàn)椴皇菍?duì)稱矩陣），由深度優(yōu)先遍歷和廣度優(yōu)先遍

歷的含義，可以寫出出答案，答案不是唯一的。

18、【問答題】有以下數(shù)據(jù)序列（19,14,23,01,68,20,84,27,55,11,10,79,12),使用希爾排

序方法將其排成升序序列。請(qǐng)回答下列問題。（1）寫出增量為4時(shí)對(duì)上述數(shù)據(jù)序列進(jìn)行一趟

希爾排序的結(jié)果。（2）給出一個(gè)可行的希爾排序增量序列。

答案：（1）12，11，10，01，19，14，23，27，55，20，84，79，68（2）4，2，1

解析：教材171頁(yè)希爾排序的思想，需要取一個(gè)小于n的整數(shù)做為第一個(gè)增量，因?yàn)樵隽?/p>

的不確定性，所以本題的答案也不唯一，如果增量序列是遞減，且最后一個(gè)增量為1也是

正確的。

19、【問答題】設(shè)有二叉排序樹如題29圖所示。請(qǐng)回答下列問題。

（1）假定二叉排序樹初始為

空，寫出一個(gè)數(shù)據(jù)輸入序列，按序插入時(shí)能得到題29圖所示的二叉排序樹。（2）能得到

題29圖所示的二叉排序樹的不同的輸入數(shù)據(jù)序列有幾個(gè)？

答案：（1）agebfdc；（2）4個(gè)

解析：從上到下遍歷，有左右子樹，則會(huì)有本同的序列。本題：遍歷可以得到agebfdc。

以e為根的樹有左右子樹，其左右子樹之間序列位置可以調(diào)換。遍歷能得到題29圖所示

的二叉排序樹的不同的輸入數(shù)據(jù)序列agebfdc；agebdfc；agebdcf；agefbdc；共四個(gè)。

20、【問答題】順序表類型定義如下：

閱讀下列算法，并回答問題。

（1）若SL1-＞data中的數(shù)據(jù)

為｛25,4,256,9，-38,47,128,256,64},SL2-＞data中的數(shù)據(jù)為｛22,4，-

63,15,29,34,42,3}，則執(zhí)行算法f30(&SL1,&SL2）后SL1-＞data和SL2-＞data中的數(shù)據(jù)

各是什么？（2）該算法的功能是什么？

答案：（1）SL1-＞data中的數(shù)據(jù)為｛25,4,256,15，29，47，128，256，64},SL2-＞data

中的數(shù)據(jù)為｛22,4，-63,9，-38，34，42，3}（2）該算法的功能是比較兩個(gè)線性表中相

同下標(biāo)位置的兩個(gè)元素，較大者放到較長(zhǎng)的線性表中，較小者放到較短的線性表中。

解析：該算法的功能是比較兩個(gè)線性表中相同下標(biāo)位置的兩個(gè)元素，較大者放到較長(zhǎng)的線

性表中，較小者放到較短的線性表中。

21、【問答題】二叉樹的存儲(chǔ)結(jié)構(gòu)類型定義如下：

（1）設(shè)二叉樹T如題31圖所

示，給出執(zhí)行A31（T）的輸出結(jié)果。

（2）給出該算法的時(shí)間復(fù)雜

度。

答案：(1)ACCABB;(2)O(n),n是二叉樹中所含結(jié)點(diǎn)個(gè)數(shù)。

解析：訪問C時(shí)候也要執(zhí)行兩遍printf，訪問完C還要在打印A本身一次再訪問B，訪問

B時(shí)候也要執(zhí)行兩遍printf。

22、【問答題】待排序記錄的數(shù)據(jù)類型定義如下：

下列算法實(shí)現(xiàn)自底向上、自頂

向下交替進(jìn)行的雙向掃描冒泡排序，請(qǐng)?jiān)诳瞻滋幪钌线m當(dāng)內(nèi)容使算法完整。

答案：（1）j>=i+1;j--;(2)j=j+1;j<n-i+1;(3)i=i+1

解析：教材174頁(yè)冒泡排序算法原題，第一個(gè)空是自底向上掃描，第二個(gè)空是自頂向下掃

描。

23、【問答題】二叉樹的存儲(chǔ)結(jié)構(gòu)類型定義如下：

（1）設(shè)二叉排序樹T如題33

圖所示，bt是指向根結(jié)點(diǎn)的指針。給出執(zhí)行A33(bt,6,100,0）的輸出結(jié)果。

（2）給出該算法的功能。

答案：

解析：該算法的功能從是T中找出所有滿足大于等于K1且小于等于k2的元素，并按升序

輸出。這里K1是6，key是20，K2是100，那么就是把大于等6小于等于100的結(jié)點(diǎn)按升

序輸出

24、【問答題】己知二叉樹的存儲(chǔ)結(jié)構(gòu)類型定義如下：

編寫遞歸算法，對(duì)于給定的一

棵二叉樹T，將其修改為鏡像二叉樹。例如，題34圖所示的兩棵二叉樹互為鏡像二叉樹。

函數(shù)的原型為：void

f34(BinTreeT);

答案：voidf34(BinTreeT){BinNode*s;If(BT){s=BT->lchild;BT->lchild=BT-

>rchild;BT->rchild=s;f34(BT->lchild);f34(BT->rchild);}}

解析：先設(shè)置一個(gè)中間變量s,用來存放左子樹的值，然后把右子樹的值交換給左子樹，再

讓右子樹獲得中間變量s值，這樣做到左右子樹結(jié)結(jié)點(diǎn)值互換，左右子樹分別遞歸，最后

完成鏡像。

25、【填空題】數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)

______________。

答案：無關(guān)

解析：數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)，是獨(dú)立于計(jì)

算機(jī)的

26、【填空題】指針P和指針q分別指向單鏈表L中的兩個(gè)相鄰結(jié)點(diǎn)，即q->next=p，且p

所指結(jié)點(diǎn)不是終端結(jié)點(diǎn)。若要?jiǎng)h除P所指結(jié)點(diǎn)，則執(zhí)行的語(yǔ)句是______________。

答案：q->next=p->next

解析：q的下個(gè)結(jié)點(diǎn)是p，如果刪除P，那么只能讓P的下個(gè)結(jié)點(diǎn)當(dāng)q的下個(gè)結(jié)點(diǎn)。

27、【填空題】一個(gè)直接或間接調(diào)用自己的函數(shù)稱為______________。

答案：遞歸函數(shù)

解析：教材71頁(yè)遞歸函數(shù)定義，一個(gè)直接或間接調(diào)用自己的函數(shù)稱為遞歸函數(shù)。

28、【填空題】廣義表(a，(b，c，d)，e，f，(g，h))的表尾是______________。

答案：((b，c，d)，e，f，(g，h))

解析：當(dāng)表為非空時(shí)，稱第一個(gè)元素是表頭，其余元素組成的表稱為表尾。本題中(a)是

表頭，((b，c，d)，e，f，(g，h))為表尾。

29、【填空題】二叉樹的前序遍歷序列和后序遍歷序列中，葉結(jié)點(diǎn)之間的相對(duì)次序

______________。

答案：不變

解析：根據(jù)三種遍歷的次序和特點(diǎn)：前序是根左右、中序是左根右、后序是左右根,因此

相對(duì)次序發(fā)生變化的都是子樹的根

30、【填空題】如果圖G存在拓?fù)渑判蛐蛄?，則G必為______________。

答案：有向無環(huán)圖

解析：教材163頁(yè)：對(duì)一個(gè)有向無環(huán)圖G進(jìn)行拓?fù)渑判?，是將G中所有頂點(diǎn)排成一個(gè)線性

序列，使得圖中任意一對(duì)頂點(diǎn)u和v，若邊(u,v)∈E(G)，則u在線性序列中出現(xiàn)在v之

前。通常，這樣的線性序列稱為簡(jiǎn)稱拓?fù)湫蛄小?/p>

31、【填空題】將一棵樹T轉(zhuǎn)換為一棵二叉樹T1，在Tl中結(jié)點(diǎn)A是結(jié)點(diǎn)B的父結(jié)點(diǎn)，則在

T中A可能是B的父結(jié)點(diǎn)或________