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

02331202110

1、【單選題】下列關于數(shù)據(jù)項和數(shù)據(jù)元素的敘述中，正確的是

數(shù)據(jù)項只能是數(shù)值類型

數(shù)據(jù)項可以包含數(shù)據(jù)元素

A:

數(shù)據(jù)元素是數(shù)據(jù)的基本單位

B:

數(shù)據(jù)元素是由數(shù)據(jù)項組成的集合

C:

答D:案：C

解析：數(shù)據(jù)元素(dataelement)是數(shù)據(jù)的基本單位。如前例中目錄卡片表中的一張卡片(表

格詞1一行)、樹中的一個結點S中的二個頂舌等都是數(shù)據(jù)元素。有時一個數(shù)據(jù)元素可由

若干個數(shù)據(jù)項(也稱為字段、域、屬性)組成，數(shù)據(jù)項是具有獨立含義的最小標識單位，如

圖書卡片信息中的登錄號、書名、作者等。P21

2、【單選題】下列關于抽象數(shù)據(jù)類型的敘述中，正確的是

抽象數(shù)據(jù)類型與具體實現(xiàn)相關

抽象數(shù)據(jù)類型是由C語言本身提供的

A:

抽象數(shù)據(jù)類型是C語言提供的類型的邏輯描述

B:

抽象數(shù)據(jù)類型將數(shù)據(jù)定義和數(shù)據(jù)操作封裝在一起

C:

答D:案：D

解析：抽象數(shù)據(jù)類型可以看作是描述問題的模型，它獨立于具體實現(xiàn)。它的特點是將數(shù)據(jù)

定義和數(shù)據(jù)操作封裝在一起，使得用戶程序只能通過在ADT中定義的某種操作來訪問其中

的數(shù)據(jù)，從而實現(xiàn)信息的隱藏性。這種抽象數(shù)據(jù)類型類似于C卄中的類。P33

3、【單選題】設有初始為空的棧S，入棧序列是f，e，d，c，b，a，出棧序列是d，e，a，

b，c，f，則需要為S分配的空間大小至少是

2

3

A:

4

B:

5

C:

答D:案：C

4、【單選題】指針head指向帶頭結點的單鏈表L的表頭，結點結構為：datanext，其中，

data為int型，next是指向后繼結點的指針。指針p指向L中的首個數(shù)據(jù)結點，指針q指向

p的后繼結點?，F(xiàn)要交換p、q所指向的兩結點中的data值，下列選項中，不能完成該任務的

操作是

head->next=q;p->next=q->next;q->next=p;

p->next=q->next;head->next=q;q->next=p;

A:

q->next=p;p->next=q->next;head->next=q;

B:

inttemp=p->data;p->data=q->data;q->data=temp;

C:

答D:案：C

5、【單選題】采用行優(yōu)先壓縮存儲方式保存6行6列對稱矩陣A的上三角部分，每個元素占

2個單元，若A中第一個元素a11的存儲地址是10，則元素a34的存儲地址是

22

26

A:

34

B:

40

C:

答D:案：C

6、【單選題】已知廣義表L=((l，i)，h)，(x，i，a，o))，下列運算中，結果得到h的是

head(tail(L))

head(tail(head(L)))

A:

head(head(tail(L)))

B:

head(head(tail(tail(L))))

C:

答D:案：B

7、【單選題】下列關于二叉樹的敘述中，錯誤的是

二叉樹可以為空

二叉樹可以保存在數(shù)組中

A:

二叉樹中葉結點的個數(shù)多于度為1結點的個數(shù)

B:

二叉樹中葉結點的個數(shù)多于度為2結點的個數(shù)

C:

答D:案：C

8、【單選題】若二叉樹的前序遍歷序列是ABCD，中序遍歷序列是ACDB，則其后序遍歷序列

是

ABDC

ACDB

A:

CDBA

B:

DCBA

C:

D:

答案：D

9、【單選題】對下圖進行廣度優(yōu)先搜索遍歷，正確的遍歷序列是

bdeac

badce

A:

acedb

B:

abced

C:

答D:案：B

10、【單選題】關于圖G的深度優(yōu)先生成樹T1與廣度優(yōu)先生成樹T2，下列敘述中正確的是

T1與T2一定相同

T1與T2可能相同

A:

T1與T2一定不相同

B:

T1與T2中所含邊數(shù)不相等

C:

答D:案：B

11、【單選題】對n個記錄進行排序，最壞情況下，時間復雜度不是O(n)2的排序方法是

直接插入排序

冒泡排序

A:

快速排序

B:

堆排序

C:

答D:案：D

12、【單選題】下列排序方法中，不宜在鏈表上實現(xiàn)的是

直接插入排序

快速排序

A:

