1、第2章 線性表1.設指針變量p指向雙向鏈表中結點A，指針變量q指向被插入結點B，要求給出在結點A的后面插入結點B的操作序列（設雙向鏈表中結點的兩個指針域分別為llink和rlink）。答：操作序列如下：q-rlink = p-rlink ; p-rlink = q ;q-rlink-llink = q ; q-llink = p ;注意答案不唯一 第3章 棧和隊列1.設有編號為1，2，3，4的四輛列車，順序進入一個棧式結構的車站，具體寫出這四輛列車開出車站的所有可能的順序。答：共計14種，分別是：1234， 1243， 1324， 1342， 1432， 2134， 2143， 2341， 2

2、314， 2431， 3214， 3241， 3421， 43212.如果輸入序列為1，2，3，4，5，6，試問能否通過棧結構得到以下兩個序列：4，3，5，6，1，2和1，3，5，4，2，6；請說明為什么不能或如何才能得到。答：（1）不能得到4，3，5，6，1，2 ；因為1，2，3，4入棧后；4，3出棧；得到序列4，3；棧中還有1，2；5入棧后即出棧，得到序列4，3，5；6入棧后即出棧，得到序列4，3，5，6；此時，棧中還有1，2；必須2先出棧，然后1再出棧，1不可能在2之前出棧。故而得不到該序列。（2）能得到輸出順序為1，3，5，4，2，6的序列。得到的操作如下：1入棧后即出棧，得到序列1；

3、2，3入棧后3即出棧，得到序列1，3；4，5入棧后，5出棧，4出棧，得到序列1，3，5，4；2出棧，得到序列1，3，5，4，2；6入棧后即出棧，得到序列1，3，5，4，2，6。3.假設正讀和反讀都相同的字符序列為“回文”，例如，abba和abcba是回文，abcde 和ababab則不是回文。假設一字符序列已存入計算機，請用堆棧判斷其是否為回文，簡述算法。答：方法一：使用數據結構:循環隊列和順序棧。算法思路為：3.比較取出的字符，若相等，繼續分別從隊列和棧中取首個字符；否則跳出循環，并設置標志flag=0;都取完，則結束，設置標志flag=1;5.flag=1,表示字符從前往后和從后往前的序列

4、完全匹配，該字符串屬于回文6.flag=0,表示字符從前往后和從后往前的序列不完全匹配，該字符串不屬于回文方法二：使用棧。將字符串的前一半入棧，再依次出棧，與后一半進行比較，若有不等則不是回文；若依次相等，則是回文。注意：本題要求簡答算法思路，并不要求寫出具體算法。4.試寫出循環隊列判空和判滿的條件（隊列最大容量為M）。答：假設循環隊列最大存儲容量為M 判空：Q.front=Q.rear （1）判滿：（Q.rear+1）%M=Q.front （2）評分標準：給出（1）和（2）式分別得3分，其他酌情扣分。5.假設Q0.10是一個循環隊列，初始狀態為front=rear=0，畫出做完下列操作后隊列

5、的頭尾指針的狀態變化情況，若不能入隊，請指出其元素，并說明理由。d,e,b,g,h入隊；d,e出隊；i,j,k,l,m入隊；n,o,p入隊答：（圖自己根據解答畫出）d,e,b,g,h入隊；狀態1：front=0，rear=5；d,e出隊；狀態2：front=2，rear=5；i,j,k,l,m入隊；狀態3：front=2，rear=10；n,o,p入隊；狀態4：front=2，rear=1；p不能入隊，因為隊列已經滿了。評分標準：狀態1、狀態4各2分，狀態2、狀態3各1分，狀態4中狀態1分，理由1分。6.若元素的進棧序列為：A、B、C、D、E，運用棧操作，能否得到出棧序列B、C、A、E、D和D

