數據結構年月真題

02331201910

1、【單選題】下列選項中,不宜采用鏈式存儲的是

無向圖

單鏈表

A:

最優二叉樹

B:

數組

C:

答D:案：D

2、【單選題】將10個數據元素保存在順序棧S中,若棧頂元素的存儲地址是100,棧中每個

元素占4個存儲單元,進棧按Stop=S.top+1修改棧頂,則棧底元素的存儲地址是

60

64

A:

136

B:

140

C:

答D:案：B

3、【單選題】設指針變量head指向循環鏈表的頭結點,next是結點的指針域,則判斷此鏈表

為空的條件是

head->next==NULL

head->next==head

A:

head->next!=NULL

B:

head->next!=head->next

C:

答D:案：B

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

4

3

A:

2

B:

1

C:

答D:案：A

5、【單選題】已知一棵完全二叉樹T共有7個分支結點,則T中葉子結點個數最少是

7

A:

8

9

B:

10

C:

答D:案：A

6、【單選題】在一棵非空二叉樹的后序遍歷序列中,所有列在根結點前面的是

左子樹中的部分結點

右子樹中的全部結點

A:

左右子樹中的全部結點

B:

左右子樹中的部分結點

C:

答D:案：C

解析：在一棵非空二叉樹的后序遍歷序列中，所有出現在根節點前面的元素都是左子樹和

右子樹中的全部節點。后序遍歷是一種遍歷二叉樹的方式，它的遍歷順序是先遍歷左子

樹，再遍歷右子樹，最后訪問根節點。因此，在后序遍歷序列中，根節點的位置是在最后

的。假設后序遍歷序列為[L1,L2,...,Ln,R1,R2,...,Rm,Root]，其中L1,

L2,...,Ln是左子樹的節點，R1,R2,...,Rm是右子樹的節點，Root是根節點。由于

后序遍歷的特性，我們可以觀察到，在序列中，所有出現在根節點前面的元素都是左子樹

和右子樹中的全部節點。也就是說，L1,L2,...,Ln,R1,R2,...,Rm都是左子樹和右

子樹中的節點，而Root是根節點。這個特性可以用來判斷一個序列是否是一個合法的后

序遍歷序列，以及還原二叉樹的結構。

7、【單選題】用鄰接表保存有n個頂點和e條邊的無向圖,鄰接表中指針個數是

e

n-e

A:

n+e

B:

n+2e

C:

答D:案：D

解析：在鄰接表中保存有n個頂點和e條邊的無向圖時，每個頂點對應一個鏈表，鏈表中

存儲與該頂點相鄰的其他頂點。對于每個頂點，我們需要一個指針來指向與之相鄰的頂

點。由于無向圖中的每條邊都會連接兩個頂點，所以每個頂點的鏈表中需要存儲與之相鄰

的頂點的信息。考慮到每條邊都會在兩個頂點之間建立連接，所以總共有2e個指針。而

每個頂點對應一個鏈表，所以需要n個指針來指向這些鏈表。因此，鄰接表中指針的個

數是n+2e。其中n表示頂點的個數，2e表示邊的個數乘以2，是因為每條邊都會在兩個

頂點之間建立連接。

8、【單選題】有向圖G中某個頂點的出度和入度均為2,則G中的頂點個數最少是

2

3

A:

4

B:

5

C:

答D:案：B

9、【單選題】在帶權圖的最短路徑問題中,路徑長度是指

路徑上邊的數目

路徑上結點的數目

A:

路徑上邊的權值之和

B:

到達終點的最短路徑數目

C:

答D:案：C

解析：在交通網絡中，常常會提出許多這樣的問題：兩地之間是否有路相通，在有多條通

路的情況下，哪--條最近，哪一條花費最少，等等。交通網絡可以用帶權圖表示，圖中頂

點表示城鎮，邊表示兩城鎮之間的道路，邊上的權值可表示兩城鎮間的距離、交通費用或

途中所需的時間等。上述這些問題就是在帶權圖中求最短路徑的問題。此時的路徑長度的

度量不再是路徑上邊的數目，而是路徑上邊的權值之和。P158

