數(shù)據(jù)結(jié)構(gòu)應(yīng)用題答案第2章線性表1.設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A,指針變量q指向被插入結(jié)點(diǎn)B,要求給出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列〔設(shè)雙向鏈表中結(jié)點(diǎn)的兩個指針域分別為llink和rlink〕.答：操作序列如下：q->rlink=p->rlink;p->rlink=q;q->rlink->llink=q;q->llink=p;注意答案不唯一第3章棧和隊(duì)列.設(shè)有編號為1,2,3,4的四輛列車,順序進(jìn)入一個棧式結(jié)構(gòu)的車站,具體寫出這四輛列車開出車站的所有可能的順序.答：共計(jì)14種,分別是：1234,1243,1324,1342,1432,2134,2143,2341,2314,24313214324134214321.如果輸入序列為1,2,3,4,5,6,試問能否通過棧結(jié)構(gòu)得到以下兩個序列：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〕能得到輸出順序?yàn)?,3,5,4,2,6的序列.得到的操作如下：1入棧后即出棧,得到序列1;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.假設(shè)正讀和反讀都相同的字符序列為“回文",例如,‘a(chǎn)bba'和'abcba'是回文,'abcde'和‘a(chǎn)babab'那么不是回文.假設(shè)一字符序列已存入計(jì)算機(jī),請用堆棧判斷其是否為回文,簡述算法.答：方法一：使用數(shù)據(jù)結(jié)構(gòu)：循環(huán)隊(duì)列和順序棧.算法思路為：.將字符串根據(jù)用戶輸入的順序分別入棧和隊(duì)列.分別從隊(duì)列和棧中取出首個字符.比較取出的字符,假設(shè)相等,繼續(xù)分別從隊(duì)列和棧中取首個字符；否那么跳出循環(huán),并設(shè)置標(biāo)志flag=0;.假設(shè)隊(duì)列和棧中的字符都取完,那么結(jié)束,設(shè)置標(biāo)志flag=1;.flag=1,表示字符從前往后和從后往前的序列完全匹配,該字符串屬于回文.flag=0,表示字符從前往后和從后往前的序列不完全匹配,該字符串不屬于回文方法二：使用棧.將字符串的前一半入棧,再依次出棧,與后一半進(jìn)行比較,假設(shè)有不等那么不是回文；假設(shè)依次相等,那么是回文.注意：此題要求簡答算法思路,并不要求寫出具體算法.TOC\o"1-5"\h\z.試寫出循環(huán)隊(duì)列判空和判滿的條件〔隊(duì)列最大容量為M〕.答：假設(shè)循環(huán)隊(duì)列最大存儲容量為M判空：Q.front==Q.rear〔1〕判滿：〔Q.rear+1〕%M==Q.front〔2〕評分標(biāo)準(zhǔn)：給出〔1〕和〔2〕式分別得3分,其他酌情扣分..假設(shè)Q[0..10]是一個循環(huán)隊(duì)列,初始狀態(tài)為front=rear=0,畫出做完以下操作后隊(duì)列的頭尾指針的狀態(tài)變化情況,假設(shè)不能入隊(duì),請指出其元素,并說明理由.d,e,b,g,h入隊(duì)；d,e出隊(duì)；i,j,k,l,m入隊(duì)；n,o,p入隊(duì)答：〔圖自己根據(jù)解答畫出〕d,e,b,g,h入隊(duì)；狀態(tài)1:front=0,rear=5;

