數(shù)據(jù)結(jié)構(gòu)(Java版)樣卷及答案第3版網(wǎng)絡(luò)

1、數(shù)據(jù)結(jié)構(gòu)（java版）課程樣卷一. 填空題（20分，每空2分）1. 聲明抽象數(shù)據(jù)類型的目的是_(unit1)_。2. 右側(cè)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)聲明為_(kāi)(unit2)_。3. 中綴表達(dá)式a+b*(c-d*(e+f)/g+h)-(i+j)*k的后綴表達(dá)式為abcdef+*g/-h+*+ij+k*-_(unit4)_。4. 設(shè)一個(gè)順序循環(huán)隊(duì)列容量為60，當(dāng)front=47，rear=23時(shí)，該隊(duì)列有_36_unit4_個(gè)元素。5. 已知二維數(shù)組a108采用行主序存儲(chǔ)，數(shù)組首地址是1000，每個(gè)元素占用4字節(jié)，則數(shù)組元素a45的存儲(chǔ)地址是_1148 unit5_。6. 已知一棵完全二叉樹(shù)的根（第0個(gè)）結(jié)點(diǎn)層次

2、為1，則第100個(gè)結(jié)點(diǎn)的層次為_(kāi)。7. 中根遍歷序列和后根遍歷序列相反的二叉樹(shù)是_。8. 由256個(gè)權(quán)值構(gòu)造一棵哈夫曼樹(shù)，則該二叉樹(shù)共有_結(jié)點(diǎn)。9. 由n個(gè)頂點(diǎn)組成的無(wú)向連通圖，最多可以有_條邊。10. 10個(gè)元素的排序數(shù)據(jù)序列采用折半查找的平均查找長(zhǎng)度是（寫(xiě)出算式）_。二. 問(wèn)答題（50分，每題5分）1. 已知目標(biāo)串為aabcbabcaabcaababc，模式串為abcaababc，寫(xiě)出模式串改進(jìn)的next數(shù)組；畫(huà)出kmp算法的匹配過(guò)程，給出字符比較次數(shù)。2. 什么是棧和隊(duì)列？?jī)烧哂泻萎愅?？什么情況下需要使用棧或隊(duì)列？采用順序存儲(chǔ)結(jié)構(gòu)的棧和隊(duì)列，在進(jìn)行插入、刪除操作時(shí)需要移動(dòng)數(shù)據(jù)元素嗎？為什

3、么？什么是隊(duì)列的假溢出？為什么順序存儲(chǔ)結(jié)構(gòu)隊(duì)列會(huì)出現(xiàn)假溢出？怎樣解決隊(duì)列的假溢出問(wèn)題？鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)隊(duì)列會(huì)出現(xiàn)假溢出嗎？順序存儲(chǔ)結(jié)構(gòu)的棧會(huì)出現(xiàn)假溢出嗎？為什么？3. 已知一棵二叉樹(shù)的中根次序遍歷序列為cbdfegamlnkjoprqihs，后根次序遍歷序列為cfgedbmnlkrqpojisha，畫(huà)出這棵二叉樹(shù)并進(jìn)行中序線索化。4. 設(shè)一段正文由字符集a,b,c,d,e,f,g,h組成，其中每個(gè)字符在正文中的出現(xiàn)次數(shù)依次為23,5,17,4,9,31,29,18，采用huffman編碼對(duì)這段正文進(jìn)行壓縮存儲(chǔ)，畫(huà)出所構(gòu)造的huffman樹(shù)，并寫(xiě)出每個(gè)字符的huffman編碼。說(shuō)明huffman編碼

4、的特點(diǎn)和作用。5. 構(gòu)造以下帶權(quán)無(wú)向圖的最小生成樹(shù)，給出該最小生成樹(shù)的代價(jià)。說(shuō)明prim算法和kruskal算法的差別。6. 畫(huà)出以下帶權(quán)有向圖采用dijkstra算法以e為源點(diǎn)的單源最短路徑所選擇的邊，并寫(xiě)出各路徑長(zhǎng)度。7. 散列表已知關(guān)鍵字序列為16,74,60,43,54,90,46,31,29,88,71,64,50，散列表長(zhǎng)度為11，采用除留余數(shù)法的散列函數(shù)為hash(k)=k % 11，畫(huà)出采用鏈地址法構(gòu)造的散列表，計(jì)算（寫(xiě)出算式）。8. 什么是二叉排序樹(shù)？二叉排序樹(shù)畫(huà)出由關(guān)鍵字序列25,27,30,12,11,18,14,20,15,22構(gòu)造的一棵二叉排序樹(shù)，計(jì)算。執(zhí)行刪除結(jié)點(diǎn)1

