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

2、聲明以下成員方法:/將所有與 pattern /將所有與 pattern 匹配的子串替換為 strString target=aababbabac, pattern=ab, str=aba;System.out.println(+target+.replaceAll(+pattern+, +str+)=+target.replaceAll(pattern,str)+); TOC o 1-5 h z A+B*（C-D*（E+F）/G+H）-（I+J）*K 的后綴表達式為。已知二維數組a108采用行主序存儲，數組首地址是1000,每個元素占用4字節，則數組元素a45的存儲地址是。由n個頂點組成的無

3、向連通圖，最多有條邊。排序關鍵字序列（升序）5,17,20,32,43,55,61,61*,72,96，采用二分法查找算法，查找96的元素比較序列是；查找35的元素比較序列是。關鍵字序列93, 17, 56, 42, 78, 15, 42*, 25, 19，采用希爾排序（升序）算法，第一趟排序后的序列是。二、問答題（50分=5分X10題）1.已知目標串為aabcbabcaabcaababc，模式串為abcaababc，寫出模式串改進的next數組；畫出KMP 算法的匹配過程，給出字符比較次數。畫出以下稀疏矩陣非零元素三元組的十字鏈表存儲結構。000 32 0 0150059 0 00 86 0

4、 0 43A7x80000000 32 0 0150059 0 00 86 0 0 43A7x80000180 0 0 6500已知一棵二叉樹的遍歷序列如下，畫出這棵二叉樹并進行中序線索化。中根遍歷序列：CBDFEGAMLNKJOPRQIHS ；后根遍歷序列：CFGEDBMNLKRQPOJISHA4.設一段正文由字符集A,B,C,D,E,F,GH組成，其中每個字符在正文中的出現次數依次為 23,5,17,4,9,31,29,18,采用Huffman編碼對這段正文進行壓縮存儲，畫出所構造的Huffman樹，并寫出每 個字符的Huffman編碼。說明Huffman編碼的特點和作用。5.已知以下無向

5、圖G7中各頂點按A,B,C,D,E,F,GH次序存儲。分別畫出采用深度優先搜索（從A開 始）和廣度優先搜索（從D開始）遍歷圖時棧或順序循環隊列（容量為6）的動態變化示意圖，說明棧或 隊列的作用。6.什么是圖的最小生成樹？構造以下帶權無向圖的最小生成樹，給出該最小生成樹代價。說明Prim算法和Kruskal算法的差別。a）帶權無向圖,BA6算法和Kruskal算法的差別。a）帶權無向圖,BA64GF10EAFEB64G12C5D1112C5D（c） Prim算法不斷擴充T,AF610B4GEC5D（d） Kruskal算法不斷合并樹，依次7.畫出以帶權帶權有向圖采用1Di默生算，以價為為源點的單

6、源最短路GB所選擇的邊邊（B寫出各路徑長度:設散列表采用鏈地址法，初始容量length為10；散列函數采用除留余數法hash（key）=key % length； 裝填因子為0.75，散列數組容量以2倍擴充。由關鍵字序列16,75,60,43,54,90,46,31,27,88,64,50構造散列 表，分別畫出擴容前和最終狀態圖，計算ASL成功畫出由關鍵字序列50, 16, 74, 60, 43, 16, 90, 46, 31, 29, 88, 71, 64, 13, 65構造的一棵二叉排序樹，計 算ASL成功執行刪除結點50、插入50,再畫出操作后的二叉排序樹。10. 什么是堆序列？堆序列在

7、堆排序算法中起什么作用？將關鍵字序列29, 10, 25, 26, 58, 12, 31, 18, 47分別建成一個最大堆和一個最小堆，寫出堆序列，畫出對應的完全二叉樹；寫出每一趟堆排序結果。若 有關鍵字重復元素，做標記以區別。三、程序閱讀和改錯題(18分=6分X3題)1. SortedCirDoublyListvT排序循環雙鏈表類增加以下成員方法，回答問題。以下merge(list)方法功能是什么？方法體中，while、if等語句功能是什么？已知兩條排序循環雙鏈表this和list的序列為26,37,61,81和18,53,75,86,90,畫出兩者的存儲結構, 以及執行merge(list

8、)方法后的狀態，標明各變量的位置。/方法功能是什么？public void merge/方法功能是什么？DoubleNode p=this.head.next;DoubleNode q=list.head.next; while (p!=this.head & DoubleNode p=this.head.next;DoubleNode q=list.head.next; while (p!=this.head & q!=list.head) if (p.data).compareTo(q.data)0) p = p.next;else q.prev = p.prev; p.prev.next

