?數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2015年10月真題（02142）

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

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2015年10月真題及答案解析（02142），該試卷為數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考?xì)v年真題試卷，包含答案及詳細(xì)解析。

一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其選出并將“答題卡”的相應(yīng)代碼涂黑。未涂、錯(cuò)涂或多涂均無(wú)分。

1.“能正確地實(shí)現(xiàn)預(yù)定的功能，滿(mǎn)足具體問(wèn)題的需要”。這種評(píng)價(jià)算法好壞的因素稱(chēng)為(　　)

A.正確性
B.易讀性
C.健壯性
D.時(shí)空性

2.有一程序片段：{ i=0; s=0; while(s<=n){ i++; s=s+i; }}，其時(shí)間復(fù)雜度是(　　)

A.O(n)
B.O(2n)
C.O(n^1/2)
D.O(1)

3.在如題3圖所示的數(shù)組A中鏈接存儲(chǔ)了一個(gè)線(xiàn)性表，表頭指針為A[0].next，則該線(xiàn)性表中第一個(gè)數(shù)據(jù)元素的值是(　　)                                        題3圖

A.60
B.50
C.78
D.40

4.在一個(gè)長(zhǎng)度為n(n>1)的單鏈表上，設(shè)有頭和尾兩個(gè)指針，下列操作與鏈表長(zhǎng)度有關(guān)的是(　　)

A.刪除單鏈表中的第一個(gè)元素
B.刪除單鏈表中的最后一個(gè)元素
C.在單鏈表中第一個(gè)元素前插入一個(gè)新元素
D.在單鏈表中最后一個(gè)元素后插入一個(gè)新元素

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

A.t->prior->prior=t->next; t->next->prior=t->prior;
B.t->prior->prior=t->prior; t->next->next=t->next;
C.t->prior->next=t->prior; t->next->prior=t->next;
D.t->prior->next=t->next; t->next->prior=t->prior;

6.下列關(guān)于棧和隊(duì)列的敘述中：Ⅰ棧和隊(duì)列都是線(xiàn)性表;Ⅱ棧和隊(duì)列都是順序表;Ⅲ棧和隊(duì)列都不能為空;Ⅳ棧和隊(duì)列都能用于遞歸過(guò)程實(shí)現(xiàn);Ⅴ棧的特點(diǎn)是先進(jìn)后出、隊(duì)列的特點(diǎn)是先進(jìn)先出，其中正確的是(　　)

A.Ⅰ和V
B.Ⅰ、Ⅱ、V
C.Ⅲ和V
D.Ⅱ、Ⅳ、V

7.二維數(shù)組A按行序優(yōu)先順序存儲(chǔ)，每個(gè)數(shù)據(jù)元素占1個(gè)存儲(chǔ)單元。若數(shù)據(jù)元素A[1][1]的存儲(chǔ)地址是420，A[3][3]的存儲(chǔ)地址是446，則A[5][5]的存儲(chǔ)地址是(　　)

A.470
B.471
C.472
D.473

8.若對(duì)一棵含有199個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按自上而下、從左到右依次對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則樹(shù)中最后一個(gè)結(jié)點(diǎn)(即編號(hào)為199)的雙親結(jié)點(diǎn)的編號(hào)為(　　)

A.99
B.100
C.101
D.198

9.對(duì)長(zhǎng)度為15的有序順序表進(jìn)行二分查找，在各記錄的查找概率均相等的情況下，查找成功時(shí)平均查找長(zhǎng)度(ASL)為(　　)

A.

B.

C.

D.

10.在如題10圖所示的有向圖中，從頂點(diǎn)1出發(fā)進(jìn)行深度優(yōu)先搜索可得到的結(jié)果序列是(　　)          題10圖

A.1423
B.1432
C.1342
D.1243

11.設(shè)森林F中有三棵樹(shù)，其結(jié)點(diǎn)的個(gè)數(shù)分別為m1、m2、m3，則與F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)數(shù)是(　　)

A.m1+m2
B.m2+m3
C.m1+m3
D.m1+m2+m3

12.假設(shè)通信電文使用的字符集為{a，b，e，d，e，f}，各字符在電文中出現(xiàn)的頻率分別為{34，5，12，23，8，18}，利用構(gòu)造Huffman樹(shù)對(duì)每個(gè)字符進(jìn)行編碼，則其中編碼長(zhǎng)度最長(zhǎng)的字符是(　　)

A.a, b
B.a，d
C.b，e
D.e，f

13.元素的進(jìn)棧次序?yàn)锳，B，C，D，E，出棧的第一個(gè)元素為E，則第四個(gè)出棧的元素為(　　)

A.D
B.C
C.B
D.A

14.平均時(shí)間復(fù)雜度和在最壞情況下的時(shí)間復(fù)雜度均是O(nlog2n)的排序算法是(　　)

A.插入排序
B.快速排序
C.選擇排序
D.堆排序

15.在待排記錄中其關(guān)鍵字序列基本有序的前提下，時(shí)間效率最高的排序方法是(　　)

