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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)數(shù)據(jù)結(jié)構(gòu)（Java版）課程樣卷教材：數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版），葉核亞編著，電子工業(yè)出版社，2015年7月出版。試題范圍：第19章，掌握基礎(chǔ)原理，熟悉經(jīng)典算法，問答題形式考核。編程題重點是：1.單/雙鏈表； 2.二叉樹/樹，遞歸算法。這是必須掌握的，即使部分學(xué)生掌握不了遞歸算法，也必須考。不考內(nèi)容：6.3 線索二叉樹求父母、插入、刪除算法（沒寫），7.5.2 Floyd，8.5.3 平衡二叉樹，第10章?？勺鳛檎n程設(shè)計題。試卷范圍和難度不超過樣卷。模擬樣卷填空題（

2、16分=2分8題）聲明抽象數(shù)據(jù)類型的目的是_。以下數(shù)據(jù)存儲結(jié)構(gòu)聲明為_。已知java.lang.String類聲明以下成員方法：public String replaceAll( pattern, str) /將所有與pattern匹配的子串替換為str下列語句的執(zhí)行結(jié)果是_。String target=aababbabac, pattern=ab, str=aba; System.out.println(+target+.replaceAll(+pattern+, +str+)=+ target.replaceAll(pattern,str)+);A+B*(C-D*(E+F)/G+H)-(I

3、+J)*K的后綴表達式為_。已知二維數(shù)組a108采用行主序存儲，數(shù)組首地址是1000，每個元素占用4字節(jié)，則數(shù)組元素a45的存儲地址是_。由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分10題）已知目標串為aabcbabcaabcaababc，模式串為abcaababc，寫出模式串改進的next

4、數(shù)組；畫出KMP算法的匹配過程，給出字符比較次數(shù)。畫出以下稀疏矩陣非零元素三元組的十字鏈表存儲結(jié)構(gòu)。已知一棵二叉樹的遍歷序列如下，畫出這棵二叉樹并進行中序線索化。中根遍歷序列：CBDFEGAMLNKJOPRQIHS； 后根遍歷序列：CFGEDBMNLKRQPOJISHA設(shè)一段正文由字符集A,B,C,D,E,F,G,H組成，其中每個字符在正文中的出現(xiàn)次數(shù)依次為23,5,17,4,9,31,29,18，采用Huffman編碼對這段正文進行壓縮存儲，畫出所構(gòu)造的Huffman樹，并寫出每個字符的Huffman編碼。說明Huffman編碼的特點和作用。已知以下無向圖中各頂點按A,B,C,D,E,F,G

5、,H次序存儲。分別畫出采用深度優(yōu)先搜索（從A開始）和廣度優(yōu)先搜索（從D開始）遍歷圖時?；蝽樞蜓h(huán)隊列（容量為6）的動態(tài)變化示意圖，說明?；蜿犃械淖饔?。什么是圖的最小生成樹？構(gòu)造以下帶權(quán)無向圖的最小生成樹，給出該最小生成樹代價。說明Prim算法和Kruskal算法的差別。 畫出以下帶權(quán)有向圖采用Dijkstra算法以E為源點的單源最短路徑所選擇的邊，寫出各路徑長度。設(shè)散列表采用鏈地址法，初始容量length為10；散列函數(shù)采用除留余數(shù)法hash(key)=key % length；裝填因子為0.75，散列數(shù)組容量以2倍擴充。由關(guān)鍵字序列16,75,60,43,54,90,46,31,27,88,

6、64,50構(gòu)造散列表，分別畫出擴容前和最終狀態(tài)圖，計算。畫出由關(guān)鍵字序列50, 16, 74, 60, 43, 16, 90, 46, 31, 29, 88, 71, 64, 13, 65構(gòu)造的一棵二叉排序樹，計算。執(zhí)行刪除結(jié)點50、插入50，再畫出操作后的二叉排序樹。什么是堆序列？堆序列在堆排序算法中起什么作用？將關(guān)鍵字序列29, 10, 25, 26, 58, 12, 31, 18, 47分別建成一個最大堆和一個最小堆，寫出堆序列，畫出對應(yīng)的完全二叉樹；寫出每一趟堆排序結(jié)果。若有關(guān)鍵字重復(fù)元素，做標記以區(qū)別。程序閱讀和改錯題（18分=6分3題）SortedCirDoublyList排序循環(huán)

7、雙鏈表類增加以下成員方法，回答問題。 以下merge(list)方法功能是什么？方法體中，while、if等語句功能是什么？ 已知兩條排序循環(huán)雙鏈表this和list的序列為26,37,61,81和18,53,75,86,90，畫出兩者的存儲結(jié)構(gòu)，以及執(zhí)行merge(list)方法后的狀態(tài)，標明各變量的位置。public void merge(SortedCirDoublyList list) /方法功能是什么？ DoubleNode p=this.head.next; DoubleNode q=list.head.next; while (p!=this.head & q!=list.hea

8、d) /循環(huán)語句功能是什么？ if (p.data).compareTo(q.data)0) p = p.next; else q.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.head.prev.next=this.head; this.head.prev = list.head.prev; list.head.prev =