5、2、插入12，再畫(huà)出操作后的二叉排序樹(shù)。9. 快速排序算法的設(shè)計(jì)思想是怎樣的？寫(xiě)出對(duì)關(guān)鍵字序列63,29,72,25,47,58,19,51,19*進(jìn)行快速排序（升序）的中間過(guò)程。10. 什么是堆序列？堆序列在堆排序算法中起什么作用？將關(guān)鍵字序列29,10,25,26,58,12,31,18,47用篩選法分別建成一個(gè)最大堆和一個(gè)最小堆，寫(xiě)出兩個(gè)堆序列并畫(huà)出其對(duì)應(yīng)的完全二叉樹(shù)。三. 程序閱讀和改錯(cuò)題（12分，每題6分）1. 下列removeall()方法欲刪除target串中所有與pattern匹配的子串。public static stringbuffer removeall(stringbu

6、ffer target, string pattern) int m=target.length(), n=pattern.length(); int i=target.indexof(pattern), k=i; while (k!=-1) int j=k+n; k=target.indexof(pattern, j); while (k0 & jk | k0 & jm) target.setcharat(i+, target.charat(j+); return target; 對(duì)于以下調(diào)用語(yǔ)句，運(yùn)行結(jié)果是什么？正確的運(yùn)行結(jié)果是什么？stringbuffer target = new st

7、ringbuffer(ababdabcdabcabc); system.out.println(removeall(target, abc); removeall()方法怎樣實(shí)現(xiàn)所求功能？ 算法存在什么錯(cuò)誤？如何改正？2. 閱讀以下程序，回答問(wèn)題。public statict extends comparable int grade(t according, binarytree bitree) int result= new intaccording.length+1; grade(according, bitree.root, result); return result;private

8、statict extends comparable void grade(t according, binarynode p, int result) if (p!=null) int i=0; while (iaccording.length & pareto(accordingi)0) i+; resulti+; grade(according, p.left, result); grade(according, p.right, result); 上述方法的功能是什么？ 寫(xiě)出執(zhí)行以下調(diào)用語(yǔ)句后的運(yùn)行結(jié)果，并畫(huà)出所創(chuàng)建的二叉樹(shù)。integer value=79,82,

9、71,63,95,90,65,75,80,55;binarytree bitree1 = new completebinarytree(value);string str=優(yōu)秀,良好,中等,及格,不及格;integer according=90,80,70,60;int result=grade(according, bitree1);for (int i=0; iresult.length; i+) system.out.print(stri+resulti+人，);system.out.println(); 四. 程序設(shè)計(jì)題（18分）1. 在單鏈表類singlylinkedlist中，增加

10、以下成員方法： （8分）public void removeall(singlylinkedlist pattern) /刪除所有與pattern匹配的子表2. 采用父母孩子兄弟鏈表表示樹(shù)，聲明樹(shù)的結(jié)點(diǎn)類和樹(shù)類；寫(xiě)出以樹(shù)的橫向凹入表示構(gòu)造樹(shù)或森林的構(gòu)造方法；對(duì)于以下樹(shù)的橫向凹入表示，畫(huà)出樹(shù)的存儲(chǔ)結(jié)構(gòu)。（10分）string prelist=中國(guó),t北京,t江蘇,tt南京,tt蘇州, 韓國(guó),t首爾,;數(shù)據(jù)結(jié)構(gòu)（java版）課程樣卷答案一. 填空題（20分=2分10）1. 使數(shù)據(jù)類型的定義和實(shí)現(xiàn)分離，使一種定義有多種實(shí)現(xiàn)。2. table可聲明為數(shù)組或順序表，元素為結(jié)點(diǎn)或單鏈表，聲明為以下4種之一

11、：node table; singlylinkedlist table; seqlistnode table;seqlistsinglylinkedlist table;3. abcdef+*g/-h+*+ij+k*-4. 365. 11486. 77. 右單支二叉樹(shù)（不包括空二叉樹(shù)和只有根結(jié)點(diǎn)的二叉樹(shù)）8. 5119. n*(n-1)/210. 二. 問(wèn)答題（50分=5分10）1. 模式串a(chǎn)bcaababc改進(jìn)的next數(shù)組為j012345678模式串a(chǎn)bcaababc中最長(zhǎng)相同的前后綴子串長(zhǎng)度k-100011212與比較=改進(jìn)的nextj-100-110200kmp算法匹配過(guò)程如下，字符比

12、較次數(shù)為20。2. 棧和隊(duì)列都屬于線性表結(jié)構(gòu)，它們是兩種特殊的線性表，棧的插入和刪除操作都在線性表的一端進(jìn)行，所以棧的特點(diǎn)是“后進(jìn)先出”；而隊(duì)列的插入和刪除操作分別在線性表的兩端進(jìn)行，所以隊(duì)列的特點(diǎn)是“先進(jìn)先出”。深度優(yōu)先搜索遍歷算法需要使用棧作為輔助結(jié)構(gòu)，廣度優(yōu)先搜索遍歷算法需要使用隊(duì)列作為輔助結(jié)構(gòu)。采用順序存儲(chǔ)結(jié)構(gòu)的棧和隊(duì)列，在進(jìn)行插入、刪除操作時(shí)不需要移動(dòng)數(shù)據(jù)元素，因?yàn)闂：完?duì)列均不能進(jìn)行中間插入、刪除操作。順序隊(duì)列，當(dāng)入隊(duì)的元素個(gè)數(shù)（包括已出隊(duì)元素）超過(guò)數(shù)組容量時(shí)，隊(duì)列尾下標(biāo)越界，數(shù)據(jù)溢出。此時(shí)，由于之前已有若干元素出隊(duì)，數(shù)組前部已空出許多存儲(chǔ)單元，所以，這種溢出并不是因存儲(chǔ)空間不夠而產(chǎn)

