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

1、精選學(xué)習(xí)資料 - - - 歡迎下載要求： 全部的題目的解答均寫在答題紙上,需寫清晰題目的序號；每張答題紙都要寫上姓名和學(xué)號；一.單項選擇題（每道題1.5 分,共計 30 分）1. 數(shù)據(jù)結(jié)構(gòu)為指；a. 一種數(shù)據(jù)類型b. 數(shù)據(jù)的儲備結(jié)構(gòu)c. 一組性質(zhì)相同的數(shù)據(jù)元素的集合d. 相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合2. 以下算法的時間復(fù)雜度為；void funint nint i=1; while i<=ni+;a. onb. on c. onlog 2nd. olog 2n3. 在一個長度為n 的有序次序表中刪除元素值為x 的元素時,在查找元素x 時采納二分查找,此時的時間復(fù)雜度為；

2、a. onb. onlog 2nc. on 2d. on 4. 在一個帶頭結(jié)點的循環(huán)單鏈表l 中,刪除元素值為x 的結(jié)點,算法的時間復(fù)雜度為；a. onb. on c. onlog 2nd. on 25. 如一個棧采納數(shù)組s0.n-1 存放其元素, 初始時棧頂指針為n,就以下元素x 進 棧的正確操作為；a.top+;stop=x;b.stop=x;top+;c.top-;stop=x;b.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. -

3、+*2#3#4#1#7. 設(shè)環(huán)形隊列中數(shù)組的下標(biāo)為0 n - 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 指向隊尾元素的位置；如當(dāng)前rear 和 front 的值分別為0 和 3,當(dāng)從隊列中刪除一個元素,再加入兩個元素后,rear 和 fr

4、ont 的值分別為；精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載a. 1 和 5b. 2和 4c. 4 和 29. 一棵深度為d. 5h（ h 1）的完全二叉樹至少有和 1個結(jié)點；a. 2 h-1b. 2hc. 2h+1d. 2 h-1+110. 一棵含有n 個結(jié)點的線索二叉樹中,其線索個數(shù)為；a. 2nb. n- 1c. n+1d. n11. 設(shè)一棵哈夫曼樹中有1999 個結(jié)點,該哈夫曼樹用于對個字符進行編碼；a. 999b. 998c. 1000d. 100112. 一個含有n 個頂點的無向連通圖采納鄰接矩陣儲備,就該矩陣肯定為；a. 對稱矩陣b. 非對稱矩陣c. 稀疏矩陣d.稠密矩陣1

5、3. 設(shè)無向連通圖有n 個頂點 e 條邊,如滿意,就圖中肯定有回路；a. e nb. e<nc. e=n- 1d. 2e n14. 對于 aoe 網(wǎng)的關(guān)鍵路徑,以下表達為正確的；a. 任何一個關(guān)鍵活動提前完成,就整個工程肯定會提前完成b. 完成整個工程的最短時間為從源點到匯點的最短路徑長度c. 一個 aoe 網(wǎng)的關(guān)鍵路徑肯定為唯獨的d. 任何一個活動連續(xù)時間的轉(zhuǎn)變可能會影響關(guān)鍵路徑的轉(zhuǎn)變15. 設(shè)有 100 個元素的有序表,用折半查找時,不勝利時最大的比較次數(shù)為；a. 25b. 50c. 10d. 716. 在一棵 m 階 b-樹中刪除一個關(guān)鍵字會引起合并,就該結(jié)點原有個關(guān)鍵字；a. 1

6、b.m/2c.m/2 - 1d.m/2 +117. 哈希查找方法一般適用于情形下的查找；a. 查找表為鏈表b. 查找表為有序表c. 關(guān)鍵字集合比地址集合大得多d. 關(guān)鍵字集合與地址集合之間存在著某種對應(yīng)關(guān)系；18. 對含有n 個元素的次序表采納直接插入排序方法進行排序,在最好情形下算法的時間復(fù)雜度為；a. onb. onlog 2nc. on 2d. on 19. 用某種排序方法對數(shù)據(jù)序列24、88、21、48、15、27、69、35、20 進行遞增排序,元素序列精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載的變化情形如下：（ 1） 24、88、21、48、15、27、69、35、20（ 2）