9、list.head; /為什么要這兩句？ list.head.next = list.head;閱讀程序，回答以下問題。 public static StringBuffer trim(StringBuffer s) /將s中所有空格刪除，返回操作后的s串 int i=0; while (is.length() & s.charAt(i)!= ) /i記住第1個空格下標 i+; for (int j=i; js.length(); j+) if (s.charAt(j)!= ) s.setCharAt(i+, s.charAt(j); /非空格字符向前移動到空格字符位置 return s; 對

10、于以下調(diào)用語句，運行結(jié)果是什么？正確的運行結(jié)果是什么？StringBuffer str = new StringBuffer( a bc d e f xyz);System.out.println(trim(+str+)=+trim(str); trim()方法怎樣實現(xiàn)所求功能？算法存在什么錯誤？ 如何改正？已知Tree類表示父母孩子兄弟鏈表存儲的樹，回答以下問題。 設(shè)一棵樹（森林）的廣義表表示如下，畫出所構(gòu)造的樹以及樹的存儲結(jié)構(gòu)圖，輸出樹的橫向凹入表示法。樹（森林）的廣義表表示：G(A(C(E,F),B,D),H(J(L),I,K) 以下levelorder()方法的功能是什么？對于上述樹（

11、森林），運行結(jié)果是什么？ levelorder()方法存在什么錯誤？如何改正？public void levelorder() LinkedQueueTreeNode que=new LinkedQueueTreeNode(); for (TreeNode p=this.root; p!=null; p=que.poll() System.out.print(p.data+ ); for (p=p.child; p!=null; p=p.sibling) que.add(p); System.out.println();程序設(shè)計題（16分=8分2題）SinglyList單鏈表類增加以下成員方法

12、，畫出操作示意圖。/刪除this中所有與pattern匹配的子表，BF模式匹配查找到再刪除public void removeAll(SinglyList pattern)實現(xiàn)以下對二叉鏈表存儲的二叉樹類BinaryTree操作的方法。/判斷二叉樹bitree是否二叉排序樹T extends Comparable boolean isSorted(BinaryTree bitree) 樣卷答案填空題（16分=2分8題）使數(shù)據(jù)類型的定義和實現(xiàn)分離，使一種定義有多種實現(xiàn)。見數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）習(xí)題解答第7頁習(xí)2-6。aababbabac.replaceAll(ab, aba)=aaba

13、abababaacABCDEF+*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分10題）模式串a(chǎn)bcaababc改進的next數(shù)組為j012345678模式串a(chǎn)bcaababc中最長相同的前后綴子串長度k-100011212與比較=改進的nextj-100-110200KMP算法匹配過程如下，字符比較次數(shù)為20

14、。見數(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分標準】構(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。堆序列概念見教材；構(gòu)造

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

16、后設(shè)置list為空，否則兩條循環(huán)雙鏈表將共用某些結(jié)點，會造成混亂。 算法描述如下圖所示，與第4版圖9.17算法同。見數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）習(xí)題解答第21頁【實驗題3-11】。先根次序遍歷樹，輸出樹的橫向凹入表示法：GACEFBDHJL IK 功能是按層次遍歷樹。上述森林的運行結(jié)果如下：層次遍歷樹： G A C B D E F levelorder()算法存在的錯誤是，只遍歷了一棵樹，無法遍歷森林。改正如下。public void levelorder() /按層次遍歷樹（森林），從根開始依次遍歷森林中的每棵樹 System.out.print(層次遍歷樹（森林）： ); Linked

17、QueueTreeNode que = new LinkedQueueTreeNode(); /創(chuàng)建一個空隊列 for (TreeNode q=this.root; q!=null; q=q.sibling) /遍歷森林 for (TreeNode p=q; p!=null; p=que.poll() /遍歷一棵樹，根沒有進隊 System.out.print(p.data+ ); for (p=p.child; p!=null; p=p.sibling) /所有孩子結(jié)點入隊 que.add(p); if (q.sibling!=null) System.out.print(，); Syste

18、m.out.println();上述森林的運行結(jié)果如下，結(jié)果正確，從根開始依次遍歷森林中的每棵樹。層次遍歷樹（森林）： G A C B D E F ，H J I K L程序設(shè)計題（16分=8分2題）單鏈表刪除所有匹配子表操作的算法描述如圖所示，該算法使用BF模式匹配查找到匹配子表，可一次刪除匹配子表。removeAll()方法聲明如下，刪除所有與pattern匹配的子表。/刪除this中所有與pattern匹配的子表，BF模式匹配查找到再刪除。public void removeAll(SinglyList pattern) if (pattern.isEmpty() /若無此句，則死循環(huán)，錯誤 return; Node start=this.head.next, front=this.head; while (start!=null) Node p=start, q=pattern.head.next; while (p!=null & q!=null & p.data.equals(q.data) /一次匹配 p=p.next; q=q.next; if (q!=null) /匹配失敗，進行下次匹配 front=start; start=start.next; else