6、、B、A、C、E？為什么？答：能得到出棧序列B、C、A、E、D，不能得到出棧序列D、B、A、C、E。其理由為：若出棧序列以D開頭，說明在D之前的入棧元素是A、B和C，三個元素中C是棧頂元素，B和A不可能早于C出棧，故不可能得到D、B、A、C、E出棧序列。7.設輸入序列為a,b,c,d,試寫出借助一個棧可得到的兩個輸出序列和兩個不能得到的輸出序列。答：借助棧結構，n個入棧元素可得到1/(n+1)(2n）！/（n!*n!）)種出棧序列。本題4個元素，可有14種出棧序列，abcd和dcba就是其中兩種。但dabc和adbc是不可能得到的兩種。8.將兩個棧存入數組V1.m應如何安排最好？這時棧空、棧滿

7、的條件是什么？答：設棧S1和棧S2共享向量V1.m，初始時，棧S1的棧頂指針top0=0，棧S2的棧頂指針top1=m+1，當top0=0為左?？?，top1=m+1為右?？眨划攖op0=0并且top1=m+1時為全?？铡．攖op1-top0=1時為棧滿。9.如果輸入序列為1 2 3 4 5 6,試問能否通過棧結構得到以下兩個序列:4 3 5 6 1 2和1 3 5 4 2 6；請說明為什么不能或如何才能得到。答：輸入序列為123456，不能得出435612，其理由是，輸出序列最后兩元素是12，前面4個元素（4356）得到后，棧中元素剩12，且2在棧頂，不可能棧底元素1在棧頂元素2之前出棧。得到

8、135426的過程如下：1入棧并出棧，得到部分輸出序列1；然后2和3入棧，3出棧，部分輸出序列變為：13；接著4和5入棧，5，4和2依次出棧，部分輸出序列變為13542；最后6入棧并退棧，得最終結果135426。10.假設以數組sq0.7存放循環隊列元素,變量f指向隊頭元素的前一位置,變量r指向隊尾元素，如用A和D分別表示入隊和出隊操作，請給出：（1）隊空的初始條件；（2）執行操作序列A3D1A5D2A1D2A4時的狀態,并作必要的說明。（A3表示三次入隊操作，D1表示一次出隊操作）答：（1）隊空的初始條件：f=r=0；（2）執行操作A3后，f=0，r=3；/A3表示三次入隊操作執行操作D1后

9、，f=1，r=3；/D1表示一次出隊操作執行操作A5后，f=1，r=0；執行操作D2后，f=3，r=0；執行操作A1后，f=3，r=1；執行操作D2后，f=5，r=1；執行操作A4后，按溢出處理。因為執行A3后，r=4，這時隊滿，若再執行A操作，則出錯。11.內存中一片連續空間（不妨假設地址從1到m）提供給兩個棧S1和S2使用，怎樣分配這部分存儲空間，使得對任一個棧，僅當這部分空間全滿時才發生上溢1 答： S1和S2共享內存中一片連續空間（地址1到m），可以將S1和S2的棧底設在兩端，兩棧頂向共享空間的中心延伸，僅當兩棧頂指針相鄰（兩棧頂指針值之差的絕對值等于1）時，判斷為棧滿，當一個棧頂指針

10、為0，另一個棧頂指針m+1時為兩棧均空。12.設一數列的輸入順序為123456，若采用堆棧結構，并以A和D分別表示入棧和出棧操作，試問通過入出棧操作的合法序列。（1）能否得到輸出順序為325641的序列。（2）能否得到輸出順序為154623的序列。答：（1）能得到325641。在123依次進棧后，3和2出棧，得部分輸出序列32；然后4，5入棧，5出棧，得部分出棧序列325；6入棧并出棧，得部分輸出序列3256；最后退棧，直到?？?。得輸出序列325641。其操作序列為AAADDAADADDD。（2）不能得到輸出順序為154623的序列。部分合法操作序列為ADAAAADDAD，得到部分輸出序列15