13、生的，稱之為假溢出。順序隊(duì)列之所以會(huì)產(chǎn)生假溢出現(xiàn)象，是因?yàn)轫樞蜿?duì)列的存儲(chǔ)單元沒(méi)有重復(fù)使用機(jī)制。解決的辦法是將順序隊(duì)列設(shè)計(jì)成循環(huán)結(jié)構(gòu)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)隊(duì)列不會(huì)出現(xiàn)假溢出。因?yàn)槊看卧厝腙?duì)，都要申請(qǐng)新結(jié)點(diǎn)，數(shù)據(jù)不會(huì)溢出。順序存儲(chǔ)結(jié)構(gòu)的棧不會(huì)出現(xiàn)假溢出。因?yàn)轫樞驐５拇鎯?chǔ)單元可以重復(fù)使用，如果數(shù)組容量不夠，則是數(shù)據(jù)溢出，而不是假溢出。3. 4. huffman編碼是一種變長(zhǎng)的編碼方案，滿足基本要求：任何一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴。huffman編碼用于實(shí)現(xiàn)無(wú)損的數(shù)據(jù)壓縮。5. 6. 7. 8. 9. 快速排序每趟在數(shù)據(jù)序列中選擇一個(gè)基準(zhǔn)值作為比較依據(jù)，將序列劃分成兩個(gè)子序列，小于基準(zhǔn)值的元素

14、序列在前端，大于基準(zhǔn)值的元素序列在后端，并確定基準(zhǔn)值的最終位置。遞歸調(diào)用再將各子序列進(jìn)一步劃分，直到子序列的長(zhǎng)度為1，則完成排序。關(guān)鍵字序列：63 29 72 25 47 58 19 51 19* 0.8, vot=63, 19* 29 51 25 47 58 19 63 72 0.6, vot=19, 19* 29 51 25 47 58 19 63 72 1.6, vot=29, 19* 19 25 29 47 58 51 63 72 1.2, vot=19, 19* 19 25 29 47 58 51 63 72 4.6, vot=47, 19* 19 25 29 47 58 51 63

15、 72 5.6, vot=58, 19* 19 25 29 47 51 58 63 72 10. 將一個(gè)數(shù)據(jù)序列看成是一棵完全二叉樹(shù)的層次遍歷序列，如果任意一個(gè)結(jié)點(diǎn)的關(guān)鍵字值都小于等于（大于等于）它的孩子結(jié)點(diǎn)的關(guān)鍵字值，則該序列為最?。ù螅┒?。最小（大）堆序列中，根結(jié)點(diǎn)值最?。ù螅?，因此，堆序列的作用是選取最?。ù螅┲?。三. 程序閱讀題（12分=6分2） 1. 運(yùn)行結(jié)果為“ababddbcdabcabc”，正確的運(yùn)行結(jié)果是“ababdd”。 removeall()方法刪除指定stringbuffer串的全部匹配子串操作，算法將待移動(dòng)若干字符一次移動(dòng)到位，從而提高算法效率。算法描述如下圖所示，說(shuō)

