2018年10月自考02331數(shù)據(jù)結構試題及答案含解析

數(shù)據(jù)結構年月真題

02331201810

1、【單選題】下列數(shù)據(jù)結構中，邏輯結構不同的是

線性表

棧

A:

隊列

B:

二叉樹

C:

答D:案：D

解析：線性表、棧、隊列的各個元素之間都是線性關系，但二叉樹的各元素間是非線性的

數(shù)據(jù)結構。

2、【單選題】將16個數(shù)據(jù)元素的線性表按順序存儲方式存儲在數(shù)組中，若第一個元素的存

儲地址是1000，第6個元素的存儲地址是1040，則最后一個元素的存儲地址是

1112

1120

A:

1124

B:

1128

C:

答D:案：B

解析：線性表的第i個元素a<>i的存儲位置LOC(a<>i)=LOC(a<>i)+(i-1)*d,得到d=8,所

以第16個元素的地址=1000+(16-1)*8=1120

3、【單選題】設棧的初始狀態(tài)為空，元素1，2，3，4，5依次入棧，不能得到的出棧序列是

1，2，3，4，5

4，5，3，2，1

A:

1，2，5，4，3

B:

1，2，5，3，4

C:

答D:案：D

解析：棧的特點：后進先出。1進，1出，2進，2出，3進，4進，5進，5出，4出，3

出。不會是3先出再4出。

4、【單選題】設指針變量P指向非空單鏈表中的結點，next是結點的指針域，則判斷P所

指結點為尾結點前一個結點的邏輯表達式中，正確的是

p->next!=NULL&&p->next一>next->next==NULL

p->next!=NULL&&p->next->next==NULL

A:

p->next->next==NULL

B:

p->next==NULL

C:

答D:案：B

解析：判斷P所指結點為尾結點前一個結點，那么p的next應該不為空，但p->next的

next應該是為空的。

5、【單選題】已知廣義表LS=（（（a，b，c），d），（e，（fg，（hi））），LS的深度

是

2

3

A:

4

B:

5

C:

答D:案：B

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

1。

6、【單選題】已知一棵完全二叉樹T的第5層上共有5個葉結點，則T中葉結點個數(shù)最少是

5

8

A:

10

B:

27

C:

答D:案：C

解析：完全二叉樹的第四層是8個節(jié)點，而第五層有5個葉結點的話，第四層也有5個結

點沒有孩子也是葉結點，那么就是10個葉結點。

7、【單選題】已知二叉樹T的前序遍歷序列為a，b，c，e，d，中序遍歷序列為c，e，b，

d，a，則T的后序遍歷序列為

c，e，d，b，a

d，e，c，b，a

A:

e，c，d，b，a

B:

e，c，b，a，d

C:

答D:案：C

解析：

根據(jù)前序遍歷和中序遍歷可以畫出該二叉樹為：對該二叉樹再后序遍歷。

先左子樹再右子樹最后根結點。后序遍歷序列為：ecdba。

8、【單選題】有向圖G有n個頂點和e條邊，G保存在鄰接矩陣M中，M中0與1的個數(shù)差

是

n(n+1)／2-e

n(n+1)／2-2e

A:

n×n-e

B:

n×n-2e

C:

答D:案：D

解析：鄰接矩陣一共有n*n個元素，因為邊的個數(shù)是e，所以鄰接矩陣中1的個數(shù)為e，

則0的個數(shù)就是n*n-e。所以0與1的個數(shù)差是n×n-2e。

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

10

12

A:

14

B:

16

C:

答D:案：B

解析：在有向圖中，所有頂點的度數(shù)之和是所有邊數(shù)的2倍，因為一條邊的兩個端點具有

兩個“度”。

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

索遍歷算法的時間復雜度是

O(n)

O(e)

A:

O(n+e)

B:

O(n×e)

C:

D:

答案：C

解析：當用鄰接矩陣表示圖時，需要對n個頂點進行訪問，所以共需要搜索n2個矩陣元

素，而在鄰接表上則需要將邊表中所有O（e）個結點搜一遍，因此深度優(yōu)先搜索遍歷算法

的時間復雜度為O（n+e）。

11、【單選題】對數(shù)據(jù)序列（26，14，17，12，7，4，3）采用二路歸并排序進行升序排

序，兩趟排序后，得到的排序結果為

14，26，17，12，4，7，3

12，14，17，26，3，4，7

A:

14，26，12，17，3，4，7

B:

14，26，12，17，3，7，4

C:

答D:案：B

解析：一趟結果為：【1416】【1217】【47】3；二趟結果為：12，14，17，26，

3，4，7。

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

希爾排序

歸并排序

A:

直接插入排序

B:

冒泡排序

C:

答D:案：A

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

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

法是不穩(wěn)定的。

13、【單選題】一組記錄的關鍵字為（35，48，47，23，44，88），利用堆排序算法進行降

序排序，建立的初始堆為

23，35，48，47，44，88