11、46后，棧中元素為23，3在棧頂，故不可能2先出棧，得不到輸出序列154623。13.設輸入序列為2，3，4，5，6，利用一個棧能得到序列2，5，3，4，6嗎？為什么？?？梢杂脝捂湵韺崿F嗎？ 答：不能得到序列2，5，3，4，6；其理由是，輸出序列第三四位兩元素是3，4，前面2個元素（2，5）得到后，棧中元素剩3，4，且4在棧頂，棧底元素3不可能在棧頂元素4之前出棧。棧可以用單鏈表實現，這就是鏈棧。由于棧只在棧頂操作，所以鏈棧通常不設頭結點。14.有5個元素，其入棧次序為：A，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧（即C第一個且D第二個出棧）的次序有哪幾個？用S表示入棧，X

12、表示出棧，寫出可能得到次序的操作序列。答：三個：CDEBA，CDBEA，CDBAECDEBA操作序列：SSSXSXSXXX；CDBEA操作序列：SSSXSXXSXX；CDBAE操作序列：SSSXSXXXSX；15.若以1、2、3、4作為雙端隊列的輸入序列，試分別求出以下條件的輸出序列：（1）能由輸入受限的雙端隊列得到，但不能由輸出受限的雙端隊列得到的輸出序列；（2）能由輸出受限的雙端隊列得到，但不能由輸入受限的雙端隊列得到的輸出序列；（3）既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列。答：（1）4132 （2）4213 （3）423116.設一個雙端隊列，元素進入該

13、隊列的次序為a，b，c，d。求既不能由輸入受限的雙端隊列得到,又不能由輸出受限的雙端隊列得到的輸出序列。答：既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列是dbca。第6章 樹和二叉樹1.（8分）已知一棵樹的邊的集合表示為：(L,N),(G,K),(G,L),(G,M),(B,E),(B,F),(D,G), (D,H),(D,I),(D,J),(A,B),(A,C),(A,D)畫出這棵樹，并回答下列問題：(1)樹根是哪個結點？哪些是葉子結點？哪些是非終端結點？(2)樹的度是多少？各個結點的度是多少？(3)樹的深度是多少？各個結點的層數是多少？以結點為根的子樹的深度是多

14、少？X72.用一維數組存放的一棵完全二叉樹如下表所示ABCDEFGHIJKL寫出先序、中序、后序、層次遍歷該二叉樹時訪問結點的順序。答案 HIDJKEBLFGCAX23.（5分）對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，證明：n0=n2+1。X34.敘述并證明二叉樹的性質3。X35.（8分）已知一棵二叉樹如下，（1）請分別寫出按前序、中序、后序和層次遍歷時得到的結點序列。（2）如果此二叉樹由森林轉換得到，請畫出原森林中的各棵樹。X1X56.（8分）畫出由下列序列得到的二叉樹以及由此二叉樹轉化的森林：先序：EBADCFHGIKJ；中序：ABCDEFGHIJK。X87.有二

15、叉樹中序序列為：ABCEFGHD，后序序列為：ABFHGEDC，請畫出此二叉樹，并寫出二叉樹的先序遍歷序列和層次遍歷序列。答案根據后序序列知根結點為C，因此左子樹：中序序列為AB 后序序列為AB 右子樹：中序序列為EFGHD ，后序序列為：FHGED 依次推得該二叉樹結構如下圖所示先序遍歷序列：CBADEGFH層次遍歷序列：CBDAEGFHX58.（8分）二叉樹T的前序遍歷序列和中次遍歷序列分別是ABCDEFG和CBEDAFG，試畫出該二叉樹，并寫出二叉樹的后序遍歷序列和層次遍歷序列。X99.（6分）二叉樹的先序序列為EBADCFHGIKJ；二叉樹的中序序列為ABCDEFGHIJK，請畫出該二