d,e出隊(duì)；狀態(tài)2：front=2,rear=5;i,j,k,l,m入隊(duì)；狀態(tài)3:front=2,rear=10;n,o,p入隊(duì)；狀態(tài)4：front=2,rear=1;p不能入隊(duì),由于隊(duì)列已經(jīng)滿了.評分標(biāo)準(zhǔn)：狀態(tài)1、狀態(tài)4各2分,狀態(tài)2、狀態(tài)3各1分,狀態(tài)4中狀態(tài)1分,理由1分..假設(shè)元素的進(jìn)棧序列為：A、B、C、D、E,運(yùn)用棧操作,能否得到出棧序列B、C、A、E、D和D、B、A、C、E?為什么答：能得到出棧序列B、C、A、E、D,不能得到出棧序列D、B、A、C、E.其理由為：假設(shè)出棧序列以D開頭,說明在D之前的入棧元素是A、B和C,三個元素中C是棧頂元素,B和A不可能早于C出棧,故不可能得到D、B、A、C、E出棧序列.設(shè)輸入序列為a,b,c,d,試寫出借助一個棧可得到的兩個輸出序列和兩個不能得到的輸出序列.答：借助棧結(jié)構(gòu),n個入棧元素可得到1/(n+1)((2n)!/(n!*n!))種出棧序列.此題4個元素,可有14種出棧序列,abcd和dcba就是其中兩種.但dabc和adbc是不可能得到的兩種.將兩個棧存入數(shù)組V[1..m]應(yīng)如何安排最好這時棧空、棧滿的條件是什么答：設(shè)棧S1和棧S2共享向量V[1..m],初始時,棧S1的棧頂指針top[0]=0,棧S2的棧頂指針top[1]=m+1,當(dāng)top[0]=0為左棧空,top[1]=m+1為右棧空；當(dāng)top[0]=0并且top[1]=m+1時為全棧空.當(dāng)top[1]-top[0]=1時為棧滿.如果輸入序列為123456,試問能否通過棧結(jié)構(gòu)得到以下兩個序列:435612和135426;請說明為什么不能或如何才能得到.答：輸入序列為123456,不能得出435612,其理由是,輸出序列最后兩元素是12,前面4個元素(4356)得到后,棧中元素剩12,且2在棧頂,不可能棧底元素1在棧頂元素2之前出棧.得到135426的過程如下：1入棧并出棧,得到局部輸出序列1;然后2和3入棧,3出棧,局部輸出序列變?yōu)椋?3;接著4和5入棧,5,4和2依次出棧,局部輸出序列變?yōu)?3542;最后6入棧并退棧,彳#最終結(jié)果135426..假設(shè)以數(shù)組sq[0..7]存放循環(huán)隊(duì)列元素,變量f指向隊(duì)頭元素的前一位置,變量r指向隊(duì)尾元素,如用A和D分別表示入隊(duì)和出隊(duì)操作,請給出:(1)隊(duì)空的初始條件;(2)執(zhí)行操作序列A3D1A5D2A1D2A4時的狀態(tài),并作必要的說明.(A3表示三次入隊(duì)操作,D1表示一次出隊(duì)操作)答：答：(1)隊(duì)空的初始條件：(2)執(zhí)行操作A3后,f=0,執(zhí)行操作D1后,f=1,執(zhí)行操作A5后,f=1,執(zhí)行操作D2后,f=3,執(zhí)行操作A1后,f=3,執(zhí)行操作D2后,f=5,f=r=0;r=3;//A3表示三次入隊(duì)操作r=3;//D1表示一次出隊(duì)操作r=0;r=0;r=1;r=1;執(zhí)行操作A4后,按溢出處理.由于執(zhí)行A3后,r=4,這時隊(duì)滿,假設(shè)再執(zhí)行A操作,那么出錯..內(nèi)存中一片連續(xù)空間(不妨假設(shè)地址從1到m)提供給兩個棧si和S2使用,怎樣分配這局部存儲空間,使得對任一個棧,僅當(dāng)這局部空間全滿時才發(fā)生上溢1答：S1和S2共享內(nèi)存中一片連續(xù)空間(地址1到城,可以將S1和S2的棧底設(shè)在兩端,兩棧頂向共享空間的中央延伸,僅當(dāng)兩棧頂指針相鄰(兩棧頂指針值之差的絕對值等于1)時,判斷為棧滿,當(dāng)一個棧頂指針為0,另一個棧頂指針m+1時為兩棧均空.12,設(shè)一數(shù)列的輸入順序?yàn)?23456,假設(shè)采用堆棧結(jié)構(gòu),并以A和D分別表示入棧和出棧操作,試問通過入出棧操作的合法序列.(1)能否得到輸出順序?yàn)?25641的序列.(2)能否得到輸出順序?yàn)?54623的序列.答：(1)能得到325641.在123依次進(jìn)棧后,3和2出棧,得局部輸出序列32;然后4,5入棧,5出棧,得局部出棧序列325;6入棧并出棧,得局部輸出序列3256;最后退棧,直到棧空.得輸出序列325641.其操作序列為AAADDAADADDD(2)不能得到輸出順序?yàn)?54623的序列.局部合法操作序列為ADAAAADDAD導(dǎo)到局部輸出序列1546后,棧中元素為23,3在棧頂,故不可能2先出棧,得不到輸出序列154623.13,設(shè)輸入序列為2,3,4,5,6,利用一個棧能得到序列2,5,3,4,6嗎為什么棧可以用單鏈表實(shí)現(xiàn)嗎答：不能得到序列2,5,3,4,6；其理由是,輸出序列第三四位兩元素是3,4,前面2個元素(2,5)得到后,棧中元素剩3,4,且4在棧頂,棧底元素3不可能在棧頂元素4之前出棧.棧可以用單鏈表實(shí)現(xiàn),這就是鏈棧.由于棧只在棧頂操作,所以鏈棧通常不設(shè)頭結(jié)點(diǎn).14,有5個元素,其入棧次序?yàn)椋篈,B,C,D,E,在各種可能的出棧次序中,以元素C,D最先出棧(即C第一個且D第二個出棧)的次序有哪幾個用S表示入棧,X表示出棧,寫出可能得到次序的操作序列.答：三個：CDEBACDBEACDBAECDEB斕作序歹U:SSSXSXSXXXCDBE斕作序歹U:SSSXSXXSXXCDBA映作序歹U:SSSXSXXXSX15.假設(shè)以1、2、3、4作為雙端隊(duì)列的輸入序列,試分別求出以下條件的輸出序列：(1)能由輸入受限的雙端隊(duì)列得到,但不能由輸出受限的雙端隊(duì)列得到的輸出序列；(2)能由輸出受限的雙端隊(duì)列得到,但不能由輸入受限的雙端隊(duì)列得到的輸出序列；(3)既不能由輸入受限的雙端隊(duì)列得到,也不能由輸出受限的雙端隊(duì)列得到的輸出序列.答：(1)4132(2)4213(3)423116,設(shè)一個雙端隊(duì)列,元素進(jìn)入該隊(duì)列的次序?yàn)閍,b,c,do求既不能由輸入受限的雙端隊(duì)列得到,又不能由輸出受限的雙端隊(duì)列得到的輸出序列.答：既不能由輸入受限的雙端隊(duì)列得到,也不能由輸出受限的雙端隊(duì)列得到的輸出序列是dbca.第6章樹和二叉樹(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))畫出這棵樹,并答復(fù)以下問題：(1)樹根是哪個結(jié)點(diǎn)哪些是葉子結(jié)點(diǎn)哪些是非終端結(jié)點(diǎn)(2)樹的度是多少各個結(jié)點(diǎn)的度是多少(3)樹的深度是多少各個結(jié)點(diǎn)的層數(shù)是多少以結(jié)點(diǎn)G為根的子樹的深度是多少X72,用一維數(shù)組存放的一棵完全二叉樹如下表所示ABCDEFGHIJKL寫出先序、中序、后序、層次遍歷該二叉樹時訪問結(jié)點(diǎn)的順序.答案HIDJKEBLFGCAX23.(5分)對任何一棵二叉樹T,如果其終端結(jié)點(diǎn)數(shù)為n.,度為2的結(jié)點(diǎn)數(shù)為止,證實(shí):nc=n2+1oX34.表達(dá)并證實(shí)二叉樹的性質(zhì)3.X35.(8分)一棵二叉樹如下,(1)請分別寫出按前序、中序、后序和層次遍歷時得到的結(jié)點(diǎn)序列.(2)如果此二叉樹由森林轉(zhuǎn)換得到,請畫出原森林中的各棵樹.