16、明如下：l 初始狀態(tài)，設(shè)i表示首次匹配子串的首字符下標(biāo)，如圖（a）所示。l 再設(shè)j表示i匹配子串之后的字符下標(biāo)，k表示下次匹配子串的首字符下標(biāo)，如圖（a）所示，將從jk-1之間的若干字符向前移動(dòng)到i處，完成刪除一個(gè)匹配子串操作。l 重復(fù)上一步操作，如果j=k，表示有兩個(gè)連續(xù)的匹配子串，則沒(méi)有移動(dòng)字符，如圖（b）所示；直到k=-1，表示其后沒(méi)有匹配子串，則將從j開(kāi)始至串尾的若干字符全部向前移動(dòng)到i處，如圖（c）所示。 算法存在錯(cuò)誤，刪除后沒(méi)將字符串長(zhǎng)度減少，導(dǎo)致仍然輸出原長(zhǎng)度字符串。改正：方法體return語(yǔ)句前增加以下一句： target.setlength(i);2. 分段統(tǒng)計(jì)二叉樹(shù)的元素個(gè)

17、數(shù)，according數(shù)組指定分段的劃分，result數(shù)組保存統(tǒng)計(jì)結(jié)果并返回。 程序運(yùn)行結(jié)果如下，所創(chuàng)建的完全二叉樹(shù)如圖所示。優(yōu)秀2人，良好2人，中等3人，及格2人，不及格1人，四. 程序設(shè)計(jì)題（18分=8+10） 以下給出參考程序。1. 刪除所有與pattern匹配的子表。public void removeall(singlylinkedlist pattern) if (pattern.isempty() return; node start=head.next, front=head; while (start!=null) node p=start, q=pattern.head.n

18、ext; while (p!=null & q!=null & p.data.equals(q.data) /一次匹配 p=p.next; q=q.next; if (q!=null) /匹配失敗，進(jìn)行下次匹配 front=start; start=start.next; else /匹配成功，刪除該匹配子表 front.next = p; start=p; 該算法使用bf模式匹配查找到匹配子表，可一次刪除匹配子表。刪除一個(gè)匹配子表操作描述如下圖所示。2. 樹(shù)的父母孩子兄弟鏈表結(jié)點(diǎn)類public class treepnode/樹(shù)的父母孩子兄弟鏈表結(jié)點(diǎn)類，泛型t指定結(jié)點(diǎn)的元素類型 public

19、 t data; /數(shù)據(jù)域，存儲(chǔ)數(shù)據(jù)元素 public treepnode parent; /指向父母結(jié)點(diǎn)的鏈 public treepnode child, sibling; /鏈，分別指向孩子、兄弟結(jié)點(diǎn) /構(gòu)造結(jié)點(diǎn)，參數(shù)分別指定元素、父母、孩子和兄弟結(jié)點(diǎn) public treepnode(t data, treepnode parent, treepnode child, treepnode sibling) this.data = data; this.parent = parent; this.child = child; this.sibling = sibling; public

20、treepnode(t data) /構(gòu)造指定值的葉子結(jié)點(diǎn) this(data, null, null, null); public treepnode() this(null, null, null, null); 樹(shù)類聲明public class treep /樹(shù)類，泛型t指定結(jié)點(diǎn)的元素類型 public treepnode root; /根結(jié)點(diǎn)，結(jié)點(diǎn)結(jié)構(gòu)是樹(shù)的父母孩子兄弟鏈表 public treep() /構(gòu)造空樹(shù) this.root=null; public string tostring() /先根次序遍歷樹(shù)并返回樹(shù)的橫向凹入表示字符串 return 先根次序遍歷樹(shù)： n +tostring(root,); private string tostring(treepnode p, string tab) /算法同樹(shù)的孩子兄弟鏈表，方法體省略 以橫向凹入表示構(gòu)造樹(shù)或森林public class treep_string /以橫向凹入表示構(gòu)造樹(shù)或森林，prelist數(shù)組存儲(chǔ)樹(shù)或森林的橫向凹入表示字符串序列 /非遞歸算法，逐個(gè)結(jié)點(diǎn)添加方式，沒(méi)有直接調(diào)用返回、插入結(jié)點(diǎn)方法 public static treep create(string prelist) t