10、【單選題】對數據序列(15,10,8,12,15,8,10)按升序進行希爾排序,增量序列為5,3,兩

趟排序后,得到的排序結果為

8,8,10,10,15,15,12

8,8,10,10,12,15,15

A:

8,10,8,10,15,15,12

B:

8,10,8,10,12,15,15

C:

答D:案：C

11、【單選題】下列排序方法中,不穩定的排序方法是

直接選擇排序

歸并排序

A:

直接插入排序

B:

基數排序

C:

答D:案：A

解析：直接選擇排序是一種不穩定的排序方法。在直接選擇排序中，每次從未排序的元素

中選擇最小（或最大）的元素，然后將其放置在已排序序列的末尾。這個過程會破壞相同

元素之間的相對順序，導致排序結果不穩定。

12、【單選題】一組記錄的關鍵字為(35,58,24,13,44,19,10),利用堆排序算法進行降序排

序,要求空間復雜度為O(1),建立的初始堆為

10,13,19,58,44,35,24

10,13,35,58,44,19,24

A:

58,44,24,13,35,19,10

B:

58,35,24,13,44,19,10

C:

答D:案：A

13、【單選題】一棵二叉排序樹中,關鍵字n所在結點的層數大于關鍵字m所在結點的層數,

則

n一定大于m

n一定小于m

A:

n一定等于m

B:

n與m的大小關系不確定

C:

答D:案：D

14、【單選題】設散列表長m=10,散列函數H(key)=key%9.表中已保存3個關鍵

字:H(13)=4,H(32)=5,H(15)=6,其余地址均為空。保存關鍵字23時存在沖突,采用線性探查法

來處理。則查找關鍵字23時的探查次數是

1

2

A:

3

B:

4

C:

答D:案：C

15、【單選題】下面關于m階(m≥3)B樹的敘述中,正確的是

終端結點可位于不同層

非終端結點至多有m+1棵子樹

A:

若樹非空,則根結點至少有2個關鍵字

B:

每個非根結點包含n個關鍵字,[m/2]-1≤n≤m-1

C:

答D:案：D

16、【問答題】設電文字符集是{e1,e2,e3,e4,e5,e6},它們出現的次數分別

為:38,12,17,26,14,20。現要為該字符集設計一種哈夫曼編碼。請回答下列問題。(1)畫出得

到的哈夫曼樹。(2)給出各符號的哈夫曼編碼。

答案：

17、【問答題】

答案：(1)ABDEFGCABDEGFC(2)ABCDEFGABCDEGFACBDEFG

18、【問答題】有以下關鍵字序列(15,20,24,32,15,7,14,23),使用快速排序方法將其按升

序排列。請回答下列問題。(1)若取第一個關鍵字為基準,寫出第一趟快速排序的結果。(2)若

取最后一個關鍵字為基準,寫出第一趟快速排序的結果

答案：(1)14,7,15,32,15,24,20,23(2)15,20,14,7,15,23,32,24

19、【問答題】

答案：

20、【問答題】

答案：(1)3,5,9,10,2,30,(2)用給定的整數建立順序表,奇數從頭插入,偶數從表尾插

入。

21、【問答題】

答案：

22、【問答題】。

答案：(1)R[mid].key==k(2)mid-1(3)mid+1

23、【問答題】

答案：(1)Q[front]!=NULL(2)rear%2(3)front++

24、【問答題】

答案：

25、【填空題】數據的四種基本存儲方法是順序存儲、鏈接存儲、____和散列存儲。

答案：索引存儲

26、【填空題】指針p和指針q分別指向單鏈表L中的兩個結點,next為指針域,則判斷這兩

個結點是否相鄰的條件是____

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

27、【填空題】遞歸求解過程中的最小子問題稱為____

答案：遞歸的終止條件(或遞歸出口)

28、【填空題】廣義表(((a,b),(c,d,e)),(f,g),h)的表頭是____

答案：((a,b),(c,d,e))

29、【填空題】3個結點的不同形狀的二叉樹有____棵。

答案：5

30、【填空題】若有向無環圖G存在2個入度為0的結點,則G至少存在____個不同的拓撲

序列。

答案：2

31、【填空題】將一棵樹T轉換為一棵二叉樹,則這棵二