16、叉樹，并寫出二叉樹的后序遍歷序列和層次遍歷序列。X1010.（8分）設一棵二叉樹的先序、中序遍歷序列分別為先序遍歷序列： A B D F C E G H 中序遍歷序列： B F D A G E H C請畫出該二叉樹，并將這棵二叉樹轉換成對應的樹（或森林）。X411.（8分）設一棵二叉樹的前序序列為ABDGECFH，中序序列為：DGBEAFHC 。試畫出該二叉樹。并寫出后序和層次遍歷序列。12.（6分）設給定一個權值集合W=(3，5，7，9，11)，要求根據給定的權值集合構造一棵哈夫曼樹并計算哈夫曼樹的帶權路徑長度WPL。X613.（8分）假設字符a,b,c,d,e,f,g,h的使用頻度分別是0

17、.15,0.19,0.07,0.08,0.04,0.23，0.13，0.11畫出哈夫曼樹并寫出a,b,c,d,e,f,g,h的Huffman（哈夫曼）編碼。X514.（8分）假設字符a,b,c,d,e,f的使用頻度分0.07,0.09,0.12,0.22,0.23,0.27，寫出a,b,c,d,e,f的Huffman（哈夫曼）編碼。X715.（8分）假設字符a,b,c,d,e,f的使用頻度分別是0.07,0.10,0.12,0.16,0.25,0.30，構造哈夫曼樹并寫出a,b,c,d,e,f的哈夫曼編碼。16.（6分）試分別畫出具有三個結點的樹和三個結點的二叉樹的不同形態。X617.請畫出下

18、圖所示的樹所對應的二叉樹。答案：18.（6分）請畫出與下列二叉樹對應的森林。X10X819.已知一棵樹邊的集合為, ,，請回答下列問題：x10（1）哪個是根結點？（2）X8哪些是葉子結點？X10哪些是分支結點？X8（3）哪個是結點G的雙親結點？（4）哪些是結點G的祖先？X8（5）哪些是結點G的孩子？X8（6）哪些是結點E的子孫？X8（7）哪些是結點E的兄弟？哪些是結點F的兄弟？（8）結點B和N的層次號分別是多少？（9）樹的深度是多少？（10）以結點C為根的子樹的深度是多少？答案（1）A； （2）D, M, N, F, J, K, L； (3) C； (4) A, C； (5) J,K；(6)

19、I, M, N； (7) E的兄弟是D，F的兄弟是G和H；（8）2, 5； (9) 5； (10) 3。X920.假設在樹中，結點x是結點y的雙親時，用（x，y）來表示樹邊。已知一棵樹邊的集合為：（i，m），（i，n），（e，i），（b，e），（b，d），（a，b），（g，j），（g，k），（c，g），（c，f），（h，l），（c，h），（a，c）。用樹形表示法畫出此樹，并回答下列問題：（1）哪個是根結點：（2）哪些是葉結點？（3）哪個是g的雙親？（4）哪些是g的祖先？（5）哪些是g的孩子？（6）哪些是e的子孫？（7）哪些是e的兄弟？哪些是f的兄弟？（8）結點b和n的層次各是多少？（9）樹的深

20、度是多少？（10）以結點c為根的子樹的深度是多少？（11）樹的度數是多少？答案：（1）根結點：a（2）葉結點：m、n、d、l、h、j、k（3）g的雙親：c（4）g的祖先：a、c（5）g的孩子：j、k（6）e的子孫：i、m、n（7）e的兄弟：d（8）b的層次：2（9）樹的深度：5 f的兄弟：g、hn的層次；5（10）以結點c為根的子樹的深度：3（11）樹的度數：321.已知一棵樹邊的結點為（I,M），(I，N),(E，I),(B，E)，(B，D),(C，B),(G，L)，(G，K)，(A，G)，(A，F),(H，J)，(A，H)，(C，A)，試畫出這棵樹，并回答下列問題：(1)哪個是根結點？(2

21、)哪些是葉子結點？(3)樹的深度是多少？答案如下圖所示。（圖不對，缺結點H的孩子結點J，）根結點C，葉子結點F、K、L、J、D、M、N，深度5 五、應用題（每小題6分，共48分）3.答：快速排序的思想：通過一趟排序將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。評分標準：只要基本思想對就可得分。3、（8分）二叉樹為：后序遍歷序列：CEDBGFA，層次遍歷序列：ABFCDGE評分標準：得出二叉樹得4分，給出后序和層次遍歷序列得4分，步驟不全酌情給分。4、（8分）哈夫曼樹：哈夫曼編碼：a：011 b：10 c