9、 = 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 = list.head;list.head.next = list.head;/循環語句功能是什么？/選擇語句功能是什么？/為什么要這兩句？2. 閱讀程序，回答以下問題。public static StringBuffe

10、r 2. 閱讀程序，回答以下問題。public static StringBuffer trim(StringBuffer s) int i=0;while (is.length() & s.charAt(i)!= ) i+;for (int j=i; j類表示父母孩子兄弟鏈表存儲的樹，回答以下問題。設一棵樹(森林)的廣義表表示如下，畫出所構造的樹以及樹的存儲結構圖，輸出樹的橫向凹入表 示法。樹(森林)的廣義表表示：G(A(C(E,F),B,D),H(J(L),I,K)以下levelorder()方法的功能是什么？對于上述樹(森林)，運行結果是什么？levelorder()方法存在什么錯誤？如

11、何改正？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();四、程序設計題(16分=8分X2題)SinglyListvT單鏈表類增加以下成員方法，畫出操作示意圖。刪除this中所有與pattern匹配的子表，BF

12、模式匹配查找到再刪除public void removeAll(SinglyList pattern)實現以下對二叉鏈表存儲的二叉樹類BinaryTree操作的方法。/判斷二叉樹 bitree 是否二叉排序樹T extends Comparable boolean isSorted(BinaryTree bitree)4-0 樣卷答案一、填空題（16分=2分X8題）使數據類型的定義和實現分離，使一種定義有多種實現。見數據結構（Java版）（第4版）習題解答第7頁習2-6。aababbabac.replaceAll（ab, aba）=aabaabababaacABCDEF+*G/-H+*+IJ+

13、K*-,見數據結構（Java版）（第4版）習題解答第27頁習4-5。mat+（i*n+j）*4=1000+（4*8+5）*4=1148n*（n-1）/243,61*,72,96；43,17,20,32。解釋見習題解答第54頁習8-9。見數據結構（Java版）（第4版）習題解答第57頁習9-4。二、問答題（50分=5分X1Q題）1.模式串abcaababc改進的next數組為j012345678模式串abcaababcp p p 中取長相冋的前后綴子串長度k-1000112120_1Pk與竹比較豐豐=學=學=kJ改進的nextj-100-110200KMP算法匹配過程如下，字符比較次數為20。1

14、I11151T111o-n12I3I4-n6-n7|aabcbabcaabcaababctargettoItlI | * | | 4 | - | 嘉 1 E I j I-0Itil-2-J 1t4|t5|t6|t7= Habcaababcp0 p1 p2 p3 p4 p5 p6 p7 p8(a)第1次匹配，t0=p0，片工卩,比較2次，next1=01i12|14|517|11oqii1i2|i3 |i4n6|i7|aabcbabcaabcaababctargetS It1I | * | J | J | - | 9 i 仏 | |to| -1J?咕 i片4|-5|I；%| Jabcaababc

15、patternHp0 p1 p2 pJ p4 p5 p6 p7 p8(b)第2次匹配，t1=p0，,t4Hp3，比較4次，next3=-11111M151T111o-ni1i2|3Ii4 ii5-6-n7|aabcbabcaabcaababctargettoIt1, 4 ItjI S I 4 I I 9 ,4 ItioItilJ |t】3, t站= Habcaababcpop1p2p3p4p5p6p7p8(c)第3次匹配，t5=p0，片工卩6，比較7次，next6=21il1151T111o-ni12I3I46-n7|aabcbabcaabcaababctargettoItlI 4 ItjI

16、J I 4 I I I 1 I 4 ItioItil-2-3 1-4I-5It16It17patternabcaababcpopip2p3p4p5p6p7pg（d）第4次匹配，tii=p2,，ti7=p8,比較7次，匹配成功，與模式串匹配的子串序號為92.見數據結構（Java版）（第4版）習題解答第34頁習5-9。見數據結構（Java版）（第4版）習題解答第37頁習6-19、第42頁圖6.9。 【評分標準】構造二叉樹3分，中序線索化2分。見數據結構（Java版）（第4版）習題解答第44頁習6-31、6-34。見數據結構（Java版）（第4版）習題解答第48頁習7-15。見數據結構（Java版）

17、（第4版）習題解答第50頁習7-11、7-15。見數據結構（Java版）（第4版）習題解答第52頁習7-15。見數據結構（Java版）（第4版）習題解答第55頁習8-12。見數據結構（Java版）（第4版）習題解答第56頁習8-19。堆序列概念見教材；構造的堆見數據結構（Java版）（第4版）習題解答第59頁習9-10。三、程序閱讀和改錯題（18分=6分X3題）1.merge（list）方法功能是：歸并兩條排序循環雙鏈表，將list中所有結點歸并到this中，合并后設 置 list 空。方法體中，while語句功能是：p、q分別遍歷this和list排序循環雙鏈表，比較p、q結點值有大小，若

18、q結點值較小，將q結點插入到p結點之前。當遍歷完一條循環雙鏈表時，while循環結束。while之后的if語句功能是：若q!=list.head，表示遍歷this結束，要將list中剩余結點（q結點開始）鏈 接到this尾，并使this與list的最后結點連接成為環形。合并后設置list為空，否則兩條循環雙鏈表將共用某些結點，會造成混亂。 算法描述如下圖所示，與第4版圖9.17算法同。this.headlist.head261837*618153758690（a）比較p、q結點值，若p結點值小，則繼續比較p的后繼；否則（M）,this.headlist.head261837*618153758

19、690（a）比較p、q結點值，若p結點值小，則繼續比較p的后繼；否則（M）,將q結點插入在p之前this.headlist.head0（b）重復執行（a）,歸并結點；當p=this.head且q!=list.head時，將q結點插入在this的最后結點之后; 并使this與list的最后結點連接成為環形。設置1 ist為空循環雙鏈表26437?53/61*758681*90i1見數據結構（Java版）（第4版）習題解答第21頁【實驗題3-11】。GA* |child dataHAA(b)森林的父母孩子兄弟鏈表GA* |child dataHAA(b)森林的父母孩子兄弟鏈表A/Aroot11J7

20、ALAAF7A 功能是按層次遍歷樹。上述森林的運行結果如下：層次遍歷樹： G A C B D E Flevelorder(層次遍歷樹： G A C B D E Flevelorder()算法存在的錯誤是，只遍歷了一棵樹，無法遍歷森林。改正如下。public void levelorder()/按層次遍歷樹(森林)，從根開始依次遍歷森林中的每棵樹System.out.print(層次遍歷樹(森林)：);LinkedQueueTreeNode que = new LinkedQueueTreeNode(); /創建一個空隊列for (TreeNode q=this.root; q!=null; q

21、=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)que.add(p);/遍歷森林/遍歷一棵樹，根沒有進隊/所有孩子結點入隊if (q.sibling!=null)System.out.print(，);System.out.println();上述森林的運行結果如下，結果正確，從根開始依次遍歷森林中的每棵樹。層次遍歷樹(森林)：G A C B D E F 層次遍歷樹(森林)：G A C B D E F ，H J

22、I K L四、程序設計題(16分=8分X2題)1.單鏈表刪除所有匹配子表操作的算法描述如圖所示，該算法使用BF模式匹配查找到匹配子表，可 一次刪除匹配子表。q=null(a)當一次匹配成功時，刪除從start結點開始的一條匹配子表p=nullq=null(a)當一次匹配成功時，刪除從start結點開始的一條匹配子表p=null(b)start再次從front的后繼結點開始尋找匹配子表并刪除removeAll()方法聲明如下，刪除所有與pattern匹配的子表。刪除this中所有與pattern匹配的子表，BF模式匹配查找到再刪除。 public void removeAll(SinglyList pattern)if (pattern.isEmpty()/若無此句，則死循環，錯誤return;Node start=this.head.next, front=this.head;while (start!=null) Node p=start, q=pattern.hea