數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題 答案

1、1. 以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（ c ）C、哈希表 2. 一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（ B ） B、1083. 假設(shè)帶頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針為head,則該鏈表為空的判定條件是（ C ）C、head>next= =head 4. 若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出棧可以穿插進(jìn)行，則不可能出現(xiàn)的出棧序列是（ D ）D、2，3，5，1，6，45. 下列關(guān)鍵字序列中，構(gòu)成小根堆的是（ A ）A、12，21，49，33，81，56，69，41 6. 下列數(shù)據(jù)結(jié)構(gòu)中，不屬于二叉樹的是（ A ）A、B樹 7. 用順序存儲的

2、方法來存儲一棵二叉樹，存放在一維數(shù)組A1.N中，若結(jié)點(diǎn)Ai有右孩子，則其右孩子是（ C ）。 C、A2i+1 8. 設(shè)樹T的高度為4，其中度為1、2、3、4的結(jié)點(diǎn)個數(shù)分別為4、2、1、1，則T中葉子數(shù)為（ D ） D、 89. 有數(shù)據(jù)53，30，37，12，45，24，96，從空二叉樹開始逐個插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，則應(yīng)選擇下面哪個序列輸入（ B ）B、37，24，12，30，53，45，9610. 對下面有向圖給出了四種可能的拓?fù)湫蛄校渲绣e誤的是（ C ）C、5，1，6，3，4，2 11. m階B-樹中所有非終端（除根之外）結(jié)點(diǎn)中的關(guān)鍵字個數(shù)必須大于或等于( B ) B、

3、m/2-112. 散列文件也稱為( C ) B 、索引文件13. 數(shù)據(jù)結(jié)構(gòu)是（ D ）D、相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合14. 從邏輯關(guān)系來看，數(shù)據(jù)元素的直接前驅(qū)為0個或1個的數(shù)據(jù)結(jié)構(gòu)只能是（ C ）C、線性結(jié)構(gòu)和樹型結(jié)構(gòu) 15. 設(shè)p為指向雙向循環(huán)鏈表中某個結(jié)點(diǎn)的指針，p所指向的結(jié)點(diǎn)的兩個鏈域分別用pllink和prlink表示，則同樣表示p指針?biāo)赶蚪Y(jié)點(diǎn)的表達(dá)式是（ D ） D、pllinkrlink16. 若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V1.m，topi代表第i個棧( i =1,2)棧頂，棧1的底在v1，棧2的底在Vm，則棧滿的條件是（ B ）B、 top1+1

4、=top2 17. 若一棵二叉樹有11個葉子結(jié)點(diǎn)，則該二叉樹中度為2的結(jié)點(diǎn)個數(shù)是（ A ）A、1018. 樹的先根序列等同于與該樹對應(yīng)的二叉樹的（ A ）A、先序序列19. 下面關(guān)于哈希(Hash，雜湊)查找的說法正確的是( C )C、不存在特別好與壞的哈希函數(shù)，要視情況而定20. 下列序列中，（ D ）是執(zhí)行第一趟快速排序后所得的序列。 D、 68，11，69，23，18 93，7321. 下列關(guān)鍵字序列中，構(gòu)成小根堆的是( D )D、 (15，28，46，37，84，58，62，41)22. ISAM文件和VASM文件屬于( C ) C、索引順序文件 23. 下面程序段的時間復(fù)雜度為（ C

5、 ）for (i=0; i<m; i+)for (j=0; j<n; j+)Aij=i*j;C、O(m*n) 24. 已知指針p和q分別指向某單鏈表中第一個結(jié)點(diǎn)和最后一個結(jié)點(diǎn)。假設(shè)指針s指向另一個單鏈表中某個結(jié)點(diǎn)，則在s所指結(jié)點(diǎn)之后插入上述鏈表應(yīng)執(zhí)行的語句為（ A ）A、q->next=s->next；s->next=p； 25. 為便于判別有向圖中是否存在回路，可借助于（ D ）D、拓?fù)渑判蛩惴?6. 若以S和X分別表示進(jìn)棧和退棧操作，則對初始狀態(tài)為空的?？梢赃M(jìn)行的棧操作系列是（ D ）D、SSSXXSXX27. 設(shè)有一順序棧S，元素s1,s2,s3,s4,s5

