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

02331201810

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

線性表

棧

A:

隊(duì)列

B:

二叉樹(shù)

C:

答D:案：D

解析：線性表、棧、隊(duì)列的各個(gè)元素之間都是線性關(guān)系，但二叉樹(shù)的各元素間是非線性的

數(shù)據(jù)結(jié)構(gòu)。

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

儲(chǔ)地址是1000，第6個(gè)元素的存儲(chǔ)地址是1040，則最后一個(gè)元素的存儲(chǔ)地址是

1112

1120

A:

1124

B:

1128

C:

答D:案：B

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

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

3、【單選題】設(shè)棧的初始狀態(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

解析：棧的特點(diǎn)：后進(jìn)先出。1進(jìn)，1出，2進(jìn)，2出，3進(jìn)，4進(jìn)，5進(jìn)，5出，4出，3

出。不會(huì)是3先出再4出。

4、【單選題】設(shè)指針變量P指向非空單鏈表中的結(jié)點(diǎn)，next是結(jié)點(diǎn)的指針域，則判斷P所

指結(jié)點(diǎn)為尾結(jié)點(diǎn)前一個(gè)結(jié)點(diǎn)的邏輯表達(dá)式中，正確的是

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所指結(jié)點(diǎn)為尾結(jié)點(diǎn)前一個(gè)結(jié)點(diǎn)，那么p的next應(yīng)該不為空，但p->next的

next應(yīng)該是為空的。

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

是

2

3

A:

4

B:

5

C:

答D:案：B

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

1。

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

5

8

A:

10

B:

27

C:

答D:案：C

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

點(diǎn)沒(méi)有孩子也是葉結(jié)點(diǎn)，那么就是10個(gè)葉結(jié)點(diǎn)。

7、【單選題】已知二叉樹(shù)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ù)前序遍歷和中序遍歷可以畫出該二叉樹(shù)為：對(duì)該二叉樹(shù)再后序遍歷。

先左子樹(shù)再右子樹(shù)最后根結(jié)點(diǎn)。后序遍歷序列為：ecdba。

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

是

n(n+1)／2-e

n(n+1)／2-2e

A:

n×n-e

B:

n×n-2e

C:

答D:案：D

解析：鄰接矩陣一共有n*n個(gè)元素，因?yàn)檫叺膫€(gè)數(shù)是e，所以鄰接矩陣中1的個(gè)數(shù)為e，

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

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

10

12

A:

14

B:

16

C:

答D:案：B

解析：在有向圖中，所有頂點(diǎn)的度數(shù)之和是所有邊數(shù)的2倍，因?yàn)橐粭l邊的兩個(gè)端點(diǎn)具有

兩個(gè)“度”。

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

解析：當(dāng)用鄰接矩陣表示圖時(shí)，需要對(duì)n個(gè)頂點(diǎn)進(jìn)行訪問(wèn)，所以共需要搜索n2個(gè)矩陣元

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

的時(shí)間復(fù)雜度為O（n+e）。

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

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

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

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

3，4，7。

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

希爾排序

歸并排序

A:

直接插入排序

B:

冒泡排序

C:

答D:案：A

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

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

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

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

序排序，建立的初始堆為

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

解析：

建堆過(guò)程如下：

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

n一定大于m

n一定小于m

A:

n一定等于m

B:

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

C:

答D:案：D

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

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

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

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

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

儲(chǔ)關(guān)鍵字36時(shí)存在沖突，采用線性探測(cè)法來(lái)處理。則查找關(guān)鍵字36時(shí)的探查次數(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,此地址是開(kāi)放的，可將49插入，所以探測(cè)了3次。

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

13，26，18，23}?，F(xiàn)要為該字符集設(shè)計(jì)哈夫曼編碼。請(qǐng)回答下列問(wèn)題。（1）給出構(gòu)造的哈

夫曼樹(shù)。（2）給出各字符的哈夫曼編碼。（3）計(jì)算電文編碼總長(zhǎng)。

答案：

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

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

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

寫出從頂點(diǎn)A開(kāi)始圖G的1個(gè)廣度優(yōu)先搜索遍歷序列。

答案：

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

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

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

方法將其排成升序序列。請(qǐng)回答下列問(wèn)題。（1）分別寫出增量為3和1的希爾排序結(jié)果。

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

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

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

解析：教材171頁(yè)希爾排序的思想：把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入

排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)，整個(gè)

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

19、【問(wèn)答題】設(shè)有二叉排序樹(shù)T如題29圖所示。現(xiàn)需在T中刪除結(jié)點(diǎn)e，請(qǐng)回答下列

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

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

少?

答案：

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

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

20、【問(wèn)答題】順序表類型定義如下：

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

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

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

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

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

解析：根據(jù)算法可知：先輸出二叉樹(shù)右孩子，然后輸出根結(jié)點(diǎn)，再輸出左孩子。因?yàn)槊總€(gè)

結(jié)點(diǎn)執(zhí)行一次，所以時(shí)間復(fù)雜度為：O(n)。

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

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

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

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

23、【問(wèn)答題】二叉樹(shù)的結(jié)構(gòu)類型定義如下：

答案：

解析：

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

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

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

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

答案：

25、【填空題】數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的______標(biāo)識(shí)單位。

答案：最小

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

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

答案：q->next=r

27、【填空題】遞歸算法設(shè)計(jì)中的最小子問(wèn)題稱為遞歸的_________。

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

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

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

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

29、【填空題】已知二叉樹(shù)的前序遍歷序列和后序遍歷序列，則對(duì)應(yīng)的二叉樹(shù)_________確

定。

答案：不唯一（或不能）

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