?數(shù)據(jù)結構導論2015年10月真題（02142）

數(shù)據(jù)結構導論2015年10月真題及答案解析（02142）

數(shù)據(jù)結構導論2015年10月真題及答案解析（02142），該試卷為數(shù)據(jù)結構導論自考歷年真題試卷，包含答案及詳細解析。

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

1.“能正確地實現(xiàn)預定的功能，滿足具體問題的需要”。這種評價算法好壞的因素稱為(　　)

A.正確性
B.易讀性
C.健壯性
D.時空性

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

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

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

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

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

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

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

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.下列關于棧和隊列的敘述中：Ⅰ棧和隊列都是線性表;Ⅱ棧和隊列都是順序表;Ⅲ棧和隊列都不能為空;Ⅳ棧和隊列都能用于遞歸過程實現(xiàn);Ⅴ棧的特點是先進后出、隊列的特點是先進先出，其中正確的是(　　)

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

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

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

8.若對一棵含有199個結點的完全二叉樹按自上而下、從左到右依次對結點編號，根結點的編號為1，則樹中最后一個結點(即編號為199)的雙親結點的編號為(　　)

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

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

A.

B.

C.

D.

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

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

11.設森林F中有三棵樹，其結點的個數(shù)分別為m1、m2、m3，則與F對應的二叉樹根結點的右子樹上的結點數(shù)是(　　)

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

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

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

13.元素的進棧次序為A，B，C，D，E，出棧的第一個元素為E，則第四個出棧的元素為(　　)

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

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

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

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

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

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

11.數(shù)據(jù)的存儲結構又稱為物理結構，可分為順序存儲、鏈式存儲、_______以及散列存儲等幾種方式。

12.一般說來，在每個邏輯結構上都定義了一組基本運算，通常這些運算包括：建立、_______、讀取、插入和刪除等。

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

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

15.稀疏矩陣可以采用_______方法進行壓縮存儲。

16.含有11個結點的完全二叉樹中度為l的結點的個數(shù)最多為_______。

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

18.對于有n個頂點的無向圖，所有生成樹中都有且僅有_______條邊。

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

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

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

112.影響排序算法時間復雜度的兩個因素是關鍵字的_______次數(shù)和記錄的移動次數(shù)。

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

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

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

22.某二叉樹結點的中序遍歷序列為ABCDEFG、后序遍歷序列為BDCAFGE。現(xiàn)要求：(1)畫出該二叉樹;(2)寫出該二叉樹的先序遍歷序列;(3)該二叉樹所對應的森林包括幾棵樹?

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

24.要求給出至少2個不同的關鍵字序列，均能構造出如題32圖所示的二叉排序樹;對此你會得出什么結論?題32圖

25.采用快速排序方法對關鍵字序列{265，301，751，129，937，863，742，694，076，438}進行升序排序，寫出其每趟排序結束后的關鍵字序列。

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

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

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