IIX1X56.〔8分〕畫出由以下序列得到的二叉樹以及由此二叉樹轉(zhuǎn)化的森林：先序：EBADCFHGIKJ中序：ABCDEFGHIJKX87.有二叉樹中序序列為：ABCEFGHD后序序列為：ABFHGEDC請畫出此二叉樹,并寫出二叉樹的先序遍歷序列和層次遍歷序列.答案根據(jù)后序序列知根結(jié)點(diǎn)為C,因此左子樹：中序序列為AB后序序列為AB右子樹：中序序列為EFGHD,后序序列為：FHGED^次推得該二叉樹結(jié)構(gòu)如以下列圖所示先序遍先序遍歷序列:層次遍歷序列:CBADEGFHCBDAEGFHX58.〔8分〕二叉樹T的前序遍歷序列和中次遍歷序列分別是ABCDEFG口CBEDAFG試畫出該二叉樹,并寫出二叉樹的后序遍歷序列和層次遍歷序列.X99.〔6分〕二叉樹的先序序列為EBADCFHGI代J二叉樹的中序序列為ABCDEFGHIJK請畫出該二叉樹,并寫出二叉樹的后序遍歷序列和層次遍歷序列.X1010.〔8分〕設(shè)一棵二叉樹的先序、中序遍歷序列分別為先序遍歷序列：ABDFCEGH中序遍歷序列：BFDAGEHC請畫出該二叉樹,并將這棵二叉樹轉(zhuǎn)換成對應(yīng)的樹〔或森林〕X411.〔8分〕設(shè)一棵二叉樹的前序序列為叉樹.并寫出后序和層次遍歷序列.12.〔6分〕設(shè)給定一個權(quán)值集合W=〔3,哈夫曼樹并計(jì)算哈夫曼樹的帶權(quán)路徑長度X613.〔8分〕假設(shè)字符a,b,c,d,e,f,g,hABDGECFH中序序歹U為：DGBEAFHC試畫出該二5,7,9,11〕,要求根據(jù)給定的權(quán)值集合構(gòu)造一棵WPL.的使用頻度分別是00.15,0.19,0.07,0.08,0.04,0.23Huffman〔哈夫曼〕編碼.X514.〔8分〕假設(shè)字符a,b,c,d,e,fa,b,c,d,e,f的Huffman〔哈夫曼〕X715.〔8分〕假設(shè)字符a,b,c,d,e,f構(gòu)造哈夫曼樹并寫出a,b,c,d,e,f,0.13,0.11畫出哈夫曼樹并寫出a,b,c,d,e,f,g,h的的使用頻度分0.07,0.09,0.12,0.22,0.23,0.27編碼.的使用頻度分另I」是0.07,0.10,0.12,0.16,0.25,0.30的哈夫曼編碼.16.〔6分〕試分別畫出具有三個結(jié)點(diǎn)的樹和三個結(jié)點(diǎn)的二叉樹的不同形態(tài).X617.請畫出以下列圖所示的樹所對應(yīng)的二叉樹.0s答案：(6分)請畫出與以下二叉樹對應(yīng)的森林.X10X819.一棵樹邊的集合為{<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>},請答復(fù)以下問題：x10(1)哪個是根結(jié)點(diǎn)(2)X8哪些是葉子結(jié)點(diǎn)X10哪些是分支結(jié)點(diǎn)X8(3)哪個是結(jié)點(diǎn)G的雙親結(jié)點(diǎn)(4)哪些是結(jié)點(diǎn)G的祖先X8(5)哪些是結(jié)點(diǎn)G的孩子X8(6)哪些是結(jié)點(diǎn)E的子孫X8(7)哪些是結(jié)點(diǎn)E的兄弟哪些是結(jié)點(diǎn)F的兄弟(8)結(jié)點(diǎn)B和N的層次號分別是多少(9)樹的深度是多少(10)以結(jié)點(diǎn)C為根的子樹的深度是多少答案(1)A;(2)D,M,N,F,J,K,L;(3)C;(4)A,C;(5)J,K;(6)I,M,N;⑺E的兄弟是D,F的兄弟是G和H;(8)2,5;(9)5;(10)3.X920.假設(shè)在樹中,結(jié)點(diǎn)x是結(jié)點(diǎn)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)}.用樹形表示法畫出此樹,并答復(fù)以下問題：(1)哪個是根結(jié)點(diǎn)：(2)哪些是葉結(jié)點(diǎn)(3)哪個是g的雙親(4)哪些是g的祖先(5)哪些是g的孩子(6)哪些是e的子孫(7)哪些是e的兄弟哪些是f的兄弟(8)結(jié)點(diǎn)b和n的層次各是多少(9)樹的深度是多少(10)以結(jié)點(diǎn)c為根的子樹的深度是多少(11)樹的度數(shù)是多少青案：□(1)根結(jié)點(diǎn)：a(2)葉結(jié)點(diǎn)：rnn、d、l、h、j、k(3)g的雙親：c(4)g的祖先：a、c(5)g的孩子：j、k(6)e的子孫：i、mrn(7)e的兄弟：d(8)b的層次：2(9)樹的深度：5f的兄弟：g、hn的層次；5