6、,s6依次進(jìn)棧，如果6個元素出棧的順序是s2,s3,s4,s6,s5,s1,則棧的容量至少應(yīng)該是( B )B、3 28. 假設(shè)以數(shù)組Am存放循環(huán)隊列的元素。已知隊列的長度為length，指針rear指向隊尾元素的下一個存儲位置，則隊頭元素所在的存儲位 置為（ B ）。B、(rear-length+m)%m 29. 在一個鏈隊列中，front和rear分別為頭指針和尾指針，則插入一個結(jié)點(diǎn)s的操作為（ D ）。D、rear->next=s;rear=s;30. 對于哈希函數(shù)H(key)=key%13,被稱為同義詞的關(guān)鍵字是（ D ）D、25和5131. 采用二叉鏈表存儲的n個結(jié)點(diǎn)的二叉樹，共

7、有空指針（ A ）個。A、n+132. 連通網(wǎng)的最小生成樹是其所有生成樹中（ D ）D、邊的權(quán)值之和最小的生成樹33. 對記錄序列(314，298，508，123，486，145)依次按個位和十位進(jìn)行兩趟基數(shù)排序之后所得結(jié)果為（ B ） B、508，314，123，145，486，29834. 任何一個無向連通圖的最小生成樹( C )。C、一棵或多棵 35. 無向圖的鄰接矩陣是一個( C ) C、對稱矩陣 36. 設(shè)無向圖G-=(V,E)和G=(V,E),如G為G的生成樹，則下列說法中不正確的是( B )。B、G為G 連通分量37. 以v1為起始結(jié)點(diǎn)對下圖進(jìn)行深度優(yōu)先遍歷，正確的遍歷序列是（

8、D ）D、 v1，v2，v5，v6，v7，v3，v438. 下面幾個符號串編碼集合中，不是前綴編碼的是（ B ）B、0,1,00,1139. 希爾排序的增量序列必須是（B ）。B、遞減的 40. 采用起泡排序法對n個關(guān)鍵字進(jìn)行升序排序，若要使排序過程中比較關(guān)鍵字的次數(shù)最多，則初始時的序列應(yīng)滿足條件（ D ） D、關(guān)鍵字從大到小排列41. 在下列內(nèi)部排序中( A )是不穩(wěn)定的。A、希爾排序42. 分別以下列序列構(gòu)造二叉排序樹，與用其它三個序列所構(gòu)造的結(jié)果不同的是( C )。A、（100，80， 90， 60， 120，110，130） 43. 在查找過程中，沖突指的是（ C ）。C、不同鍵值對應(yīng)

9、相同的存儲地址44. 對有14個元素的有序表A1.14作二分查找，查找元素A4時的被比較元素依次為（ D ）。D、A7，A3，A5，A445. 以v1為起始結(jié)點(diǎn)對下圖進(jìn)行廣度度優(yōu)先遍歷，正確的遍歷序列是（ A ）A、 v1，v2，v3，v4，v5，v6，v7二、填空題(本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分)1. 數(shù)據(jù)的物理結(jié)構(gòu)包括 數(shù)據(jù)元素 的存儲和 數(shù)據(jù)之間關(guān)系 的存儲。2. 若一個算法中的語句頻度之和為T(n)=1921n+4nlogn,則算法的時間復(fù)雜度為 nlogn 。 3. 下面程序段的時間復(fù)雜度是 。 i=1； while (i<=n) i=i*

