《數(shù)據(jù)結(jié)構(gòu)(Java版)葉核亞(第4版)》樣卷及答案

1、 數(shù)據(jù)結(jié)構(gòu)（Java版）課程樣卷教材：數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版），葉核亞編著，電子工業(yè)出版社，2015年7月出版。試題范圍：第19章，掌握基礎(chǔ)原理，熟悉經(jīng)典算法，問答題形式考核。編程題重點(diǎn)是：1.單/雙鏈表；2.二叉樹/樹，遞歸算法。這是必須掌握的，即使部分學(xué)生掌握不了遞歸算法，也必須考。不考內(nèi)容：6.3線索二叉樹求父母、插入、刪除算法（沒寫），7.5.2Floyd，8.5.3平衡二叉樹，第10章。可作為課程設(shè)計(jì)題。試卷范圍和難度不超過樣卷。4-0模擬樣卷一、填空題（16分=2分X8題）聲明抽象數(shù)據(jù)類型的目的是以下數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)聲明為tableNode 3.已知java.lang.Stri

2、ng類聲明以下成員方法:/將所有與pattern匹配的子串替換為strpublicStringreplaceAll(Stringpattern,Stringstr)下列語句的執(zhí)行結(jié)果是Stringtarget=aababbabac,pattern=ab,str=aba;System.out.println(+target+.replaceAll(+pattern+,+str+)=+target.replaceAll(pattern,str)+);TOC o 1-5 h zA+B*（C-D*（E+F）/G+H）-（I+J）*K的后綴表達(dá)式為。已知二維數(shù)組a108采用行主序存儲(chǔ),數(shù)組首地址是100

3、0,每個(gè)元素占用4字節(jié)，則數(shù)組元素a45的存儲(chǔ)地址是。由n個(gè)頂點(diǎn)組成的無向連通圖，最多有條邊。排序關(guān)鍵字序列（升序）5,17,20,32,43,55,61,61*,72,96，采用二分法查找算法，查找96的元素比較序列是；查找35的元素比較序列是。關(guān)鍵字序列93,17,56,42,78,15,42*,25,19，采用希爾排序（升序）算法，第一趟排序后的序列是。二、問答題（50分=5分X10題）1.已知目標(biāo)串為aabcbabcaabcaababc,模式串為abcaababc,寫出模式串改進(jìn)的next數(shù)組；畫出KMP算法的匹配過程，給出字符比較次數(shù)。- #-一 一畫出以下稀疏矩陣非零元素三元組的十

4、字鏈表存儲(chǔ)結(jié)構(gòu)。000320015000059000860043A7x8000000180006500- #-一 #一- #-一 #一已知一棵二叉樹的遍歷序列如下，畫出這棵二叉樹并進(jìn)行中序線索化。中根遍歷序列：CBDFEGAMLNKJOPRQIHS；后根遍歷序列：CFGEDBMNLKRQPOJISHA4.設(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ǔ)，畫出所構(gòu)造的Huffman樹，并寫出每個(gè)字符的Huffman編碼。說明Huffman編碼的特點(diǎn)和作用。5.已知以下無

5、向圖G中各頂點(diǎn)按A,B,C,D,E,F,G,H次序存儲(chǔ)。分別畫出采用深度優(yōu)先搜索（從A開7始）和廣度優(yōu)先搜索（從D開始）遍歷圖時(shí)?；蝽樞蜓h(huán)隊(duì)列（容量為6）的動(dòng)態(tài)變化示意圖，說明棧或隊(duì)列的作用。- #-一 #一- #-一 #一6.什么是圖的最小生成樹？構(gòu)造以下帶權(quán)無向圖的最小生成樹，給出該最小生成樹代價(jià)。說明Prim算法和Kruskal算法的差別。弋13:卩飛4和1612/iiC./a）帶權(quán)無向圖AF610B4GE12C5D11b）最小生成樹，代價(jià)為45AF6104B4GE125CDc)Prim算法不斷擴(kuò)充T,d）Kruska1算法不斷合并樹，依次7.畫出以下帶權(quán)有向圖采用DijkStr算法以

6、E為源點(diǎn)的單擴(kuò)充最短路徑所選擇的（BG出各路徑長度。- #-一 #一- -一 #一設(shè)散列表采用鏈地址法，初始容量length為10；散列函數(shù)采用除留余數(shù)法hash（key）=key%length；裝填因子為0.75，散列數(shù)組容量以2倍擴(kuò)充。由關(guān)鍵字序列16,75,60,43,54,90,46,31,27,88,64,50構(gòu)造散列表，分別畫出擴(kuò)容前和最終狀態(tài)圖，計(jì)算ASL。成功畫出由關(guān)鍵字序列50,16,74,60,43,16,90,46,31,29,88,71,64,13,65構(gòu)造的一棵二叉排序樹，計(jì)算ASL。執(zhí)行刪除結(jié)點(diǎn)50、插入50，再畫出操作后的二叉排序樹。成功10.什么是堆序列？堆序列

