數(shù)據(jù)結構考試題3

1、要求：所有的題目的解答均寫在答題紙上，需寫清楚題目的序號。每張答題紙都要寫上姓名和學號。一、單項選擇題（每小題2分，共計40分）1. 數(shù)據(jù)結構是指 。A. 一種數(shù)據(jù)類型B. 數(shù)據(jù)的存儲結構C. 一組性質相同的數(shù)據(jù)元素的集合D. 相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合2. 以下算法的時間復雜度為 。void fun(int n)int i=1;while (i<=n)i+;A. O(n)B. O()C. O(nlog2n)D. O(log2n)3. 現(xiàn)要設計一個高效的算法，在一個長度為n的有序順序表中刪除所有元素值為x的元素（假設這樣的元素是不唯一的），這樣的算法時間復雜度為 。A

2、. O(n)B. O(nlog2n)C. O(n2)D. O()4. 在一個帶頭結點的循環(huán)雙鏈表L中，要刪除p所指結點，算法的時間復雜度為 。A. O(n)B. O()C. O(1)D. O(n2)5. 若一個棧采用數(shù)組s0.n-1存放其元素，初始時棧頂指針top為n，則以下元素x進棧的正確操作是 。A.top+;stop=x;B.stop=x;top+;C.top-;stop=x;D.stop=x;top-;6. 中綴表達式“2*(3+4)-1”的后綴表達式是 ，其中#表示一個數(shù)值的結束。A. 2#3#4#1#*+-B. 2#3#4#+*1#-C. 2#3#4#*+1#-D. -+*2#3#

3、4#1#7. 設循環(huán)隊列中數(shù)組的下標為0N-1，其隊頭、隊尾指針分別為front和rear（front指向隊列中隊頭元素的前一個位置，rear指向隊尾元素的位置），則其元素個數(shù)為 。A. rear-frontB. rear-front-1C. (rear-front)N+1D. (rear-front+N)N8. 若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，隊頭指針front指向隊列中隊頭元素的前一個位置，隊尾指針rear指向隊尾元素的位置。若當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為 。A. 1和5B. 2和4C. 4和2D.

4、 5和19. 一棵高度為h（h1）的完全二叉樹至少有 個結點。A. 2h-1B. 2hC. 2h+1D. 2h-1+110. 一棵含有n個結點的線索二叉樹中，其線索個數(shù)為 。A. 2nB. n-1C. n+1D. n11. 設一棵哈夫曼樹中有1999個結點，該哈夫曼樹用于對 個字符進行編碼。A. 999B. 998C. 1000D. 100112. 一個含有n個頂點的無向連通圖采用鄰接矩陣存儲，則該矩陣一定是 。A. 對稱矩陣B. 非對稱矩陣C. 稀疏矩陣D. 稠密矩陣13. 設無向連通圖有n個頂點e條邊，若滿足 ，則圖中一定有回路。A. enB. e<nC. e=n-1D. 2en14

5、. 對于AOE網的關鍵路徑，以下敘述 是正確的。A. 任何一個關鍵活動提前完成，則整個工程一定會提前完成B. 完成整個工程的最短時間是從源點到匯點的最短路徑長度C. 一個AOE網的關鍵路徑一定是唯一的D. 任何一個活動持續(xù)時間的改變可能會影響關鍵路徑的改變15. 設有100個元素的有序表，用折半查找時，不成功時最大的比較次數(shù)是 。A. 25B. 50C. 10D. 716. 在一棵m階B-樹中刪除一個關鍵字會引起合并，則該結點原有 個關鍵字。A. 1B. ém/2ùC. ém/2ù-1D. ém/2ù+117. 哈希查找方法一般適用于

6、 情況下的查找。A. 查找表為鏈表B. 查找表為有序表C. 關鍵字集合比地址集合大得多D. 關鍵字集合與地址集合之間存在著某種對應關系。18. 對含有n個元素的順序表采用直接插入排序方法進行排序，在最好情況下算法的時間復雜度為 。A. O(n)B. O(nlog2n)C. O(n2)D. O()19. 用某種排序方法對數(shù)據(jù)序列24,88,21,48,15,27,69,35,20進行遞增排序，元素序列的變化情況如下：（1）24,88,21,48,15,27,69,35,20（2）20,15,21,24,48,27,69,35,88（3）15,20,21,24,35,27,48,69,88（4）1

7、5,20,21,24,27,35,48,69,88則所采用的排序方法是 。A. 快速排序B. 簡單選擇排序C. 直接插入排序D. 二路歸并排序20. 以下排序方法中， 不需要進行關鍵字的比較。A.快速排序B.歸并排序C.基數(shù)排序D.堆排序二、問答題（共4小題，每小題10分，共計40分）1. 如果一個含有n（n>1）個元素的線性表的運算只有4種：刪除第一個元素；刪除最后一個元素；在第一個元素前面插入新元素；在最后一個元素的后面插入新元素，則最好使用以下哪種存儲結構（所有鏈表均帶有頭結點），并簡要說明理由。（1）只有尾結點指針沒有頭結點指針的循環(huán)單鏈表（2）只有尾結點指針沒有頭結點指針的非循