(10)以結(jié)點(diǎn)c為根的子樹的深度：21.一棵樹邊的結(jié)點(diǎn)為(I,M),K),(A,G),(A,F),(H,J),(A,(1)哪個是根結(jié)點(diǎn)(2)哪些是葉子結(jié)點(diǎn)(3)樹的深度是多少答案如以下列圖所示.(圖不對,缺結(jié)點(diǎn)3(11)樹的度數(shù)：3(I,N),(E,I),(B3(11)樹的度數(shù)：3(I,N),(E,I),(B,E),(B,D),(C,B),(G,L),(G,H),(C,A)},試畫出這棵樹,并答復(fù)以下問題：H的孩子結(jié)點(diǎn)J,)五、應(yīng)用題(每題6分,共48分)3.答：快速排序的思想：通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩局部,其中一局部記錄的關(guān)鍵字均比另一局部記錄的關(guān)鍵字小,那么可分別對這兩局部記錄繼續(xù)進(jìn)行排序,以到達(dá)整個序列有序.評分標(biāo)準(zhǔn)：只要根本思想對就可得分.3、(8分)二叉樹為：后序遍歷序列：CEDBGFA,層次遍歷序列：ABFCDGE評分標(biāo)準(zhǔn)：得出二叉樹得4分,給出后序和層次遍歷序列得4分,步驟不全酌情給分.4、(8分)哈夫曼樹：

哈夫曼編碼:a：01哈夫曼編碼:a：011e：0001b：f：1011評分標(biāo)準(zhǔn)：得出哈夫曼樹給5、〔10分〕〔1〕鄰接表存儲結(jié)構(gòu)c：00000g：0014分,給出哈夫曼編碼給d：0010h：01014分,步驟不全酌情給分.〔2〕深度優(yōu)先遍歷序列：BADCEF廣度優(yōu)先遍歷序列：BACEDF評分標(biāo)準(zhǔn)：畫出鄰接表存儲結(jié)構(gòu)得他情況全酌情給分.6、〔8分〕二叉判定樹5分,求出深度優(yōu)先和廣度優(yōu)先遍歷序列得平均查找長度:ASL=(1+2*2+4*3+3*4)/10平均查找長度:評分標(biāo)準(zhǔn)：得出二叉判定樹給6分,求出平均查找長度給2分,步驟不全酌情給分.以達(dá)2、〔6分〕快速排序的思想：通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩局部,其中一局部記錄的關(guān)鍵字均比另一局部記錄的關(guān)鍵字小,那么可分別對這兩局部記錄繼續(xù)進(jìn)行排序,到整個序列有序以達(dá)評分標(biāo)準(zhǔn)：只要根本思想對就可得分.3、〔8分〕二叉樹為：

后序遍歷序列：CEDBGFA后序遍歷序列：CEDBGFA,層次遍歷序列:ABFCDGE評分標(biāo)準(zhǔn)：得出二叉樹得4分,4、〔4分,步驟不全酌情給分.給出后序和層次遍歷序列得哈夫曼編碼:a：011e：0001b:f:1011評分標(biāo)準(zhǔn)：得出哈夫曼樹給5、〔10分〕〔1〕鄰接表存儲結(jié)構(gòu)c：00000g：0014分,給出哈夫曼編碼給d：0010h：01014分,步驟不全酌情給分.〔2〕深度優(yōu)先遍歷序列：BADCEF廣度優(yōu)先遍歷序列：BACEDF評分標(biāo)準(zhǔn)：畫出鄰接表存儲結(jié)構(gòu)得5分,求出深度優(yōu)先和廣度優(yōu)先遍歷序列得5分,其他情況全酌情給分.6、〔8分〕二叉判定樹3812725204538127252045901003260平均查找長度:ASL=(1+2*2+4*3+3*4)/10平均查找長度:評分標(biāo)準(zhǔn)：得出二叉判定樹給6分,求出平均查找長度給2分,步驟不全酌情給分.四、算法題〔22分〕1、〔6分〕評分標(biāo)準(zhǔn)：每寫錯一種形態(tài)扣1分.2、〔8分〕(1)前序：ABDGCEFH中序：DGBAECHF后序：GDBEHFCA層次：ABCDEFGH(2)二叉樹所對應(yīng)的森林：評分標(biāo)準(zhǔn)：第一小評分標(biāo)準(zhǔn)：第一小題每個1分,第二小題三棵樹4分,每錯一個扣1分.評分標(biāo)準(zhǔn)：沒有過程或過程不全酌情減分4、(8分)評分標(biāo)準(zhǔn)：結(jié)果正確得5分,步驟不全酌情扣分.5、(10分)(1)(4分)哈希表:012345678910111213141516173217634924401030314647(2)(4分)假設(shè)查找關(guān)鍵字63,需要與關(guān)鍵字31、16、47、32、17進(jìn)行比較.(2分)平均查找長度：ASLc=(6*1+2+3*3+6)/11=23/116、(8分)2548126520(2536)48126520(253648)126520(12253648)6520(1225364865)20(122025364865)評分標(biāo)準(zhǔn)：每一趟插入得1分,步驟不全酌情扣分.三、應(yīng)用題(43分)1、(6分)對任何一棵二叉樹,如果其終端結(jié)點(diǎn)數(shù)為n.,度為2的結(jié)點(diǎn)數(shù)為n2,那么怵=m+1.證實(shí)：設(shè)二叉樹白^結(jié)點(diǎn)總數(shù)為n,度為1的結(jié)點(diǎn)個數(shù)為nb那么有：TOC\o"1-5"\h\z\o"CurrentDocument"n=n0+m+n2(1)又在二叉樹中除了根結(jié)點(diǎn)每個結(jié)點(diǎn)都有一個分支指向它,這些分支是有度為1和度為2的結(jié)點(diǎn)發(fā)出的,由此得到：\o"CurrentDocument"n-1=n1+2*n2(2)由式(1)和(2)得n0=n2+1,證畢.評分標(biāo)準(zhǔn)：表達(dá)定理得2分,證實(shí)得4分,其他酌情扣分.2、(8分)哈夫曼樹為：評分標(biāo)評分標(biāo)準(zhǔn)：得出哈夫曼樹給4分,給出哈夫曼編碼給4分,步驟不全酌情給分.由此可得哈夫曼編碼分別為：a：000b：001c：100d：101e：01f:113、(8分)二叉排序樹的構(gòu)造過程如下:451212323220127512323202083250832202025125平均查找長度：ASL=(1+2*2+4*3+2*4+5)■^5^751275,283220節(jié)25石45751275509083250902064⑧5分/10=33分評分標(biāo)準(zhǔn)：得出二叉判定樹給54、〔7分〕拓?fù)湫蛄袠?gòu)造過程B輸出A,DEE〕—/、亭1c輸出C〔D——-E——拓?fù)溆行蛐蛄泻髢煞N：ABCDEF評分標(biāo)準(zhǔn)：只有結(jié)果沒有過程給5、〔8分〕鄰接矩陣為,010001<0分,求出平均查找長度給3分,步驟不全酌情給分.~F〕輸出BD<E：\F\___Z9「F輸出Di；E——-F和ACBDEF5分,過程不全或過程/、止確酌情扣分.100010、010010101111010100011000110000010100」最小生成樹為:3分,過程評分標(biāo)準(zhǔn)：寫出鄰接矩陣給3分,最小生成樹給5分,只有結(jié)果沒有過程給不全或過程不正確酌3分,過程6、〔6分〕快速排序的思想：通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩局部,其中一局部記錄的關(guān)鍵字均比另一局部記錄的關(guān)鍵字小,那么可分別對這兩局部記錄繼續(xù)進(jìn)行排序,以達(dá)到整個序列有序.一趟快速排序的結(jié)果：40,38,27,20,13,49,76,80,65評分標(biāo)準(zhǔn)：寫出快速排序思想給3分,給出一趟排序結(jié)果給3分.四、算法題〔22分〕三、應(yīng)用題〔43分〕1、〔6分〕3分C

