中科院計(jì)算機(jī)算法分析與設(shè)計(jì)習(xí)題答案

1、精選課件1第一章 復(fù)雜性分析初步 習(xí)題 語 句 s/e 頻率 總步數(shù)template void Mult(T *a, T *b, int m, int n, int p) 0 0 0for(int i=0; im; i+) 1 m+1 m+1for(int j=0; jp; j+) 1 m*(p+1) m*p+m T sum=0; 1 m*p m*p for(int k=0; kn; 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ì)計(jì) 2*m*p*n+4*m*p+2*m+11. 試確定下述

2、程序的執(zhí)行步數(shù)，該函數(shù)實(shí)現(xiàn)一個mn矩陣與一個np矩陣之間的乘法:s/e 表示每次執(zhí)行該語句所要執(zhí)行的程序步數(shù),頻率是指該語句總的執(zhí)行次數(shù)。精選課件22 函數(shù)MinMax用來查找數(shù)組a0:n-1中的最大元素和最小元素，以下給出兩個程序。令n為實(shí)例特征。試問：在各個程序中，a中元素之間的比較次數(shù)在最壞情況下各是多少？ 6. 按照漸進(jìn)階從低到高的順序排列以下表達(dá)式:!,20,3,log,43/22nnnnnn!3420log23/2nnnnnn2) 1(3ntemplatebool MinMax(T a, int n, int& Min, int& Max) if(n1) return false;

3、 Min=Max=0; /初始化 for(int i=1; iai) Min=i; if(aMaxai) Max=i; return true;最好，最壞，平均比較次數(shù)都是最好，最壞，平均比較次數(shù)都是 2*（n-1）templatebool MinMax(T a, int n, int& Min, int& Max) if(n1) return false; Min=Max=0; /初始化 for(int i=1; iai) Min=i; else if(aMaxB-E|0B-A-C|0C-B-D-E|0D-C|0E-A-C-F-G|0F-E-G|0G-E-F|0精選課件11ABEDGCF11

4、234756111554A-B-E|0B-A-C|0C-B-D-E|0D-C|0E-A-C-F-G|0F-E-G|0G-E-F|0初始化 DFN:=0，num:=1；DFNL(A,null)， DFN(A):=num=1; L(A):=num=1; num+:=2。 DFN(B)=0, DFNL(B,A) DFN(B):=num= 2, L(B):=num=2, num+:=3; DFN(A)=10, A=A, 無操作。 DFN(C)=0 DFNL(C,B) DFN(C):= num=3, L(C):=num=3,num+:=4; DFN(B)=10, B=B, 無操作. DFN(D)=0,

5、DFNL(D,C)， DFN(D):=num= 4; L(D):=num=4; num+:=5; DFN(C)=30,C=C，無操作. DFNL(D,C) 結(jié)束結(jié)束。 DFN(E)=0, DFNL(E,C), DFN(E):=5; L(E):=5; num+:=6; DFN(A)=10,AC, L(E)=min (L(E), DFN(A)=1。 DFN(C)=30，C=C，無操作。 DFN(F)=0，DFNL(F,E)， DFN(F):=num=6; L(F):=num=6; num+:=7; DFN(E)=50，E=E，無操作。 DFN(G)=0，DFNL(G,F)， DFN(G):=num

6、=7; L(G):=num=7; num+:=8； DFN(E)=50,EF，L(G)=min (L(G),DFN(E)=5; DFN(F)=60,F=F,無操作。 DFNL(G,F) 結(jié)束結(jié)束 L(F):=min (L(F)，L(G)=min(6,5)=5 DFNL(F,E)的結(jié)束。的結(jié)束。 L(E):=min (L(E),L(F)=min(1,5)=1 DFNL(E,C) 結(jié)束。結(jié)束。 L(C):=min (L(C),L(E)=min(3,1)=1 DFNL(C,B) 結(jié)束。結(jié)束。 L(B):=min (L(B),L(C)=min(2,1)=1 DFNL(B,A) 結(jié)束。 L(A):=mi

7、n (L(A),L(B)=1 因DFN(E)=0，E null,則L(A)=min (L(A),DFN(E)=1DFNL(A,null) 結(jié)束。精選課件12序號頂點(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,

8、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)精選課件137. 對圖的另一種檢索方法是 D-Search。該方法與 BFS 的不同之處在于將隊(duì)列換成棧，即下一個要檢測的結(jié)點(diǎn)是最新加到未檢測結(jié)點(diǎn)表的那個結(jié)點(diǎn)。 1）寫一個D-Search算法；2）證明由結(jié)點(diǎn)v開始的D-Search能夠訪問v可到達(dá)的所有結(jié)點(diǎn)； 3）你的算法的時、空復(fù)雜度是什么？（類比BFS算法）（類比定理2.2.1證明）精選課件14proc DBFS(v) / PushS(v , S);/

9、 將S初始化為只含有一個元素v的棧 while S非空 do u:= PullHead(S); count:=count+1; visitedu:=count; for 鄰接于u的所有頂點(diǎn)w do if sw=0 then PushS(w , S); /將w壓入棧中 sw:=1; endif endfor endwhile endDBFS圖的D搜索算法偽代碼：proc DBFT(G, ) /count、s同DBFS中的說明，branch是統(tǒng)計(jì)圖G的連通分支數(shù) count:=0; branch:=0; for i to n do si:=0; /將所有的頂點(diǎn)標(biāo)記為未被訪問 endfor for

10、i to do if si=0 then DBFS(i); branch:=branch+1; endif endfor endDBFT精選課件152）證明：除結(jié)點(diǎn)v外，只有當(dāng)結(jié)點(diǎn)w滿足sw=0時才被壓入棧中，因此每個結(jié)點(diǎn)至多有一次被壓入棧中，搜索不會出現(xiàn)重疊和死循環(huán)現(xiàn)象，對于每一個v可到達(dá)的節(jié)點(diǎn)，要么直接被訪問，要么被壓入棧中，只有棧內(nèi)節(jié)點(diǎn)全部彈出被訪問后，搜索才會結(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時才被壓入棧中，因此每個結(jié)點(diǎn)至多有一次被壓入棧中。需要的棧 空間至多是-1；visited數(shù)組變量所需要的空間為；其余變量

11、所用的空間為O(1)，所以s(,)= ()。 如果使用鄰接鏈表， for循環(huán)要做d(u)次，而while循環(huán)需要做次，又visited、s和count的賦值都需要次操作，因而t (,)= (+ )。 如果采用鄰接矩陣，則while循環(huán)總共需要做2次操作，visited、s和count的賦值都需要次操作，因而t (,)= (2)。精選課件168.考慮下面這棵假想的對策樹：1）使用最大最小方法(2-4-2)式獲取各結(jié)點(diǎn)的值； 2）弈者A為獲勝應(yīng)該什么棋著？ 3）列出算法VEB計(jì)算這棵對策樹結(jié)點(diǎn)的值時各結(jié)點(diǎn)被計(jì)算的順序4）對樹中每個結(jié)點(diǎn)X，用(2-4-3)式計(jì)算V(X)； 5）在取X根，l=10,

12、LB =-, D=的情況下，用算法AB計(jì)算此樹的根的值期間，這棵樹的那些結(jié)點(diǎn)沒有計(jì)算？841551030592050 1861510520精選課件172064205481562030550841520510305920 50 186151055201）使用最大最小方法(2-4-2)式獲取各結(jié)點(diǎn)的值maxmaxmaxminmin精選課件182）弈者A為獲勝應(yīng)該什么棋著？ 2064205481562030550841520510305920 50X1X2X3X4X1.1X1.2X2.1X2.2X3.1X3.2X4.1X4.2X1.1.1X1.1.2X1.1.3X1.2.1

13、X2.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精選課件193）列出算法VEB計(jì)算這棵對策樹結(jié)點(diǎn)的值時各結(jié)點(diǎn)被計(jì)算的順序46151051),(lXVEB), 1,(:1lXVEBans), 1,(1lXVEB), 2,(1 , 1lXVEB), 3,(1 , 1 , 1lXVEB)(), 1,(,max(:)(2ansreturnforendifendanslXVEBansanselseansreturnthenDansifdodtofromiforiendXeret

14、urnthenlXif)(0是終局或), 4,(1111lXVEB)(:1111Xeans 子節(jié)點(diǎn)）(:VEBans-523469),(DlXVEB)5, 3,(, 5max(), 3,(,max(:?522, 1 , 12, 1 , 1lXVEBanslXVEBansansifor）子節(jié)點(diǎn)1(:VEBans）子節(jié)點(diǎn)1(:VEBans）子節(jié)點(diǎn)1(:VEBans510)(2, 1 , 1EXe-1010)10, 5max()10, 3,(,10max(), 3,(,max(:?1033 , 1 , 13 , 1 , 1lXVEBanslXVEBansansifor15)(3 , 1 , 1EXe

15、15)15,10max(-1515)()15( 1 , 1XVEBreturn，即結(jié)束1515?15-2i-666)6(,15max(:ans578-6-4410?62i4(:）Eeans)6,(, 6max(:2XVEBans）子節(jié)點(diǎn)1(:)6, 1,(2VEBanslXVEB64-4)return(ans True?642i11-4精選課件203）列出算法VEB計(jì)算這棵對策樹結(jié)點(diǎn)的值時各結(jié)點(diǎn)被計(jì)算的順序20-6-4-20-5415620305-4-15 -20 -5 -10 -30 -5-6-15-10-55202420231519223412 141618 211711312695781

16、011精選課件214）對樹中每個結(jié)點(diǎn)X，用(2-4-3)式計(jì)算V(X)； 20-6-4-20-5481562030550-8-4-15 -20 -5 -10 -30 -5-9 -20 -50-18-6-15-10-5520精選課件225）在取X根，l=10, LB =-, D=的情況下，用算法AB計(jì)算此樹的根的值期間，這棵樹的那些結(jié)點(diǎn)沒有計(jì)算？20-6-6-20-206156203020-4-15 -20 -5 -10 -30 -5-6-15-10-5520精選課件231520202010206206156615105）在取X根，l=10, LB =-, D=的情況下，用算法AB計(jì)算此樹的根的值期間，這棵樹的那些結(jié)點(diǎn)沒