22、：00000 d：0010e：0001 f：11 g：001 h：0101評分標準：得出哈夫曼樹給4分，給出哈夫曼編碼給4分，步驟不全酌情給分。5、（10分）（1）鄰接表存儲結構（2）深度優先遍歷序列：BADCEF 廣度優先遍歷序列：BACEDF評分標準：畫出鄰接表存儲結構得5分，求出深度優先和廣度優先遍歷序列得5分，其他情況全酌情給分。6、（8分）二叉判定樹平均查找長度：ASL=（1+2*2+4*3+3*4）/10=2.9 評分標準：得出二叉判定樹給6分，求出平均查找長度給2分，步驟不全酌情給分。2、（6分）快速排序的思想：通過一趟排序將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均

23、比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。評分標準：只要基本思想對就可得分。3、（8分）二叉樹為：后序遍歷序列：CEDBGFA，層次遍歷序列：ABFCDGE評分標準：得出二叉樹得4分，給出后序和層次遍歷序列得4分，步驟不全酌情給分。4、（8分）哈夫曼樹：哈夫曼編碼：a：011 b：10 c：00000 d：0010e：0001 f：11 g：001 h：0101 評分標準：得出哈夫曼樹給4分，給出哈夫曼編碼給4分，步驟不全酌情給分。5、（10分）（1）鄰接表存儲結構（2）深度優先遍歷序列：BADCEF 廣度優先遍歷序列：BACEDF評分標準：畫出鄰接表存

24、儲結構得5分，求出深度優先和廣度優先遍歷序列得5分，其他情況全酌情給分。6、（8分）二叉判定樹平均查找長度：ASL=（1+2*2+4*3+3*4）/10=2.9 評分標準：得出二叉判定樹給6分，求出平均查找長度給2分，步驟不全酌情給分。四、算法題（22分）1、（6分）評分標準：每寫錯一種形態扣1分。2、（8分）（1）前序：ABDGCEFH 中序：DGBAECHF 后序：GDBEHFCA 層次：ABCDEFGH（2）二叉樹所對應的森林：評分標準：第一小題每個1分，第二小題三棵樹4分，每錯一個扣1分。3、（8分）二叉排序樹的構造過程如下：評分標準：沒有過程或過程不全酌情減分4、（8分）評分標準：結

25、果正確得5分，步驟不全酌情扣分。5、（10分）（1）（4分）哈希表：012345678910111213141516173217634924401030314647（2）（4分）若查找關鍵字63，需要與關鍵字31、16、47、32、17進行比較。（3）（2分）平均查找長度：ASLsc=（6*1+2+3*3+6）/11=23/116、（8分）（36）25 48 12 65 20（25 36）48 12 65 20（25 36 48）12 65 20（12 25 36 48）65 20（12 25 36 48 65）20 （12 20 25 36 48 65）評分標準：每一趟插入得1分，步驟不全酌

26、情扣分。三、應用題（43分）1、（6分）對任何一棵二叉樹，如果其終端結點數為n0，度為2的結點數為n2，則n0=n2+1。證明：設二叉樹的結點總數為n，度為1的結點個數為n1，則有： n=n0+n1+n2 （1） 又在二叉樹中除了根結點每個結點都有一個分支指向它，這些分支是有度為1和度為2的結點發出的，由此得到： n-1=n1+2*n2 （2）由式（1）和（2）得n0=n2+1，證畢。評分標準：敘述定理得2分，證明得4分，其他酌情扣分。 2、（8分）哈夫曼樹為：由此可得哈夫曼編碼分別為：a：000b：001 c：100d：101 e：01 f：11 評分標準：得出哈夫曼樹給4分，給出哈夫曼編碼

