數(shù)據(jù)結(jié)構(gòu)考試題3

1、要求：所有的題目的解答均寫在答題紙上，需寫清楚題目的序號(hào)。每張答題紙都要寫上姓名和學(xué)號(hào)。一、單項(xiàng)選擇題（每小題2分，共計(jì)40分）1. 數(shù)據(jù)結(jié)構(gòu)是指 。A. 一種數(shù)據(jù)類型B. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C. 一組性質(zhì)相同的數(shù)據(jù)元素的集合D. 相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合2. 以下算法的時(shí)間復(fù)雜度為 。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)要設(shè)計(jì)一個(gè)高效的算法，在一個(gè)長(zhǎng)度為n的有序順序表中刪除所有元素值為x的元素（假設(shè)這樣的元素是不唯一的），這樣的算法時(shí)間復(fù)雜度為 。A

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

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

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

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

6、 情況下的查找。A. 查找表為鏈表B. 查找表為有序表C. 關(guān)鍵字集合比地址集合大得多D. 關(guān)鍵字集合與地址集合之間存在著某種對(duì)應(yīng)關(guān)系。18. 對(duì)含有n個(gè)元素的順序表采用直接插入排序方法進(jìn)行排序，在最好情況下算法的時(shí)間復(fù)雜度為 。A. O(n)B. O(nlog2n)C. O(n2)D. O()19. 用某種排序方法對(duì)數(shù)據(jù)序列24,88,21,48,15,27,69,35,20進(jìn)行遞增排序，元素序列的變化情況如下：（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. 簡(jiǎn)單選擇排序C. 直接插入排序D. 二路歸并排序20. 以下排序方法中， 不需要進(jìn)行關(guān)鍵字的比較。A.快速排序B.歸并排序C.基數(shù)排序D.堆排序二、問(wèn)答題（共4小題，每小題10分，共計(jì)40分）1. 如果一個(gè)含有n（n>1）個(gè)元素的線性表的運(yùn)算只有4種：刪除第一個(gè)元素；刪除最后一個(gè)元素；在第一個(gè)元素前面插入新元素；在最后一個(gè)元素的后面插入新元素，則最好使用以下哪種存儲(chǔ)結(jié)構(gòu)（所有鏈表均帶有頭結(jié)點(diǎn)），并簡(jiǎn)要說(shuō)明理由。（1）只有尾結(jié)點(diǎn)指針沒(méi)有頭結(jié)點(diǎn)指針的循環(huán)單鏈表（2）只有尾結(jié)點(diǎn)指針沒(méi)有頭結(jié)點(diǎn)指針的非循

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

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

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

11、如下：在求最短路徑時(shí)，S（存放頂點(diǎn)集），dist（存放最短路徑長(zhǎng)度）和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最后得到的結(jié)果如下：頂點(diǎn)0到頂點(diǎn)1的最短距離為5，最短路徑為：0、4、1頂點(diǎn)0到頂點(diǎn)2的最短距離為6，最短路徑為：0、4、1、2頂點(diǎn)0到頂點(diǎn)3的最短距離為7，最短路徑為：0、4、1、3頂點(diǎn)0到頂點(diǎn)4的最短距離為2，最短路徑為：0、4。3. 答：（1）先序遍歷得到的

12、序列為：(12,5,2,8,6,10,16,15,18,20)，中序序列是一個(gè)有序序列，所以為：(2,5,6,8,10,12,15,16,18,20)，由先序序列和中序序列可以構(gòu)造出對(duì)應(yīng)的二叉樹，如圖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【評(píng)分說(shuō)明】（1）小題占6分，（2）（3）小題各占2分。4. 該數(shù)組一定構(gòu)成一個(gè)大根堆。當(dāng)R是遞減時(shí)，其數(shù)組元素為k1、k2、kn，

13、從中看出下標(biāo)越大的元素值越小，對(duì)于任一元素ki，有ki>k2i，ki>k2i+1（i<n/2），這正好滿足大根堆的特性，所以構(gòu)成一個(gè)大根堆。【評(píng)分說(shuō)明】回答是給5分，說(shuō)明理由給5分。三、算法設(shè)計(jì)題（每小題10分，共計(jì)20分）1. 設(shè)A和B是兩個(gè)結(jié)點(diǎn)個(gè)數(shù)分別為m和n的單鏈表（帶頭結(jié)點(diǎn)），其中元素遞增有序。設(shè)計(jì)一個(gè)盡可能高效的算法求A和B的交集，要求不破壞A、B的結(jié)點(diǎn)，將交集存放在單鏈表C中。給出你所設(shè)計(jì)的算法的時(shí)間復(fù)雜度和空間復(fù)雜度。解：算法如下：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;算法的時(shí)間復(fù)雜度為O(m+n)，空間復(fù)雜度為O(MIN(m,n)?！驹u(píng)分說(shuō)明】算法為8分，算法的時(shí)間復(fù)雜度和空間復(fù)雜度各占1分。2. 假設(shè)二叉樹b采用二叉鏈存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法void findparent(BTNode *b,ElemType x,BTNode *&p)求指定值為x的結(jié)點(diǎn)的雙親結(jié)點(diǎn)p，提示，根結(jié)點(diǎn)的雙親為NULL，若未找到這樣的結(jié)點(diǎn)，p亦為NULL。解：算法如下：void findparent(BTNode *b,ElemType x,BTNode *&p)if (b!=NULL)if (b->data=x) p=NULL;e