10、3；4. 循環(huán)隊列用數(shù)組A0.m-1存放其元素值，已知其頭尾指針分別是front和rear ，則當(dāng)前隊列的元素個數(shù)是 （ rear-front+m ）% m 5. 主要是使插入和刪除等操作統(tǒng)一 6. （n-1）/2 。7. 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是 深度優(yōu)先 。8. 線性表L=（a1,a2,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是 相同值關(guān)鍵字 。9. 已知一無向圖G=（V，E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)現(xiàn)用某一種圖遍歷方法從頂點(diǎn)a開始遍歷圖，得到的序列為abecd，則采用的是

11、 前移 遍歷方法。10. 如果排序過程不改變 時間復(fù)雜度 之間的相對次序，則稱該排序方法是穩(wěn)定的。11. 從順序表中刪除一個元素時，表中所有在被刪元素之后的元素均需 出度 一個位置。 12. 當(dāng)問題的規(guī)模n趨向無窮大時，算法執(zhí)行時間T(n)的數(shù)量級被稱為算法的 10 。13. 若以鄰接矩陣表示有向圖，則鄰接矩陣上第i行中非零元素的個數(shù)即為頂點(diǎn)vi的 sxssxxssxssxxx 。14. 一棵含999個結(jié)點(diǎn)的完全二叉樹的深度為 12 。15. 假設(shè)S和X分別表示進(jìn)棧和出棧操作，由輸入序列“ABC”得到輸出序列“BCA”的操作序列為SSXSXX，則由“a*b+c/d”得到“ab*cd/+”的操作

12、序列為 4 。16. .如圖所示的有向無環(huán)圖可以排出 L->next->next=L 17. 邊 種不同的拓?fù)湫蛄小?8. 從空樹起，依次插入關(guān)鍵字1l，27，35，48，52，66和73構(gòu)造所得的二叉排序樹，在等概率查找的假設(shè)下，查找成功時的平均查找長度為 384 。19. 帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L中只有一個元素結(jié)點(diǎn)的條件是 隊列 。 20. 求最小生成樹的克魯斯卡爾(Kruskal)算法耗用的時間與圖中 邊稠密 、邊稀疏 的數(shù)目正相關(guān)。21. 已知一棵完全二叉樹中共有768結(jié)點(diǎn)，則該樹中共有 5 個葉子結(jié)點(diǎn)。22. 實現(xiàn)圖的廣度優(yōu)先搜索，除了一個標(biāo)志數(shù)組標(biāo)志已訪問的圖的結(jié)點(diǎn)外，還

13、需要 8、64 存放被訪問的結(jié)點(diǎn)以實現(xiàn)遍歷。23. Prim（普里姆）算法適用于求 2h-1 的網(wǎng)的最小生成樹；kruskal（克魯斯卡爾）算法適用于求 2h-1 的網(wǎng)的最小生成樹。24. 對長度為20的有序表進(jìn)行二分查找的判定樹的高度為 n-1 。25. 設(shè)一棵完全二叉樹有128個結(jié)點(diǎn)，則該完全二叉樹的深度為 n ，有_ 個葉子結(jié)點(diǎn)。26. 高度為h的完全二叉樹中最少有 棧 個結(jié)點(diǎn)，最多有 個結(jié)點(diǎn)。27. 設(shè)連通圖G中有n個頂點(diǎn)e條邊，則對應(yīng)的最小生成樹上有 3 條邊。28. 構(gòu)造n個結(jié)點(diǎn)的強(qiáng)連通圖，至少有 O(n2) 條弧。29. 表達(dá)式求值是 （42,13,94,55,05,46,17）

14、 應(yīng)用的一個典型例子。30. 設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5,e6依次通過棧S，一個元素出棧后即進(jìn)入隊列Q，若6個元素出隊的序列是e2,e4,e3,e6,e5,e1，則棧的容量至少應(yīng)該是 。31. 快速排序算法在最差的情況下其時間復(fù)雜度是 。32. 對序列55，46，13，05，94，17，42進(jìn)行基數(shù)排序，第一趟排序后的結(jié)果是 。三、應(yīng)用題（本大題共5小題，每小題6分，共30分）1. 已知二叉樹的先序遍歷序列ABCDEFGH，中序遍歷序列為CBEDFAGH，畫出二叉樹。答案：二叉樹形態(tài) 2. 如圖請給出鄰接表、鄰接矩陣及逆鄰接表。V1V3V2V4參考答案如下：