7、在堆排序算法中起什么作用？將關(guān)鍵字序列29,10,25,26,58,12,31,18,47分別建成一個(gè)最大堆和一個(gè)最小堆，寫出堆序列，畫出對(duì)應(yīng)的完全二叉樹；寫出每一趟堆排序結(jié)果。若有關(guān)鍵字重復(fù)元素，做標(biāo)記以區(qū)別。三、程序閱讀和改錯(cuò)題(18分=6分X3題)1.SortedCirDoublyListvT排序循環(huán)雙鏈表類增加以下成員方法，回答問題。以下merge(list)方法功能是什么？方法體中，while、if等語句功能是什么？已知兩條排序循環(huán)雙鏈表this和list的序列為26,37,61,81和18,53,75,86,90,畫出兩者的存儲(chǔ)結(jié)構(gòu),以及執(zhí)行merge(list)方法后的狀態(tài)，標(biāo)明

8、各變量的位置。publicvoidmerge(SortedCirDoublyListlist)DoubleNodep=this.head.next;DoubleNodeq=list.head.next;while(p!=this.head&q!=list.head)if(p.data).compareTo(q.data)0)p=p.next;elseq.prev=p.prev;p.prev.next=q;p.prev=q;q=q.next;q.prev.next=p;if(q!=list.head)q.prev=this.head.prev;this.head.prev.next=q;list