7、 20、15、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. 快速排序c. 直接插入排序20. 以下序列為堆的為；b. 簡潔選擇排序d.歸并排序a. 75、65、30、15、25、45、20、10c. 75、45、65、30、15、25、20、10b. 75、65、45、10、30、25、20、15d. 75、45、65、10、25、30、20、15二.問答題（共4 小題,每道題10 分,共計 40 分）1. 假如對含有n（ n>1）個元素的線性

8、表的運算只有4 種：刪除第一個元素；刪除最終一個元素；在第一個元素前面插入新元素；在最終一個元素的后面插入新元素,就最好使用以下哪種儲備結(jié)構(gòu),并簡要說明理由；（ 1）只有尾結(jié)點指針沒有頭結(jié)點指針的循環(huán)單鏈表（ 2）只有尾結(jié)點指針沒有頭結(jié)點指針的非循環(huán)雙鏈表（ 3）只有頭結(jié)點指針沒有尾結(jié)點指針的循環(huán)雙鏈表（ 4）既有頭結(jié)點指針也有尾結(jié)點指針的循環(huán)單鏈表2. 已知一棵度為4 的樹中,其度為0.1.2.3 的結(jié)點數(shù)分別為14.4.3.2,求該樹 的結(jié)點總數(shù)n 和度為 4 的結(jié)點個數(shù),并給出推導(dǎo)過程；3. 有人提出這樣的一種從圖g 中頂點 u 開頭構(gòu)造最小生成樹的方法：假設(shè) g=v ,e為一個具有 n

9、 個頂點的帶權(quán)連通無向圖, t=u ,te 為 g 的最小生成樹, 其中 u 為 t 的頂點集, te 為 t 的邊集,就由 g 構(gòu)造從起始頂點 u 動身的最小生成樹 t 的步驟如下：（ 1）初始化u=u ；以 u 到其他頂點的全部邊為候選邊；（ 2）重復(fù)以下步驟n- 1 次,使得其他n- 1 個頂點被加入到u 中；從候選邊中選擇權(quán)值最小的邊加入到te,設(shè)該邊在 v - u 中的頂點為 v,將 v 加入 u 中；考查頂點v,將 v 與 v - u 頂點集中的全部邊作為新的候選邊；如此方法求得的t 為最小生成樹,請予以證明；如不能求得最小邊,請舉出反例；4. 有一棵二叉排序樹按先序遍歷得到的序列

10、為：12、5、2、8、6、10、16、15、18、20 ；回答以下問題：（ 1）畫出該二叉排序樹；（ 2）給出該二叉排序樹的中序遍歷序列；（ 3）求在等概率下的查找勝利和不勝利情形下的平均查找長度；三.算法設(shè)計題（每道題10 分,共計 30 分）1. 設(shè) a 和 b 為兩個結(jié)點個數(shù)分別為m 和 n 的單鏈表（帶頭結(jié)點） ,其中元素遞增有序；精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載設(shè)計一個盡可能高效的算法求a 和 b 的交集,要求不破壞a .b 的結(jié)點,將交集存放在單鏈表 c 中；給出你所設(shè)計的算法的時間復(fù)雜度和空間復(fù)雜度；2. 假設(shè)二叉樹b采納二叉鏈儲備結(jié)構(gòu),設(shè)計一個算法voidfind

11、parentbtnode*b、elemtypex、btnode*&p 求指定值為x 的結(jié)點的雙親結(jié)點p,提示,根結(jié)點的雙親為 null ,如在 b 中未找到值為x 的結(jié)點, p 亦為 null ；3. 假設(shè)一個連通圖采納鄰接表g 儲備結(jié)構(gòu)表示；設(shè)計一個算法, 求起點u 到終點 v 的經(jīng)過頂點k 的全部路徑；四.附加題（ 10 分）說明：附加題不計入期未考試總分,但計入本課程的總分；假設(shè)某專業(yè)有如干個班,每個班有如干同學(xué),每個同學(xué)包含姓名和分?jǐn)?shù),這樣構(gòu)成一棵樹,如圖1 所示；假設(shè)樹中每個結(jié)點的name 域均不相同,該樹采納孩子兄弟鏈儲備結(jié)構(gòu),其結(jié)點類型定義如下：typedef struc