15、（1）鄰接表：(注意邊表中鄰接點(diǎn)域的值是頂點(diǎn)的序號，這里頂點(diǎn)的序號是頂點(diǎn)的下標(biāo)值-1)   vertex firstedge  next  （2）逆鄰接表：（3）3. 。答案：原來的電文為：eatst4. 請畫出下圖所示的樹所對應(yīng)的二叉樹，并寫出對應(yīng)二叉樹的先序遍歷和中序遍歷。12345678答案：12345678先序遍歷為：12345687 中序遍歷為：348675215. 設(shè)散列表為HT13, 散列函數(shù)為 H (key) = key %13。用閉散列法解決沖突, 對下列關(guān)鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15,

16、 36 造表。采用線性探查法尋找下一個空位, 畫出相應(yīng)的散列表, 并計算等概率下搜索成功的平均搜索長度。答案：使用散列函數(shù) H(key) = key mod 13，有H(12) = 12, H(23) = 10,H(45) = 6,H(57) = 5,H(20) = 7,H(03) = 3,H(78) = 0,H(31) = 5,H(15) = 2,H(36) = 10.利用線性探查法造表： 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 (1) (1) (1) (1) (1) (1) (4) (1) (2) (1)搜索成功

17、的平均搜索長度為ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 6. 已知帶權(quán)圖G如圖所示，畫出圖G的一棵最小生成樹。答：7. 假設(shè)用于通信的電文由字符集a,b,c,d,e,f,g,h中的字母構(gòu)成，這8個字母在電文中出現(xiàn)的概率分別為0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10，請為這8個字母設(shè)計哈夫曼編碼。哈夫曼編碼為：a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000注意：答案不唯一8. 試用權(quán)集合12,4,5,6,1,2構(gòu)造哈夫曼樹，并計算哈夫曼樹的

