中國(guó)科學(xué)院大學(xué)歷年計(jì)算機(jī)算法作業(yè)和歷年習(xí)題

1、79中國(guó)科學(xué)院大學(xué)歷年習(xí)題習(xí)題一 復(fù)雜性分析初步1. 試確定下述程序的執(zhí)行步數(shù)，該函數(shù)實(shí)現(xiàn)一個(gè)m×n矩陣與一個(gè)n×p矩陣之間的乘法： 矩陣乘法運(yùn)算 template<class T> void Mult(T *a, T *b, int m, int n, int p) /m×n矩陣a與n×p矩陣b相成得到m×p矩陣c for(int i=0; i<m; i+) for(int j=0; j<p; j+) T sum=0; for(int k=0; k<n; k+) Sum+=aik*bkj; Cij=sum; 語

2、句 s/e 頻率 總步數(shù)template<class T> void Mult(T *a, T *b, int m, int n, int p) 0 0 0for(int i=0; i<m; i+) 1 m+1 m+1for(int j=0; j<p; j+) 1 m*(p+1) m*p+m T sum=0; 1 m*p m*p for(int k=0; k<n; k+) 1 m*p*(n+1) m*p*n+m*p Sum+=aik*bkj; 1 m*p*n m*p*n Cij=sum; 1 m*p m*p 總 計(jì) 2*m*p*n+4*m*p+2*m+1其中 s/

3、e 表示每次執(zhí)行該語句所要執(zhí)行的程序步數(shù)。頻率是指該語句總的執(zhí)行次數(shù)。2 函數(shù)MinMax用來查找數(shù)組a0:n-1中的最大元素和最小元素，以下給出兩個(gè)程序。令n為實(shí)例特征。試問：在各個(gè)程序中，a中元素之間的比較次數(shù)在最壞情況下各是多少？ 找最大最小元素 方法一template<class T>bool MinMax(T a, int n, int& Min, int& Max)/尋找a0:n-1中的最小元素與最大元素 /如果數(shù)組中的元素?cái)?shù)目小于1，則還回false if(n<1) return false; Min=Max=0; /初始化 for(int i=

4、1; i<n; i+) if(aMin>ai) Min=i; if(aMax<ai) Max=i; return true;最好，最壞，平均比較次數(shù)都是 2*（n-1） 找最大最小元素 方法二template<class T>bool MinMax(T a, int n, int& Min, int& Max)/尋找a0:n-1中的最小元素與最大元素 /如果數(shù)組中的元素?cái)?shù)目小于1，則還回false if(n<1) return false; Min=Max=0; /初始化 for(int i=1; i<n; i+) if(aMin>

5、;ai) Min=i; else if(aMax<ai) Max=i; return true;最壞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ī)模為多大的問題?規(guī)模時(shí)間復(fù)雜度（步數(shù)）原運(yùn)行速度（

6、時(shí)間/每步）總時(shí)間關(guān)系式為 時(shí)間復(fù)雜度（計(jì)算步數(shù)）*運(yùn)行速度(時(shí)間/每步)=運(yùn)行所需時(shí)間，即解：設(shè)在新機(jī)器上秒內(nèi)能解決規(guī)模為的問題，時(shí)間復(fù)雜度變?yōu)?，由于新機(jī)器運(yùn)行速度提高64倍，則運(yùn)行速度變?yōu)?，由關(guān)系式，得，解得2) 若上述算法改進(jìn)后，新算法的計(jì)算復(fù)雜度為, 則在新機(jī)器上用秒時(shí)間能解決輸入規(guī)模為多大的問題？設(shè)在新機(jī)器上用秒時(shí)間能解決輸入規(guī)模為的問題，則由于新復(fù)雜度 ，新機(jī)器的運(yùn)行速度為， 代入關(guān)系式，得，解得3）若進(jìn)一步改進(jìn)算法，最新的算法的時(shí)間復(fù)雜度為 ，其余條件不變，在新機(jī)器上運(yùn)行，在秒內(nèi)能夠解決輸入規(guī)模為多大的問題？設(shè)可解決的最大時(shí)間復(fù)雜度為，則可解決的最大時(shí)間復(fù)雜度為，（n為原始的輸入