23，35，47，48，44，88

A:

35，23，47，48，44，88

B:

35，23，47，44，48，88

C:

答D:案：B

解析：

建堆過程如下：

14、【單選題】一棵二叉排序樹中，關鍵字n所在結點是關鍵字m所在結點的孩子，則

n一定大于m

n一定小于m

A:

n一定等于m

B:

n與m的大小關系不確定

C:

答D:案：D

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

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

以大小關系不確定。

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

addr（18）=3，addr（35）=5，addr（51）=6，addr（22）=7，其余地址均為開放地址。存

儲關鍵字36時存在沖突，采用線性探測法來處理。則查找關鍵字36時的探查次數(shù)是

1

2

A:

3

B:

4

C:

答D:案：C

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

再探查h2=(7+1)%15=8,此地址是開放的，可將49插入，所以探測了3次。

16、【問答題】設電文字符集是{el，e2，e3，e4，e5），各字符出現(xiàn)的次數(shù)分別為{36，

13，26，18，23}。現(xiàn)要為該字符集設計哈夫曼編碼。請回答下列問題。（1）給出構造的哈

夫曼樹。（2）給出各字符的哈夫曼編碼。（3）計算電文編碼總長。

答案：

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

（1）根據(jù)鄰接矩陣畫出圖

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

寫出從頂點A開始圖G的1個廣度優(yōu)先搜索遍歷序列。

答案：

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

優(yōu)先遍歷的含義，可以寫出答案，答案不是唯一的。

18、【問答題】有數(shù)據(jù)序列（12，17，05，10，20，24，45，11，10，12），使用希爾排序

方法將其排成升序序列。請回答下列問題。（1）分別寫出增量為3和1的希爾排序結果。

（2）計算第一趟希爾排序中數(shù)據(jù)元素之間的總交換次數(shù)（兩個元素之間的交換記1次）。

答案：（1）增量為3時希爾排序結果：10，11，05，12，17，10，12，20，24，45增

量為1時希爾排序結果：05，10，10，11，12，12，17，20，24，45（2）5次

解析：教材171頁希爾排序的思想：把記錄按下標的一定增量分組，對每組使用直接插入

排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個

文件恰被分成一組，算法便終止。

19、【問答題】設有二叉排序樹T如題29圖所示?，F(xiàn)需在T中刪除結點e，請回答下列

問題。（1）畫出刪除后的二叉排序樹（僅需畫出一棵）。（2）在你實現(xiàn)的刪除過程

中，指針域更新的次數(shù)是多

少?

答案：

解析：答案一，指針變更兩次，g的左孩子變?yōu)閒,b的父結點變?yōu)閒。答案二：指針變更

三次，g的左孩子變?yōu)閐,f變?yōu)閐的右孩子，c變?yōu)閎的右孩子。

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

答案：（1）調(diào)用f30（）后的返回值是-33。（2）該算法按兩個線性表的最短長度

minlength查找兩個線性表中前minlength個元素的最小值。

解析：根據(jù)算法可知，找出兩個線性表中前8個值中的最小值，應該是-33。

21、【問答題】二叉樹的存儲結構類型定義如下：

答案：（1）CEDAB（2）時間復雜度為O(n),其中n是二叉樹中所含結點個數(shù)。

解析：根據(jù)算法可知：先輸出二叉樹右孩子，然后輸出根結點，再輸出左孩子。因為每個

結點執(zhí)行一次，所以時間復雜度為：O(n)。

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

答案：（1）n-1;(2)j--;(3)R[j]=temp;

解析：直接插入排序基本操作是將一條記錄插入到已排好的有序表中，從而得到一個新

的、記錄數(shù)量增1的有序表。

23、【問答題】二叉樹的結構類型定義如下：

答案：

解析：

中序遍歷二叉樹先左子樹后根最后右子樹，并按函數(shù)要求，題中給的左是

14，右是30，所以結果為：23，15，28，19，29。

24、【問答題】已知n個單鏈表的表頭指針保存在數(shù)組A中，單鏈表中的結點類型及數(shù)組

類型定義如下，存儲形式如34圖所示。

答案：

25、【填空題】數(shù)據(jù)項是具有獨立含義的______標識單位。

答案：最小

26、【填空題】指針P和q分別指向單鏈表L中的兩個相鄰結點，即q->next=P。若要在q

所指結點后插入指針r所指結點，則執(zhí)行的語句是r->next=p；_________。

答案：q->next=r

27、【填空題】遞歸算法設計中的最小子問題稱為遞歸的_________。

答案：終止條件（或遞歸出口）

28、【填空題】廣義表（（a，b），（c，d），e，（f（g,h）））的表尾是_________。

答案：（(c，d)，e，(f(g,h))）

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

29、【填空題】已知二叉樹的前序遍歷序列和后序遍歷序列，則對應的二叉樹_________確

定。

答案：不唯一（或不能）

解析：根據(jù)三種遍歷的次序和特