...wd...wd...wd中國(guó)科學(xué)院大學(xué)歷年習(xí)題習(xí)題一復(fù)雜性分析初步1.試確定下述程序的執(zhí)行步數(shù)，該函數(shù)實(shí)現(xiàn)一個(gè)m×n矩陣與一個(gè)n×p矩陣之間的乘法：矩陣乘法運(yùn)算template<classT>voidMult(T**a,T**b,intm,intn,intp){//m×n矩陣a與n×p矩陣b相成得到m×p矩陣cfor(inti=0;i<m;i++)for(intj=0;j<p;j++){Tsum=0;for(intk=0;k<n;k++)Sum+=a[i][k]*b[k][j];C[i][j]=sum;}}語(yǔ)句s/e頻率總步數(shù)語(yǔ)句s/e頻率總步數(shù)template<classT>voidMult(T**a,T**b,intm,intn,intp)000{for(inti=0;i<m;i++)1m+1m+1for(intj=0;j<p;j++){1m*(p+1)m*p+mTsum=0;1m*pm*pfor(intk=0;k<n;k++)1m*p*(n+1)m*p*n+m*pSum+=a[i][k]*b[k][j];1m*p*nm*p*nC[i][j]=sum;1m*pm*p}}總計(jì)2*m*p*n+4*m*p+2*m+1其中s/e表示每次執(zhí)行該語(yǔ)句所要執(zhí)行的程序步數(shù)。頻率是指該語(yǔ)句總的執(zhí)行次數(shù)。2．函數(shù)MinMax用來(lái)查找數(shù)組a[0:n-1]中的最大元素和最小元素，以下給出兩個(gè)程序。令n為實(shí)例特征。試問(wèn)：在各個(gè)程序中，a中元素之間的對(duì)比次數(shù)在最壞情況下各是多少找最大最小元素方法一template<classT>boolMinMax(Ta[],intn,int&Min,int&Max){//尋找a[0:n-1]中的最小元素與最大元素//如果數(shù)組中的元素?cái)?shù)目小于1，那么還回falseif(n<1)returnfalse;Min=Max=0;//初始化for(inti=1;i<n;i++){if(a[Min]>a[i])Min=i;if(a[Max]<a[i])Max=i;}returntrue;}最好，最壞，平均對(duì)比次數(shù)都是2*〔n-1〕找最大最小元素方法二template<classT>boolMinMax(Ta[],intn,int&Min,int&Max){//尋找a[0:n-1]中的最小元素與最大元素//如果數(shù)組中的元素?cái)?shù)目小于1，那么還回falseif(n<1)returnfalse;Min=Max=0;//初始化for(inti=1;i<n;i++){if(a[Min]>a[i])Min=i;elseif(a[Max]<a[i])Max=i;}returntrue;}最壞2*〔n-1〕，最好n-1,平均3.證明以下不等式不成立：1).2).；4．證明：當(dāng)且僅當(dāng)時(shí)，。5.下面那些規(guī)那么是正確的為什么1).；錯(cuò)2).；錯(cuò)3).；錯(cuò)4).；錯(cuò)5).。錯(cuò)6).對(duì)6.按照漸進(jìn)階從低到高的順序排列以下表達(dá)式:順序：7.1)假設(shè)某算法在輸入規(guī)模是時(shí)為.在某臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)并完成該算法的時(shí)間是秒.現(xiàn)有另一臺(tái)計(jì)算機(jī),其運(yùn)行速度為第一臺(tái)的64倍,那么,在這臺(tái)計(jì)算機(jī)上用同一算法在秒內(nèi)能解決規(guī)模為多大的問(wèn)題?規(guī)模時(shí)間復(fù)雜度〔步數(shù)〕原運(yùn)行速度〔時(shí)間/每步〕總時(shí)間關(guān)系式為時(shí)間復(fù)雜度〔計(jì)算步數(shù)〕*運(yùn)行速度(時(shí)間/每步)=運(yùn)行所需時(shí)間，即解：設(shè)在新機(jī)器上秒內(nèi)能解決規(guī)模為的問(wèn)題，時(shí)間復(fù)雜度變?yōu)?，由于新機(jī)器運(yùn)行速度提高64倍，那么運(yùn)行速度變?yōu)椋申P(guān)系式，得，解得2)假設(shè)上述算法改良后，新算法的計(jì)算復(fù)雜度為,那么在新機(jī)器上用秒時(shí)間能解決輸入規(guī)模為多大的問(wèn)題設(shè)在新機(jī)器上用秒時(shí)間能解決輸入規(guī)模為的問(wèn)題，那么由于新復(fù)雜度，新機(jī)器的運(yùn)行速度為，代入關(guān)系式，得，解得3〕假設(shè)進(jìn)一步改良算法，最新的算法的時(shí)間復(fù)雜度為，其余條件不變，在新機(jī)器上運(yùn)行，在秒內(nèi)能夠解決輸入規(guī)模為多大的問(wèn)題設(shè)可解決的最大時(shí)間復(fù)雜度為，那么可解決的最大時(shí)間復(fù)雜度為，〔n為原始的輸入規(guī)?！?。因?yàn)?，且為常?shù)不隨輸入規(guī)模n變化，所以任意規(guī)模的n都可在t秒內(nèi)解決。8.Fibonacci數(shù)有遞推關(guān)系：試求出的表達(dá)式。解：方法一：當(dāng)時(shí)，由遞推公式得特征方程為解得，那么可設(shè)由，，解得，故，當(dāng)時(shí)，帶入驗(yàn)證亦成立。故方法二：也可直接推導(dǎo)可得可得，設(shè)，那么為等比數(shù)列，先求出，然后代入即可求得。第二章局部習(xí)題參考答案1.證明以下結(jié)論：1〕在一個(gè)無(wú)向圖中，如果每個(gè)頂點(diǎn)的度大于等于2，那么該該圖一定含有圈；2〕在一個(gè)有向圖D中，如果每個(gè)頂點(diǎn)的出度都大于等于1，那么該圖一定含有一個(gè)有向圈。1〕證明：設(shè)無(wú)向圖最長(zhǎng)的跡每個(gè)頂點(diǎn)度大于等于2，故存在與相異的點(diǎn)與相鄰，假設(shè)那么得到比更長(zhǎng)的跡，與P的取法矛盾。因此，，是閉跡，從而存在圈證明*：設(shè)在無(wú)向圖G中，有n個(gè)頂點(diǎn)，m條邊。由題意知，m>=(2n)/2=n，而一個(gè)含有n個(gè)頂點(diǎn)的樹(shù)有n-1條邊。因m>=n>n-1，故該圖一定含有圈?！捕x：跡是指邊不重復(fù)的途徑，而頂點(diǎn)不重復(fù)的途徑稱為路。起點(diǎn)和終點(diǎn)重合的途徑稱為閉途徑，起點(diǎn)和終點(diǎn)重合的跡稱為閉跡，頂點(diǎn)不重復(fù)的閉跡稱為圈。〕2〕證明：設(shè)有向圖最長(zhǎng)的有向跡每個(gè)頂點(diǎn)出度大于等于1，故存在為的出度連接點(diǎn)，使得成為一條有向邊，假設(shè)那么得到比更長(zhǎng)的有向跡，與P矛盾，因此必有，從而該圖一定含有有向圈。2.設(shè)D是至少有三個(gè)頂點(diǎn)的連通有向圖。如果D中包含有向的Euler環(huán)游〔即是通過(guò)D中每條有向邊恰好一次的閉跡〕，那么D中每一頂點(diǎn)的出度和入度相等。反之，如果D中每一頂點(diǎn)的出度與入度都相等，那么D一定包含有向的Euler環(huán)游。這兩個(gè)結(jié)論是正確的嗎請(qǐng)說(shuō)明理由。如果G是至少有三個(gè)頂點(diǎn)的無(wú)向圖，那么G包含Euler環(huán)游的條件是什么證明：1〕假設(shè)圖D中包含有向Euler環(huán)游，下證明每個(gè)頂點(diǎn)的入度和出度相等。如果該有向圖含有Euler環(huán)游，那么該環(huán)游必經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次，每經(jīng)過(guò)一次，必為“進(jìn)〞一次接著“出〞一次，從而入度等于出度。從而，對(duì)于任意頂點(diǎn)，不管該環(huán)游經(jīng)過(guò)該頂點(diǎn)多少次，必有入度等于出度。2〕假設(shè)圖D中每個(gè)頂點(diǎn)的入度和出度相等，那么該圖D包含Euler環(huán)游。證明如下。對(duì)頂點(diǎn)個(gè)數(shù)進(jìn)展歸納。當(dāng)頂點(diǎn)數(shù)|v(D)|=2時(shí)，因?yàn)槊總€(gè)點(diǎn)的入度和出度相等，易得構(gòu)成有向Euler環(huán)游。假設(shè)頂點(diǎn)數(shù)|v(D)|=k時(shí)結(jié)論成立，那么當(dāng)頂點(diǎn)數(shù)|v(D)|=k+1時(shí)，任取v∈v(D).設(shè)S={以v為終點(diǎn)的邊}，K={以v為始點(diǎn)的邊}，因?yàn)関的入度和出度相等，故S和K中邊數(shù)相等。記G=D-v.對(duì)G做如下操作:任取S和K中各一條邊，設(shè)在D中，，那么對(duì)G和S做如下操作,，重復(fù)此步驟直到S為空。這個(gè)過(guò)程最終得到的G有k個(gè)頂點(diǎn)，且每個(gè)頂點(diǎn)的度與在G中完全一樣。由歸納假設(shè)，G中存在有向Euler環(huán)游，設(shè)為C。在G中從任一點(diǎn)出發(fā)沿C的對(duì)應(yīng)邊前行，每當(dāng)遇到上述添加邊v1v2時(shí)，都用對(duì)應(yīng)的兩條邊e1，e2代替，這樣可以獲得有向Euler環(huán)游。3〕G是至少有三個(gè)頂點(diǎn)的無(wú)向圖，那么G包含Euler環(huán)游等價(jià)于G中無(wú)奇度頂點(diǎn)?！布慈我忭旤c(diǎn)的度為偶數(shù)〕。3．設(shè)G是具有n個(gè)頂點(diǎn)和m條邊的無(wú)向圖，如果G是連通的，而且滿足m=n-1,證明G是樹(shù)。證明：思路一：只需證明G中無(wú)圈。假設(shè)G中有圈，那么刪去圈上任一條邊G仍連通。而每個(gè)連通圖邊數(shù)e>=n(頂點(diǎn)數(shù))–1，但刪去一條邊后G中只有n-2條邊，此時(shí)不連通，從而矛盾，故G中無(wú)圈，所以G為樹(shù)。思路二：當(dāng)時(shí)，，兩個(gè)頂點(diǎn)一條邊且連通無(wú)環(huán)路，顯然是樹(shù)。設(shè)當(dāng)時(shí)，命題成立，那么當(dāng)時(shí)，因?yàn)镚連通且無(wú)環(huán)路，所以至少存在一個(gè)頂點(diǎn)，他的度數(shù)為1，設(shè)該頂點(diǎn)所關(guān)聯(lián)的邊為那么去掉頂點(diǎn)和，便得到了一個(gè)有k-1個(gè)頂點(diǎn)的連通無(wú)向無(wú)環(huán)路的子圖，且的邊數(shù)，頂點(diǎn)數(shù)。由于m=n-1,所以，由歸納假設(shè)知，是樹(shù)。由于相當(dāng)于在中為添加了一個(gè)子節(jié)點(diǎn)，所以G也是樹(shù)。由〔1〕，〔2〕原命題得證。4.假設(shè)用一個(gè)的數(shù)組來(lái)描述一個(gè)有向圖的鄰接矩陣，完成下面工作：1〕編寫(xiě)一個(gè)函數(shù)以確定頂點(diǎn)的出度，函數(shù)的復(fù)雜性應(yīng)為：2〕編寫(xiě)一個(gè)函數(shù)以確定圖中邊的數(shù)目，函數(shù)的復(fù)雜性應(yīng)為3〕編寫(xiě)一個(gè)函數(shù)刪除邊，并確定代碼的復(fù)雜性。解答：〔1〕鄰接矩陣表示為，待確定的頂點(diǎn)為第m個(gè)頂點(diǎn)intCountVout(int*a,intn,intm){intout=0;for(inti=0;i<n;i++)if(a[m-1][i]==1)out++;returnout;}〔2〕確定圖中邊的數(shù)目的函數(shù)如下：intEdgeNumber(int*a,intn){intnum=0;for(inti=0;i<n;i++)for(intj=0;j<n;j++)if(a[i][j]==1)num++;returnnum;}〔3〕刪除邊〔i,j〕的函數(shù)如下：voiddeleteEdge(int*a，inti,intj){if(a[i-1][j-1]==0)return;a[i-1][j-1]=0;return;}代碼的時(shí)間復(fù)雜性為Θ(1)5.實(shí)現(xiàn)圖的D-搜索算法，要求用SPARKS語(yǔ)言寫(xiě)出算法的偽代碼，或者用一種計(jì)算機(jī)高級(jí)語(yǔ)言寫(xiě)出程序。解:D搜索算法的根本思想是，用棧代替BFS中的隊(duì)列，先將起始頂點(diǎn)存入棧中，搜索時(shí)，取出棧頂?shù)脑?，遍歷搜索其相鄰接點(diǎn)，假設(shè)其鄰接點(diǎn)還未搜索，那么存入棧中并標(biāo)記，遍歷所有鄰接點(diǎn)后，取出此時(shí)棧頂?shù)脑剞D(zhuǎn)入下一輪遍歷搜索，直至棧變?yōu)榭諚?。ProcDBFS(v)//從頂點(diǎn)v開(kāi)場(chǎng)，數(shù)組visited標(biāo)示頂點(diǎn)被訪問(wèn)的順序；PushS(v,S);//首先訪問(wèn)v,將S初始化為只含有一個(gè)元素v的棧count:=count+1;visited[v]:=count;WhileS非空dou:=PullHead(S);count:=count+1;visited[w]:=count;//區(qū)別隊(duì)列先進(jìn)先出，此先進(jìn)后出for鄰接于u的所有頂點(diǎn)wdoifs[w]=0thenPushS(w,S);//將w存入棧Ss[w]:=1;end{if}end{for}end{while}end{DBFS}注：PushS(w,S)將w存入棧S;PullHead(S)為取出棧最上面的元素，并從棧中刪除ProcDBFT(G，m)//m為不連通分支數(shù)count:=0;計(jì)數(shù)器，標(biāo)示已經(jīng)被訪問(wèn)的頂點(diǎn)個(gè)數(shù)foritondos[i]:=0;//數(shù)組s用來(lái)標(biāo)示各頂點(diǎn)是否曾被搜索，是那么標(biāo)記為1，否那么標(biāo)記為0；end{for}foritomdo//遍歷不連通分支的情況ifs[i]=0thenDBFS(i);end{if}end{for}end{DBFT}6.下面的無(wú)向圖以鄰接鏈表存儲(chǔ)，而且在關(guān)于每個(gè)頂點(diǎn)的鏈表中與該頂點(diǎn)相鄰的頂點(diǎn)是按照字母順序排列的。試以此圖為例描述講義中算法DFNL的執(zhí)行過(guò)程。一個(gè)無(wú)向圖G一個(gè)無(wú)向圖GABEDGCF11234756111554A->B->E|0B->A->C|0C->B->D->E|0D->C|0E->A->C->F->G|0F->E->G|0G->E->F|0解：初始化數(shù)組DFN:=0，num=1；A為樹(shù)的根節(jié)點(diǎn),對(duì)A計(jì)算DFNL(A,null)，DFN(A)：=num=1;L(A)：=num=1;num:=1+1=2。從鄰接鏈表查到A的鄰接點(diǎn)B，因?yàn)镈FN(B)=0,對(duì)B計(jì)算DFNL(B,A)DFN(B)：=num=2;L(B)：=num=2;num：=2+1=3。查鄰接鏈表得到B的鄰接點(diǎn)A，因?yàn)镈FN(A)=10,但A=A,即是B的父節(jié)點(diǎn)，無(wú)操作。接著查找鄰接鏈表得到B的鄰接點(diǎn)C，因?yàn)镈FN(C)=0,對(duì)C計(jì)算DFNL(C,B)DFN(C)：=num=3;L(C)：=num=3;num:=3+1=4。查找C的鄰接點(diǎn)B，因?yàn)镈FN(B)=10,但B=B,即是C的父節(jié)點(diǎn)，無(wú)操作。接著查找鄰接鏈表得到C的鄰接點(diǎn)D，因?yàn)镈FN(D)=0,對(duì)D計(jì)算DFNL(D,C)，DFN(D)：=num=4;L(D)：=num=4;num:=4+1=5。查找得D鄰接點(diǎn)C，而DFN(C)=3≠0,但C=C，為D的父節(jié)點(diǎn)，L(D)保持不變。D的鄰接鏈表完畢，DFNL(D,C)的計(jì)算完畢。返回到D的父節(jié)點(diǎn)C，查找鄰接鏈表得到C的鄰接點(diǎn)E，因?yàn)镈FN(E)=0,對(duì)E計(jì)算DFNL(E,C),DFN(E)：=num=5;L(E)：=num=5;num:5+1=6;查找得E鄰接點(diǎn)A，因DFN(A)=1≠0，又A≠C，變換L(E)=min(L(E),DFN(A))=1。查找得E鄰接點(diǎn)C，因DFN(C)=3≠0，但C=C，無(wú)操作。查找得E鄰接點(diǎn)F，因DFN(F)=0，對(duì)F計(jì)算DFNL(F,E)，DFN(F)：=num=6;L(F)：=num=6;num:=6+1=7;查找得F鄰接點(diǎn)E，因DFN(E)=5≠0，但E=E，無(wú)操作。查找得F鄰接點(diǎn)G，因DFN(G)=0，對(duì)G計(jì)算DFNL(G,F)，DFN(G)：=num=7;L(G)：=num=7;num=7+1=8；查找G鄰接點(diǎn)E，因DFN(E)=5≠0，又E≠F，L(G)=min(L(G),DFN(E))=5查找得G鄰接點(diǎn)F,因DFN(F)=6≠0，但F=F，無(wú)操作。G的鄰接鏈表完畢，DFNL(G,F)的計(jì)算完畢。L(F)：=min(L(F)，L(G))=min(6,5)=5F的鄰接鏈表完畢，DFNL(F,E)的計(jì)算完畢。L(E):=min(L(E),L(F))=min(1,5)=1E鄰接鏈表完畢，DFNL(E,C)計(jì)算完畢。L(C):=min(L(C),L(E))=min(3,1)=1C的鄰接鏈表完畢，DFNL(C,B)計(jì)算完畢。L(B):=min(L(B),L(C))=min(2,1)=1查找B的鄰接鏈表完畢，DFNL(B,A)計(jì)算完畢。L(A):=min(L(A),L(B))=1查找得A的鄰接點(diǎn)E，因DFN(E)=0，又E≠null,那么L(A)=min(L(A),DFN(E))=1查找A的鄰接鏈表完畢，DFNL(A,null)計(jì)算完畢。最終結(jié)果為：深索數(shù)DFN，與最低深索數(shù)L如下DFN(A)=1，DFN(B)=2，DFN(C)=3，DFN(D)=4，DFN(E)=5，DFN(F)=6，DFN(G)=7L(A)=1;L(B)=1;L(C)=1;L(D)=4;L(E)=1;L(F)=5;L(G)=5.序節(jié)點(diǎn)DFNL棧頂—棧底2-連通割點(diǎn)1A1(1,0,0,0,0,0,0)(A,B)2B2(1,2,0,0,0,0,0)(B,C),(A,B)3C3(1,2,3,0,0,0,0)(C,D),(B,C),(A,B)4D4(1,2,3,4,0,0,0)(B,C),(A,B){(C,D)};C5E5(1,1,1,4,1,0,0)(E,F),(E,A),(B,C),(A,B)6F6(1,1,1,4,1,6,0)(F,G),(E,F),(E,A),(B,C),(A,B)7G7(1,1,1,4,1,5,5)(E,A),(B,C),(A,B){(G,E),(F,G),(E,F)}E8(1,1,1,4,1,5,5){(E,A),(B,C),(A,B)}附課本講義程序2-3-1對(duì)圖2-3-5的執(zhí)行過(guò)程開(kāi)場(chǎng)DFNL(A,*)DFN(A):=1;L(A):=1;num:=2;AABBBACBBCBADCBBCBAECBBCBAFCBBFCBAAFCBB∵DFN(B)=0,∴DFNL(B,A)DFN(B):=2;L(B):=2;num:=3;∵DFN(A)=10,但A=A,∴不做任何事情∵DFN(C)=0,∴DFNL(C,B)DFN(C):=3;L(C):=3;num:=4;∵DFN(B)=20,但B=B,∴不做任何事情∵DFN(D)=0,∴DFNL(D,C)DFN(D):=4;L(D):=4>DFN(C);num:=5;彈出〔C,D〕邊∵DFN(C)=30,但C=C,∴不做任何事情∵DFN(E)=0,∴DFNL(E,C)DFN(E):=5;L(E):=5>DFN(C);num:=6;彈出〔C,E〕邊∵DFN(C)=30,但C=C,∵DFN(F)=0,∴DFNL(F,C)DFN(F):=6;L(F):=6;num:=7;∵DFN(A)=10,AC,∴L(F):=min{6,1}=1;∵DFN(C)=30,但C=C,FFCBAFFCBAGAFCBBGFFCBAHGAFCBBGFFCBAIGAFCBBIGFFCBAFIGAFCBBIIGFFCBAJFIGAFCBBJIIGFFCBAFJFIGAFCBBJJIIGFFCBAGFJFIGAFCBB∵DFN(G)=0,∴DFNL(G,F)DFN(G):=7;L(G):=7;num:=8;∵DFN(F)=60,但F=F,∵DFN(H)=0,∴DFNL(H,G)DFN(H):=8;L(H):=8>DFN(G);num:=9;彈出〔G,H〕邊∵DFN(G)=70,但G=G,∵DFN(I)=0,∴DFNL(I,G)DFN(I):=9;L(I):=9;num:=10;∵DFN(F)=60,FG,∴L(I):=min{9,6}=6;∵DFN(G)=70,但G=G,∵DFN(J)=0,∴DFNL(J,I)DFN(J):=10;L(J):=10;num:=11;∵DFN(F)=60,FI,∴L(J):=min{10,6}=6;∵DFN(G)=70,GI,∴L(J):=min{6,7}=6;∵DFN(I)=90,但I(xiàn)=I,L(I):=min{6,6}=6;L(G):=min{7,6}=6DFN(F)彈出(J,G),(J,F),(I,J),(I,F),(G,I),(F,G)邊L(F):=min{1,6}=1;L(C):=min{3,1}=1;L(B):=min{2,1}=1DFN(A)彈出(F,A),(C,F),(B,C),(A,B)邊7對(duì)圖的另一種檢索方法是D-Search。該方法與BFS的不同之處在于將隊(duì)列換成棧，即下一個(gè)要檢測(cè)的結(jié)點(diǎn)是最新加到未檢測(cè)結(jié)點(diǎn)表的那個(gè)結(jié)點(diǎn)。1〕寫(xiě)一個(gè)D-Search算法；2〕證明由結(jié)點(diǎn)v開(kāi)場(chǎng)的D-Search能夠訪問(wèn)v可到達(dá)的所有結(jié)點(diǎn)；3〕你的算法的時(shí)、空復(fù)雜度是什么解：1〕同第5題，procDBFS(v)//寬度優(yōu)先搜索G，從頂點(diǎn)v開(kāi)場(chǎng)執(zhí)行，數(shù)組visited標(biāo)示各//頂點(diǎn)被訪問(wèn)的序數(shù)；數(shù)組s將用來(lái)標(biāo)示各頂點(diǎn)是否曾被放進(jìn)待檢查隊(duì)//列，是那么過(guò)標(biāo)記為1，否那么標(biāo)記為0；計(jì)數(shù)器count計(jì)數(shù)到目前為止已//經(jīng)被訪問(wèn)的頂點(diǎn)個(gè)數(shù)，其初始化為在v之前已經(jīng)被訪問(wèn)的頂點(diǎn)個(gè)數(shù)PushS(v,S);//將S初始化為只含有一個(gè)元素v的棧whileS非空dou:=PullHead(S);count:=count+1;visited[u]:=count;for鄰接于u的所有頂點(diǎn)wdoifs[w]=0thenPushS(w,S);//將w壓入棧中s[w]:=1;end{if}end{for}end{while}end{DBFS}圖的D—搜索算法偽代碼：procDBFT(G,ν)//count、s同DBFS中的說(shuō)明，branch是統(tǒng)計(jì)圖G的連通分支數(shù)count:=0;branch:=0;foritondos[i]:=0;//將所有的頂點(diǎn)標(biāo)記為未被訪問(wèn)end{for}foritoνdoifs[i]=0thenDBFS(i);branch:=branch+1;end{if}end{for}end{DBFT}2〕證明：除結(jié)點(diǎn)v外，只有當(dāng)結(jié)點(diǎn)w滿足s[w]=0時(shí)才被壓入棧中，因此每個(gè)結(jié)點(diǎn)至多有一次被壓入棧中，搜索不會(huì)出現(xiàn)重疊和死循環(huán)現(xiàn)象，對(duì)于每一個(gè)v可到達(dá)的節(jié)點(diǎn)，要么直接被訪問(wèn)，要么被壓入棧中，只有棧內(nèi)節(jié)點(diǎn)全部彈出被訪問(wèn)后，搜索才會(huì)完畢，所以由結(jié)點(diǎn)v開(kāi)場(chǎng)的D-Search能夠訪問(wèn)v可到達(dá)的所有結(jié)點(diǎn)。3〕：除結(jié)點(diǎn)v外，只有當(dāng)結(jié)點(diǎn)w滿足s[w]=0時(shí)才被壓入棧中，因此每個(gè)結(jié)點(diǎn)至多有一次被壓入棧中。需要的棧空間至多是ν-1；visited數(shù)組變量所需要的空間為ν；其余變量所用的空間為O(1)，所以s(ν,ε)=Θ(ν)。如果使用鄰接鏈表，for循環(huán)要做d(u)次，而while循環(huán)需要做ν次，又visited、s和count的賦值都需要ν次操作，因而t(ν，ε)=Θ(ν+ε)。如果采用鄰接矩陣，那么while循環(huán)總共需要做ν2次操作，visited、s和count的賦值都需要ν次操作，因而t(ν，ε)=Θ(ν2)。8.考慮下面這棵假想的對(duì)策樹(shù)：解：20206420548156203055084152051030592050186151055201〕使用最大最小方法(2-4-2)式獲取各結(jié)點(diǎn)的值maxmaxmaxminmin2〕22〕弈者A為獲勝應(yīng)該什么棋著20642054815620305508415205103059205018615105520XX1X2X3X4X1.1X1.2X2.1X2.2X3.1X3.2X4.1X4.2X1.1.1X1.1.2X1.1.3X1.2.1X2.1.1X2.2.1X3.1.1X3.1.2X1.1.1.1X3.1.2.1X3.2.1X3.2.2X3.2.3X4.1.1X4.2.1X4.4.2X4.2.3X4.2.4第三章分治算法習(xí)題1、編寫(xiě)程序?qū)崿F(xiàn)歸并算法和快速排序算法參見(jiàn)后附程序2、用長(zhǎng)為100、200、300、400、500、600、700、800、900、1000的10個(gè)數(shù)組的排列來(lái)統(tǒng)計(jì)這兩種算法的時(shí)間復(fù)雜性。有些同學(xué)用的微秒us用s可能需要把上面的長(zhǎng)度改為10000，……，100000，都可以大局部的結(jié)果是快速排序算法要比歸并算法快一些。3、討論歸并排序算法的空間復(fù)雜性。解析：歸并排序由分解與合并兩局部組成，如果用表示歸并排序所用的空間。那么由MergeSort(low,mid)//將第一子數(shù)組排序MergeSort(mid+1,high)//將第二子數(shù)組排序Merge(low,mid,high)//歸并兩個(gè)已經(jīng)排序的子數(shù)組那么遞歸推導(dǎo)得又由存儲(chǔ)數(shù)組長(zhǎng)度為，那么有因此，空間復(fù)雜度為。4、說(shuō)明算法PartSelect的時(shí)間復(fù)雜性為證明：提示：假定數(shù)組中的元素各不一樣，且第一次劃分時(shí)劃分元素是第小元素的概率為。因?yàn)镻artition中的case語(yǔ)句所要求的時(shí)間都是，所以，存在常數(shù)，使得算法PartSelect的平均時(shí)間復(fù)雜度可以表示為令取試證明。證明：令表示n個(gè)元素的數(shù)組A中尋找第k小元素的平均時(shí)間復(fù)雜度，因的時(shí)間復(fù)雜度是，故存在常數(shù)c，使得算法PartSelect的平均時(shí)間復(fù)雜度可以表示為令且不妨設(shè)等式在時(shí)成立，那么滿足以下用第二數(shù)學(xué)歸納法證明。取當(dāng)時(shí)，取cC/4,那么當(dāng)時(shí)，成立。對(duì)于一般的n，設(shè)對(duì)所有小于n的自然數(shù)成立，那么得證。證明：〔1〕當(dāng)時(shí)，假設(shè)數(shù)組A中元素互不一樣。由于每個(gè)具有7個(gè)元素的數(shù)組的中間值u是該數(shù)組中的第4小元素，因此數(shù)組中至少有4個(gè)元素不大于u，個(gè)中間值中至少有個(gè)不大于這些中間值的中間值v。因此，在數(shù)組A中至少有個(gè)元素不大于v。換句話說(shuō)，A中至多有個(gè)元素大于v。同理，至多有個(gè)元素小于v。這樣，以v為劃分元素，產(chǎn)生的新數(shù)組至多有個(gè)元素。當(dāng)時(shí)，。另一方面，在整個(gè)執(zhí)行過(guò)程中，遞歸調(diào)用Select函數(shù)一次，涉及規(guī)模為，而下一次循環(huán)Loop涉及的數(shù)組規(guī)模為。程序中其他執(zhí)行步的時(shí)間復(fù)雜度至多是n的倍數(shù)，用表示算法在數(shù)組長(zhǎng)度為n的時(shí)間復(fù)雜度，那么當(dāng)時(shí)，有遞歸關(guān)系用數(shù)學(xué)歸納法可以證明，。所以時(shí)間復(fù)雜度是。〔2〕當(dāng)時(shí)，使用上述方法進(jìn)展分析，可知在進(jìn)展劃分后數(shù)組A中有至多個(gè)元素。而遞歸關(guān)系為。假設(shè)通過(guò)歸納法證明出有的形式，用數(shù)學(xué)歸納法可以證明，。所以時(shí)間復(fù)雜度是。歸并排序的C++語(yǔ)言描述#include<iostream.h>template<classT>voidMergeSort(Ta[],intleft,intright);template<classT>voidMerge(Tc[],Td[],intl,intm,intr);template<classT>voidCopy(Ta[],Tb[],intl,intr);voidmain(){intconstn(5);inta[n];cout<<"Input"<<n<<"numbersplease:";for(inti=0;i<n;i++)cin>>a[i];//for(intj=0;j<n;j++)//b[j]=a[j];MergeSort(a,0,n-1);cout<<"Thesortedarrayis"<<endl;for(i=0;i<n;i++)cout<<a[i];cout<<endl;}template<classT>voidMergeSort(Ta[],intleft,intright)//{if(left<right){inti=(left+right)/2;T*b=newT[];MergeSort(a,left,i);MergeSort(a,i+1,right);Merge(a,b,left,i,right);Copy(a,b,left,right);}template<classT>voidMerge(Tc[],Td[],intl,intm,intr){inti=l;intj=m+1;intk=l;while((i<=m)&&(j<=r)){if(c[i]<=c[j])d[k++]=c[i++];elsed[k++]=c[j++];}if(i>m){for(intq=j;q<=r;q++)d[k++]=c[q];}elsefor(intq=i;q<=m;q++)d[k++]=c[q];}template<classT>voidCopy(Ta[],Tb[],intl,intr){for(inti=l;i<=r;i++)a[i]=b[i];}快速排序的C++語(yǔ)言描述#include<iostream.h>template<classT>voidQuickSort(Ta[],intp,intr);template<classT>intPartition(Ta[],intp,intr);voidmain(){intconstn(5);inta[n];cout<<"Input"<<n<<"numbersplease:";for(inti=0;i<n;i++)cin>>a[i];QuickSort(a,0,n-1);cout<<"Thesortedarrayis"<<endl;for(i=0;i<n;i++)cout<<a[i]<<"";cout<<endl;}template<classT>voidQuickSort(Ta[],intp,intr){if(p<r){intq=Partition(a,p,r);QuickSort(a,p,q-1);QuickSort(a,q+1,r);}}template<classT>intPartition(Ta[],intp,intr){inti=p,j=r+1;Tx=a[p];while(true){while(a[++i]<x);while(a[--j]>x);if(i>=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}template<classT>inlinevoidSwap(T&s,T&t){Ttemp=s;s=t;t=temp;}第四章作業(yè)局部參考答案設(shè)有個(gè)顧客同時(shí)等待一項(xiàng)服務(wù)。顧客需要的服務(wù)時(shí)間為。應(yīng)該若何安排個(gè)顧客的服務(wù)次序才能使總的等待時(shí)間到達(dá)最小總的等待時(shí)間是各顧客等待服務(wù)的時(shí)間的總和。試給出你的做法的理由〔證明〕。策略：對(duì)進(jìn)展排序，然后按照遞增順序依次服務(wù)即可。解析：設(shè)得到服務(wù)的顧客的順序?yàn)?，那么總等待時(shí)間為那么在總等待時(shí)間T中的權(quán)重最大，的權(quán)重最小。故讓所需時(shí)間少的顧客先得到服務(wù)可以減少總等待時(shí)間。證明：設(shè)，下證明當(dāng)按照不減順序依次服務(wù)時(shí)，為最優(yōu)策略。記按照次序服務(wù)時(shí)，等待時(shí)間為，下證明任意互換兩者的次序，都不減。即假設(shè)互換兩位顧客的次序，互換后等待總時(shí)間為，那么有由于那么有同理可證其它次序，都可以由經(jīng)過(guò)有限次兩兩調(diào)換順序后得到，而每次交換，總時(shí)間不減，從而為最優(yōu)策略。字符出現(xiàn)的頻率分布恰好是前8個(gè)Fibonacci數(shù)，它們的Huffman編碼是什么將結(jié)果推廣到個(gè)字符的頻率分布恰好是前個(gè)Fibonacci數(shù)的情形。Fibonacci數(shù)的定義為：解：前8個(gè)數(shù)為a，b，c，d，e，f，g，h1，1，2，3，5，8，13，21Huffman哈夫曼編碼樹(shù)為：5454h:21332012742g:13f:8e:5d:3C:2b:1a：101000000111111所以a的編碼為：1111111b的編碼為：1111110c的編碼為：111110d的編碼為：11110e的編碼為：1110f的編碼為：110g的編碼為：10h的編碼為：0推廣到n個(gè)字符：第1個(gè)字符：n-1個(gè)1，第2個(gè)字符：n-2個(gè)1，1個(gè)0，第3個(gè)字符：n-3個(gè)1，1個(gè)0，……第n-1個(gè)字符：1個(gè)1，1個(gè)0，10第n個(gè)字符：1個(gè)0，0設(shè)是準(zhǔn)備存放到長(zhǎng)為L(zhǎng)的磁帶上的n個(gè)程序，程序需要的帶長(zhǎng)為。設(shè)，要求選取一個(gè)能放在帶上的程序的最大子集合〔即其中含有最多個(gè)數(shù)的程序〕。構(gòu)造的一種貪心策略是按的非降次序?qū)⒊绦蛴?jì)入集合。1)證明這一策略總能找到最大子集，使得。2)設(shè)是使用上述貪心算法得到的子集合，磁帶的利用率可以小到何種程度3)試說(shuō)明1)中提到的設(shè)計(jì)謀略不一定得到使取最大值的子集合。證明：不妨設(shè)，假設(shè)該貪心策略構(gòu)造的子集合為，那么滿足。要證明能找到最大子集，只需說(shuō)明s為可包含的最多程序段數(shù)即可。即證不存在多于s個(gè)的程序集合，使得。反證法，假設(shè)存在多于s個(gè)的程序集，滿足。因?yàn)榉墙敌蚺帕?，那么。因?yàn)榍覟檎麛?shù)，那么其前s+1項(xiàng)滿足。這與貪心策略構(gòu)造的子集和中s滿足的矛盾。故假設(shè)不成立，得證。2〕磁帶的利用率為;〔甚至最小可為0，此時(shí)任意或者〕3)按照1〕的策略可以使磁帶上的程序數(shù)量最多，但程序的總長(zhǎng)度不一定是最大的，假設(shè)為Q的最大子集，但是假設(shè)用代替，仍滿足，那么為總長(zhǎng)度更優(yōu)子集。4.同學(xué)們的幾種不同答案構(gòu)造哈夫曼樹(shù)思想，將所有的節(jié)點(diǎn)放到一個(gè)隊(duì)列中，用一個(gè)節(jié)點(diǎn)替換兩個(gè)頻率最低的節(jié)點(diǎn)，新節(jié)點(diǎn)的頻率就是這兩個(gè)節(jié)點(diǎn)的頻率之和。這樣，新節(jié)點(diǎn)就是兩個(gè)被替換節(jié)點(diǎn)的父節(jié)點(diǎn)了。如此循環(huán)，直到隊(duì)列中只剩一個(gè)節(jié)點(diǎn)〔樹(shù)根〕。答案1〕偽代碼：typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;procHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)ifn<=1thenreturnHuffmanTreep;integers1,s2,i,m,start,c,f;char*cd;m:=2*n-1;HT[0].weight:=1000000;p:=HT+1;foritondo(*p).weight:=*w;(*p).parent:=(*p).lchild:=(*p).rchild:=0;++p;++w;end{for}foritomdo(*p).weight=(*p).parent=(*p).lchild=(*p).rchild=0;++p;end{for}forifromn+1tomdoSelect(HT,i-1,s1,s2);HT[s1].parent:=i;HT[s2].parent:=i;HT[i].lchild:=s1;HT[i].rchild:=s2;HT[i].weight:=HT[s1].weight+HT[s2].weight;end{for}cd[n-1]='\0';//編碼完畢符foritondostart:=n-1;//編碼完畢符位置f:=i;c:=i;forffromHT[f].parenttof=0doifHT[f].lchild=ccd[--start]:='0';elsecd[--start]:='1';end{else}end{if}end{for}end{for}end{HuffmanCoding}源代碼：#include<stdio.h>#include<stdlib.h>#include<string.h>#include<iostream>usingnamespacestd;#defineinfinite50000//定義Huffman樹(shù)和Huffman編碼的存儲(chǔ)表示typedefstruct{unsignedintweight;//字符的頻數(shù)unsignedintparent,lchild,rchild;//雙親結(jié)點(diǎn)，左孩子，右孩子}HTNode,*HuffmanTree;typedefchar**HuffmanCode;voidSelect(HuffmanTreeHT,intn,int&s1,int&s2);voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn);voidmain(){inti,n,*w;cout<<"enterthesizeofthecode:";cin>>n;cout<<endl;w=(int*)malloc((n+1)*sizeof(int));cout<<"entertheweightofthecode:"<<endl;for(i=1;i<=n;i++)//逐個(gè)輸入每個(gè)字符的出現(xiàn)的頻數(shù)，并用空格隔開(kāi)cin>>w[i];HuffmanTreeHT;HuffmanCodeHC;HuffmanCoding(HT,HC,w+1,n);cout<<"thehuffmancodeis:"<<endl;for(i=1;i<=n;i++){cout<<w[i]<<":";cout<<HC[i]<<"";}cout<<endl;system("pause");}//在HuffmanTree中HT[1…n]選擇parent為且weight最小的兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為s1和s2voidSelect(HuffmanTreeHT,intn,int&s1,int&s2){inti;s1=s2=0;for(i=1;i<=n;i++){if(HT[i].parent==0&&HT[s2].weight>HT[i].weight)s2=i;elseif(HT[i].parent==0&&HT[s1].weight>HT[i].weight)s1=i;}}//構(gòu)造Huffman樹(shù)HT，并求出n個(gè)字符的Huffman編碼HCvoidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){if(n<=1)return;HuffmanTreep;ints1,s2,i,m,start,c,f;char*cd;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));HT[0].weight=infinite;//將號(hào)單元置一個(gè)較大的數(shù)for(p=HT+1,i=1;i<=n;++i,++p,++w){(*p).weight=*w;//將n個(gè)字符的頻數(shù)送到HT.weight[1…n](*p).parent=(*p).lchild=(*p).rchild=0;//雙親孩子初始化為}for(;i<=m;++i,++p)(*p).weight=(*p).parent=(*p).lchild=(*p).rchild=0;//將HuffmanTree結(jié)點(diǎn)權(quán)值HT.weight[n+1…m+1]〔頻數(shù)〕及雙親孩子初始化為for(i=n+1;i<=m;++i)//根據(jù)Huffman編碼原理進(jìn)展構(gòu)建Huffman樹(shù){Select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}//從葉子到根逆向求每個(gè)字符的Huffman編碼HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n個(gè)字符編碼的頭指針向量，注號(hào)單元未用cd=(char*)malloc(n*sizeof(char));//分配求編碼的工作空間cd[n-1]='\0';//編碼完畢符for(i=1;i<=n;++i)//逐個(gè)字符求Huffman編碼{start=n-1;//編碼完畢符位置for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//從葉子到根逆向求編碼{if(HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';}HC[i]=(char*)malloc((n-start)*sizeof(char));//為第i個(gè)字符編碼分配空間strcpy_s(HC[i],sizeof(&cd[start]),&cd[start]);}free(cd);}答案2〕c語(yǔ)言實(shí)現(xiàn):huffman編碼解碼#include<stdio.h>#include<stdlib.h>#include<string.h>#defineN100#defineM2*N-1typedefchar*HuffmanCode[2*M];//haffman編碼typedefstruct{intweight;//權(quán)值intparent;//父節(jié)節(jié)點(diǎn)intLChild;//左子節(jié)點(diǎn)intRChild;//右子節(jié)點(diǎn)}HTNode,Huffman[M+1];//huffman樹(shù)typedefstructNode{intweight;//葉子結(jié)點(diǎn)的權(quán)值charc;//葉子結(jié)點(diǎn)intnum;//葉子結(jié)點(diǎn)的二進(jìn)制碼的長(zhǎng)度}WNode,WeightNode[N];/***產(chǎn)生葉子結(jié)點(diǎn)的字符和權(quán)值***/voidCreateWeight(charch[],int*s,WeightNodeCW,int*p){inti,j,k;inttag;*p=0;//葉子節(jié)點(diǎn)個(gè)數(shù)//統(tǒng)計(jì)字符出現(xiàn)個(gè)數(shù),放入CWfor(i=0;ch[i]!='\0';i++){tag=1;for(j=0;j<i;j++)if(ch[j]==ch[i]){tag=0;break;}if(tag){CW[++*p].c=ch[i];CW[*p].weight=1;for(k=i+1;ch[k]!='\0';k++)if(ch[i]==ch[k])CW[*p].weight++;//權(quán)值累加}}*s=i;//字符串長(zhǎng)度}/********創(chuàng)立HuffmanTree********/voidCreateHuffmanTree(Huffmanht,WeightNodew,intn){inti,j;ints1,s2;//初始化哈夫曼樹(shù)for(i=1;i<=n;i++){ht[i].weight=w[i].weight;ht[i].parent=0;ht[i].LChild=0;ht[i].RChild=0;}for(i=n+1;i<=2*n-1;i++){ht[i].weight=0;ht[i].parent=0;ht[i].LChild=0;ht[i].RChild=0;}for(i=n+1;i<=2*n-1;i++){for(j=1;j<=i-1;j++)if(!ht[j].parent)break;s1=j;//找到第一個(gè)雙親不為零的結(jié)點(diǎn)for(;j<=i-1;j++)if(!ht[j].parent)s1=ht[s1].weight>ht[j].weight?j:s1;ht[s1].parent=i;ht[i].LChild=s1;for(j=1;j<=i-1;j++)if(!ht[j].parent)break;s2=j;//找到第二個(gè)雙親不為零的結(jié)點(diǎn)for(;j<=i-1;j++)if(!ht[j].parent)s2=ht[s2].weight>ht[j].weight?j:s2;ht[s2].parent=i;ht[i].RChild=s2;ht[i].weight=ht[s1].weight+ht[s2].weight;//權(quán)值累加}}/***********葉子結(jié)點(diǎn)的編碼***********/voidCrtHuffmanNodeCode(Huffmanht,charch[],HuffmanCodeh,WeightNodeweight,intm,intn){inti,c,p,start;char*cd;cd=(char*)malloc(n*sizeof(char));cd[n-1]='\0';//末尾置0for(i=1;i<=n;i++){start=n-1;//cd串每次從末尾開(kāi)場(chǎng)c=i;p=ht[i].parent;//p在n+1至2n-1while(p)//沿父親方向遍歷,直到為0{start--;//依次向前置值if(ht[p].LChild==c)//與左子一樣,置0cd[start]='0';else//否那么置1cd[start]='1';c=p;p=ht[p].parent;}weight[i].num=n-start;//二進(jìn)制碼的長(zhǎng)度(包含末尾0)h[i]=(char*)malloc((n-start)*sizeof(char));strcpy(h[i],&cd[start]);//將二進(jìn)制字符串拷貝到指針數(shù)組h中}free(cd);//釋放cd內(nèi)存system("pause");}/*********所有字符的編碼*********/voidCrtHuffmanCode(charch[],HuffmanCodeh,HuffmanCodehc,WeightNodeweight,intn,intm){inti,k;for(i=0;i<m;i++){for(k=1;k<=n;k++)/*從weight[k].c中查找與ch[i]相等的下標(biāo)K*/if(ch[i]==weight[k].c)break;hc[i]=(char*)malloc((weight[k].num)*sizeof(char));strcpy(hc[i],h[k]);//拷貝二進(jìn)制編碼}}/*****解碼*****/voidTrsHuffmanTree(Huffmanht,WeightNodew,HuffmanCodehc,intn,intm){inti=0,j,p;printf("***StringInformation***\n");while(i<m){p=2*n-1;//從父親節(jié)點(diǎn)向下遍歷直到葉子節(jié)點(diǎn)for(j=0;hc[i][j]!='\0';j++){if(hc[i][j]=='0')p=ht[p].LChild;elsep=ht[p].RChild;}printf("%c",w[p].c);/*打印原信息*/i++;}}/*****釋放huffman編碼內(nèi)存*****/voidFreeHuffmanCode(HuffmanCodeh,HuffmanCodehc,intn,intm){inti;for(i=1;i<=n;i++)//釋放葉子結(jié)點(diǎn)的編碼free(h[i]);for(i=0;i<m;i++)//釋放所有結(jié)點(diǎn)的編碼free(hc[i]);}voidmain(){inti,n=0;/*n為葉子結(jié)點(diǎn)的個(gè)數(shù)*/intm=0;/*m為字符串ch[]的長(zhǎng)度*/charch[N];/*ch[N]存放輸入的字符串*/Huffmanht;/*Huffman二叉數(shù)*/HuffmanCodeh,hc;/*h存放葉子結(jié)點(diǎn)的編碼，hc存放所有結(jié)點(diǎn)的編碼*/WeightNodeweight;/*存放葉子結(jié)點(diǎn)的信息*/printf("\t***HuffmanCoding***\n");printf("pleaseinputinformation:");gets(ch);/*輸入字符串*/CreateWeight(ch,&m,weight,&n);/*產(chǎn)生葉子結(jié)點(diǎn)信息，m為字符串ch[]的長(zhǎng)度*/printf("***WeightInformation***\nNode");for(i=1;i<=n;i++)/*輸出葉子結(jié)點(diǎn)的字符與權(quán)值*/printf("%c",weight[i].c);printf("\nWeight");for(i=1;i<=n;i++)printf("%d",weight[i].weight);CreateHuffmanTree(ht,weight,n);/*產(chǎn)生Huffman樹(shù)*/printf("\n***HuffamnTreeInformation***\n");printf("\ti\tweight\tparent\tLChild\tRChild\n");for(i=1;i<=2*n-1;i++)/*打印Huffman樹(shù)的信息*/printf("\t%d\t%d\t%d\t%d\t%d\n",i,ht[i].weight,ht[i].parent,ht[i].LChild,ht[i].RChild);CrtHuffmanNodeCode(ht,ch,h,weight,m,n);/*葉子結(jié)點(diǎn)的編碼*/printf("***NodeCode***\n");/*打印葉子結(jié)點(diǎn)的編碼*/for(i=1;i<=n;i++){printf("\t%c:",weight[i].c);printf("%s\n",h[i]);}CrtHuffmanCode(ch,h,hc,weight,n,m);/*所有字符的編碼*/printf("***StringCode***\n");/*打印字符串的編碼*/for(i=0;i<m;i++)printf("%s",hc[i]);system("pause");TrsHuffmanTree(ht,weight,hc,n,m);/*解碼*/FreeHuffmanCode(h,hc,n,m);system("pause");}答案3〕(1)偽代碼：ProcHuffmanCode(A) //A[1…n]是待編碼的數(shù)組，n為數(shù)組長(zhǎng)度 localh;//最小化堆，內(nèi)含元素為結(jié)點(diǎn)類型，堆初始為空 integeri; Nodep,q,r;//結(jié)點(diǎn)數(shù)據(jù)構(gòu)造，內(nèi)含數(shù)值以及分別指向左、右兒子的兩個(gè)指針 forifrom1totondo//將數(shù)組A中的所有元素插入堆 Insert(h,A(i)); end{for}; whileh元素個(gè)數(shù)大于1then p=DeleteMin(h);//移除最小的兩個(gè)結(jié)點(diǎn) q=DeleteMin(h); r=p+q;r.left=min(p,q);r.right=max(p,q);//構(gòu)造新的結(jié)點(diǎn)r，其值為p,q值之和。 //左兒子為p和q值較小的，右兒子為較 //大的 Insert(h,r);//將r插入堆中 end{while}; p=DeleteMin(h);//取出最后一個(gè)結(jié)點(diǎn)，此節(jié)點(diǎn)即為huffman樹(shù)的根節(jié)點(diǎn)。end{HuffmanCode}(2)javacode：樹(shù)節(jié)點(diǎn)TreeNode:packagegraduate;publicclassTreeNode{privateTreeNodeleft;privateTreeNoderight;privateintvalue;privateintcode;publicTreeNode(){ setLeft(null); setRight(null); setValue(0); setCode(-1); }publicTreeNodegetLeft(){returnleft; }publicvoidsetLeft(TreeNodeleft){this.left=left; }publicTreeNodegetRight(){returnright; }publicvoidsetRight(TreeNoderight){this.right=right; }publicintgetValue(){returnvalue; }publicvoidsetValue(intvalue){this.value=value; }publicintgetCode(){returncode; }publicvoidsetCode(intcode){this.code=code; }}堆節(jié)點(diǎn)HeapNode:packagegraduate;publicclassHeapNode{privateintiData;publicHeapNode(intkey){iData=key; }publicvoidsetKey(intid){iData=id; }publicintgetKey(){returniData; }}堆：packagegraduate;publicclassHeap{privateHeapNode[]heapArray;//堆容器privateintmaxSize;//堆得最大大小privateintcurrentSize;//堆大小publicHeap(int_maxSize){maxSize=_maxSize;heapArray=newHeapNode[maxSize];currentSize=0; }publicvoidfilterDown(intstart,intendOfHeap){inti=start;intj=2*i+1;//j是i的左子女位置 HeapNodetemp=heapArray[i];while(j<=endOfHeap){//檢查是否到最后位置if(j<endOfHeap//讓j指向兩子女中的小者 &&heapArray[j].getKey()>heapArray[j+1].getKey()){ j++; }if(temp.getKey()<=heapArray[j].getKey()){//小那么不做調(diào)整break; }else{//否那么小者上移，i，j下降heapArray[i]=heapArray[j]; i=j; j=2*j+1; } }heapArray[i]=temp; }publicvoidfilterUp(intstart){intj=start;inti=(j-1)/2; HeapNodetemp=heapArray[j];while(j>0){//沿雙親結(jié)點(diǎn)路徑向上直達(dá)根節(jié)點(diǎn)if(heapArray[i].getKey()<=temp.getKey()){//雙親結(jié)點(diǎn)值小，不調(diào)整break; }else{//雙親結(jié)點(diǎn)值大，調(diào)整heapArray[j]=heapArray[i]; j=i; i=(i-1)/2; }heapArray[j]=temp;//回送 } }publicbooleaninsert(HeapNodenewNode){if(isFull()){returnfalse; }else{heapArray[currentSize]=newNode; filterUp(currentSize);currentSize++; }returntrue; }publicHeapNoderemoveMin(){if(isEmpty()){returnnull; } HeapNoderoot=heapArray[0];heapArray[0]=heapArray[currentSize-1];currentSize--; filterDown(0,currentSize-1);returnroot; }publicbooleanisEmpty(){returncurrentSize==0; }publicbooleanisFull(){returncurrentSize==maxSize; }publicintgetCurrentSize(){returncurrentSize; }publicvoidmakeEmpty(){currentSize=0; }}Huffman編碼方法：packagegraduate;importjava.util.HashMap;importjava.util.Iterator;publicclassHuf