7、規(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è)無向圖中，如果每個(gè)頂點(diǎn)的度大于等于2，則該該圖一定含有圈；2）在一個(gè)有向圖D中，如果每個(gè)頂點(diǎn)的出度都大于等于1，則該圖一定含有一個(gè)有向圈。1）證明：設(shè)無向圖最長(zhǎng)的跡每個(gè)頂點(diǎn)度大于等于2，故存在與相異的點(diǎn)與相鄰，若則得到比更長(zhǎng)的跡，與P的取法矛盾。因此

8、，是閉跡，從而存在圈證明*：設(shè)在無向圖G中，有n個(gè)頂點(diǎn)，m條邊。由題意知，m>=(2n)/2=n，而一個(gè)含有n個(gè)頂點(diǎn)的樹有n-1條邊。因m>=n>n-1，故該圖一定含有圈。（定義：跡是指邊不重復(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)，使得成為一條有向邊，若則得到比更長(zhǎng)的有向跡，與P矛盾，因此必有，從而該圖一定含有有向圈。2.設(shè)D是至少有三個(gè)頂點(diǎn)的連通有向圖。如果D中包含有向的Euler環(huán)游（即是通過D中每條有向邊恰好一次的

9、閉跡），則D中每一頂點(diǎn)的出度和入度相等。反之，如果D中每一頂點(diǎn)的出度與入度都相等，則D一定包含有向的Euler環(huán)游。這兩個(gè)結(jié)論是正確的嗎？請(qǐng)說明理由。如果G是至少有三個(gè)頂點(diǎn)的無向圖，則G包含Euler環(huán)游的條件是什么？證明：1）若圖D中包含有向Euler環(huán)游，下證明每個(gè)頂點(diǎn)的入度和出度相等。如果該有向圖含有Euler環(huán)游，那么該環(huán)游必經(jīng)過每個(gè)頂點(diǎn)至少一次，每經(jīng)過一次，必為“進(jìn)”一次接著“出”一次，從而入度等于出度。從而，對(duì)于任意頂點(diǎn)，不管該環(huán)游經(jīng)過該頂點(diǎn)多少次，必有入度等于出度。2）若圖D中每個(gè)頂點(diǎn)的入度和出度相等，則該圖D包含Euler環(huán)游。證明如下。對(duì)頂點(diǎn)個(gè)數(shù)進(jìn)行歸納。當(dāng)頂點(diǎn)數(shù)|v(D)|

10、=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í)，任取vv(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è)過程最終得到的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）

11、G是至少有三個(gè)頂點(diǎn)的無向圖，則G包含Euler環(huán)游等價(jià)于G中無奇度頂點(diǎn)。（即任意頂點(diǎn)的度為偶數(shù)）。 3設(shè)G是具有n個(gè)頂點(diǎn)和m條邊的無向圖，如果G是連通的，而且滿足m = n-1,證明G是樹。證明：思路一：只需證明G中無圈。若G中有圈，則刪去圈上任一條邊G仍連通。而每個(gè)連通圖邊數(shù)e>=n(頂點(diǎn)數(shù)) 1，但刪去一條邊后G中只有n-2條邊，此時(shí)不連通，從而矛盾，故G中無圈，所以G為樹。思路二：當(dāng)時(shí)，兩個(gè)頂點(diǎn)一條邊且連通無環(huán)路，顯然是樹。設(shè)當(dāng)時(shí)，命題成立，則當(dāng)時(shí)，因?yàn)镚連通且無環(huán)路，所以至少存在一個(gè)頂點(diǎn)，他的度數(shù)為1，設(shè)該頂點(diǎn)所關(guān)聯(lián)的邊為那么去掉頂點(diǎn)和，便得到了一個(gè)有k-1個(gè)頂點(diǎn)的連通無向無環(huán)路

12、的子圖，且的邊數(shù)，頂點(diǎn)數(shù)。由于m=n-1,所以，由歸納假設(shè)知，是樹。由于相當(dāng)于在中為添加了一個(gè)子節(jié)點(diǎn)，所以G也是樹。由（1），（2）原命題得證。4. 假設(shè)用一個(gè)的數(shù)組來描述一個(gè)有向圖的鄰接矩陣，完成下面工作：1）編寫一個(gè)函數(shù)以確定頂點(diǎn)的出度，函數(shù)的復(fù)雜性應(yīng)為：2）編寫一個(gè)函數(shù)以確定圖中邊的數(shù)目，函數(shù)的復(fù)雜性應(yīng)為3）編寫一個(gè)函數(shù)刪除邊，并確定代碼的復(fù)雜性。解答：（1）鄰接矩陣表示為，待確定的頂點(diǎn)為第m個(gè)頂點(diǎn)int CountVout(int *a,int n,int m)int out = 0;for(int i=0;i<n;i+) if(am-1i=1) out+;return out;