27、給4分，步驟不全酌情給分。3、（8分）二叉排序樹的構造過程如下：5分平均查找長度：ASL=（1+2*2+4*3+2*4+5）/10=3 3分評分標準：得出二叉判定樹給5分，求出平均查找長度給3分，步驟不全酌情給分。4、（7分）拓撲序列構造過程拓撲有序序列有兩種：ABCDEF和ACBDEF 評分標準：只有結果沒有過程給5分，過程不全或過程不正確酌情扣分。5、（8分）鄰接矩陣為最小生成樹為：評分標準：寫出鄰接矩陣給3分，最小生成樹給5分，只有結果沒有過程給3分，過程不全或過程不正確酌情扣分。6、（6分）快速排序的思想：通過一趟排序將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記

28、錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。一趟快速排序的結果：40，38，27，20，13，49，76，80，65評分標準：寫出快速排序思想給3分，給出一趟排序結果給3分。四、算法題（22分）三、應用題（43分）1、（6分）3分3分評分標準：構造出二叉樹得3分，二叉樹的生成森林得3分。2、（8分）5分平均查找長度：ASL=（1+2*2+4*3+3*4）/10=2.9 3分評分標準：得出二叉判定樹給4分，求出平均查找長度給2分，步驟不全酌情給分。3、（7分）鄰接矩陣：3分深度優先序列：abcdehf或abchedf或abcfdeh或abcfhed（不唯一）2分廣度優先

29、序列：abfcdhe或afbcdhe或abfchde或afbchde（不唯一）2分評分標準：寫出圖的鄰接矩陣的2分，深度優先序列得2分，廣度優先序列得2分，其他酌情給分。4、（8分）最短路徑：終點12345B6(A,B)4(A,C,B)C2(A,C)D5(A,C,D)5(A,C,D)E6(A,C,E)6(A,C,E)6(A,C,E)F8(A,C,D,F)8(A,C,D,F)SAA,CA,C,BA,C,B,DA,B,C,D,E評分標準：最短路徑給5分，過程給3分，結果正確沒有過程或過程不對酌情減分。5、（8分）哈希表：01234567891011121401682755192084231110平

30、均查找長度：ASLsc=（6*1+2+3*3+4）/11=21/11評分標準：寫出哈希表得5分，查找長度3分6、（5分）（1）是大頂堆（2）不是堆，調整以后為100，98，66，85，80，60，40，77，82，10，20（3）是小頂堆評分標準：判斷正確得3分，調整得3分四、算法題（22分）1、（5分）假設循環隊列最大存儲容量為M 判空：Q.front=Q.rear （1）判滿：（Q.rear+1）%M=Q.front （2）評分標準：給出（1）和（2）式分別得2分，前提假設得1分，其他酌情扣分。2、（5分）對任何一棵二叉樹，如果其終端結點數為n0，度為2的結點數為n2，則n0=n2+1。證

31、明：設二叉樹的結點總數為n，度為1的結點個數為n1，則有： n=n0+n1+n2 （1） 又在二叉樹中除了根結點每個結點都有一個分支指向它，這些分支是有度為1和度為2的結點發出的，由此得到： n-1=n1+2*n2 （2）由式（1）和（2）得n0=n2+1，證畢。評分標準：給出（1）和（2）式分別得2分，得出結論得1分，其他酌情扣分。3、（7分）哈夫曼樹為：由此可得哈夫曼編碼分別為：a：000b：001 c：100d：101 e：01 f：11 評分標準：得出哈夫曼樹給4分，給出哈夫曼編碼給3分，步驟不全酌情給分。4、（8分）二叉排序樹：評分標準：構造出二叉排序樹得5分，平均查找長度得3分，步