A.直接插入排序
B.快速排序
C.選擇排序
D.堆排序

二、填空題(本大題共13小題，每小題2分，共26分)

11.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)又稱(chēng)為物理結(jié)構(gòu)，可分為順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、_______以及散列存儲(chǔ)等幾種方式。

12.一般說(shuō)來(lái)，在每個(gè)邏輯結(jié)構(gòu)上都定義了一組基本運(yùn)算，通常這些運(yùn)算包括：建立、_______、讀取、插入和刪除等。

13.某帶有頭結(jié)點(diǎn)的單鏈表的頭指針為head，則判斷該單鏈表為非空的條件是_______。

14.數(shù)組Q[n]表示一個(gè)循環(huán)隊(duì)列，設(shè)f的值為隊(duì)列中第一個(gè)元素的位置，r的值為隊(duì)列中實(shí)際隊(duì)尾的位置加1，并假定隊(duì)列中最多只有n-1個(gè)元素，則計(jì)算隊(duì)列中元素個(gè)數(shù)的公式是_______.

15.稀疏矩陣可以采用_______方法進(jìn)行壓縮存儲(chǔ)。

16.含有11個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中度為l的結(jié)點(diǎn)的個(gè)數(shù)最多為_(kāi)______。

17.高度(深度)為k的二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)最多是2K-1、最少是_______。

18.對(duì)于有n個(gè)頂點(diǎn)的無(wú)向圖，所有生成樹(shù)中都有且僅有_______條邊。

19.設(shè)散列表的地址空間為0到12，散列函數(shù)為h(k)=k mod 13，用線(xiàn)性探測(cè)法解決沖突。現(xiàn)要將關(guān)鍵字序列{10，100，32，45，58，128，3，29，200，400，0}映射到該散列表中，則其中關(guān)鍵字值58的地址為_(kāi)______。

110.假設(shè)有K個(gè)關(guān)鍵字互為同義詞，若用線(xiàn)性探測(cè)法把這K個(gè)關(guān)鍵字用散列函數(shù)H將它們存入長(zhǎng)度為m的散列表中(K≤m)，則至少共需進(jìn)行_______次探測(cè)。

111.在關(guān)鍵字序列{07，12，15，18，27，32，41，92}中用二分法查找和給定值92相等的關(guān)鍵字，在查找過(guò)程中依次和給定值92比較的關(guān)鍵字是_______。

112.影響排序算法時(shí)間復(fù)雜度的兩個(gè)因素是關(guān)鍵字的_______次數(shù)和記錄的移動(dòng)次數(shù)。

113.在直接插入、直接選擇和冒泡這三種排序方法中，不穩(wěn)定的排序方法是_______。

三、應(yīng)用題(本大題共5小題，每小題6分，共30分)

21.設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，7個(gè)元素abcdefg依次進(jìn)入棧S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出隊(duì)的順序是bdcfeag?，F(xiàn)要求：(1)棧S容量至少是多少?(2)在(1)的情況下，畫(huà)出該棧中元素最多時(shí)的一個(gè)狀態(tài)示意圖。

22.某二叉樹(shù)結(jié)點(diǎn)的中序遍歷序列為ABCDEFG、后序遍歷序列為BDCAFGE?，F(xiàn)要求：(1)畫(huà)出該二叉樹(shù);(2)寫(xiě)出該二叉樹(shù)的先序遍歷序列;(3)該二叉樹(shù)所對(duì)應(yīng)的森林包括幾棵樹(shù)?

23.假設(shè)有一棵完全二叉樹(shù)按自上而下、從左到右的層序組織包含A、B、C、D、E、F、G這7個(gè)結(jié)點(diǎn)，分別給出其鄰接矩陣和鄰接表。

24.要求給出至少2個(gè)不同的關(guān)鍵字序列，均能構(gòu)造出如題32圖所示的二叉排序樹(shù);對(duì)此你會(huì)得出什么結(jié)論?題32圖

25.采用快速排序方法對(duì)關(guān)鍵字序列{265，301，751，129，937，863，742，694，076，438}進(jìn)行升序排序，寫(xiě)出其每趟排序結(jié)束后的關(guān)鍵字序列。

四、算法設(shè)計(jì)題(本大題共2小題，每小題7分。共14分)

31.寫(xiě)出復(fù)制一棵二叉樹(shù)的算法。設(shè)原二叉樹(shù)根結(jié)點(diǎn)由指針root指向，復(fù)制得到的二叉樹(shù)根結(jié)點(diǎn)由指針newroot指向，函數(shù)頭為：void CopyTree( BTNode *root, BTNode * newroot )，二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)為：typedef struct btnode {      DataType data;     struct btnode *lchild, *rchild;}BTNode, *BTree;

32.已知帶頭結(jié)點(diǎn)的單鏈表L是按數(shù)據(jù)域值非遞減有序鏈接的，試寫(xiě)一算法將值為x的結(jié)點(diǎn)插入表L中，使得L仍然是有序鏈接的。