13、（2）確定圖中邊的數(shù)目的函數(shù)如下：int EdgeNumber(int*a,int n)int num =0;for(int i=0;i<n;i+) for(int j=0;j<n;j+) if(aij=1) num+;return num;（3）刪除邊（i , j）的函數(shù)如下：void deleteEdge(int *a，int i ,int j) if(ai-1j-1=0) return; ai-1j-1 = 0;return;代碼的時(shí)間復(fù)雜性為(1) 5.實(shí)現(xiàn)圖的D-搜索算法，要求用SPARKS語言寫出算法的偽代碼，或者用一種計(jì)算機(jī)高級(jí)語言寫出程序。解:D搜索算法的基本思想是

14、，用棧代替BFS中的隊(duì)列，先將起始頂點(diǎn)存入棧中，搜索時(shí)，取出棧頂?shù)脑兀闅v搜索其相鄰接點(diǎn)，若其鄰接點(diǎn)還未搜索，則存入棧中并標(biāo)記，遍歷所有鄰接點(diǎn)后，取出此時(shí)棧頂?shù)脑剞D(zhuǎn)入下一輪遍歷搜索，直至棧變?yōu)榭諚！?Proc DBFS (v) /從頂點(diǎn)v開始，數(shù)組visited標(biāo)示頂點(diǎn)被訪問的順序； PushS(v , S); /首先訪問v,將S初始化為只含有一個(gè)元素v的棧count :=count +1; visitedv := count;While S 非空 do u :=PullHead(S); count :=count +1; visitedw := count; /區(qū)別隊(duì)列先進(jìn)先出，此先進(jìn)后

15、出for 鄰接于u的所有頂點(diǎn)w doif sw = 0 then PushS(w,S); /將w存入棧S sw:= 1; endif endfor endwhile endDBFS注：PushS(w,S)將w存入棧S; PullHead(S)為取出棧最上面的元素，并從棧中刪除Proc DBFT(G，m) /m為不連通分支數(shù) count:=0 ;計(jì)數(shù)器，標(biāo)示已經(jīng)被訪問的頂點(diǎn)個(gè)數(shù) for i to n do si:=0; /數(shù)組s用來標(biāo)示各頂點(diǎn)是否曾被搜索，是則標(biāo)記為1，否則標(biāo)記為0； endfor for i to m do /遍歷不連通分支的情況 if si=0 then DBFS (i);

16、endif endforendDBFT6.下面的無向圖以鄰接鏈表存儲(chǔ)，而且在關(guān)于每個(gè)頂點(diǎn)的鏈表中與該頂點(diǎn)相鄰的頂點(diǎn)是按照字母順序排列的。試以此圖為例描述講義中算法DFNL的執(zhí)行過程。一個(gè)無向圖 G ABEDGCF11234756111554鄰接鏈表A->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為樹的根節(jié)點(diǎn),對(duì)A計(jì)算DFNL(A,null)，DFN(A)：=num=

17、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)=1¹0, 但A=A,即是B的父節(jié)點(diǎn)，無操作。接著查找鄰接鏈表得到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)=1¹0, 但B=B,即是C的父節(jié)點(diǎn)，無操作。接著查找鄰接鏈表得到C的鄰接點(diǎn)D，因?yàn)?/p>