12、t nodechar name50;/ 專業(yè).班號或姓名float score;/ 分 數(shù)struct node *child;/ 指向最左邊的孩子結(jié)點struct node *brother;/ 指向下一個兄弟結(jié)點 tnode;完成以下算法：（ 1）設(shè)計一個算法求全部的同學(xué)人數(shù)；（ 2）求指定某班的平均分；name:運算機專業(yè)score:0精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載name:計科 1 score:0name:計科 n score:0精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載name:王華score:86name:李明sco

13、re:79name:張兵score:79name:陳強score:85name:許源score:92name:張山score:69精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載圖 1 一棵同學(xué)成果樹精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載“數(shù)據(jù)結(jié)構(gòu)”考試試題（a ）參考答案要求： 全部的題目的解答均寫在答題紙上,需寫清晰題目的序號；每張答題紙都要寫上姓名和學(xué)號；一.單項選擇題（每道題1.5 分,共計 30 分）1. d2. a3. a4. a5. c6. b7. d8. b9. a10. c11. c12. a13. a14. d15. d16. c17. d18. a19. a20.

14、c二.問答題（共4 小題,每道題10 分,共計 40 分）1. 答：此題答案為（3）,由于實現(xiàn)上述4 種運算的時間復(fù)雜度均為o1 ；【評分說明】選擇結(jié)果占4 分,理由占6 分；如結(jié)果錯誤,但對各操作時間復(fù)雜度作了分析,可給2 5 分；2. 答：結(jié)點總數(shù)n=n0+n1+n2+n3+n4,即 n=23+ n4,又有： 度之和 =n- 1=0×n0+1×n1+2×n2+3×n3+4×n4,即 n=17+4 n4,綜合兩式得：n4=2, n=25；所以,該樹的結(jié)點總數(shù)為25,度為4的結(jié)點個數(shù)為2；【評分說明】結(jié)果為4 分,過程占6 分；3. 答：此方法

15、不能求得最小生成樹；例如,對于如圖5.1（ a）所示的帶權(quán)連通無向圖,依據(jù)上述方法從頂點 0 開頭求得的結(jié)果為 5.1（b）所示的樹,明顯它不為最小生成樹, 正確的最小生成樹如圖 5.1（c）所示；在有些情形下,上述方法無法求得結(jié)果,例如對于如圖5.1（ d）所示的帶權(quán)連通無向 圖,從頂點0 動身,找到頂點1（邊（ 0、1） ,從頂點1 動身,找到頂點3（邊（ 1、3） ,再從頂點 3 動身,找到頂點0（邊（ 3、0）,這樣構(gòu)成回路,就不能求得最小生成樹了；0012141313精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載325（ a）325（ b）精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下

16、載精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載0114332012313425精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載（ c）圖 1求最小生成樹的反例（ d）精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載說明：只需給出一種情形即可；【評分說明】回答不能求得最小生成樹得5 分,反例為5 分；如指出可求得最小生成樹,依據(jù)證明過程給1 2 分；精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載4. 答：（ 1）先序遍歷得到的序列為：12、5、2、8、6、10、16、15、18、20 ,中序序列為一個有序序列,所以為：2、5、6、8、10、12、15、