8、環(huán)雙鏈表（3）只有頭結點指針沒有尾結點指針的循環(huán)雙鏈表（4）既有頭結點指針也有尾結點指針的循環(huán)單鏈表2. 對于圖1所示的帶權有向圖，采用Dijkstra算法求從頂點0到其他頂點的最短路徑，要求給出求解過程，包括每一步的S集合、dist和path數(shù)組元素。圖1 一個有向圖3. 有一棵二叉排序樹按先序遍歷得到的序列為：(12,5,2,8,6,10,16,15,18,20)?；卮鹨韵聠栴}：（1）畫出該二叉排序樹。（2）給出該二叉排序樹的中序遍歷序列。（3）求在等概率下的查找成功和不成功情況下的平均查找長度。4. 一個含有n個互不相同的整數(shù)的數(shù)組R1.n，其中所有元素是遞減有序的，將其看成是一棵完全二

9、叉樹，該樹構成一個大根堆嗎？若不是，請給一個反例，若是，請說明理由。三、算法設計題（每小題10分，共計20分）1. 設A和B是兩個結點個數(shù)分別為m和n的單鏈表（帶頭結點），其中元素遞增有序。設計一個盡可能高效的算法求A和B的交集，要求不破壞A、B的結點，將交集存放在單鏈表C中。給出你所設計的算法的時間復雜度和空間復雜度。2. 假設二叉樹b采用二叉鏈存儲結構，設計一個算法void findparent(BTNode *b,ElemType x,BTNode *&p)求指定值為x的結點（假設這樣的結點是唯一的）的雙親結點地址p，提示，根結點的雙親為NULL，若在b中未找到值為x的結點，p亦

10、為NULL?！皵?shù)據(jù)結構”考試試題（A）參考答案要求：所有的題目的解答均寫在答題紙上，需寫清楚題目的序號。每張答題紙都要寫上姓名和學號。一、單項選擇題（每小題2分，共計40分）1. D2. A3. A4. C5. C6. B7. D8. B9. A10. C11. C12. A13. A14. D15. D16. C17. D18. A19. A20. C二、問答題（共4小題，每小題10分，共計40分）1. 答：本題答案為（3），因為實現(xiàn)上述4種運算的時間復雜度均為O(1)。【評分說明】選擇結果占4分，理由占6分。若結果錯誤，但對各操作時間復雜度作了分析，可給25分。2. 答：該圖對應的鄰接矩陣

11、如下：在求最短路徑時，S（存放頂點集），dist（存放最短路徑長度）和path（存放最短路徑）的變化如下： S dist path 0 1 2 3 4 0 1 2 3 4 0 0, 4 0, 1 ,4 0,1,2,4 0,1,2,3,40692000-100599204040056720411005672041100567204110最后得到的結果如下：頂點0到頂點1的最短距離為5，最短路徑為：0、4、1頂點0到頂點2的最短距離為6，最短路徑為：0、4、1、2頂點0到頂點3的最短距離為7，最短路徑為：0、4、1、3頂點0到頂點4的最短距離為2，最短路徑為：0、4。3. 答：（1）先序遍歷得到的

12、序列為：(12,5,2,8,6,10,16,15,18,20)，中序序列是一個有序序列，所以為：(2,5,6,8,10,12,15,16,18,20)，由先序序列和中序序列可以構造出對應的二叉樹，如圖2所示。（2）中序遍歷序列為：2,5,6,8,10,12,15,16,18,20。（3）ASL成功=(1×1+2×2+4×3+3×4)/10=29/10。ASL不成功=(5×3+6×4/11=39/11。圖2【評分說明】（1）小題占6分，（2）（3）小題各占2分。4. 該數(shù)組一定構成一個大根堆。當R是遞減時，其數(shù)組元素為k1、k2、kn，

13、從中看出下標越大的元素值越小，對于任一元素ki，有ki>k2i，ki>k2i+1（i<n/2），這正好滿足大根堆的特性，所以構成一個大根堆?！驹u分說明】回答是給5分，說明理由給5分。三、算法設計題（每小題10分，共計20分）1. 設A和B是兩個結點個數(shù)分別為m和n的單鏈表（帶頭結點），其中元素遞增有序。設計一個盡可能高效的算法求A和B的交集，要求不破壞A、B的結點，將交集存放在單鏈表C中。給出你所設計的算法的時間復雜度和空間復雜度。解：算法如下：void insertion(LinkList *A,LinkList *B,LinkList *&C)LinkList *

14、p=A->next,*q=B->next,*s,*t;C=(LinkList *)malloc(sizeof(LinkList);t=C;while (p!=NULL && q!=NULL)if (p->data=q->data)s=(LinkList *)malloc(sizeof(LinkList);s->data=p->data;t->next=s;t=s;p=p->next;q=q->next;else if (p->data<q->data)p=p->next;elseq=q->nex

15、t;t->next=NULL;算法的時間復雜度為O(m+n)，空間復雜度為O(MIN(m,n)。【評分說明】算法為8分，算法的時間復雜度和空間復雜度各占1分。2. 假設二叉樹b采用二叉鏈存儲結構，設計一個算法void findparent(BTNode *b,ElemType x,BTNode *&p)求指定值為x的結點的雙親結點p，提示，根結點的雙親為NULL，若未找到這樣的結點，p亦為NULL。解：算法如下：void findparent(BTNode *b,ElemType x,BTNode *&p)if (b!=NULL)if (b->data=x) p=NULL;e