最新數(shù)據(jù)結(jié)構(gòu)考試題3只是分享

1、學(xué)習(xí)資料要求： 所有的題目的解答均寫在答題紙上，需寫清楚題目的序號(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(n )C. O(nlog2n)D. O(log 2n)3. 現(xiàn)要設(shè)計(jì)一個(gè)高效的算法，在一個(gè)長度為n 的有序順序表中刪除所有元素值為x 的元素（假設(shè)這樣的元素是不唯一的），這樣

2、的算法時(shí)間復(fù)雜度為。A. O( n)B. O( nlog2n)C. O(n2)D. O(n )4. 在一個(gè)帶頭結(jié)點(diǎn)的循環(huán)雙鏈表L 中，要?jiǎng)h除 p 所指結(jié)點(diǎn)，算法的時(shí)間復(fù)雜度為。A. O( n)B. O( n )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

3、#+*1# -C. 2#3#4#*+1# -D. - +*2#3#4#1#7. 設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)為0 N - 1，其隊(duì)頭、隊(duì)尾指針分別為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ù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，隊(duì)頭指針front 指向隊(duì)列中隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針 rear 指向隊(duì)尾元素的位置。若當(dāng)前rear 和 front 的值分別為 0 和

4、 3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear 和 front 的值分別為。精品文檔學(xué)習(xí)資料A.1和5B.2和4C.4和2D.5和19.一棵高度為h（ h 1）的完全二叉樹至少有個(gè)結(jié)點(diǎn)。A. 2 h-1B. 2hC. 2h+1D. 2h-1+110.一棵含有n 個(gè)結(jié)點(diǎn)的線索二叉樹中，其線索個(gè)數(shù)為。A. 2 nB. 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)的無向連通圖采用鄰接矩陣存儲(chǔ)，則該矩陣一定是。A.對(duì)稱矩陣B. 非對(duì)稱矩陣C.稀疏矩陣D. 稠

5、密矩陣13.設(shè)無向連通圖有 n 個(gè)頂點(diǎn) e 條邊，若滿足，則圖中一定有回路。A. e nB. e<nC. e=n- 1D. 2e n14.對(duì)于 AOE 網(wǎng)的關(guān)鍵路徑，以下敘述是正確的。A. 任何一個(gè)關(guān)鍵活動(dòng)提前完成，則整個(gè)工程一定會(huì)提前完成B. 完成整個(gè)工程的最短時(shí)間是從源點(diǎn)到匯點(diǎn)的最短路徑長度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.

6、1B.m/2C. m/2 - 1D.m/2 +117.哈希查找方法一般適用于情況下的查找。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(n )19. 用某種排序方法對(duì)數(shù)據(jù)序列24,88,21,48,15,27,69,35,20 進(jìn)行遞增排序，元素序列精品文檔學(xué)習(xí)資料的變化情況如下：（ 1） 24,88,21,48,15,27,69,35,20（ 2） 20,1

7、5,21,24,48,27,69,35,88（ 3） 15,20,21,24,35,27,48,69,88（ 4） 15,20,21,24,27,35,48,69,88則所采用的排序方法是。A. 快速排序B. 簡單選擇排序C. 直接插入排序D. 二路歸并排序20. 以下排序方法中，不需要進(jìn)行關(guān)鍵字的比較。A. 快速排序B.歸并排序C.基數(shù)排序D.堆排序二、問答題（共 4 小題，每小題 10 分，共計(jì) 40 分）1. 如果一個(gè)含有 n（ n>1）個(gè)元素的線性表的運(yùn)算只有 4 種：刪除第一個(gè)元素；刪除最后一個(gè)元素；在第一個(gè)元素前面插入新元素；在最后一個(gè)元素的后面插入新元素，則最好使用以下哪種

8、存儲(chǔ)結(jié)構(gòu)（所有鏈表均帶有頭結(jié)點(diǎn)），并簡要說明理由。（ 1）只有尾結(jié)點(diǎn)指針沒有頭結(jié)點(diǎn)指針的循環(huán)單鏈表（ 2）只有尾結(jié)點(diǎn)指針沒有頭結(jié)點(diǎn)指針的非循環(huán)雙鏈表（ 3）只有頭結(jié)點(diǎn)指針沒有尾結(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)的最短路徑，要求給出求解過程，包括每一步的S 集合、 dist 和 path 數(shù)組元素。4237061239122圖 1 一個(gè)有向圖3. 有一棵二叉排序樹按先序遍歷得到的序列為：(12,5,2,8,6,10,16,15,18,20) ?；卮鹨韵聠栴}：（ 1）畫出該二

9、叉排序樹。（ 2）給出該二叉排序樹的中序遍歷序列。（ 3）求在等概率下的查找成功和不成功情況下的平均查找長度。4. 一個(gè)含有 n 個(gè)互不相同的整數(shù)的數(shù)組 R1.n，其中所有元素是遞減有序的，將其看成是一棵完全二叉樹，該樹構(gòu)成一個(gè)大根堆嗎？若不是，請給一個(gè)反例，若是，請說明理由。精品文檔學(xué)習(xí)資料三、算法設(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è)二

10、叉樹b采用二叉鏈存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法voidfindparent(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 亦為 NULL 。精品文檔學(xué)習(xí)資料“數(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.

11、D15. D16. C17. D18. A19. A20. C二、問答題（共 4 小題，每小題 10 分，共計(jì) 40 分）1. 答：本題答案為（3），因?yàn)閷?shí)現(xiàn)上述【評(píng)分說明】選擇結(jié)果占4 分，理由占4 種運(yùn)算的時(shí)間復(fù)雜度均為O(1) 。6 分。若結(jié)果錯(cuò)誤，但對(duì)各操作時(shí)間復(fù)雜度作了分析，可給2 5 分。2. 答：該圖對(duì)應(yīng)的鄰接矩陣如下：0692012020370在求最短路徑時(shí)，S（存放頂點(diǎn)集） ， dist （存放最短路徑長度）和path （存放最短路徑）的變化如下：Sdistpath012340123400692000- 100, 405992040400, 1 ,405672041100,1

12、,2,405672041100,1,2,3,40567204110最后得到的結(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,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）中序遍

13、歷序列為： 2,5,6,8,10,12,15,16,18,20 。精品文檔學(xué)習(xí)資料（ 3）ASL 成功 =(1 ×1+2×2+4×3+3×4)/10=29/10 。ASL 不成功 =(5 ×3+6 ×4/11=39/11 。1251628151861020圖 2【評(píng)分說明】（ 1）小題占6 分，（2）（ 3）小題各占2 分。4. 該數(shù)組一定構(gòu)成一個(gè)大根堆。當(dāng) R 是遞減時(shí)，其數(shù)組元素為 k1、 k2、 、 kn，從中看出下標(biāo)越大的元素值越小，對(duì)于任一元素 ki，有 ki>k2i，ki >k2i+1 （i <n/2），

14、這正好滿足大根堆的特性，所以構(gòu)成一個(gè)大根堆。【評(píng)分說明】回答是給5 分，說明理由給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 *p=A->next,*q=B->next,*s,*t; C=

15、(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->next;精品文檔學(xué)習(xí)資料t->next=NULL;算法的時(shí)間復(fù)雜度為O(m+n)，空間復(fù)雜度為O(MIN( m,n)。【評(píng)分說明】算法為8 分，算法的時(shí)間復(fù)雜度和空間復(fù)雜度各占1 分。2. 假設(shè)二叉樹b采用二叉鏈存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法voidfindparent(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