17、16、18、20 ,由先序序列和中序序列可以構(gòu)造出對應(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 ；12精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載52861016151820精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載圖 2【評分說明】 （ 1）小題占6 分,（2）（ 3）小題各占2 分；三.算法設(shè)計題（每道題10 分,共計 30 分）1

18、. 設(shè) a 和 b 為兩個結(jié)點個數(shù)分別為m 和 n 的單鏈表（帶頭結(jié)點） ,其中元素遞增有序；設(shè)計一個盡可能高效的算法求a 和 b 的交集,要求不破壞a .b 的結(jié)點,將交集存放在單鏈表 c 中；給出你所設(shè)計的算法的時間復(fù)雜度和空間復(fù)雜度；解：算法如下：void insertionlinklist *a、linklist *b、linklist *&c linklist *p=a->next、*q=b->next、*s、*t; c=linklist *mallocsizeoflinklist; t=c;while p.=null && q.=nullif p

19、->data=q->datas=linklist *mallocsizeoflinklist; s->data=p->data;t->next=s;t=s;p=p->next; q=q->next;else if p->data<q->data p=p->next;精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載elseq=q->next;精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載t->next=null;精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載算法的時間復(fù)雜度為om+n ,空間復(fù)雜度為ominm、n ；【評

20、分說明】算法為8 分,算法的時間復(fù)雜度和空間復(fù)雜度各占1 分；2. 假設(shè)二叉樹b采納二叉鏈儲備結(jié)構(gòu),設(shè)計一個算法voidfindparentbtnode*b、elemtypex、btnode*&p 求指定值為x 的結(jié)點的雙親結(jié)點p,提示,根結(jié)點的雙親為 null ,如未找到這樣的結(jié)點,p 亦 為 null ；解：算法如下：void findparentbtnode *b、elemtype x、btnode *&pif b.=nullif b->data=x p=null;else if b->lchild.=null && b->lchild-

21、>data=x p=b;else if b->rchild.=null && b->rchild->data=x p=b;elsefindparentb->lchild、x、p; if p=nullfindparentb->rchild、x、p;else p=null;【評分說明】此題有多種解法,相應(yīng)給分；3. 假設(shè)一個連通圖采納鄰接表g 儲備結(jié)構(gòu)表示；設(shè)計一個算法, 求起點u 到終點 v 的經(jīng)過頂點k 的全部路徑；解：算法如下：int visitedmaxv=0;/ 全局變量void pathallalgraph*g、int u、int v

22、、int k、int path、int d/d為到當(dāng)前為止已走過的路徑長度,調(diào)用時初值為-1int m、i; arcnode*p; visitedu=1;d+;/路徑長度增1pathd=u;/將當(dāng)前頂點添加到路徑中if u=v && inpath、d、k=l/輸出一條路徑printf" "for i=0;i<=d;i+printf"%d "、pathi; printf"n"p=g->adjlistu.firstarc;/p指向頂點 u 的第一條弧的弧頭節(jié)點while p.=null精品學(xué)習(xí)資料精選學(xué)習(xí)資料

23、- - - 歡迎下載m=p->adjvex;/m為 u 的鄰接點if visitedm=0/ 如該頂點未標(biāo)記拜訪、 就遞歸拜訪之pathallg、m、v、l、path、d;p=p->nextarc;/ 找 u 的下一個鄰接點visitedu=0;/ 復(fù)原環(huán)境：使該頂點可重新使用int inint path、int d、int k /判定頂點k 為否包含在路徑中int i;for i=0;i<=d;i+if pathi=kreturn 1;return 0;【評分說明】此題采納dfs 算法給出一條路徑時給8 分,采納bfs 算法給出一條路徑時給 6 分；四.附加題（ 10 分）說明：附加題不計入期未考試總分,但計入本課程的總分；假設(shè)某專業(yè)有如干個班,每個班有如干同學(xué),每個同學(xué)包含姓名和分?jǐn)?shù),這樣構(gòu)成一棵樹,如圖1 所示；假設(shè)樹中每個結(jié)點的name 域均不相同,該樹采納孩子兄弟鏈儲備結(jié)構(gòu),其結(jié)點類型定義如下：typedef struct nodechar name50;/ 專業(yè).班號或姓名float score;/ 分 數(shù)struct node *child;/ 指向最左邊的孩子結(jié)點struct node *brother;/