18、帶權(quán)路徑長度。WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=699. 畫出與如圖所示森林對應(yīng)的二叉樹。答：10. 已知一個散列表如下圖所示：3520334859 0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函數(shù)為h(key)=key%13, 處理沖突的方法為雙重散列法，探查序列為： hi=(h(key)+*h1(key)%m =0,1,，m-1其中： h1(key)=key%11+1回答下列問題：（1）對表中關(guān)鍵字35，20，33和48進(jìn)行查找時，所需進(jìn)行的比較次數(shù)各為多少？（2）該散列表在等概率查找時查找成功的平均查找長度為多少？答：（）對關(guān)鍵字

19、35、20、33和48進(jìn)行查找的比較次數(shù)為、；（）平均查找長度11. 請畫出與下列二叉樹對應(yīng)的森林。答：12. 對于給定結(jié)點(diǎn)的關(guān)鍵字集合K=5，7，3，1，9，6，4，8，2，10，（1）試構(gòu)造一棵二叉排序樹；（2）求等概率情況下的平均查找長度ASL。答：74312596108（2）ASL=(1*1+2*2+3*4+4*3)/10=2.913. 給出下圖對應(yīng)的鄰接矩陣，并給出A，B，C三個頂點(diǎn)的出度與入度 答案: 鄰接矩陣為： A B C D E F其中頂點(diǎn)A的入度為2，出度為1；其中頂點(diǎn)B的入度為2，出度為2；其中頂點(diǎn)C的入度為1，出度為3；14. 已知圖5.32如下所示，求從頂點(diǎn)a到其余各

20、頂點(diǎn)的最短路徑。（給出求解過程）543223356abdfce答：終點(diǎn)最短路徑求解過程b6 (a,b)5 (a,c,b)c3 (a,c)d¥6 (a,c,d)6 (a,c,d)e¥7 (a,c,e)7 (a,c,e)7 (a,c,e)f¥¥¥9 (a,c,d,f)9 (a,c,d,f)vjcbdefSa,ca,c,ba,c,da,c,ea,c,d,f15. 閱讀下列算法，并回答問題：（1）假設(shè)串由合法的英文字母和空格組成，并以0作結(jié)束符。設(shè)串s=”Iamastudent”(表示空格符)，寫出f30（s）的返回值；（2）簡述算法f30的功能。in

21、t f30 (char*s)答案：(1) 4(2)算法功能：統(tǒng)計單詞的個數(shù)。16. 閱讀下列函數(shù),并回答問題：（1）假設(shè)隊列q中的元素為(a,b,c,d,e),其中“a”為隊頭元素。寫出執(zhí)行函數(shù)調(diào)用Conv(&q)后的隊列q；（2）簡述算法Conv的功能。答案：（1） e，d，c，b，a（2） 將隊列里的值反轉(zhuǎn)17. 閱讀下列函數(shù),并回答問題：已知整形數(shù)組L1.8中的元素依次為（19，18，15，17，16，13，12，10），閱讀下列函數(shù)，并寫出執(zhí)行函數(shù)調(diào)用sort(L, 8)時，對L進(jìn)行的頭兩趟（pass分別為0和1）處理結(jié)果。答案：（1）第一趟（pass = 0）19 15 18

22、 16 17 12 13 10（2）第二趟（pass = 1）19 15 16 18 12 17 10 13keynext18. 已知帶頭結(jié)點(diǎn)的單鏈表中的關(guān)鍵字為整數(shù)，為提高查找效率，需將它改建為采用拉鏈法處理沖突的散列表。設(shè)散列表的長度為m，散列函數(shù)為Hash(key)=key%m。鏈表的結(jié)點(diǎn)結(jié)構(gòu)為： 。請在空缺處填入適當(dāng)內(nèi)容，使其成為一個完整算法。void f33 (LinkList L, LinkList H, int m)答案：（1） NULL （2）p->next=Hj p=q19. 下列函數(shù)的功能是，對以帶頭結(jié)點(diǎn)的單鏈表作為存儲結(jié)構(gòu)的兩個遞增有序表（表中不存在值相同的數(shù)據(jù)元素

23、）進(jìn)行如下操作：將所有在Lb表中存在而La表中不存在的結(jié)點(diǎn)插入到La中，其中La和Lb分別為兩個鏈表的頭指針。請在空缺處填入合適內(nèi)容，使其成為一個完整的算法。答案：（1）pre->next=pb （2）pre->next=pa （3）pre->next=pb20. 閱讀算法f30，并回答問題：下列算法為有向圖拓?fù)渑判?請在空缺處填入合適的內(nèi)容，使其成為一個完整的算法。答案：(1）top=-1 （2）top=graphj.count （3）graphk.count=021. 閱讀算法f31，并回答問題：下列算法功能為在數(shù)組a的前n(n>=1)個元素中找出第k(1<=

24、k<=n)小的值。這里假設(shè)數(shù)組a中各元素的值都不相同。請在空缺處填入合適的內(nèi)容，使其成為一個完整的算法。答案：（1）(i=k) return; （2）i+1 （3）i-122. 閱讀算法f33，并回答問題：下列算法功能為奇偶交換排序，思路如下：第一趟對所有奇數(shù)的i,將ai和ai+1進(jìn)行比較,第二趟對所有偶數(shù)的i,將ai和ai+1進(jìn)行比較,每次比較時若ai>ai+1,將二者交換;以后重復(fù)上述二趟過程,直至整個數(shù)組有序。請在空缺處填入合適的內(nèi)容，使其成為一個完整的算法。答案： (1)ai=t (2)(i=2;i<=n;i+=2) (3)flag四、算法設(shè)計題（本大題共2小題，每小

25、題10分，共20分）1. 已知單鏈表的結(jié)點(diǎn)類型為Lnode，包含next和data成員。編寫算法，實現(xiàn)帶頭結(jié)點(diǎn)單鏈表的逆置算法。參考答案： void invent(Lnode *head) Lnode *p,*q; if(!head->next) return ERROR; p=head->next; q=p->next; p->next =NULL; while(q) p=q; q=q->next; p->next=head->next; head->next=p; 2. 編寫一個函數(shù)，要求借助一個棧把一個數(shù)組中的數(shù)據(jù)元素逆置。其中，棧類型為S

26、eqStack，可以直接使用InitStack(SeqStack*)、Push(SeqStack*,ElemType)、Pop(SeqStack*,ElemType*)函數(shù)。參考答案：void Inverse(ElemType arr,int n)SeqStack *s;int i;InitStack(&s);for(i=0;i<n;i+) /數(shù)組元素依次入棧Push(s,arri);for(i=0;i<n;i+) /棧中元素依次出棧，存入數(shù)組，是數(shù)組逆序Pop(s,&arri);3. 二叉樹采用鏈接存儲結(jié)構(gòu)，結(jié)點(diǎn)類型為Btree，包括left、right和data

27、三個成員，試設(shè)計一個算法計算一棵給定二叉樹的度為2的結(jié)點(diǎn)的個數(shù)。參考答案：int twochild(Btree *b) int num1,num2; if (b=NULL) return 0; else num1=twochild1(b->left); num2=twochild1(b->right);if ( b->left!=NULL&&b->right!=NULL) return (num1+num2+1); else return (num1+num2); 4. 假設(shè)以帶雙親指針的二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，其結(jié)點(diǎn)結(jié)構(gòu)的類型說明如下所示：typ

28、edef char DataType;typedef struct node DataType data; struct node *lchild, *rchild; /左右孩子指針 struct node *parent; /指向雙親的指針 BinTNode;typedef BinTNode *BinTree;若px為指向非空二叉樹中某個結(jié)點(diǎn)的指針，可借助該結(jié)構(gòu)求得px所指結(jié)點(diǎn)在二叉樹的中序序列中的后繼。(1)就后繼的不同情況，簡要敘述實現(xiàn)求后繼操作的方法；參考答案：（1）分兩種情況討論當(dāng)*px的右子樹不為空時，則從*px的右孩子開始，沿其左孩子往下查找，直到找到一個沒有左孩子的節(jié)點(diǎn)為止，則

29、該結(jié)點(diǎn)為*px在中序序列中的后繼；當(dāng)*px的右孩子為空時，則沿*px的雙親指針鏈向上查找，直至找到其左子樹中包含*px的最年輕祖先，則該祖先結(jié)點(diǎn)為*px在中序序列中的后繼。(2)編寫算法求px所指結(jié)點(diǎn)的中序序列后繼，并在算法語句中加注注釋。（2）BinTree f34(BinTree px)BinTree q=px->rchild;if(q!=NULL)/沿左孩子往下查找px=q;while(px->lchild!=NULL)px=px->lchild;else/沿雙親指針鏈向上查找while(px!=NULL && px->rchild=q)q=px;

30、px=px->parent;return px;/返回所找到的中序序列后繼結(jié)點(diǎn)的指針 /或者無后繼結(jié)點(diǎn)時返回空指針5. 已有鄰接表表示的有向圖，請編程判斷從第u頂點(diǎn)至第v頂點(diǎn)是否有簡單路徑，若有則印出該路徑上的頂點(diǎn)。參考答案： void AllSPdfs(AdjList g,vertype u,vertype v) /求有向圖g中頂點(diǎn)u到頂點(diǎn)v的所有簡單路徑，初始調(diào)用形式：AllSPdfs(g,u,v)int top=0,s; s+top=u; visitedu=1; while (top>0 | p) p=gstop.firstarc; /第一個鄰接點(diǎn)。 while (p!=null && vis