2015年10月自考02142數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題及答案含解析

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論年月真題

02142201510

1、【單選題】“能正確地實現(xiàn)預(yù)定的功能，滿足具體問題的需要”。這種評價算法好壞的因

素稱為

正確性

易讀性

A:

健壯性

B:

時空性

C:

答D:案：A

解析：正確性：能正確地實現(xiàn)預(yù)定的功能，滿足具體問題的需要。處理數(shù)據(jù)使用的算法是

否得當(dāng)，能不能得到預(yù)想的結(jié)果。

2、【單選題】有一程序片段：{i=0；s=0；while(s<=n){i++；s=s+i；}}，其時間復(fù)雜度是

O（n）

O（2n）

A:

O（n1/2）

B:

O（1）

C:

答D:案：C

3、【單選題】在如題3圖所示的數(shù)組A中鏈接存儲了一個線性表，表頭指針為

A[0]．next，則該線性表中第一個數(shù)據(jù)元素的值是

60

50

A:

78

B:

40

C:

答D:案：C

4、【單選題】在一個長度為n(n>1)的單鏈表上，設(shè)有頭和尾兩個指針，下列操作與鏈表長

度有關(guān)的是

刪除單鏈表中的第一個元素

刪除單鏈表中的最后一個元素

A:

在單鏈表中第一個元素前插入一個新元素

B:

在單鏈表中最后一個元素后插入一個新元素

C:

答D:案：B

5、【單選題】某雙向鏈表中的結(jié)點(diǎn)如題5圖所示。刪除t所指結(jié)點(diǎn)的操作為

t->prior->prior=t->next;t->next->prior=t->prior

t->prior->prior=t->prior;t->next->next=t->next

A:

t->prior->next=t->prior;t->next->prior=t->next

B:

t->prior->next=t->next;t->next->prior=t->prior

C:

答D:案：D

6、【單選題】下列關(guān)于棧和隊列的敘述中：Ⅰ棧和隊列都是線性表；Ⅱ棧和隊列都是順序

表；Ⅲ棧和隊列都不能為空；Ⅳ棧和隊列都能用于遞歸過程實現(xiàn)；Ⅴ棧的特點(diǎn)是先進(jìn)后出、

隊列的特點(diǎn)是先進(jìn)先出，其中正確的是

Ⅰ和V

Ⅰ、Ⅱ、V

A:

Ⅲ和V

B:

Ⅱ、Ⅳ、V

C:

答D:案：A

7、【單選題】二維數(shù)組A按行序優(yōu)先順序存儲，每個數(shù)據(jù)元素占1個存儲單元。若數(shù)據(jù)元素

A[1][1]的存儲地址是420，A[3][3]的存儲地址是446，則A[5][5]的存儲地址是

470

471

A:

472

B:

473

C:

答D:案：C

8、【單選題】若對一棵含有199個結(jié)點(diǎn)的完全二叉樹按自上而下、從左到右依次對結(jié)點(diǎn)編

號，根結(jié)點(diǎn)的編號為l，則樹中最后一個結(jié)點(diǎn)(即編號為l99)的雙親結(jié)點(diǎn)的編號為

99

100

A:

101

B:

198

C:

答D:案：A

9、【單選題】對長度為15的有序順序表進(jìn)行二分查找，在各記錄的查找概率均相等的情況

下，查找成功時平均查找長度(ASL)為

A:

B:

C:

答D:案：B

10、【單選題】在如題10圖所示的有向圖中，從頂點(diǎn)1出發(fā)進(jìn)行深度優(yōu)先搜索可得到的

結(jié)果序列是

1423

1432

A:

1342

B:

1243

C:

答D:案：D

11、【單選題】設(shè)森林F中有三棵樹，其結(jié)點(diǎn)的個數(shù)分別為m1、m2、m3，則與F對應(yīng)的二

叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)數(shù)是

m1+m2

m2+m3

A:

m1\+m3

B:

m1+m2\+m3

C:

答D:案：B

12、【單選題】假設(shè)通信電文使用的字符集為{a，b，e，d，e，f}，各字符在電文中出現(xiàn)的

頻率分別為{34，5，12，23，8，18}，利用構(gòu)造Huffman樹對每個字符進(jìn)行編碼，則其中編

碼長度最長的字符是

a.b

a，d

A:

b，e

B:

e，f

C:

答D:案：C

13、【單選題】元素的進(jìn)棧次序為A，B，c，D，E，出棧的第一個元素為E，則第四個出棧

的元素為

D

C

A:

B

B:

A

C:

答D:案：C

14、【單選題】平均時間復(fù)雜度和在最壞情況下的時間復(fù)雜度均是0(Nlog2n)的排序算法是

插入排序

快速排序

A:

選擇排序D

B:

堆排序

C:

答D:案：D

15、【單選題】在待排記錄中其關(guān)鍵字序列基本有序的前提下，時間效率最高的排序方法是

直接插入排序

快速排序

A:

選擇排序

B:

C:

堆排序

答D:案：A