歸并排序

B:

基數(shù)排序

C:

答D:案：B

解析：一般的排序方法都可以在順序結構（一維數(shù)組）上實現(xiàn)。當記錄本身信息量較大時,

為了避免移動記錄耗費大量的時間，可以采用鏈式存儲結構。例如插入排序、歸并排序、

基數(shù)排序易于在鏈表上實現(xiàn)，使之減少記錄的移動次數(shù)，但有的排序方法，如快速排序、

堆排序在鏈表上卻難于實現(xiàn)，在這種請況下，可以提取關鍵字建立索引表，然后對索引表

進行排序。P191

13、【單選題】若元素序列11，13，15，7，8，9，23，2，5是采用下列排序算法之一得到

的第2趟排序后的結果，則該排序算法是

直接插入排序

冒泡排序

A:

選擇排序

B:

二路歸并排序

C:

答D:案：A

14、【單選題】在長度為n(≥100)的有序線性表中進行二分查找，查找成功時，查找長度不

多于4的關鍵字個數(shù)是

4

7

A:

15

B:

100

C:

答D:案：C

15、【單選題】將下列數(shù)據(jù)分別依次插入到初始為空的二叉排序樹中，能得到高度最低二叉

排序樹的是

9，7，2，1，4，10

6，4，1，8，10，5

A:

5，1，2，6，3，4

B:

2，4，7，5，8，10

C:

答D:案：B

16、【問答題】鏈棧為什么不必設置頭結點？

答案：鏈棧是運算受限的單鏈表，鏈表的頭指針可以看作是棧頂指針，入棧和出棧操作僅

限制在表頭位置（棧頂）進行，因此不必設置頭結點。

17、【問答題】已知字符集{a，b，c，d，e}中各字符出現(xiàn)的頻次分別為2，3，6，8，10，

對字符集進行哈夫曼編碼，字符a的編碼是000，字符e的編碼是11，則其余3個字符的編

碼分別是什么？

答案：

18、【問答題】設有向圖G如題28圖所示，給出圖G的鄰接矩陣。

答案：

19、【問答題】設有關鍵字16，15，32，11，6，30，將它們依次保存在哈希表（長度為7

的一維數(shù)組）中，哈希函數(shù)為H(k)=kmod7，采用線性探查法解決沖突。已知關鍵字16已放置

在數(shù)組下標為2的位置。請畫出哈希表。

答案：

20、【問答題】程序f30()創(chuàng)建了一個帶頭結點的含n(n≥3)個數(shù)據(jù)結點的單鏈表L，L前

兩個數(shù)據(jù)結點中的data值均為1，從第3個結點開始，結點的data值是其前兩個結點

data值之和。請在空白處填上適當內(nèi)容將算法補充完整。

答案：

21、【問答題】已知圖的鄰接矩陣表示的存儲結構定義如下，算法f31()統(tǒng)計圖中各頂點

的度，并返回最大度數(shù)。請在空白處填上適當內(nèi)容將算法補充完整。

答案：

22、【問答題】已知二叉排序樹結點的數(shù)據(jù)類型定義及二叉排序樹的某個算法f32()如

下。

請回答下列問題。

(1)f32()的功能是什么？

(2)對于題32圖所示的二叉排序樹T，調用f32(T，100，612)后的輸出是什么？

答案：

23、【問答題】閱讀程序，并回答下列問題。

答案：(1)f33=2(2)在數(shù)組中采用二分查找（折半查找）法查找指定元素，若查找成

功，則返回指定元素在數(shù)組中的下標；如果查找失敗，則返回-1。

24、【問答題】設n個整數(shù)存放在數(shù)組A中，請編寫函數(shù)f34(intA[]，intn)，將所有奇

數(shù)調整到所有偶數(shù)之前。

答案：

25、【填空題】非空的帶頭結點的單循環(huán)鏈表中，終端結點的指針域指向的是鏈表的

_______。

答案：頭結點

26、【填空題】已知循環(huán)隊列存儲在一維數(shù)組A[0..n-1]中，頭指針是front，尾指針是

rear，初始時front的值和rear的值均是0，則第1個入隊元素存儲在數(shù)組中存儲位置的下

標是_______。

答案：0

27、【填空題】將中級表達式9-(2+4*7)轉換為后綴表達式的結果是_______。

答案：9247*+-

28、【填空題】廣義表G=(27，G)的深度是_______。

答案：∞

29、【填空題】具有n(n≥1)個結點的二叉樹，采用二叉鏈表存儲，空指針域的個數(shù)是

_______。

答案：n+1

30、【填空題】兩個無向連通圖均含有10個頂點，它們之間的邊數(shù)差最大是_______。

答案：36

31、【填空題】有向圖G存在拓