東南大學(xué)算法設(shè)計與分析課程考試復(fù)習(xí)試題題庫及答案

1、 PAGE PAGE 46東南大學(xué)算法設(shè)計與分析課程考試復(fù)習(xí)試題題庫及答案什么是基本運算？答：基本運算是解決問題時占支配地位的運算（一般1 種，偶爾兩種）；討論一個算法優(yōu)劣時，只討論基本運算的執(zhí)行次數(shù)。什么是算法的時間復(fù)雜性（度）？（度運算量。T(n)=4n3什么是算法的漸近時間復(fù)雜性？答：當(dāng)輸入規(guī)模趨向于極限情形時（相當(dāng)大）的時間復(fù)雜性。表示漸進時間復(fù)雜性的三個記號的具體定義是什么？答：1. T(n)= c n01，nn0T(n)c*f(n)（給出了算法時間復(fù)雜度的上界，不可能比c*f(n)更大T(n)=(f(n)：c0，n01，nn0nT(n)c*f(n)成立。（給出了算法時間復(fù)雜度的下界

2、， c*f(n)更小）T(n)=(f(n)：若存在c1,c20，和正整數(shù)n01，使得當(dāng)nn0 時，總有 T(n)c1*f(n)，且有無窮多個使得T(n)c2*f(n)成立，即T(n)= O(f(n)與T(n)=(f(n)都成立。（既給出了算法時間復(fù)雜度的上界， 也給出了下界）什么是最壞情況時間復(fù)雜性？什么是平均情況時間復(fù)雜性？n多的時間復(fù)雜性。平均情況時間復(fù)雜性是規(guī)模為 n 的所有輸入的算法時間復(fù)雜度的平均值（一般均假設(shè)每種輸入情況以等概率出現(xiàn)）。一般認為什么是算法？什么是計算過程？a.確定性（無二義（每條指令能夠執(zhí)行輸入 d.輸出 e.有窮性（令執(zhí)行的次數(shù)有窮）只滿足前 4 條而不滿足第 5

3、 條的有窮指令序列通常稱之為計算過程。算法研究有哪幾個主要步驟？主要從哪幾個方面評價算法？答：算法研究的主要步驟是1)2）3）4）分析 5）測試1）正確性 2）健壯性 3）簡單性 4）高效性 5）8答：1. 多項式時間的算法互相之間雖有差距，一般可以接受。nk(x出？答：設(shè) 0(x), 1(x), 2(x),n(x), 的值都在同一個數(shù)域中） （k=0,1,2, k(x) 1 i1(x) 2 i2 (x) + + p ip (x) k(x)數(shù)項線性表出。根據(jù)特征根的情況，常系數(shù)線性遞歸方程的解有哪幾種不同的形式？答：1.若方程(*)r 1， 2， r i j)，則齊次方程(*)的解為 anA1

4、+ A2+ +Ar(齊通解，即齊次方（A1Arr）若 2(* ei ei A ncos(n )+B nsin(n ) (A,B 是(*)k 對應(yīng)的解的部分為 C1 n+C2n n+ n2 n+ +Ck nk-1 n (C1Ck若(*)f(n)0(q(n)是(*)的一個解， 則(*)方程(*)的齊通解（含有待定系數(shù)q(n)（非齊特解），（待定系數(shù)由邊界條件唯一確定）求和中的通項與積分中的被積函數(shù)之間有什么樣的關(guān)系？項得上下界。示？答：T(n)=a*T(n/b)+f(n)若有 0, 使f(n)=O()f(n)的量級多項式地小于的量級), 則T(n)=()。若f(n)= () (即f(n)的量級等于

5、的量級), 則T(n) =()3)若f(n)= (), 則T(n)=( ) 0,f(n)= () +)(aLogbn(f(n)的量級多項式地大于的abLognc2時，可以把n個數(shù)據(jù)元素分為大致相等的兩半， 一半有n/2 個數(shù)據(jù)元素而另一半有n/2 個數(shù)據(jù)元素。先分別找出各自組中的最大元和最小元然后將兩個最大元進行比較就可得n個元素的最大元；將兩個最小元進行比較，就可得n個元素的最小元。（比較次數(shù)么情況下可以達到下界？答：在規(guī)模為n3n/2-2n=2kn2kn 2（e.g. 42=32+8+2），則算法的時間復(fù)雜度仍可達到 3n/2-2。如何用分治法求兩個nxyn=2kxa2n/2+b，yc2n

6、/2+da, c, d 均為 n/2 位二進制數(shù)。 于是 x*y= (a2n/2+b) (c2n/2+d) = ac2n +(ad+bc)2n/2 + bd，計算式ac2n + (ad+bc)2n/2 + bd中的ad+bc可寫為： 而(ad+bc)= (a+b) (d+c) - ac - bd, 因此在ac和bd計算出之后， 只要再做4 次加減法，一次（n/2位數(shù)的）乘法就可以計算出ad+bc。 而原來計算(ad+bc) 需要做2次乘法、一次加法； 新的計算公式比原方法少做了一次乘法。T(n)=3T(n/2) + (n)， 即 a=3, b=2, f(n)= (n) 。 此 時 有 ：= =

7、 并仍有f(n)=O()，)(aLogbn于是有T(n)=(n1.59)， 比(n2)要好不少。200Select（k）算法的主要思路。答：1.S50，k2.nn/55553（間元）得到一個長為n/5MM|M|/2小的數(shù)（中位數(shù)），記為 mS，O(n)simsi3，S1S2m；S3m。k（S2m）：k|S1|；|S1|S1|+|S2|。 下面針對這三種情況分別進行討論。6.ak|S1|kS1km3n/10-6S1 m，S17n/10+6|S1|7n/10+6。Select（k,S1）T(7n/10+6)。6.b：若|S1|S1|+|S2|，則第km，因此在S3S3k-|S1|-|S2|Sele

8、ct（k-|S1|-|S2|, S3），Skm3n/10-61T(n)分別為什么？1p+qT(n)=T(p*n)+T(q*n)+a*np+q答：T(n)a*n*k=0(p+q)k矩陣相乘算法目前最好的時間復(fù)雜度是多少？O（n2.376） 18StrassenA，B4n/2C11=A11B11+A12B21, C12=A11B12+A12 C21=A21B11+A22B21, C22=A21B12+A22B22同時引入下列 Mi(i=1,2.7)則計算兩個n7n/27T(n/2), 18n/2T(n)=7T(n/2)+ (n2),由主定理T(n)= (n2.81).Strassen （n3）得固

9、定看法。19200300關(guān)鍵？該算法是否可改進？答：主程序算法：nnxyXYXnxxyXiXjYiYjxyXO(1)時間對其實現(xiàn)分拆。（ (n log n)） 將數(shù)組INDINDi=i（i=1,2,n）INDxy 坐標(biāo)的對應(yīng)關(guān)系的機制， INDiyYix XYnyyxYiYjIND iIND jyYi之O(1)xYiXIND iyx調(diào)用子程序FCPP(1,n,X,Y,IND, ,p,q) 就可求得n FCPP33y然后進行分治，求得兩邊的 L和 R，從而求得 。 求出分割線，掃描當(dāng)前的所有點，把落到2 帶狀區(qū)域內(nèi)的點找出來， 并使這些點的y坐標(biāo)仍然保持從小到大的次序。對落到2帶狀區(qū)域內(nèi)的每一個

10、點檢查其后面的7個點若有距離更近的點對，則把最小距離 （及最近點對(p,q)）更新， 執(zhí)行完畢時，最小距離 及最近點對(p,q)就得到了。FCPP(j,k,X,Ypres,INDpres, ,p,q)中的參數(shù)說明： Xnxj,kXk-j+1y（已按從小到大的次序排好）INDpresk-j+1，INDpresiyYpresi的xX ,p,qk-j+1 和最近點對(p,q)。算法中的幾個關(guān)鍵點：分割線的尋找和最小距離相關(guān)的比較次數(shù)的判定p7況可以考慮減小比較次數(shù)。DFTn=2m什么是快速傅立葉變換（FFT）？FFT2(nlogn)DFTFFT.2ab2a b（n=2m.2n2DFT，所得到兩個向量

11、2nDFT-1,2c什么是平衡？分治法與平衡有著什么樣的關(guān)系？謂的平衡。分治法與動態(tài)規(guī)劃法之間的相同點是什么？不同之處在哪些方面？答：與分治法類似，動態(tài)規(guī)劃法 也是把問題一層一層地分解為規(guī)模逐漸減小的同類型的子問題。簡述求矩陣連乘最少乘法次數(shù)的動態(tài)規(guī)劃算法（300答：按照做最后一次乘法的位置進行劃分，該矩陣連乘一共可分為 j-i 種情況即有(j-i)種斷開方式： Mi(Mi+1Mj)，(MiMi+1)(Mi+2Mj)，(MiMi+1Mj-1)Mj。其中任一對括號內(nèi)的矩陣個數(shù)（即規(guī)模）不超過 j-i。j-i(MiMk)和(Mk+1Mj)mk+1,j。 于是，形為(MiMk)(Mk+1Mj)的矩陣

12、連乘所需的最少乘法次數(shù)為：mik+mk+1,j+ri-1rkrj。 此式中的所有參加運算的數(shù)均已知， 故此式O(1)ikjj-iMiMi+1Mj-1Mj（ij）mijO(j-i)時間里完成。mii=0（相當(dāng)于單個矩陣的情況）， 然后首先求出M1M2,M2M3,Mn-1Mnmi,i+1(i=1,2,n-1),ri-1riri+1,mii=mi+1,i+1=0； 再利用這些結(jié)果和（*）M1M2M3, M2M3 M4, , Mn-2Mn-1Mnmi,i+3(i=1,2,n-3)， mi,i+4(i=1,2,n-4)，m1,nM1M2Mn-1Mn能夠用動態(tài)規(guī)劃法求解的問題通常具有什么樣的特征？答：若一

13、個問題可以分解為若干個高度重復(fù)的子問題， 且問題也具有最優(yōu)子結(jié)構(gòu)性質(zhì)，就可以用動態(tài)規(guī)劃法求解： 以遞推的方式逐層計算最優(yōu)值并記錄必要的信息， 最后根據(jù)記錄的信息構(gòu)造最優(yōu)解。LCSCi,j為什么需要這樣計算？ZX，Z0CI,j=maxCi-1,j,Ci,j-1i,j0 xi!=yiC，Ci,jXiYjLCSCi,jCi-1,j-1,Ci-1,jCi,j-1均已Xi=YjXiYj，Ci,jLCS(Xm-1，Y)LCS(X，Yn-1)LCS(Xm-1，Yn-1)的長度, 因而具有重疊LCSLCS200300為關(guān)鍵？cijTijci,k-1Ti,k-1ck,jTk,jak(i+1kj)Ti,k-1，

14、Tk,jTi,k-1akwi,k-1，wi,k-1，ck,j+wk,jak0，pkak+pk-1+qk-1， wk,j=qk+pk+1+qk+1+pj+qj， 從 而 有 wi,k-1+wkj+pk = qi+pi+1+qi+1+pk-1+qk-1+ pk +qk+pk+1+qk+1+pj+qj = wij。 由此得到以ak 為根、耗費最小的樹的總耗費為：ci,k-1+ckj+wi,jpi（i=1,2,n）qj（j=0,1,2,n）wi,j-1 wi,j= wi,j-1+pj + qjwijci,k-1ckjakO(1)bi，ai+1，bi+1，aj，bjTij。 因此，最優(yōu)子樹Tijcij=

15、cminj k i j k i i,-1+ckj+wijcijTij的根的算法CijWij得出的。有了 Tij 的根的序號后，如何構(gòu)造出最優(yōu)二分搜索樹？Tijak (rijkBuild-tree(i,j,r,A) /*Tij*/If ij return nill; pointernewnode(nodetype); krij; /* 必 有 i 0 then if EDk為Nothen /*作業(yè) Dk放在當(dāng)前最左空位*/ FiDk; i1; EDk 置為Yeselse if E-Dk為Nothen /*作業(yè)-Dk放在當(dāng)前最右空位*/Fj-Dk; j1; E-Dk 置為Yesk1；什么是備忘錄方

16、法？它在什么情況下使用較為有效？答：若有大量的子問題無需求解時，用備忘錄方法較省時。但當(dāng)無需計算的子問題只有少部分或全部都要計算時，用遞推方法比備忘錄方法要好（如矩陣連乘，最優(yōu)二分搜索樹）答：若沒有內(nèi)部名，則每次合并時兩個集合中的所有元素均要改名（n-1UnionO(n2) 。要點。n大的代價，但利用平攤分析后對整體考慮， 可以得到較小的平均代價。平攤分析方法主要有：聚集方法，會計方法和勢能方法。n每一類耗費的總和， 然后再把各類耗費總加起來。的費用，以達到簡化代價計算的目地。CiiD0DiiDi-1 ， (Di)Di定義第 i 個操作的平攤代價為：= Ci +( (Di)- (Di-1)（即

17、實際代價加上勢的變化），為什么樹結(jié)構(gòu)下執(zhí)行 O(n)條帶路徑壓縮的 Union-Find 指令只需要O(n*G(n)時間？O(n)Find1） O(n)FindO(n)FindO(n)FindFindFind 指令只會碰到一個根（及其兒子），O(n)FindO(n)，樣，根及其兒子的費用已全部計算在內(nèi)。ik (0km-2)ik+1ikG(n)FindO(n)FindO(n*G(n)。路徑費用：由于其秩在組號為gn/F(g)，中的結(jié)點的收取的路徑費用 不超過n/F(g)*F(g)-(F(g-1)+1)cn， 即算法在最壞情況下不是線性的。用200300Link(v,rWeightWeightr改

18、。（LinkrvvTrv之下，TvTvWeight）TrWeight設(shè)用 Find-Depth 指令可以查到 v 的深度為 Depth(v)，（Depth(vFind-Depth）rDepth(r)=0（也是值）。執(zhí)行 Link 指令后，把 r 作為 v 的兒子，則此時在原先的森林中，rDepth(v)+1D-森林中，rs。由 Weight 的性質(zhì)，在 D-森林中的 2 棵樹合并之前，有：rsWeightr=0(rD-森林中的 2 棵樹合并之后，在原先森林中 r 的深度為rsWeightr+Weightv（WeightrDepth(v)+1，rsWeightr+Weightv= Depth(v

19、)+1由上述兩式可得：Weightr=Depthv+1-WeightvWeightr。TrrTrWeight只要 r的新 Weight 值正確，Tr2、Countvk then 輸出i*/輸 出 i 被 第 j 條 E 指 令 所 刪 除 ； UNION(j，Succj，Succj)； SuccPredjSuccj；/*jPredSuccjPredj UnionfindLas VegasMonte Carlo隨機算法有哪些優(yōu)點？答：LasVegas但在少數(shù)應(yīng)用中，可能出現(xiàn)求不出解的情況。此時需再次調(diào)用算 法進行計以及調(diào)用一次產(chǎn)生失?。ㄇ蟛怀鼋猓┑母怕?。Mont Carlop（p1。通過算法的反

20、復(fù)執(zhí)行（即以增大算法的執(zhí)行時間為 代價），能夠使發(fā)生錯誤的k隨機算法的優(yōu)點：已知的、最好的確定性算法要好。是極為簡單的。它不依賴于某種固定的模式，只是由于運氣不好才出現(xiàn)此種情況。k答：Random Sampling（Las Vegas）n（1，2， n），n 個數(shù)中隨機地m（mn）nBii，若Bi為未iBim 個不同的數(shù)全部被選出為止。找第 k 小元素的隨機算法（Las Vegas 算法）：nAi=x,n-1xS1(元素均0r+ij+1RASPRAM 模擬 TM 的方法如下圖：TMkr1rkjC(j)jjRAMa0k分別為a0,b0,z0）ckk帶上的次格內(nèi)容（a1,b1,z1）；因此，TMj

21、RAMc+k*C(j)+j（C(j)j0）e.g.：1c+k*1+2TM 模擬 RAM 的方法如下圖：5TMRAM10RAM2RAMr0 34RAM5Turing答：Turing遞歸可枚舉集（完全）遞歸集原始遞歸集部分遞歸函數(shù)完全遞歸函數(shù)原始遞歸函數(shù)非確定性 Turing 機與確定性 Turing 機的主要區(qū)別在什么地方？DTM，NDTMQTk（qi, a1, a2, , ak）， Q(TL,R,S)kQ(TL,R,S)kDTMDTMIDID0 ID1 ID2 NDTMID（因為在每個格局都可能有多個選擇。NDTMn（n2）NDTMn非確定性 Turing 機的時間復(fù)雜度是如何定義的？答：ND

22、TMT(n): 對于可接受的輸入串， T(n)=max關(guān)于輸入 的時間復(fù)雜度 | 的長為nNDTM 最短路徑長度，然后對這些長度求最大。PNPTuringP NPP=L|LDTM受的語言NP=L|LNDTMNDTMNPSAS，SAA對判定問題類AAS（SA，F(xiàn)，對S F 是否AANP（NDTMNPPNPCookLL00（字符串的集合f：*，滿足1） *， Lf()L0；若的長為則f()的長不超過這里PL(n)是一個多項式；*， n，f (p(n)算。則稱 L 可多項式變換為 L0，記作 Lp L0。CookKarpKarpCook。CookKarpKarp定義簡潔，CookNPNPNP-har

23、d答：NP-完全性語言1（狹義，Karp）：2L0NP-C1)L0NP; 2) LNP，LpL0。NP-L0NP-C的， 則稱該問題是 NP-C 的。有些最優(yōu)化問題（ L0）NP2要求：LNP，Lp L0NP-hardNP-20NP-NP-hardDTMNP-CNPDTMP=NPNPDTM（PNP）， NP-CDTM即有 NP-CP= 。AIAAI(ratio factor)=RA(I)=maxA(I)/OPT(I),OPT(I)/A(I)由于是取 max，故近似比總是大于等于 1 的。絕對近似比rA=InfRA(I) 對一切 即算法A 對于一切實例I 的近似比的最小上界（相當(dāng)于最大值）。rA

24、=supr1|n0，OPT(I)n0例，都有r 即反映了近似比的收斂情況，它允許OPT(I)rA。什么是多項式時間近似方案（PTAS）？什么是完全多項式時間近似方案（FPTAS，F(xiàn)PAS）？答多項式時間近似方案（PTAS,PolynomialTimeApproximation設(shè)是求解某類問題的多項式時間近似算法， 0 的絕對近似比1 APTAS。完全多項式時間近似方案 （FPTAS，F(xiàn)PAS, Fully Polynomial Time Approximation Scheme）PTASp(|I|,1/ )為時間復(fù)雜度上界，則稱是一個FPTAS。什么是偽多項式時間的算法？如何用動態(tài)規(guī)劃法求解背

25、包問題？In，max(I)，p(n,max(I)為上界， 則稱該算法是偽多項式時間的算法。動態(tài)規(guī)劃法。對 0kn，0bB，設(shè) f(b)為：kb因此，f(B)就是該問題的最優(yōu)解。根據(jù) f(b)的定義可知子問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。0 x，xk,bb，uk，1，0k=0(b)=0（0bB），此為遞推計算的基礎(chǔ)值。設(shè)對 b0,B，(b)，(b)， ，f(b)均已計算出來，此時需要對區(qū)間0,Bb（0bB），逐一求出(b)bsk若 b (bukxk,b1，fk (b)fk-1 (b-sk)+ckxk,b0，fk (b)fk-1 (b)。k=n，b=B(B)O(nB)。xb=Bj=nxj,b：xj,b=0u

26、jjj-1； xj,b=1ujjS（S然后執(zhí)行 bb-sj 以及 jj-1。j=1O(n)O(nB)。BnnB因此，算法是偽多項式時間的算法。NP 的假定之下，可以分成哪 4 類（舉例）？ NP-hard 問題在 P答：NP-hardPNP41FPTAS（e.g.Knapsack）2、 有 PTAS 而沒有 FPTAS（e.g. k-Knapsack）3、 沒有 PTAS，但有絕對近似比為常數(shù)的近似算法(Bin-Packing)4、 沒有絕對近似比為常數(shù)的近似算法(e.g. TSP)為什么當(dāng) k2，k 背包問題不存在 FPTAS，除非 P=NP？答：反證法：設(shè)A是該問題的FPTAS，時間復(fù)雜度

27、上界為P(|I|,1/ 對每個實例I，令 =1/2ncmax，將I和作為A的輸入，AFPTAS，OPT(I)(1+ )A(I)，0OPT(I)-A(I) A(I) ncmax=。但OPT(I)A(I)都是正整數(shù)，OPT(I)=A(I)，A(I)p(n，2ncmax)AkA：kI，nsj (1jn)， kI：jsj，價值 cj=1(1jn)，背包容量 Bi=(1ik)。I AIOPT(I)=n（k）時，A對 I 回答為Yes。注意，k 等分割有解 iff A回答為YesIIO(n)時間，|I|=|I|=n，=， Ap(n,)=p(n,2n)，n，AkNP-CP=NP，與 PNP 矛盾。結(jié)論：假設(shè)

28、 PNP，則 k 背包問題沒有 FPTAS。2014算法設(shè)計與分析課程試題題庫含答案1、一個算法應(yīng)有哪些主要特征？又窮性，確定性，可行性，0 個或多個輸入，一個或多個輸出2、分治法and Conquer）與動態(tài)規(guī)劃Programming）有什么同？從新求解。3、 試舉例說明貪心算法對有的問題是有效的，而對一些問題是無效的。貪心算有效性：最小生成樹、哈弗曼、活動安排、單元最短路徑。無效反例：01 背包問題，無向圖找最短路徑問題。4、求解方程f(n)=f(n-1)+f(n-2)，f(1)=f(2)=1由 f(n)=f(n-1)+f(n-2)可得f(n)-f(n-1)-f(n-2)=0,可得方程的特

29、征方程為x 2 x 1 0,x x12,則可得x x115 ,21515f (n) c1()n 2c ()n22又f f (2) 可得551155f c 21c12 f (2) (15 )2 c (15)2c1可得c12122 a,cb5525511f (n) a()n b()n225、求解方程T(n)=2T(n/2)+1，T(1)=1，設(shè)。T (n) (n / 2) 12T (n / 2) 22 T (n / 22 ) 222 T (n / 22 ) 23 T (n / 23 ) 22.2k 1 T (n / 2k 1 ) 2k T (n / 2k ) 2k 1上面所有式子相加，相消得T(n

30、) 2k T20 21 22 2k1 2k 2k1* 1 2 2k 16、編寫一個Quick Sorting 算法，并分析時間復(fù)雜性。int part(int *a,int p,int r) int i,j,x,t;x=ar; i=p-1;for(j=p;j=r-1;j+) if(aj=x)i+;t=ai; ai=aj;aj=t;t=ai+1; ai+1=ar; ar=t; return i+1;void quicksort(int *a,int p,int r) int q;if(pr) q=part(a,p,r);quicksort(a,p,q-1); quicksort(a,q+1,r)

31、;快速排序時間復(fù)雜度最壞情況為O(n2) ,平均為 O(nlogn);7、利用Quick Sorting的原理，編寫一個查找第k 小元素的算法K不能大于數(shù)的長度。int part(int *a,int p,int r) int i,j,x,t;x=ar; i=p-1;for(j=p;j=r-1;j+) if(ajk)return k_last(a,i,mid-1,k); else if(mid+1)k)return k_last(a,mid+1,j,k);8、編寫一個Heap Sorting 算法，并分析時間復(fù)雜性。void max_heapify(int *A,int i)/int larg

32、est,t,l,r;l=2*i;r=2*i+1; if(lAi) largest=l; else largest=i;if(rAlargest) largest=r; if(largest!=i)t=Ai;Ai=Alargest; Alargest=t; max_heapify(A,largest);void build_max_heap(int *A,int lenth)/int i;heap_sizeA=lenth; for(i=lenth/2;i=1;i-)max_heapify(A,i);heapsort(int *A,int lenth) int i,t;build_max_heap

33、(A,lenth); for(i=lenth;i=2;i-)t=A1;A1=Ai;Ai=t;heap_sizeA-; max_heapify(A,1);9、編寫一個算法，可以檢測一個字符串是否回文（如：afaddafa，abwba 等。int fun(char *A,int n) int i ,j;i=0,j=n-1; while(i=j)if(Ai!=Aj)break; i+;j-;if(i=j)return 0;else return 1;10、如果是檢測一個字符串中是否包含一個回文子串，應(yīng)如何編寫算法。如果找最大的回文子串呢？int judge(char *A,int n0, int n

34、1) int i,j;i=n0;j=n1;while(i=j) if(Ai!=Aj)break; i+;j-;if(i=j)return 0;else return 1;int fun(char *A,int n) int i,j,k; for(i=1,i=n-1;i-)for(j=0;j=1;i-)for(j=0;j=n-i-1;j+) if(fun(&A,j,i+j)=1)output(&A,j,i+j);return 1;return 0;此時最先找到的即為最大回文。11、設(shè)n個不同的整數(shù)排好序后存在數(shù)組T1n中若存在一個下標(biāo)i使得i設(shè)計一個有效的算法找到該下標(biāo)。要求時間復(fù)雜性是O(lo

35、gn)。void fun()int low=1,high=n,mid; mid=(low+high)/2; while(lowmid)high=mid-1; else low=high+1; mid=(low+high)/2;if(low=high)printf(“%d”,mid);12、編寫一個采用KMP 的算法查找T的子串并判斷匹配失敗的字符是否在P中，以此確定可滑動的最大距離。T1lenthT，P1lenthP； int next100;int lenthT,lenthP;void get_next(char *P) int i,j;i=1;j=0;next1=0;while(i=len

36、thP) if(j=0|Pi=Pj)+i;+j;if(Pi!=Pj) nexti=j; else nexti=nextj;else j=nextj;int KMP(char *T,char *P) int i,j;i=1;j=1;get_next(P); while(i=lenthT&jlenthP)return i-lenthP; else return 0;13、考慮一個“模糊”的算法查找T 的子串P，先快速找到與P 相似的子串，進一步確認之。int new_get_index(char *T,char *P)int a,b,c; a=0;b=strlen(p);c=(a+b)/2; in

37、t k=0;while() if(Pa!=Tk+a|Pb!=Tk+b|Pc!=Tk+c)k+;continue; for(int j=0;jb;j+)if(Pj!=Tj+k)break;if(j=b)return k;14、設(shè)計一個算法確定K個矩陣相乘的最優(yōu)次序，并分析該算法的時間復(fù)雜性int m100100;int s100100;void fun(int *p,int n) int i,j,k,l,q;for(i=1;i=n;i+) mii=0; for(l=2;l=n;l+)for(i=1;i=n-l+1;i+) j=i+l-1; mij=32767;for(k=i;k=j-1;k+)

38、q=mik+mk+1j+pi-1*pk*pj; if(qmij)mij=q;sij=k;n時間復(fù)雜度為(n2) n2152 次比較。#include stdafx.h #includestdio.h #define N 100int bN; int l=0;int Max(int *a,int m,int n)/求最大值int x1,x2; if(n-m=am)bl=am;l+;return n; elsebl=an;l+;return m;else x1=Max(a,m,(m+n)/2);x2=Max(a,(m+n)/2+1,n); if(ax1=ax2)return x1; else re

39、turn x2;int Min(int *b,int m,int n)int x1,x2; if(n-m=1)if(m=n)return m;else if(bnbm)return n; else return m;/求最小值elsex1=Min(b,m,(m+n)/2);x2=Min(b,(m+n)/2+1,n); if(bx1=bx2)return x1; else return x2;void main()int aN;int s,i,n;printf(Please input the number :);scanf(%d,&n); printf(Please input :); for

40、(i=0;in;i+)scanf(%d,&ai);s=Max(a,0,n-1); printf(Max: s=Min(b,0,l-1); printf(Min: 16A1：n并思考為什么是這樣的結(jié)果。大家自己看看，呵呵！17、在一個數(shù)組中出現(xiàn)次數(shù)最多的元素稱為“眾數(shù)，編寫一個找出眾數(shù)的算法并分析算法時間復(fù)雜性。int most(int a,int length)/length 數(shù)組長度int i,j,k;int max,value;int num100100; num00=a0;num01=1; j=0;for(i=1;ilength;i+)for(k=0;kj)j+;numj0=ai;num

41、j1=1;max=0; for(k=;kmax)max=numk1;value=numk0;return value;/出現(xiàn)次數(shù)最多的數(shù)字18、設(shè)計一個使用Hash法的算法在數(shù)組中找出“眾數(shù)，并分析時間復(fù)雜性 Hash(long T,int n)struct node *temp,*p; struct node *array1000; int i,temp,num;int max=1; num=sqrt(n);for(i=0;inext=NULL; for(i=0;ielem=Ti;p-count=1;p-next=NULL; arraytemp-next=p;elsep=findinlink

42、(head,Ti);if(p=NULL)p=create();p-elem=Ti;p-count=1;p-next=NULL; addtolink(head,p);elsecount+;找到該元素if(p-countmax)max=p-count;19、設(shè)計一個時間復(fù)雜性不超過的算法找出n 個數(shù)組成的序列中最長的調(diào)遞增序列。typedef struct lenint start; int end; int lon;Len;void longest(int a)Len first,second; int i,j; first.lon=0;i=0;while(1)second.start=i; s

43、econd.lon=1; while(aifirst.lon)first.start=second.start; first.end=second.end; first.lon=second.lon;i+;out: if(first.lonsecond.lon)first.start=second.start; first.end=second.end; first.lon=second.lon;/*輸出 first 的結(jié)果*/20、從1，2， ，n 中找出所有質(zhì)數(shù)，設(shè)計一個比較優(yōu)的算法。int Bn; void fun()int i,j,k,s0=0,s1=0;B0=2;B1=3; k=1;

44、for(i=6;i=n;i+=6) for(j=1;j=k;j+)if(s0=0&(i-1)%Bj=0)s0=1; if(s1=0&(i+1)%Bj=0)s1=1;if(s1=1&s0=1)break;if(s0=0)k+;Bk=i-1;if(s1=0)k+;Bk=i+1;for(i=0;i=k;i+) printf(%d ,Bi);if(i+1)%10=0)printf(n);printf(n);21、測試一個圖是否連通圖，可以用深度優(yōu)先搜索算法或?qū)挾葍?yōu)先搜索算法，什么情況下，用哪種算法更好一些？2223242526試求圖中所有點對之間的所有路徑，并找出兩點之間最短的路徑。二叉檢索樹的主要問

45、題是樹高，編寫一個控制檢索樹樹高的算法。試寫一個在 23 樹上刪除一個節(jié)點的算法。采用深度優(yōu)先算法找出一個無向圖的所有雙向連通分支。編寫一個算法，找出一個有向圖的所有強連同分支。int N=4; int int visited100=0; int f100;int cout=0;void DFS(int v,int s) int j; visitedv=1;sign+;fcout=v;cout+;/fnif(s=1)printf(%d ,v); for(j=0;jN;j+)if(Gv-1j=1)/如果 Gv-1j有通路且未被訪問者訪問之if(!visitedj+1) if(s=0)DFS(j+

46、1,0);else DFS(j+1,1);void fun()int v,i,j,t;for(v=0;vN;v+)if(!visitedv+1)DFS(v+1,0); /第一次深度優(yōu)先遍for(i=0;iN;i+)/矩陣轉(zhuǎn)置for(j=i+1;jN;j+)/N 為圖中節(jié)點數(shù)t=Gij;Gij=Gji;Gji=t;for(i=0;i=0;i-)if(!visitedfi)DFS(fi,1);if(i!=cout-1)printf(n);27、為什么查找連通分支的算法總是采用深度優(yōu)先算法，采用寬度優(yōu)先算法可嗎？為什么？28、編寫找出一個網(wǎng)絡(luò)的最大流的算法。#include #include usi

47、ng namespace std; const int maxN=201;static int edgemaxNmaxN; bool visitedmaxN;int fathermaxN;int N, M; /邊數(shù),頂點數(shù)int ans; /結(jié)果void Ford_Fulkerson( )while(1)/一次大循環(huán),找到一條可能的增廣路徑queue q;memset(visited, 0, sizeof(visited);memset(father, -1, sizeof(father); int now;visited0 = true; q.push(0);while(!q.empty()

48、/廣度優(yōu)先now = q.front(); q.pop();if(now = M-1) break; for(int i = 0; i M; i+)/每次父親節(jié)點都要更新,0 的邊就不算了if(edgenowi & !visitedi)fatheri = now; visitedi = true; q.push(i);/if(!visitedM-1) break; int u, min = 0 xFFFF;for(u = M-1; u; u = fatheru)/找出權(quán)值最小的邊if(edgefatheruu N M)ans = 0;memset(edge, 0, sizeof(edge);

49、for(int i = 0; i s e w; edges-1e-1 += w;Ford_Fulkerson(); cout ans endl;return 0;29、采用最大流算法編寫一個二分圖的最大匹配算法。#include stdafx.h #include #define N 6#define L 3#define R 3using namespace std; bool RToL(int);int mapNN = 0,0,0,1,1,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;int lienN = -1;int matchedN = 0;bool LToR(int curPoint)/左邊的點找右邊可以連接的點for(int i=L; iN; i+)/對每個右邊的點if(mapcurPointi & lieni = -1)/如果未進入鏈里liencurPoint = i;/這個點連接到右邊的點i