解析：插入排序通過數(shù)據(jù)元素的交換來逐步消除線性表中的逆序,所以關(guān)鍵字比較的次數(shù)

與記錄的初始排列次序有關(guān),在待排序的元素序列基本有序的前提下,效率最高。

16、【問答題】設(shè)棧S和隊列Q的初始狀態(tài)均為空，7個元素abcdefg依次進(jìn)入棧S。若每

個元素出棧后立即進(jìn)入隊列Q，且7個元素出隊的順序是bdcfeag．現(xiàn)要求：(1)棧s的容

量至少是多少?(2)在(1)的情況下，畫出該棧中元素最多時的一個狀態(tài)示意圖。

答案：

17、【問答題】某二叉樹結(jié)點(diǎn)的中序遍歷序列為ABCDEFG、后序遍歷序列為BDCAFGE．現(xiàn)

要求：(1)畫出該二叉樹；(2)寫出該二叉樹的先序遍歷序列；3)該二叉樹所對應(yīng)的森林

包括幾棵樹?

答案：

18、【問答題】假設(shè)有一棵完全二叉樹按自上而下、從左到右的層序組織包含A、B、C、D、

E、F、G這7個結(jié)點(diǎn)，分別給出其鄰接矩陣和鄰接表。

答案：

19、【問答題】要求給出至少2個不同的關(guān)鍵字序列，均能構(gòu)造出如題32圖所示的二叉

排序樹；對此你會得出什么結(jié)論?

答案：(1)e,f,g,b,a,d,c或e,b,d,c,a,f,g或e,f,g,b,d,c,a等等(2)不同的關(guān)鍵字序

列，可能會得到同樣的二叉排序樹。

20、【問答題】采用快速排序方法對關(guān)鍵字序列{265，301，751，129，937，863，742，

694，076，438}進(jìn)行升序排序，寫出其每趟排序結(jié)束后的關(guān)鍵字序列。

答案：初始態(tài):[265301751129937863742694076438]第一趟:[076

129]265[751937863742694301438]第二趟:076[129]265[438301694

742]751[863937]第三趟:076129265[301]438[694742]751863[937]第四趟:076

129265301438694[742]751863937第五趟:076129265301438694742751

863937

21、【問答題】寫出復(fù)制一棵二叉樹的算法。設(shè)原二叉樹根結(jié)點(diǎn)由指針root指向，復(fù)制

得到的二叉樹根結(jié)點(diǎn)由指針newroot指向，函數(shù)頭為：voidCopyTree(BTNode*root，

BTNode，*newroot)，二叉樹的存儲結(jié)構(gòu)為：

答案：

22、【問答題】已知帶頭結(jié)點(diǎn)的單鏈表L是按數(shù)據(jù)域值非遞減有序鏈接的，試寫一算法將值

為x的結(jié)點(diǎn)插入表L中，使得L仍然是有序鏈接的。

答案：

23、【填空題】數(shù)據(jù)的存儲結(jié)構(gòu)又稱為物理結(jié)構(gòu)，可分為順序存儲、鏈?zhǔn)酱鎯?、_______以

及散列存儲等幾種方式。

答案：素引存儲

24、【填空題】一般說來，在每個邏輯結(jié)構(gòu)上都定義了一組基本運(yùn)算，通常這些運(yùn)算包括：

建立、_______、讀取、插入和刪除等。

答案：查找

25、【填空題】某帶有頭結(jié)點(diǎn)的單鏈表的頭指針為head，則判斷該單鏈表為非空的條件是

_______。

答案：head->next!=NULL

26、【填空題】數(shù)組Q[n]表示一個循環(huán)隊列，設(shè)f的值為隊列中第一個元素的位置，r的值

為隊列中實際隊尾的位置加1，并假定隊列中最多只有n一1個元素，則計算隊列中元素個數(shù)

的公式是_______.

答案：(r-f+n)%n

27、【填空題】稀疏矩陣可以采用_______方法進(jìn)行壓縮存儲。

答案：三元組表示

28、【填空題】含有11個結(jié)點(diǎn)的完全二叉樹中度為1的結(jié)點(diǎn)的個數(shù)最多為_______。

答案：1

29、【填空題】高度(深度)為k的二叉樹中結(jié)點(diǎn)個數(shù)最多是2k-l、最少是_______。

答案：k

30、【填空題】對于有n個頂點(diǎn)的無向圖，所有生成樹中都有且僅有_______條邊。

答案：n-1

31、【填空題】設(shè)散列表的地址空間為0到12，散列函數(shù)為h(k)=kmodl3，用線性探測法

解決沖突?，F(xiàn)要將關(guān)鍵字序列{10，100，32，45，58，128，3，29，200，400，0}映射到該

散列表中，則其中關(guān)鍵字值58的地址為_______。

答案：8

32、【填空題】假設(shè)有K個關(guān)鍵字互為同義詞，若用線性探測法把這K個關(guān)鍵字用散列函數(shù)

H將它們存人長度為m的散列表中(K≤m)，則至少共需進(jìn)行_______次探測。

答案：K(K+1)/2