3分C評分標(biāo)準(zhǔn):2、〔8分〕3分.平均查找長度:構(gòu)造評分標(biāo)準(zhǔn):2、〔8分〕3分.平均查找長度:構(gòu)造出二叉樹得3分,二叉樹的生成森林得ASL=(5分分評分標(biāo)準(zhǔn):得出二叉判定樹給步驟不全酌情給分.3、〔7分〕鄰接矩陣:金1O08002001Q05Q0Q0Q0Q0O05od3867O0Q03Q08Q0Q0od00od88832Q06Q0Q0Q0Q0007Q03Q0Q0求出平均查找長度給2分,3分或abchedf或afbcdheabcfhedafbchde或abcfdeh或或abfchde或深度優(yōu)先序列:廣度優(yōu)先序列:abcdehf

abfcdhe〔不唯一〕〔不唯一〕評分標(biāo)準(zhǔn):寫出圖的鄰接矩陣的2分,深度優(yōu)先序列得2分,廣度優(yōu)先序列得2分,其他酌情給分.4、〔8分〕最短路徑:終點(diǎn)12345B6(A,B)4(A,C,B)C2(A,C)Doo5(A,C,D)5(A,C,D)Eoo6(A,C,E)6(A,C,E)6(A,C,E)Foooooo8(A,C,D,F)8(A,C,D,F)S{A}{A,C}{A,C,B}{A,C,B,D}{A,B,C,D,E}評分標(biāo)準(zhǔn)：最短路徑給5分,過程給3分,結(jié)果正確沒有過程或過程不對酌情減分.5、〔8分〕哈希表:01234567891011121401682755192084231110平均查找長度：ASbc=〔6*1+2+3*3+4〕/11=21/11評分標(biāo)準(zhǔn)：寫出哈希表得5分,查找長度3分6、〔5分〕〔1〕是大頂堆〔2〕不是堆,調(diào)整以后為100,98,66,85,80,60,40,77,82,10,20〔3〕是小頂堆評分標(biāo)準(zhǔn)：判斷正確得3分,調(diào)整得3分四、算法題〔22分〕1、〔5分〕假設(shè)循環(huán)隊(duì)列最大存儲容量為MTOC\o"1-5"\h\z判空：Q.front==Q.rear〔1〕判滿：〔Q.rear+1〕%M==Q.front〔2〕評分標(biāo)準(zhǔn)：給出〔1〕和〔2〕式分別得2分,前提假設(shè)得1分,其他酌情扣分.2、〔5分〕對任何一棵二叉樹,如果其終端結(jié)點(diǎn)數(shù)為n.,度為2的結(jié)點(diǎn)數(shù)為n2,那么怵=m+1.證實(shí)：設(shè)二叉樹白^結(jié)點(diǎn)總數(shù)為n,度為1的結(jié)點(diǎn)個數(shù)為m,那么有：n=n0+m+n2〔1〕又在二叉樹中除了根結(jié)點(diǎn)每個結(jié)點(diǎn)都有一個分支指向它,這些分支是有度為1和度為2的結(jié)點(diǎn)發(fā)出的,由此得到：n-1=n1+2*n2〔2〕由式〔1〕和〔2〕得n0=n2+1,證畢.評分標(biāo)準(zhǔn)：給出〔1〕和〔2〕式分別得2分,得出結(jié)論得1分,其他酌情扣分.3、〔7分〕哈夫曼樹為：由此可得哈夫曼編碼分別為：a：000b：001c：100d：101e：01f:11評分標(biāo)準(zhǔn)：得出哈夫曼樹給4分,給出哈夫曼編碼給3分,步驟不全酌情給分.4、〔8分〕二叉排序樹：

JanFebMarAprJunMaySepJanFebMarAprJunMaySepAugJulOctDecNovASL=(1+2*2+3*3+4*3+5*2+6)/12=3.5評分標(biāo)準(zhǔn)：構(gòu)造出二叉排序樹得5分,平均查找長度得3分,步驟不全酌情扣分.5、〔7分〕由C開始的深度優(yōu)先生成序列：CDEABF評分標(biāo)準(zhǔn)：畫出原圖得4分,求出深度優(yōu)先生成序列得3分,其他情況酌情給分.6、〔8分〕最短路徑求解過程：終點(diǎn)12345B6(A,B)4(A,C,B)C2(A,C)Doo5(A,C,D)5(A,C,D)Eoo6(A,C,E)6(A,C,E)6(A,C,E)Foooooo8(A,C,D,F)8(A,C,D,F)S{A}{A,C}{A,C,B}{A,C,B,D}{A,B,C,D,E}評分標(biāo)準(zhǔn)：結(jié)果正確沒有過程得5分,步驟不全或不正確酌情扣分.五、算法題〔共20分〕1、〔5分〕評分標(biāo)準(zhǔn)：每寫對一種形態(tài)得1分.以達(dá)2、〔5分〕快速排序的思想：通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩局部,其中一局部記錄的關(guān)鍵字均比另一局部記錄的關(guān)鍵字小,那么可分別對這兩局部記錄繼續(xù)進(jìn)行排序,到整個序列有序以達(dá)評分標(biāo)準(zhǔn)：只要根本思想對就可得分.3、〔7分〕(1)前序：ABDGCEFH中序：DGBAECHF后序：GDBEHFCA層次：ABCDEFGH〔2〕二叉樹所對應(yīng)的森林:評分評分標(biāo)準(zhǔn)：第一小題每個1分,第二小題三棵樹,每個1分.4、〔8分〕關(guān)鍵路徑為:求解過程:vevlell-eA00a1011B56ra2000C22a3055D611a4561E99Pa5220F1015a66115G1516a7990H1414a89101I2323a910155a1014140a1115161評分標(biāo)準(zhǔn)：結(jié)果正確沒有過程給5分,過程不全或過程不正確酌情扣分.5、〔8分〕最小生成樹為：

6、哈希表:01234567891011121401682755192084231110平均查找長度：ASLsc=〔6*1+2+3*3+4〕/11=21/11評分標(biāo)準(zhǔn)：寫出哈希表得5分,查找長度2分,其他情況酌情給分.五、算法題〔20分〕四、應(yīng)用題〔40分〕4分評分標(biāo)準(zhǔn)：構(gòu)造出二叉樹得4分,二叉樹的生成森林得4分.2、〔8分〕二叉排序樹的構(gòu)造過程如下：評分標(biāo)準(zhǔn)：沒有過程或過程不全酌情減分3、〔8分〕鄰接矩陣：

1odQ0Q02od、1OO500Q0Q000od5od3Q06700003008Q0004分O0oOO08OOOO32Q06Q0Q0Q0Q0產(chǎn)oO7OO3OO深度優(yōu)先序列:廣度優(yōu)先序列:abcdehf或abchedf或abcfdeh或abc深度優(yōu)先序列:廣度優(yōu)先序列:abfcdhe或afbcdhe或abfchde或afbchde〔不唯一〕4分評分標(biāo)準(zhǔn)：寫出圖的鄰接矩陣的4分,深度優(yōu)先序列得2分,其他酌情給分.4、〔8分〕3.程不對酌情減分.4分,過程給4分,結(jié)果正確沒有過程或過5、〔8分〕哈希表:012345678911112322034510011240平均查找長度:ASLsc=〔7*1+2+3+3〕/10=1.5評分標(biāo)準(zhǔn)：寫出哈希表得5分,查找長度3分

1fde1c1baEFC評分標(biāo)準(zhǔn)：每寫錯一種形態(tài)扣1分.011、算1fde1c1baEFC評分標(biāo)準(zhǔn)：每寫錯一種形態(tài)扣1分.011、算法題〔20分〕應(yīng)用題〔40分〕〔5分〕0C為n2,那么n0=n2+1.評分標(biāo)準(zhǔn)：表達(dá)不恰當(dāng)酌情扣分.00100由此可得哈夫曼編碼分別為:a：0000b:0001c:001d：01e：10f：114、〔8分〕拓?fù)湫蛄袠?gòu)造過程n0,度為2的結(jié)點(diǎn)數(shù)3、〔8分〕哈夫曼樹為:評分標(biāo)準(zhǔn)：得出哈夫曼樹給酌情給分.4分,給出哈夫曼編碼給4分,步驟不全2、〔5分〕對任何一棵二叉樹,如果其終端結(jié)點(diǎn)數(shù)為輸出A輸出BDE—聲小一ZC輸出CD——：E,輸出DE——拓?fù)溆行蛐蛄泻髢煞N：ABCDEF評分標(biāo)準(zhǔn)：只有結(jié)果沒有過程給分.5、〔8分〕最小生成樹為：A：5J4E評分標(biāo)準(zhǔn)：只有結(jié)果沒有過程給分.X1-,FFF和ACBDEF5分,過程不全或過程/、止確酌情扣5CA1B5C3D父一5分,過程不全或過程/、止確酌情扣6、〔8分〕〔1〕由裝載因子0.7,數(shù)據(jù)總數(shù)7個,得一維數(shù)組大小為7/0,7=10儲空間長度為10,采用線性探測再散列法處理沖突,所構(gòu)造的散列表為：01234567893071411818.9..〔2〕查找成功的ASL=〔1+1+1+1+2+1+1〕/