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

1、精選學(xué)習(xí)資料 - - - 歡迎下載要求： 全部的題目的解答均寫在答題紙上,需寫清晰題目的序號(hào)；每張答題紙都要寫上姓名和學(xué)號(hào)；一.單項(xiàng)選擇題（每道題1.5 分,共計(jì) 30 分）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 funint nint i=1; while i<=ni+;a. onb. on c. onlog 2nd. olog 2n3. 在一個(gè)長(zhǎng)度為n 的有序次序表中刪除元素值為x 的元素時(shí),在查找元素x 時(shí)采納二分查找,此時(shí)的時(shí)間復(fù)雜度為；

2、a. onb. onlog 2nc. on 2d. on 4. 在一個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表l 中,刪除元素值為x 的結(jié)點(diǎn),算法的時(shí)間復(fù)雜度為；a. onb. on c. onlog 2nd. on 25. 如一個(gè)棧采納數(shù)組s0.n-1 存放其元素, 初始時(shí)棧頂指針為n,就以下元素x 進(jìn) 棧的正確操作為；a.top+;stop=x;b.stop=x;top+;c.top-;stop=x;b.stop=x;top-;6. 中綴表達(dá)式“2*3+4 - 1”的后綴表達(dá)式為,其中 #表示一個(gè)數(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)形隊(duì)列中數(shù)組的下標(biāo)為0 n - 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 和 fr

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

5、3. 設(shè)無(wú)向連通圖有n 個(gè)頂點(diǎn) e 條邊,如滿意,就圖中肯定有回路；a. e nb. e<nc. e=n- 1d. 2e n14. 對(duì)于 aoe 網(wǎng)的關(guān)鍵路徑,以下表達(dá)為正確的；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ú)的d. 任何一個(gè)活動(dòng)連續(xù)時(shí)間的轉(zhuǎn)變可能會(huì)影響關(guān)鍵路徑的轉(zhuǎn)變15. 設(shè)有 100 個(gè)元素的有序表,用折半查找時(shí),不勝利時(shí)最大的比較次數(shù)為；a. 25b. 50c. 10d. 716. 在一棵 m 階 b-樹(shù)中刪除一個(gè)關(guān)鍵字會(huì)引起合并,就該結(jié)點(diǎn)原有個(gè)關(guān)鍵字；a. 1

6、b.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. onb. onlog 2nc. on 2d. on 19. 用某種排序方法對(duì)數(shù)據(jù)序列24、88、21、48、15、27、69、35、20 進(jìn)行遞增排序,元素序列精品學(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. 簡(jiǎn)潔選擇排序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二.問(wèn)答題（共4 小題,每道題10 分,共計(jì) 40 分）1. 假如對(duì)含有n（ n>1）個(gè)元素的線性

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

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

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

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

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

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

14、c二.問(wèn)答題（共4 小題,每道題10 分,共計(jì) 40 分）1. 答：此題答案為（3）,由于實(shí)現(xiàn)上述4 種運(yùn)算的時(shí)間復(fù)雜度均為o1 ；【評(píng)分說(shuō)明】選擇結(jié)果占4 分,理由占6 分；如結(jié)果錯(cuò)誤,但對(duì)各操作時(shí)間復(fù)雜度作了分析,可給2 5 分；2. 答：結(jié)點(diǎn)總數(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；所以,該樹(shù)的結(jié)點(diǎn)總數(shù)為25,度為4的結(jié)點(diǎn)個(gè)數(shù)為2；【評(píng)分說(shuō)明】結(jié)果為4 分,過(guò)程占6 分；3. 答：此方法

15、不能求得最小生成樹(shù)；例如,對(duì)于如圖5.1（ a）所示的帶權(quán)連通無(wú)向圖,依據(jù)上述方法從頂點(diǎn) 0 開(kāi)頭求得的結(jié)果為 5.1（b）所示的樹(shù),明顯它不為最小生成樹(shù), 正確的最小生成樹(shù)如圖 5.1（c）所示；在有些情形下,上述方法無(wú)法求得結(jié)果,例如對(duì)于如圖5.1（ d）所示的帶權(quán)連通無(wú)向 圖,從頂點(diǎn)0 動(dòng)身,找到頂點(diǎn)1（邊（ 0、1） ,從頂點(diǎn)1 動(dòng)身,找到頂點(diǎn)3（邊（ 1、3） ,再?gòu)捻旤c(diǎn) 3 動(dòng)身,找到頂點(diǎn)0（邊（ 3、0）,這樣構(gòu)成回路,就不能求得最小生成樹(shù)了；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求最小生成樹(shù)的反例（ d）精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載說(shuō)明：只需給出一種情形即可；【評(píng)分說(shuō)明】回答不能求得最小生成樹(shù)得5 分,反例為5 分；如指出可求得最小生成樹(shù),依據(jù)證明過(guò)程給1 2 分；精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載4. 答：（ 1）先序遍歷得到的序列為：12、5、2、8、6、10、16、15、18、20 ,中序序列為一個(gè)有序序列,所以為：2、5、6、8、10、12、15、

17、16、18、20 ,由先序序列和中序序列可以構(gòu)造出對(duì)應(yīng)的二叉樹(shù),如圖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【評(píng)分說(shuō)明】 （ 1）小題占6 分,（2）（ 3）小題各占2 分；三.算法設(shè)計(jì)題（每道題10 分,共計(jì) 30 分）1

18、. 設(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 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í)資料 - - - 歡迎下載算法的時(shí)間復(fù)雜度為om+n ,空間復(fù)雜度為ominm、n ；【評(píng)

20、分說(shuō)明】算法為8 分,算法的時(shí)間復(fù)雜度和空間復(fù)雜度各占1 分；2. 假設(shè)二叉樹(shù)b采納二叉鏈儲(chǔ)備結(jié)構(gòu),設(shè)計(jì)一個(gè)算法voidfindparentbtnode*b、elemtypex、btnode*&p 求指定值為x 的結(jié)點(diǎn)的雙親結(jié)點(diǎn)p,提示,根結(jié)點(diǎn)的雙親為 null ,如未找到這樣的結(jié)點(diǎn),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;【評(píng)分說(shuō)明】此題有多種解法,相應(yīng)給分；3. 假設(shè)一個(gè)連通圖采納鄰接表g 儲(chǔ)備結(jié)構(gòu)表示；設(shè)計(jì)一個(gè)算法, 求起點(diǎn)u 到終點(diǎn) v 的經(jīng)過(guò)頂點(diǎn)k 的全部路徑；解：算法如下：int visitedmaxv=0;/ 全局變量void pathallalgraph*g、int u、int v

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

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