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

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

02331201710

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

線性表

雙向鏈表

A:

二叉樹

B:

有向圖

C:

答D:案：B

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

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

有向圖需要查找某一個元素時，都必須從第一個元素開始進行查找。

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

元素的存儲地址是105，則該順序表最后一個元素的存儲地址是

111

144

A:

155

B:

156

C:

答D:案：C

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

的地址=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

解析：棧的特點：后進先出，且容量為3.答案B的順序為：1進，2進，2出，3進，4

進，4出，3出，5進，6進，6出，5出，1出。

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

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

p->next->next==head

p->next==head

A:

p->next->next==NULL

B:

p->next==NULL

C:

答D:案：B

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

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

2

3

A:

4

B:

5

C:

答D:案：C

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

1

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

9

10

A:

11

B:

12

C:

答D:案：A

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

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

少是9個。

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

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

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

A:

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

B:

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

C:

答D:案：B

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

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

元素的個數(shù)是

n(n+1)/2-e

n(n+1)/2—2e

A:

n×n-e

B:

n×n一2e

C:

答D:案：A

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

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

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

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

10

20

A:

30

B:

40

C:

答D:案：A

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

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

歷的算法的時間復雜度是

O(n)

O(e)

A:

O(n+e)

B:

O(n×e)

C:

答D:案：C

解析：鄰接表存儲的有向圖進行廣度優(yōu)先遍歷的時間復雜度與圖中的頂點個數(shù)以及邊數(shù)都

相關(guān)

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

序，兩趟排序后，得到的排序結(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

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

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

法是不穩(wěn)定的

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

排序，建立的初始堆為

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頁堆排序定義，建堆過程如下：

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

n一定大于m

n一定小于m

A:

n一定等于m

B:

C:

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

答D:案：D

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

所有結(jié)點的值均小于根結(jié)點的值，因為題目中m和n并沒有給出是左子樹還是右子樹，所

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

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

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

在沖突，采用線性探查法來處理。則查找關(guān)鍵字49時的探查次數(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è)計哈夫曼編碼。請回答下列問題。（1）畫出得到的哈夫

曼樹。（2）給出各符號的哈夫曼編碼。

答案：

解析：

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

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

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

（1）寫出從頂點A開始圖G

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

先搜索遍歷序列。

答案：(1)ABCEGDFACEGBDFADFGBCE(2)ABCDEFGADCBFEG

解析：

根據(jù)鄰接矩陣可以畫出這個有向圖（因為不是對稱矩陣），由深度優(yōu)先遍歷和廣度優(yōu)先遍

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

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

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

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

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

解析：教材171頁希爾排序的思想，需要取一個小于n的整數(shù)做為第一個增量，因為增量

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

正確的。

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

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

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

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

答案：（1）agebfdc；（2）4個

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

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

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

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）該算法的功能是比較兩個線性表中相

同下標位置的兩個元素，較大者放到較長的線性表中，較小者放到較短的線性表中。

解析：該算法的功能是比較兩個線性表中相同下標位置的兩個元素，較大者放到較長的線

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

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

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

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

（2）給出該算法的時間復雜

度。

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

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

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

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

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

向下交替進行的雙向掃描冒泡排序，請在空白處填上適當內(nèi)容使算法完整。

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

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

描。

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

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

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

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

答案：

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

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

序輸出

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

編寫遞歸算法，對于給定的一

棵二叉樹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è)置一個中間變量s,用來存放左子樹的值，然后把右子樹的值交換給左子樹，再

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

完成鏡像。

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

______________。

答案：無關(guān)

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

算機的

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

所指結(jié)點不是終端結(jié)點。若要刪除P所指結(jié)點，則執(zhí)行的語句是______________。

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

解析：q的下個結(jié)點是p，如果刪除P，那么只能讓P的下個結(jié)點當q的下個結(jié)點。

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

答案：遞歸函數(shù)

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

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

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

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

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

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

______________。

答案：不變

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

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

30、【填空題】如果圖G存在拓撲排序序列，則G必為______________。

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

解析：教材163頁：對一個有向無環(huán)圖G進行拓撲排序，是將G中所有頂點排成一個線性

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

前。通常，這樣的線性序列稱為簡稱拓撲序列。

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

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