9、.head.prev.next=this.head;this.head.prev=list.head.prev;list.head.prev=list.head;list.head.next=list.head;/方法功能是什么？/循環(huán)語句功能是什么？/選擇語句功能是什么？/為什么要這兩句？2.閱讀程序，回答以下問題。publicstaticStringBuffertrim(StringBuffers)inti=0;while(is.length()&s.charAt(i)!=)i+;for(intj=i;j類表示父母孩子兄弟鏈表存儲(chǔ)的樹，回答以下問題。設(shè)一棵樹(森林)的廣義表表示如下，畫出所

10、構(gòu)造的樹以及樹的存儲(chǔ)結(jié)構(gòu)圖，輸出樹的橫向凹入表示法。樹(森林)的廣義表表示：G(A(C(E,F),B,D),H(J(L),I,K)以下levelorder()方法的功能是什么？對(duì)于上述樹(森林)，運(yùn)行結(jié)果是什么？levelorder()方法存在什么錯(cuò)誤？如何改正？publicvoidlevelorder()LinkedQueueTreeNodeque=newLinkedQueueTreeNode();for(TreeNodep=this.root;p!=null;p=que.poll()System.out.print(p.data+);for(p=p.child;p!=null;p=p.si

11、bling)que.add(p);System.out.println();四、程序設(shè)計(jì)題(16分=8分X2題)SinglyListvT單鏈表類增加以下成員方法，畫出操作示意圖。刪除this中所有與pattern匹配的子表，BF模式匹配查找到再刪除publicvoidremoveAll(SinglyListpattern)實(shí)現(xiàn)以下對(duì)二叉鏈表存儲(chǔ)的二叉樹類BinaryTreevT操作的方法。判斷二叉樹bitree是否二叉排序樹TextendsComparablebooleanisSorted(BinaryTreebitree)- -一 #一4-0樣卷答案一、填空題（16分=2分X8題）使數(shù)據(jù)類型

12、的定義和實(shí)現(xiàn)分離，使一種定義有多種實(shí)現(xiàn)。見數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）習(xí)題解答第7頁習(xí)2-6。aababbabac.replaceAll（ab,aba）=aabaabababaacABCDEF+*G/-H+*+IJ+K*-,見數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）習(xí)題解答第27頁習(xí)4-5。mat+（i*n+j）*4=1000+（4*8+5）*4=1148n*（n-1）/243,61*,72,96；43,17,20,32。解釋見習(xí)題解答第54頁習(xí)8-9。見數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）習(xí)題解答第57頁習(xí)9-4。二、問答題（50分=5分X10題）1.模式串a(chǎn)bcaababc改進(jìn)的next數(shù)組為j0

13、12345678模式串a(chǎn)bcaababcp0p,p中取長相冋的前后綴子串長度k-10001121201丿,p與p比較學(xué)學(xué)=學(xué)=學(xué)=k丿改進(jìn)的nextj-100-110200KMP算法匹配過程如下,字符比較次數(shù)為20。t0t1t2t3t4t5t6t7t8t9t10t11t12t13t14t15t16t17targetaabcbabcaabcaababcabcaababcp0p1p2p3p4p5p6p7p8(a)第1次匹配，to=Po，-HP，比較2次，next1=0t0t1t2t3t4t5t6t7t8t9t10t11t12t13t14t15t16t17aabcbabcaabcaababc=itt

14、ernabcaababctargetp0p1p2p3p4p5p6p7p8(b)第2次匹配，t=Po，,七4工卩3，比較4次，next3=Taabcbabcaabcaababcttt2ttttttttttttttargetttHabcaababcp0p1p2p3p4p5p6p7p8(c)第3次匹配,t二Po,一1工卩6，比較7次,next6=2t0tt2tjt5t6t7t8t9t10tnt2t3t4t5t6t7targetaabcbabcaabcaababcpatternabcaababcp0p1p2p3p4p5p6p7p8（d）第4次匹配，t1=p2,t7=p8，比較7次，匹配成功，與模式串匹

15、配的子串序號(hào)為92.見數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）習(xí)題解答第34頁習(xí)5-9。見數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）習(xí)題解答第37頁習(xí)6-19、第42頁圖6.9?！驹u(píng)分標(biāo)準(zhǔn)】構(gòu)造二叉樹3分，中序線索化2分。見數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）習(xí)題解答第44頁習(xí)6-31、6-34。見數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）習(xí)題解答第48頁習(xí)7-15。見數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）習(xí)題解答第50頁習(xí)7-11、7-15。見數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）習(xí)題解答第52頁習(xí)7-15。見數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）習(xí)題解答第55頁習(xí)8-12。見數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）習(xí)題解答第56頁習(xí)8-19。堆序

16、列概念見教材；構(gòu)造的堆見數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）習(xí)題解答第59頁習(xí)9-10。三、程序閱讀和改錯(cuò)題（18分=6分X3題）1.merge（list）方法功能是：歸并兩條排序循環(huán)雙鏈表，將list中所有結(jié)點(diǎn)歸并到this中，合并后設(shè)置list空。方法體中，while語句功能是：p、q分別遍歷this和list排序循環(huán)雙鏈表，比較p、q結(jié)點(diǎn)值有大小，若q結(jié)點(diǎn)值較小，將q結(jié)點(diǎn)插入到p結(jié)點(diǎn)之前。當(dāng)遍歷完一條循環(huán)雙鏈表時(shí)，while循環(huán)結(jié)束。while之后的if語句功能是：若q!=list.head,表示遍歷this結(jié)束，要將list中剩余結(jié)點(diǎn)（q結(jié)點(diǎn)開始）鏈接到this尾，并使this與list的

17、最后結(jié)點(diǎn)連接成為環(huán)形。合并后設(shè)置list為空，否則兩條循環(huán)雙鏈表將共用某些結(jié)點(diǎn)，會(huì)造成混亂。算法描述如下圖所示，與第4版圖9.17算法同。（a）比較p、q結(jié)點(diǎn)值，若p結(jié)點(diǎn)值小，則繼續(xù)比較p的后繼；否則（2）,將q結(jié)點(diǎn)插入在p之前this.headlist.head268118P（b）重復(fù)執(zhí)行（a）,歸并結(jié)點(diǎn)；當(dāng)p=this.head且q!=list.head時(shí)，將q結(jié)點(diǎn)插入在this的最后結(jié)點(diǎn)之后;并使this與list的最后結(jié)點(diǎn)連接成為環(huán)形。設(shè)置list為空循環(huán)雙鏈表37T53Z61F77586*q90*1- #-一 #一見數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）習(xí)題解答第21頁【實(shí)驗(yàn)題3-11】。

18、- -一 #一childdatasiblingC/kAB*4A卞PAALAAEAF7A(b)森林的父母孩子兄弟鏈表功能是按層次遍歷樹。上述森林的運(yùn)行結(jié)果如下：層次遍歷樹：GACBDEFlevelorder()算法存在的錯(cuò)誤是，只遍歷了一棵樹，無法遍歷森林。改正如下。publicvoidlevelorder()/按層次遍歷樹(森林)，從根開始依次遍歷森林中的每棵樹System.out.print(層次遍歷樹(森林)：);LinkedQueueTreeNodeque=newLinkedQueueTreeNode();/創(chuàng)建一個(gè)空隊(duì)列for(TreeNodeq=this.root;q!=null;q

19、=q.sibling)for(TreeNodep=q;p!=null;p=que.poll()System.out.print(p.data+);for(p=p.child;p!=null;p=p.sibling)que.add(p);/遍歷森林/遍歷一棵樹，根沒有進(jìn)隊(duì)/所有孩子結(jié)點(diǎn)入隊(duì)- #-一 #一if(q.sibling!=null)System.out.print(，);System.out.println();上述森林的運(yùn)行結(jié)果如下，結(jié)果正確，從根開始依次遍歷森林中的每棵樹。層次遍歷樹(森林)：GACBDEF，HJIKL- #-一 #一- -一 #一四、程序設(shè)計(jì)題(16分=8分X2題

20、)1.單鏈表刪除所有匹配子表操作的算法描述如圖所示，該算法使用BF模式匹配查找到匹配子表，可一次刪除匹配子表。frontstartq=nullthis.headpattemhead4%*(a)當(dāng)一次匹配成功時(shí)，刪除從start結(jié)點(diǎn)開始的一條匹配子表p=null(b)start再次從front的后繼結(jié)點(diǎn)開始尋找匹配子表并刪除removeAll()方法聲明如下，刪除所有與pattern匹配的子表。刪除this中所有與pattern匹配的子表，BF模式匹配查找到再刪除。publicvoidremoveAll(SinglyListpattern)if(pattern.isEmpty()/若無此句，則死循環(huán)，錯(cuò)誤return;Nodestart=this.head.next,front=this.head;while(start!=null)Nodep=start,q=pattern.head.next;while(p!=null&q!=