32、驟不全酌情扣分。5、（7分）由C開始的深度優先生成序列：CDEABF評分標準：畫出原圖得4分，求出深度優先生成序列得3分，其他情況酌情給分。6、（8分）最短路徑求解過程：終點12345B6(A,B)4(A,C,B)C2(A,C)D5(A,C,D)5(A,C,D)E6(A,C,E)6(A,C,E)6(A,C,E)F8(A,C,D,F)8(A,C,D,F)SAA,CA,C,BA,C,B,DA,B,C,D,E評分標準：結果正確沒有過程得5分，步驟不全或不正確酌情扣分。五、算法題（共20分）1、（5分）評分標準：每寫對一種形態得1分。2、（5分）快速排序的思想：通過一趟排序將待排序記錄分割成獨立的兩部

33、分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。評分標準：只要基本思想對就可得分。3、（7分）（1）前序：ABDGCEFH 中序：DGBAECHF 后序：GDBEHFCA 層次：ABCDEFGH（2）二叉樹所對應的森林：評分標準：第一小題每個1分，第二小題三棵樹，每個1分。4、（8分）關鍵路徑為： 求解過程：vevlell-eA00a1011B56a2000C22a3055D611a4561E99a5220F1015a66115G1516a7990H1414a89101I2323a910155a1014140a1115161評分標準

34、：結果正確沒有過程給5分，過程不全或過程不正確酌情扣分。5、（8分）最小生成樹為：評分標準：結果正確沒有過程給5分，過程不全或過程不正確酌情扣分。6、哈希表：01234567891011121401682755192084231110平均查找長度：ASLsc=（6*1+2+3*3+4）/11=21/11評分標準：寫出哈希表得5分，查找長度2分，其他情況酌情給分。五、算法題（20分）四、應用題（40分）1、（8分）4分4分評分標準：構造出二叉樹得4分，二叉樹的生成森林得4分。2、（8分）二叉排序樹的構造過程如下：評分標準：沒有過程或過程不全酌情減分3、（8分）鄰接矩陣：4分深度優先序列：abcd

35、ehf或abchedf或abcfdeh或abcfhed（不唯一）廣度優先序列：abfcdhe或afbcdhe或abfchde或afbchde（不唯一）4分評分標準：寫出圖的鄰接矩陣的4分，深度優先序列得2分，其他酌情給分。4、（8分）3評分標準：最小生成樹給4分，過程給4分，結果正確沒有過程或過程不對酌情減分。5、（8分）哈希表：012345678910111232920032455810010126400平均查找長度：ASLsc評分標準：寫出哈希表得5分，查找長度3分四、算法題（20分）三、應用題（40分）1、（5分）評分標準：每寫錯一種形態扣1分。2、（5分）對任何一棵二叉樹，如果其終端結

36、點數為n0，度為2的結點數為n2，則n0=n2+1。評分標準：敘述不恰當酌情扣分。3、（8分）哈夫曼樹為：由此可得哈夫曼編碼分別為：a：0000 b：0001 c：001 d：01 e：10 f：11 評分標準：得出哈夫曼樹給4分，給出哈夫曼編碼給4分，步驟不全酌情給分。4、（8分）拓撲序列構造過程拓撲有序序列有兩種：ABCDEF和ACBDEF 評分標準：只有結果沒有過程給5分，過程不全或過程不正確酌情扣分。5、（8分）最小生成樹為：評分標準：只有結果沒有過程給5分，過程不全或過程不正確酌情扣分。6、（8分）（1）由裝載因子0.7，數據總數7個，得一維數組大小為7/0.7=10，存儲空間長度為10，采用線性探測再散列法處理沖突，所構造的散列表為：01234567893071411818.9.（2）查找成功的ASL=(1+1+1+1+2+1+1)/7=8/7評分標準：構造出哈希表得6分，求出平均查找長度得2分。7、（6分）快速排序的思想：通過一趟排序將待