18、DFN(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)=30,但C=C，為D的父節(jié)點(diǎn)， L(D)保持不變。D的鄰接鏈表結(jié)束，DFNL(D,C)的計(jì)算結(jié)束。返回到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)=10，又AC，變換L(E)=min(L(E),DFN(A)=1。查找得E鄰接點(diǎn)C，因DFN(C)=30，但C=C，無操作。查找得

19、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)=50，但E=E，無操作。 查找得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)=50，又EF，L(G)=min(L(G),DFN(E)=5 查找得G鄰接點(diǎn)F,因DFN(F)=60，但F=F，無操作。 G的鄰接鏈表結(jié)束，DFNL(G,F)的計(jì)算結(jié)束。 L(F)：=min(L(F)，L(G)=min(

20、6,5)=5 F的鄰接鏈表結(jié)束，DFNL(F,E)的計(jì)算結(jié)束。 L(E):=min(L(E),L(F)=min(1,5)=1E鄰接鏈表結(jié)束， DFNL(E,C)計(jì)算結(jié)束。L(C):=min(L(C),L(E)=min(3,1)=1 C的鄰接鏈表結(jié)束，DFNL(C,B)計(jì)算結(jié)束。 L(B):=min(L(B),L(C)=min(2,1)=1 查找B的鄰接鏈表結(jié)束，DFNL(B,A)計(jì)算結(jié)束。 L(A):=min(L(A),L(B)=1 查找得A的鄰接點(diǎn)E，因DFN(E)=0，又Enull,則L(A)=min(L(A),DFN(E)=1查找A的鄰接鏈表結(jié)束，DFNL(A,null)計(jì)算結(jié)束。最終結(jié)

21、果為：深索數(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),(

22、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í)行過程開始 DFNL(A,*)DFN(A):=1; L(A):=1; num:=2;A B BB AC BBC B AD C BBC B AE C BBC B AF C BBF C B AA F C BB DFN(B)=0, DFNL(B,A) DFN(B

23、):=2; L(B):=2; num:=3; DFN(A)=1¹0, 但A=A, 不做任何事情 DFN(C)=0, DFNL(C,B) DFN(C):=3; L(C):=3; num:=4; DFN(B)=2¹0, 但B=B, 不做任何事情 DFN(D)=0, DFNL(D,C) DFN(D):=4; L(D):=4 > DFN( C); num:=5; 彈出（C,D）邊 DFN(C)=3¹0, 但C=C, 不做任何事情 DFN(E)=0, DFNL(E,C) DFN(E):=5; L(E):=5 > DFN( C); num:=6; 彈出（C,E）邊

24、 DFN(C)=3¹0, 但C=C, DFN(F)=0, DFNL(F,C) DFN(F):=6; L(F):=6; num:=7; DFN(A)=1¹0, A¹C, L(F):=min6,1=1; DFN(C)=3¹0, 但C=C,F F C B AG A F C BBG F F C B AH G A F C BBG F F C B AI G A F C BBI G F F C B AF I G A F C BBI I G F F C B AJ F I G A F C BBJ I I G F F C B AF J F I G A F C BBJ J I

25、 I G F F C B AG F J F I G A F C BB DFN(G)=0, DFNL(G,F) DFN(G):=7; L(G):=7; num:=8; DFN(F)=6¹0, 但F=F, DFN(H)=0, DFNL(H,G) DFN(H):=8; L(H):=8 > DFN(G); num:=9; 彈出（G,H）邊 DFN(G)=7¹0, 但G=G, DFN(I)=0, DFNL(I,G) DFN(I):=9; L(I):=9; num:=10; DFN(F)=6¹0, F¹G, L(I):=min9,6=6; DFN(G)=7&#

26、185;0, 但G=G, DFN(J)=0, DFNL(J,I) DFN(J):=10; L(J):=10; num:=11; DFN(F)=6¹0, F¹I, L(J):=min10,6=6; DFN(G)=7¹0, G¹I, L(J):=min6,7=6; DFN(I)=9¹0, 但I(xiàn)=I, L(I):=min6,6=6; L(G):=min7,6=6 ³ DFN(F) 彈出(J,G), (J,F), (I,J), (I,F), (G,I), (F,G) 邊 L(F):=min1,6=1; L(C ):=min3,1=1;L(B)

27、:=min2,1=1 ³ DFN(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）寫一個(gè)D-Search算法； 2）證明由結(jié)點(diǎn)v開始的D-Search能夠訪問v可到達(dá)的所有結(jié)點(diǎn)； 3）你的算法的時(shí)、空復(fù)雜度是什么？解：1）同第5題，proc DBFS(v) /寬度優(yōu)先搜索G，從頂點(diǎn)v開始執(zhí)行，數(shù)組visited標(biāo)示各 /頂點(diǎn)被訪問的序數(shù)；數(shù)組s將用來標(biāo)示各頂點(diǎn)是否曾被放進(jìn)待檢查隊(duì) /列，是則過標(biāo)記為1，否則標(biāo)記為0；

28、計(jì)數(shù)器count計(jì)數(shù)到目前為止已/經(jīng)被訪問的頂點(diǎn)個(gè)數(shù)，其初始化為在v之前已經(jīng)被訪問的頂點(diǎn)個(gè)數(shù) PushS(v , S);/ 將S初始化為只含有一個(gè)元素v的棧while S非空 do u:= PullHead(S); count:=count+1; visitedu:=count; for 鄰接于u的所有頂點(diǎn)w do if sw=0 thenPushS(w , S); /將w壓入棧中sw:=1; endif endfor endwhile endDBFS圖的D搜索算法偽代碼：proc DBFT(G, ) /count、s同DBFS中的說明，branch是統(tǒng)計(jì)圖G的連通分支數(shù) count:=0;

29、branch:=0; for i to n do si:=0; /將所有的頂點(diǎn)標(biāo)記為未被訪問 endforfor i to do if si=0 then DBFS(i); branch:=branch+1; endif endfor endDBFT2）證明：除結(jié)點(diǎn)v外，只有當(dāng)結(jié)點(diǎn)w滿足sw=0時(shí)才被壓入棧中，因此每個(gè)結(jié)點(diǎn)至多有一次被壓入棧中，搜索不會(huì)出現(xiàn)重疊和死循環(huán)現(xiàn)象，對(duì)于每一個(gè)v可到達(dá)的節(jié)點(diǎn)，要么直接被訪問，要么被壓入棧中，只有棧內(nèi)節(jié)點(diǎn)全部彈出被訪問后，搜索才會(huì)結(jié)束，所以由結(jié)點(diǎn)v開始的D-Search能夠訪問v可到達(dá)的所有結(jié)點(diǎn)。3）：除結(jié)點(diǎn)v外，只有當(dāng)結(jié)點(diǎn)w滿足sw=0時(shí)才被壓入棧中，因

30、此每個(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ì)策樹：解：206420548156203055084152051030592050186151055201）使用最大最小方法(2-4-2)式獲

31、取各結(jié)點(diǎn)的值maxmaxmaxminmin2）2）弈者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、編寫程序?qū)崿F(xiàn)歸并算法和快速排序算法參見后附程序2、用長(zhǎng)為100、200、300、400、500、6

32、00、700、800、900、1000的10個(gè)數(shù)組的排列來統(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、說明算法PartS

33、elect的時(shí)間復(fù)雜性為證明：提示：假定數(shù)組中的元素各不相同，且第一次劃分時(shí)劃分元素是第小元素的概率為。因?yàn)镻artition中的case語句所要求的時(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ù)組

34、的中間值u是該數(shù)組中的第4小元素，因此數(shù)組中至少有4個(gè)元素不大于u，個(gè)中間值中至少有個(gè)不大于這些中間值的中間值v。因此，在數(shù)組A中至少有個(gè)元素不大于v。換句話說，A中至多有個(gè)元素大于v。同理，至多有個(gè)元素小于v。這樣，以v為劃分元素，產(chǎn)生的新數(shù)組至多有個(gè)元素。當(dāng)時(shí)，。另一方面，在整個(gè)執(zhí)行過程中，遞歸調(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)系

35、為。若通過歸納法證明出有的形式，用數(shù)學(xué)歸納法可以證明，。所以時(shí)間復(fù)雜度是。歸并排序的 C+語言描述 #include<iostream.h> template<class T>void MergeSort(T a,int left,int right); template<class T>void Merge(T c,T d, int l,int m,int r); template<class T>void Copy(T a,T b,int l,int r); void main() int const n(5); int an; cout&l

36、t;<"Input "<<n<<"numbers please:" for(int i=0;i<n;i+) cin>>ai; /for(int j=0;j<n;j+) /bj=aj; MergeSort(a,0,n-1); cout<<"The sorted array is"<<endl; for(i=0;i<n;i+) cout<<ai; cout<<endl; template<class T> void Me

37、rgeSort(T a,int left,int right) / if(left<right) int i=(left+right)/2; T *b=new T; MergeSort(a,left,i); MergeSort(a,i+1,right); Merge(a,b,left,i,right); Copy(a,b,left,right); template<class T> void Merge(T c,T d,int l,int m,int r) int i=l; int j=m+1; int k=l; while(i<=m)&&(j<=

38、r) if(ci<=cj)dk+=ci+; else dk+=cj+; if(i>m) for(int q=j;q<=r;q+) dk+=cq; else for(int q=i;q<=m;q+) dk+=cq; template<class T> void Copy(T a,T b, int l,int r) for(int i=l;i<=r;i+) ai=bi; 快速排序的 C+語言描述 #include<iostream.h> template<class T>void QuickSort(T a,int p,int r)

39、; template<class T>int Partition(T a,int p,int r); void main() int const n(5); int an; cout<<"Input "<<n<<"numbers please:" for(int i=0;i<n;i+) cin>>ai; QuickSort(a,0,n-1); cout<<"The sorted array is"<<endl; for(i=0;i<n;i+

40、) cout<<ai<<" " cout<<endl; template<class T> void QuickSort(T a,int p,int r) if(p<r) int q=Partition(a,p,r); QuickSort(a,p,q-1); QuickSort(a,q+1,r); template<class T> int Partition(T a,int p,int r) int i=p,j=r+1; T x=ap; while(true) while(a+i<x); while(

41、a-j>x); if(i>=j)break; Swap(ai,aj); ap=aj; aj=x; return j; template<class T> inline void Swap(T &s,T &t) T temp=s; s=t; t=temp; 第四章作業(yè) 部分參考答案1 設(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í)間為則在

42、總等待時(shí)間T中的權(quán)重最大，的權(quán)重最小。故讓所需時(shí)間少的顧客先得到服務(wù)可以減少總等待時(shí)間。證明：設(shè)，下證明當(dāng)按照不減順序依次服務(wù)時(shí)，為最優(yōu)策略。記按照次序服務(wù)時(shí)，等待時(shí)間為，下證明任意互換兩者的次序，都不減。即假設(shè)互換兩位顧客的次序，互換后等待總時(shí)間為，則有由于則有同理可證其它次序，都可以由經(jīng)過有限次兩兩調(diào)換順序后得到，而每次交換，總時(shí)間不減，從而為最優(yōu)策略。2 字符出現(xiàn)的頻率分布恰好是前8個(gè)Fibonacci數(shù)，它們的Huffman編碼是什么？將結(jié)果推廣到個(gè)字符的頻率分布恰好是前個(gè)Fibonacci數(shù)的情形。Fibonacci數(shù)的定義為：解：前8個(gè)數(shù)為a， b， c， d， e， f， g，

43、h1， 1， 2， 3， 5， 8， 13， 21Huffman哈夫曼編碼樹為： 54h:21332012742g:13f:8e:5d:3C:2b:1a：101000000111111所以a 的編碼為：1111111b的編碼為：1111110c的編碼為：111110 d的編碼為：11110e的編碼為：1110 f的編碼為：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 ， 03 設(shè)是準(zhǔn)備存放到長(zhǎng)為L(zhǎng)的磁帶上的n個(gè)程序，程序需要的

44、帶長(zhǎng)為。設(shè)，要求選取一個(gè)能放在帶上的程序的最大子集合（即其中含有最多個(gè)數(shù)的程序）。構(gòu)造的一種貪心策略是按的非降次序?qū)⒊绦蛴?jì)入集合。1) 證明這一策略總能找到最大子集，使得。2) 設(shè)是使用上述貪心算法得到的子集合，磁帶的利用率可以小到何種程度？3) 試說明1)中提到的設(shè)計(jì)策略不一定得到使取最大值的子集合。1） 證明：不妨設(shè)，若該貪心策略構(gòu)造的子集合為，則滿足。要證明能找到最大子集，只需說明s為可包含的最多程序段數(shù)即可。即證不存在多于s個(gè)的程序集合，使得。反證法，假設(shè)存在多于s個(gè)的程序集，滿足。因?yàn)榉墙敌蚺帕?，則。因?yàn)榍覟檎麛?shù)，則其前s+1項(xiàng)滿足。這與貪心策略構(gòu)造的子集和中s滿足的矛盾。故假設(shè)不成

45、立，得證。2）磁帶的利用率為;（甚至最小可為0，此時(shí)任意或者）3)按照1）的策略可以使磁帶上的程序數(shù)量最多，但程序的總長(zhǎng)度不一定是最大的，假設(shè)為Q的最大子集，但是若用代替，仍滿足，則為總長(zhǎng)度更優(yōu)子集。4.同學(xué)們的幾種不同答案構(gòu)造哈夫曼樹思想，將所有的節(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)（樹根）。答案1）偽代碼： typedef struct unsigned int weight; unsigned int parent, lchild, rchild; HTNod

46、e, * HuffmanTree; typedef char * HuffmanCode; proc HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) if n<=1 then return HuffmanTree p; integer s1, s2, i, m, start, c, f; char *cd; m := 2 * n - 1; HT0.weight := 1000000; p := HT+1; for i to n do (*p).weight := *w; (*p).parent := (*p).lchild := (*p).rchild := 0; +p; +w; endfor for i to m do (*p).weight = (*p).parent = (*p).lchild = (*p).rchild = 0; +p; endfor