1、東南大學算法設計與分析課程考試復習試題題庫及答案1什么是基本運算？ 答：基本運算是解決問題時占支配地位的運算(一般1 種，偶爾兩種)；討 論一個算法優(yōu)劣時，只討論基本運算的執(zhí)行次數(shù)。2 什么是算法的時間復雜性(度)？ 答：算法的時間復雜性(度)是指用輸入規(guī)模的某個函數(shù)來表示算法的基本 運算量。T(n)=4n33什么是算法的漸近時間復雜性？ 答：當輸入規(guī)模趨向于極限情形時(相當大)的時間復雜性。4表示漸進時間復雜性的三個記號的具體定義是什么？答：1. T(n)= O(f(n)：若存在c 0和正整數(shù)nOl,使得當n2n0時， 總有T(n)Wc *f(n)。(給出了算法時間復雜度的上界，不可能比c*

2、 f(n)更大)T(n)二Q (f(n):若存在c 0，和正整數(shù)n01,使得當n三n0時， 存在無窮多個n ,使得T(n)$c*f(n)成立。(給出了算法時間復雜度的下界， 復雜度不可能比 c*f(n) 更小)T(n)= 0 (f(n):若存在cl,c20，和正整數(shù)n01，使得當n三nO 時，總有T(n)Wc1 *f(n), 且有無窮多個n,使得T(n)$c2 *f(n)成立，即： T(n)= O(f(n)與T(n)=Q (f(n)都成立。(既給出了算法時間復雜度的上界， 也給出了下界)5什么是最壞情況時間復雜性？什么是平均情況時間復雜性？答：最壞情況時間復雜性是規(guī)模為n的所有輸入中，基本運算

3、執(zhí)行次數(shù)為最 多的時間復雜性。平均情況時間復雜性是規(guī)模為n的所有輸入的算法時間復雜度的平均值 (一般均假設每種輸入情況以等概率出現(xiàn))。6一般認為什么是算法？什么是計算過程？答：一般認為，算法是由若干條指令組成的有窮序列，有五個特性a.確定 性(無二義) b. 能行性(每條指令能夠執(zhí)行) c. 輸入 d. 輸出 e. 有窮性(每條指 令執(zhí)行的次數(shù)有窮)只滿足前 4 條而不滿足第 5 條的有窮指令序列通常稱之為計算過程。7 算法研究有哪幾個主要步驟？主要從哪幾個方面評價算法？答：算法研究的主要步驟是1)設計 2)表示 3)確認，合法輸入和不合法輸 入的處理 4)分析 5 )測試評價算法的標準有 1

4、)正確性 2)健壯性 3)簡單性 4)高效性 5)最優(yōu)性8 關于多項式時間與指數(shù)時間有什么樣的結論？答：1. 多項式時間的算法互相之間雖有差距，一般可以接受。指數(shù)量級時間的算法對于較大的 n 無實用價值。9什么是相互獨立的函數(shù)序列？何時稱函數(shù)項“k(x)能被其它函數(shù)項線性表 出？答：設0(x),卩1(x),卩2(x), . ,|J n(x), .是某一數(shù)域上的函數(shù) 序列，(x的值以及J k(x) (k=0,l,2,)的值都在同一個數(shù)域中)任取J k(x) (k=0,l,2,)，不存在數(shù)域中的數(shù)a 1, a 2,，a p，使得j k (x) = a 1j i1(x) + a 2j i2 (x)

5、+ a pj ip (x)，即任何一個函數(shù)項J k(x)不能被其它函 數(shù)項線性表出。10根據(jù)特征根的情況，常系數(shù)線性遞歸方程的解有哪幾種不同的形式？答：1.若方程(*)恰有r個互不相同的特征根a 1，a 2,，a r (即iHj 時有a i#a j)，則齊次方程(*)的解為an=A1+ A2+Ar(齊通解，即齊次方 程的通解)(A1Ar為待定系數(shù)，可由r個連續(xù)的邊界條件唯一確定)若a 1，a 2是(*)方程的一對共扼復數(shù)根p和p， ei0 ei0 .則這兩 個根對應的解的部分為Ap ncos(n0 )+Bp nsin(n0 ) (A,B為實的待定系數(shù))若 a 是(*) 方程的 k 重根，則 a

6、 對應的解的部分為 C1a n+C2na n+C3 n2a n+Ck nkTa n (C1Ck為待定常數(shù))4若(*)方程中的f(n)工0(非齊次)，且q(n)是(*)的一個解，貝0(*)方程 的解為： (*) 的齊通解(含有待定系數(shù)) +q(n) (非齊特解)， (齊通解中的 待定系數(shù)由邊界條件唯一確定)11 求和中的通項與積分中的被積函數(shù)之間有什么樣的關系？答：求和中的通項的表達形式一般就是被積函數(shù)，一般用放縮的方法求得通 項得上下界。12主定理的內容是什么？根據(jù)主定理的結論，可以獲得哪些關于算法改進的啟 示？答：T(n)二a*T(n/b)+f(n)若有 0,使f(n)=O()(即f(n)的

7、量級多項式地小于的量級)，則 T(n)= 0 ()。若f(n)= 0 ()(即f(n)的量級等于的量級)，則T(n) =0 ()。若 f(n)二 0 (),則 T(n)=0 ()3)若有 0,使f(n)= () +)(aLogbn(即f(n)的量級多項式地大于的 量級)，且滿足正規(guī)性條件：abLogn存在常數(shù)c2時，可以把n個數(shù)據(jù)元素分為大致相等的兩半，一半有 n/2 個數(shù)據(jù)元 素，而另一半有 n/2 個數(shù)據(jù)元素。先分別找出各自組中的最大元和最小元, 然后 將兩個最大元進行比較，就可得n個元素的最大元；將兩個最小元進行比 較，就可得 n 個元素的最小元。求最大、最小元算法的時間復雜度(比較次數(shù)

8、)下界是多少？分治算法在什 么情況下可以達到下界？答：在規(guī)模為 n 的數(shù)據(jù)元素集合中找出最大元和最小元， 至少需要 3n/2-2 次比較，即3n/2-2是找最大最小元算法的下界。當n=2k，或當n工2k時，若n 是若干2的整數(shù)幕之和，(e.g. 42=32+8+2 )，則算法的時間復雜度仍可達到3n/2-2。15如何用分治法求兩個n位二進制數(shù)x和y的乘積？算法的時間復雜度是多少？答：若n=2k，則x可表為a2n/2+b, y可表為c2n/2+d (如圖)，其中a, b, c， d 均為 n/2 位二進制數(shù)。 于是 x*y= (a2n/2+b) (c2n/2+d) = ac2n + (ad+bc

9、)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) + 0 (n)，即 a=3, b=2, f(n)=0 (n)。此時有：二二 naLogbn32Lognl.59，并仍有 f(n)=O()， )(aLogbn 于是有 T(n)= 0 (nl.59)，

10、 比0 (n2)要好不少。16用200字概括Select (求第k小元)算法的主要思路。答：1.若S50，則采用堆排序的方法找出第k小的元素2將n個元素分成n/5組，每組5個元素對每個5元組進行排序，全部5元組排序后，從每組中取出第3個元素(中 間元)得到一個長為n/5的數(shù)組M遞歸調用Select(|M|/2,M)，即在M數(shù)組中找到第|M|/2小的數(shù) (中位數(shù))，記為 m依次掃描整個數(shù)組S,此項工作所需時間為0(n)。當 sim 時將 si 放入數(shù)組 S3；在得到的3個集合中，S1中的數(shù)均小于m；S2中的數(shù)均等于m； S3中的數(shù)均大于m。按照k值大小，共可分成下列三種情況(注意S2至少有一個元

11、素 m)： kW|Sl|；|Sl|Sl| + |S2|。下面針對這三種情 況分別進行討論。6.a：若kW|Sl|,則第k小元素必定在S1中。此時遞歸調用Select(k,Sl), 就可以獲得第k小元素。因大于等于m的數(shù)據(jù)元素至少有3n/10-6個，而S1 中的數(shù)均小于m,故S1中的數(shù)據(jù)元素至多有7n/10+6個，即|Sl|W7n/10+6。 因此，調用Select (k,S1 )的 時間復雜度不超過T(7n/10+6)。6.b :若|Sl|S1| + |S2|，則第k小元素必定大于m，因此在S3中。而且此時 該元素在 S3 中應為第 k-|S1|-|S2| 小的元素。 于是遞歸調用 Selec

12、t(k-|S1|-|S2|, S3)，就可以獲得S中的第k小元素。因小于等于m的數(shù)據(jù) 元素至少有 3n/10-6 個1的情況下，T(n)分別為什么？ 1及p+q時間復雜度為 T(n)=T(p*n)+T(q*n)+a*n 時，在 p+q答：T(n)Wa *n* Ek=0(p+q)k17矩陣相乘算法目前最好的時間復雜度是多少？答：目前矩陣乘法最好的時間復雜度是能做到0 ( n 2 . 3 7 6 )18 敘述 Strassen 矩陣相乘算法的主要思路和意義。答：把矩陣A，B分成4個規(guī)模為n/2的子矩陣快C11=A11B11+A12B21, C12=A11B12+A12C21=A21B11+A22B

13、21, C22=A21B12+A22B22同時引入下列 Mi(i=1,2.7)則計算兩個n階矩陣的乘法為7對n/2階矩陣的乘法(時間為7T(n/2), 以及18對n/2階矩陣的加減法則遞歸方程為T(n)=7T(n/2)+ 0 (n2),由主定理 得T(n)= 0 (n2.81). Strassen矩陣相乘算法意義在于打破了人們認為矩陣乘法 得時間復雜度為0(n3)得固定看法。19試用200300字概述尋找最近點對算法的主要步驟。該算法中有哪幾點最為 關鍵？該算法是否可改進？答：主程序算法：讀入n個點的坐標，這n個點的x坐標和y坐標 分別放在X, Y兩個數(shù)組中， 然后進行預處理：對X數(shù)組中的n個

14、x坐標值按從小到大的次序進行排序，排 序過程中保持 x 坐標和 y 坐標的對應關系：若Xi與Xj對換位置，則Yi與Yj也做相同的對換。另外，若兩個 點的x坐標相同，則y坐標值小的排前。X數(shù)組排好之后就固定了，以后不再 改變，以便在O( 1)時間對其實現(xiàn)分拆。(排序時間為0 (n log n)將數(shù)組 IND初始化為：INDi=i (i=l,2,-,n)。數(shù)組IND即是用來保持x坐標和y 坐標的對應關系的機制，INDi記錄的是 其y坐標值為Yi的點所對應的x 坐標在X數(shù)組中的下標。對Y數(shù)組中的n個y坐標值按從小到大的次序進行排 序，排序過程中保持y坐標和x坐標的對應關系：若Yi與Yj對換位置， 則

15、IND i與IND j也做相同的對換。這樣，當給了一個點的y坐標Yi之 后，就可以在O( 1)時間找到其對應的x坐標：Yi與XIND i就是該點的 y 坐標和 x 坐標。調用子程序FCPP(1,n,X,Y,IND,6 ,p,q)就可求得n個點中的最近點對(p,q) 和最小距離6。子程序FCPP的主要執(zhí)行過程：首先看當前處理的點數(shù)。若不 超過3個點，就直接進行相互比較。若超過3個點，則把點的y坐標分為兩部 分：左邊和右邊。然后進行分治，求得兩邊的6 L和6 R，從而求得6。求出分割線，掃描 當前的所有點，把落到26帶狀區(qū)域內的點找出來，并使這些點的y坐標仍然 保持從小到大的次序。對落到26 帶狀

16、區(qū)域內的每一個點檢查其后面的7個點， 若有距離更近的點對，則把最小距離6 (及最近點對(p,q)更新，執(zhí)行完畢 時，最小距離6及最近點對(p,q)就得到了。子程序FCPP(j,k,X,Ypres,INDpres,6 ,p,q)中的參數(shù)說明：X數(shù)組存放已 排好序的n個點的x坐標。j,k為當前處理的X數(shù)組一段中的最小和最大下標。 Ypres數(shù)組存放當前處理的k-j+1個點的y坐標(已按從小到大的次序排好)。 INDpres數(shù)組的長度也是k-j+1， INDpresi記錄了其y坐標值 為Ypres i的 點的x坐標在X數(shù)組中的下標值。6 ,p,q均為返回值，給出當前處理的k-j+1 個點中的最小距離

17、6和最近點對(p,q)。算法中的幾個關鍵點：分割線的尋找和最小距離相關的比較次數(shù)的判定算法可以優(yōu)化：比如對 p 點之后的7 個點檢查時未考慮兩點均屬同一側的情 況可以考慮減小比較次數(shù)。做 DFT 時，是否總假定有 n=2m？答：是個，總有 n=2m什么是快速傅立葉變換(FFT)?如何用FFT來計算2個多項式的乘積？答：能在0 (nlogn)時間里完成DFT的算法就稱為FFT.給了2 個多項式的系數(shù)向量 a 和 b 之后，若其系數(shù)不是 2 的冪次，則將 a 和b的規(guī)模擴大(向量最后加若干個0)使得n=2m.然后把這兩個向量維數(shù)再擴 大一倍，得到兩個維數(shù)為2n的向量。分別對2個向量做DFT，所得到

18、兩個向量 進行點乘，再對結果做2n階的DFT-1,即可求得2多項式相乘后的多項式系數(shù)c什么是平衡？分治法與平衡有著什么樣的關系？答：在使用分治法和遞歸時，要盡量把問題分成規(guī)模相等，或至少是規(guī)模相 近的子問題，這樣才能提高算法的效率。使子問題規(guī)模盡量接近的做法，就是所 謂的平衡。分治法與動態(tài)規(guī)劃法之間的相同點是什么？不同之處在哪些方面？答：與分治法類似，動態(tài)規(guī)劃法 也是把問題一層一層地分解為規(guī)模逐漸減 小的同類型的子問題。動態(tài)規(guī)劃法與分治法的一個重要的不同點在于，用分治法分解后得到的子問 題通常都是相互獨立的， 而用動態(tài)規(guī)劃法分解后得到的子問題很多都是重復的。 因此，對重復出現(xiàn)的子問題，只是在第

19、一次遇到時才進行計算，然后把計算所得 的結果保存起來；當再次遇到該子問題時，就直接引用已保存的結果，而不再重 新求解。簡述求矩陣連乘最少乘法次數(shù)的動態(tài)規(guī)劃算法(不超過 300字)答：按照做最后一次乘法的位置進行劃分，該矩陣連乘一共可分為j-i種情況即有(j-i)種斷開方式：Mi(Mi+lMj),(MiMi+l)(Mi+2Mj),，(MiMi+lMj-l)Mj。其中任一對括號內的矩陣個數(shù)(即規(guī)模)不超過j-i。由于在此之前我們已知 任一個規(guī)模不超過j-i的矩陣連乘所需的最少乘法 次數(shù)，故(MiMk)和(Mk+1Mj)所需的最少乘法次數(shù)已知，將它們分別記之為 mik和mk+l,j。于是，形為(Mi

20、Mk)(Mk+lMj)的矩陣連乘所需的最少乘法次數(shù) 為：mik+mk+l,j+ri-lXrkXrj。此式中的所有參加運算的數(shù)均已知，故此式 在0( 1)時間里即可完成計算。對滿足iWkj的共j-i種情況逐一進行比較， 我們就可以得到矩陣連乘MiMi+1Mj-1Mj (ij)所需的最少乘法次數(shù)mij為：mij二min (iWkj) mik+mk+1,j+riTXrkXrj, (*) 其計算可在 0(j-i) 時間里完成。于是在初始時我們定義mii=0 (相當于單個矩陣的情況)，然后首先求出 計算M1M2, M2M3,，Mn-1Mn所需的乘法次數(shù)mi,i+l(i=l,2,n-1),具體數(shù) 值為ri

21、-lXriXri+1,因mii= m i+1, i+1=0；再利用這些結果和(*)式，就 可以求出計算M1M2M3, M2M3 M4,，Mn-2Mn-1Mn所需的最少乘法次數(shù) mi,i+2(i=l,2,n-2)。同理，可依次算出 mi,i+3(i=l,2,n-3)， mi,i+4(i=l,2,n-4)，直至算出m1,n即M1M2Mn-1Mn矩陣連乘所需的 最少乘法次數(shù)。能夠用動態(tài)規(guī)劃法求解的問題通常具有什么樣的特征？答：若一個問題可以分解為若干個高度重復的子問題， 且問題也具有最優(yōu) 子結構性質，就可以用動態(tài)規(guī)劃法求解： 以遞推的方式逐層計算最優(yōu)值并記錄 必要的信息， 最后根據(jù)記錄的信息構造最優(yōu)

22、解。什么是最長公共子序列問題？在求LCS的算法中，Ci,j是如何計算的？ 為什么需要這樣計算？答：若ZX，Z0 且 xi=yiCI,j=maxCi-1,j,Ci,j-1若 i,j0 且 xi!=yi二維數(shù)組C，用Ci,j記錄Xi與Yj的LCS的長度 如果我們是自底向上進 行遞推計算，那么在計算Ci,j之前，Ci-1,j-1, Ci-1,j與Ci,j-1均已 計算出來。此時我們 根據(jù)Xi=Yj還是Xi#Yj，就可以計算出Ci,j。計算的理由：求LCS(Xm-1，Y)的長度與LCS(X，Yn-1)的長度 這兩個 問題不是相互獨立的：兩者都要求LCS(Xm-1， Yn-1)的長度，因而具有重疊 性。

23、另外兩個序列的LCS中包含了兩個序列的前綴的LCS,故問題具有最優(yōu)子 結構性質考慮用動態(tài)規(guī)劃法。用200300字概述求最優(yōu)二分搜索樹算法的主要步驟。算法中有哪幾點最 為關鍵？答：記cij是最優(yōu)子樹Tij的耗費，則ci,k-l是最優(yōu)子樹Ti,k-1的耗費, ck,j是最優(yōu)子樹Tk,j的耗費?？疾煲詀k (i+lWkWj)為根、由結點bi, ai+1, bi+1,，aj, bj構成的、耗費最小的樹的總耗費：該樹的左子樹必然是Ti,k-1, 右子樹必然是Tk,j。這棵樹的總耗費可分為三部分：左子樹、右子樹和根。由 于Ti,k-1作為左子樹接到結點ak之下時，其耗費增加wi,k-l,故左子樹的耗 費為

24、：ci,k-1+ wi,k-1,同理，右子樹的耗費為：ck,j+wk,j,由于根ak的深 度為0,按定義，根的耗費為pk。因此，以ak為根、耗費最小的樹的總耗費 為：ci,kl+ wi,kl+ckj+wk,j+pk。 注意到，wi,k_l二qi+pi+l+qi+l+ +pkl+qkT, wk,j二qk+pk+l+qk+l+pj+qj, 從而有 wi,kl+wkj+pk 二 qi+pi+l+qi+l+pkl+qkT+ pk +qk+pk+l+qk+l+pj+qj 二 wij。 由此得到以 ak為根、耗費最小的樹的總耗費為：ci,k-l+ckj+wi,j由于pi (i=l,2,n) , qj (

25、j=0,l,2,n)在初始時已經知道，若wi,j1 已知，則根據(jù)wi,j= wi,j1+pj + qj可以計算出wij。故當ci,k1與ckj已 知時，以ak為根的樹的最小總耗費在0( 1)時間就可以計算出來。分別計算以 ai+1, ai+2,，aj為根、含有結點bi, ai+1, bi+1,，aj, bj的樹的最小 總耗費，從中選出耗費最小的樹，此即最優(yōu)子樹Tij。因此，最優(yōu)子樹Tij的 耗費 cij二cminj k i W j k i W i,-1+ckj+wij。遞推求 cij 及記錄 Tij 的根的算法本算法的關鍵點：分析出最優(yōu)二分搜索樹具有最優(yōu)子結構；在計算中規(guī)模較 小的最優(yōu)子樹在計

26、算中要被多次用到。Cij和Wij都是可以通過前面的計算遞推 得出的。有了 Tij的根的序號后，如何構造出最優(yōu)二分搜索樹？答：設Tij的根為ak (rij記錄到的值是k),則從根開始建結點。Buildtree(i,j,r,A) /*建立最優(yōu)子樹 Tij*/If ij return nill;poi nt ernewnode(node ty pe);krij; /*必有 i 0 then if EDk為Nothen /*作業(yè) Dk放在當前最左空位 */ FiDk; i 增 1; EDk置為Yeselse if E-Dk為No then /*作業(yè)-Dk 放在當前最右空位*/ Fj-Dk; j 減 1

27、; E-Dk置為Yes什么是備忘錄方法？它在什么情況下使用較為有效？答：若有大量的子問題無需求解時，用備忘錄方法較省時。但當無需計算的子問題只有少部分或全部都要計算時，用遞推方法比備忘錄方法要好(如矩陣連乘，最優(yōu)二分搜索樹)。 簡單不相交集的合并算法中為什么要引進集合的外部名和內部名？ 答：若沒有內部名，則每次合并時兩個集合中的所有元素均要改名(改為 K)，這樣，在 n-1 次 Union 中改名的時間就變?yōu)?O(n2) 。什么是平攤分析？平攤分析常用的手法有哪幾種？簡單說明這幾種手法的要點。答：考慮 n 條指令執(zhí)行的最壞時間復雜性。 即使某些指令執(zhí)行時具有比較 大的代價，但利用平攤分析后對整

28、體考慮， 可以得到較小的平均代價。平攤分析方法主要有：聚集方法，會計方法和勢能方法。聚集方法：全局考慮時間復雜性，把n條指令的耗費分為幾類；分別計算每一類耗費的總和， 然后再把各類耗費總加起來。會計方法：利用幾個操作之間的聯(lián)系，在一個操作中預先支付下面某個操作 的費用，以達到簡化代價計算的目地。勢能方法：設Ci為第i個操作的實際代價，D0 為處理對象的數(shù)據(jù)結構的初始狀態(tài)，Di為第i個操作施加于數(shù)據(jù)結構Di-1之上后數(shù)據(jù)結構的狀態(tài)，引入勢函數(shù)0，0 (Di)是與Di相關的勢。定義第 i 個操作的平攤代價為：=Ci +(0 (Di)- 0 (Di-1)(即實際代價加上勢的變化)，為什么樹結構下執(zhí)行

29、0(n)條帶路徑壓縮的Union-Find指令只需要 0(n*G(n)時間？答：用平攤分析的聚集方法，把O(n)條Find指令的耗費分為三類：O(n)條Find指令的根費用，O(n)條Find指令的組費用，O(n)條Find指令的路徑費用。根費用：執(zhí)行一條Find指令時，處理根及其兒子所需的費用。一條Find 指令只會碰到一個根(及其兒子)，故O(n)條Find指令的根費用為O(n),這 樣，根及其兒子的費用已全部計算在內。組費用：若結點ik (OWkWm-2)與其父結點ik+1的秩不在同一個秩組中， 則對ik收取一個組費用。因最多有G(n)個組，故一條Find指令最多只會碰到 G(n)個結點

30、、其秩與其父結點的秩不在同一個秩組中，故O(n)條Find指令的 組費用最多為O(n*G(n)。路徑費用：由于其秩在組號為g的組中結點的個數(shù)不超過n/F (g)，故組g 中的結點的收取的路徑費用 不超過n/F(g)*F(g)-(F(g-1)+1)cn，即算法在最壞情況下不是線性的。用200300字概述Link(v,r )程序的執(zhí)行過程。該程序的要點在什么地方？答：要點在于：為保持Weight的性質，合并的同時要對Weightr進行修 改。(由于原先的Link就是把r接到v之下，而含有v的樹中各結點的深度并 未受到任何影響，現(xiàn)在把Tr接在v之下，Tv中的各結點當然也不會受到任何 影響，故Tv樹中

31、各結點的Weight值無需修改。)Tr樹中各結點的Weight值 如何修改？設用Find-Depth指令可以查到v的深度為Depth(v)，(注意Depth(v)是Find-Depth指令的返回值而不是函數(shù))而在原先的森 林中，由于r是根，故原先有Depth(r)=O (也是值)。執(zhí)行 Link 指令后，把 r 作為 v 的兒子，則此時在原先的森林中，r的深度為Depth(v)+l。設在D-森林中，r的兒子是s。由Weight的性質，在D-森林中的2棵樹合并之前，有：從r到s路徑上各結點的權和+舊 Weightr=O(r在原森林中的深度)D-森林中的2棵樹合并之后，在原先森林中r的深度為從 r

32、 到 s 的權和+新 Weightr+Weightv(按 Weight 的性質)，另一方面，按上述分析，在原先森林中 r 的深度為 Depth(v)+1，故有從 r 到 s 的權和+新 Weightr+Weightv二 Depth(v)+l。由上述兩式可得：新 Weightr二Depthv+l-Weightv +舊 Weightr。由于Tr中的其它各結點相對于r的位置合并后均未改變，故Tr中的其它各結點的Weight值無需改變，只要 r 的新 Weight 值正確，則 Tr 中的其它各結點就都能夠正確計算出其在原森林中的高度。2、Countvk then 輸出i未被刪除else /* i 確實

33、被刪除了*/輸出i被第j條E指令所刪除；UNION（j，Succj，Succj）；SuccPredjSuccj； /* 集合 j 不再存在*/PredSuccjPredj 算法最關鍵的在于集合的Union和find算法的使用。比較 Las Vegas 算法和 Monte Carlo 算法，它們有什么相同和相異之處?隨機算法有哪些優(yōu)點？答：LasVegas算法總是給出正確的結果，但在少數(shù)應用中，可能出現(xiàn)求不出解的情況。此時需再次調用算 法進行計 算，直到獲得解為止。對于此類算法，主要是分析算法的時間復雜度的期望值， 以及調用一次產生失敗（求不出解）的概率。Mont Carlo算法通常不能保證計

34、算出來的結果總是正確的，一般只能斷定所給解的正確性不小于p （VpVl =。 通過算法的反復執(zhí)行（即以增大算法的執(zhí)行時間為 代價），能夠使發(fā)生錯誤的 概率小到可以忽略的程度。由于每次執(zhí)行的算法是獨立的，故k次執(zhí)行均發(fā)生錯 誤的概率為（l-p）k。隨機算法的優(yōu)點：對于某一給定的問題，隨機算法所需的時間與空間復雜性， 往往比當前 已知的、最好的確定性算法要好。到目前為止設計出來的各種隨機算法，無論是從理解上還是實現(xiàn)上，都 是極為簡單的。3. 隨機算法避免了去構造最壞情況的例子。最壞情況雖有可能發(fā)生，但是 它不依賴于某種固定的模式，只是由于運氣不好才出現(xiàn)此種情況。簡述隨機取數(shù)算法和找第k小元素的隨機

35、算法。答：Random Sampling 問題(Las Vegas 算法)設給定n個元素(為簡單起見，設為1, 2, n),要求從n個數(shù)中隨機地 選取m個數(shù)(mWn)。可以用一個長為n的布爾數(shù)組B來標識i是否被選中，初 始時均表為未選中。然后隨機產生1, n之間的一個整數(shù)i,若Bi為未 選中，則將i加入被選中隊列，同時把Bi標識為已選中，反復執(zhí)行直到m 個不同的數(shù)全部被選出為止。找第k小元素的隨機算法(Las Vegas算法)：在n個數(shù)中隨機的找一個數(shù)Ai=x,然后將其余n-1個數(shù)與x比較，分別 放入三個數(shù)組中：S1(元素均x), S2(元素均=x), S3(元素均x)。若|Sl|$k 則調用

36、Select(k,S1)；若(|S1| + |S2| )$k，則第k小元素就是x；否則就有 (|S1| + |S2|)V k,此時調用 Select(k-|S1|-|S2|,S3)。什么是Sherwood隨機化方法？簡述Test ing St ring Equali ty算法的誤判 率分析。答：Sherwood隨機化方法(屬Las Vegas算法)如果某個問題已經有了一 個平均性質較好的確定性算法， 但是該算法在最壞情況下效率不高，此時引入 一個隨機數(shù)發(fā)生器 (通常是服從均勻分布，根據(jù)問題需要也可以產生其他的分 布)，將一個確定性算法改成一個隨機算法，使得對于任何輸入實例， 該算法 在概率意義

37、下都有很好的性能(e.g. Selec t. Quicksort等)。如果算法(所 給的確定性算法)無法直接使用Sherwood方法，則可以采用隨機預處理的方法， 使得輸入對象服從均勻分布 (或其他分布)，然后再用確定性算法對其進行處 理。所得效果在概率意義下與Sherwood型算法相同。數(shù)論定理1：設n (n)是小于n的素數(shù)個數(shù)，則n (n)nnelog,誤差率不 超過6%。VM=2n2, Prfailure的分母 n (M)Prfailure的分子W使得Ip(x)=Ip(y)的素數(shù)p(pVM)的個數(shù)二能夠整 除丨I(x)-I(y)丨的素數(shù)p(pVM)的個數(shù)(Ta三b (mod p) iff

38、 p整除丨a-b | )數(shù)論定理2：如果aV2n，則能夠整除a的素數(shù)個數(shù)不超過n (n)個。(只 要n不是太小。)PrfailureWn (n) / n (M)nnnneelog/log/2二nl。即誤匹配的概率小 于n1。設xHy,如果取k個不同的小于2n2的素數(shù)來求Ip（x）和Ip（y）,由于事 件的獨立性，因此事件均發(fā)生的概率滿足乘法規(guī)則，即k次試驗均有Ip（x）=Ip（y） 但xHy （誤匹配）的概率小于knl。當n較大、且重復了 k次試驗時，誤匹 配的概率趨于0。計算模型RAM與RASP之間有什么相同和相異之處？答:RAM和RASP的相同之處在于作為計算模型都有各種尋址指令，且任何一

39、 個RAM程序，都可由一個RASP程序來模擬實現(xiàn)，且時間復雜性數(shù)量級相同（不 論哪一種耗費標準）。即如果RAM程序的時間復雜度為T（n），則RASP實現(xiàn)同樣功能的程序的時 間復雜度為kT（n） （k為常數(shù)）。任何一個RASP程序都可由RAM程序來模擬，且 時間復雜性的量級相同（無論哪一種耗費標準）。RASP程序與RAM程序之間可 以相互模擬， 且無論哪一種耗費標準，兩者的時間復雜性的量級均相同。不同之處在于：RAM的程序一經給定就不允許修改；而RASP （Random Access St ored Program ）的程序可以修改，只要將程序放在存儲器上就可以。 RASP 程序沒有間接尋址Al

40、an Turing 是怎樣對人類計算過程進行概括的？答： Turing 根據(jù)這個過程構造出了一個計算模型，稱之為 Turing 機。這個計算模型有一條帶子（帶子相當于一張紙），帶子上有無窮多個方格， 每個方格中可以寫給定有窮符號表中的一個字符。有一個讀寫頭（讀相當于用眼 睛來看，寫相當于擦或寫）。還有一個有窮狀態(tài)控制器FSC （相當于人腦）， FSC 根據(jù)當前讀到的符號（相當于眼睛看到的）和自己當前的狀態(tài)（相當于人腦的決策）決定三件事：改變讀寫頭當前所指的字母（相當于在紙上改寫一些符號），改變（或不改 變）自己當前的狀態(tài)（準備下一步的計算），使讀寫頭左移或右移或不動（相當 于改變眼睛看到的范圍

41、）。Church-Turing Thesis 的內容是什么？它有什么意義？答：任何合理的計算模型都是相互等價的（計算范圍相同）。合理：單位時間內可以完成的工作量，有一個多項式的上限。不合理舉例： 任意多道的并行計算。由于有任何二字，故無法進行證明。但迄今為止所有被 提出的合理計算模型均滿足該論題。這個論題說明：可計算性本身是不依賴于具體模型的客觀存在。RAM程序、RASP程序與Turing機相互之間的時間復雜度關系是怎樣的(考 慮兩種耗費標準)？答：任何一個RAM程序，都可由一個RASP程序來模擬實現(xiàn)，且時間復雜性 數(shù)量級相同(不論哪一種耗費標準)。即如果 RAM 程序的時間復雜度為 T(n)

42、， 則RASP實現(xiàn)同樣功能的程序的時間復雜度為kT(n)(k為常數(shù))。當一臺TM的時間復雜度為T(n)時，模擬該TM的RAM程序的對數(shù)耗費 不超過O(T(n)logT(n)；而當一不含乘、除法指令的RAM程序的對數(shù)耗費為T(n) 時，模擬該程序的TM的時間復雜度不超過O(T2(n)；當一含有乘、除法指令的 RAM程序的對數(shù)耗費為T(n)時，模擬該程序的TM的時間復雜度不超過O(T3(n)。在對數(shù)耗費的標準下，RAM，RASP與TM是多項式相關的計算模型。RASP程序如何模擬RAM程序？ RAM如何模擬Turing機？ Turing機如何模 擬 RAM？答：RASP程序按下圖模擬RAM程序：在模

43、擬過程中，RASP的第r+i號寄存器始終對應于RAM的第i號寄存 器，RASP的R1作為暫存器。R0與r0在一條指令的模擬過程中可能不對應，但 在一條指令模擬的開始和結束時一定對應。模擬非間址尋址指令時，先將指令對應的編碼放入 j 寄存器，若 操作數(shù)為 =i，則去掉=，將i放入j+1寄存器，若操作數(shù)為i，要看i是否為0： i 為 0 時，將 0 放入 j+1 寄存器， i0 時，將 r+i 放入 j+1 寄存器。間址尋址的 RAM指令，可以用一組RASP指令來模擬實現(xiàn)。RAM 模擬 TM 的方法如下圖：模擬時存儲內容的對應方法按上圖所示OTM的k個帶頭的位置 分別放在RAM 的單元r1至rk中

44、，即第j個單元的內容C(j)就是第j個帶頭在第j條帶上的 當前位置。c為RAM存儲器中存放a0的單元之前的單元編 號。k條帶上的首格 內容(分別為aO,bO,zO)存放在第c號單元后的k個單元中；其后再放k條 帶上的次格內容(分別為al,bl,zl)；因此，TM的第j條帶當前掃描著的單 元的內容是存放在RAM存儲 器的第c+k*C(j)+j個單元中，即內容為 C(c+k*C(j)+j)。(C(j)是第j個帶頭的當前位置，而位置的計數(shù)是從0開始的)e.g.:第 二條帶第1個格子中的內容放在第c+k*1+2號單元。TM 模擬 RAM 的方法如下圖：用5帶TM來模擬RAM程序的過程:帶1用來記錄內容

45、為非0的RAM寄存器的編號及該寄存器的內容。帶2存放 RAM累加器r0中的內容a 0,帶3作為暫存工作帶。帶4上放RAM輸入帶上的內 容，帶5上放輸出。Turing機所接受的語言是什么樣的語言？各種語言之間有什么樣的關系？答：Turing可計算函數(shù)部分遞歸函數(shù)。遞歸可枚舉集(完全)遞歸集原始遞歸集部分遞歸函數(shù)完全遞歸函數(shù)原始遞歸函數(shù)非確定性Turing機與確定性Turing機的主要區(qū)別在什么地方？答：與DTM不同的是，NDTM的每一步動作允許有若干個選擇，對于給定的 QXTk的一個元素(qi, al, a2, , ak)，它的6轉移函數(shù)值不是對應于一個 QX(TXL,R,S)k中的一個元素，而

46、是對應于QX(TXL,R,S)k中的一個子 集。與DTM不同的是，DTM的ID序列是線性的：ID0卜ID1卜ID2 卜IDm, 而NDTM的ID序列通常是用樹來描述的(因為在每個格局都可能有多個選擇)。NDTM的另一種解釋是，每當遇到n個(n$2)選擇時，NDTM就把自身復制 n個，讓它們進行并行的計算。由于具有任意多道并行計算的能力，非確定性Turing機的時間復雜度是如何定義的？答：NDTM的時間復雜度T(n):對于可接受的輸入串，T(n)=max關于輸入 3的時間復雜度| 3的長為n且被該NDTM接受即先求出每一個被接受3的 最短路徑長度，然后對這些長度求最大。什么是P類與NP類語言？如

47、不用非確定性Turing機的概念，如何定義P 類與NP類的問題？答：語言族P=L|L是一個能在多項式時間內被一臺DTM接 受的語言NP= L|L是一個能在多項式時間內被一臺NDTM接受的語言不需要NDTM概念的NP問題的定義設S是一個集合，若某個判定問題A的所有解均屬于S，則S中的一個元 素稱為問題A的一個證書(certificate)，S被稱為是A的證書所構成的集合。 對判定問題類A,若存在一個由A的證書所構成的集合S (S中含有A的全部解)， 且存在一個算法F，對S中的每一個證書a， F可在多項式時間里驗證a是否 為A的一個解，則稱AWNP。(該定義與用NDTM概念的NP類定義是等價的。)

48、稱P類問題是多項式時間可解的。稱NP類問題是多項式時間可驗證的。Karp多項式規(guī)約是如何表述的？它與Cook多項式規(guī)約之間的關系如何？ 答：Karp規(guī)約：設L、L0分別是字母表工、工0上的語言（字符串的集合）， 若存在兩個閉包間的一個變換f：E*-工*，滿足Vw 三工*, 3 WLOf（3 ）WL0；2)3)若3的長為n,則f（w ）的長不超過PL（n）,這里PL（n）是一個多項式; 任取3三工*，設3的長度為n,則f（3 ）在多項式時間p（n）2)3)則稱L可多項式變換為L0,記作LWp L0。它和Cook規(guī)約的關系是Karp的要求嚴，Cook的要求松，即滿足Karp就滿 足 Cook。至今

49、尚未發(fā)現(xiàn)滿足Cook而不滿足Karp的語言，即兩者大體等價。Karp的 定義簡潔，Cook的定義繁瑣。什么是NP-完全性語言？什么是NP-完全性問題？什么是NP-hard問題？ 答：NP-完全性語言定義1 （狹義，Karp）:稱滿足下述2條的語言L0是NP-C的： l）L0WNP; 2） VLWNP，都有 LWpLO。NP-完全性問題：若某個判定問題進行編碼后，所對應的語言L0是NP-C 的，則稱該問題是NP-C的。有些最優(yōu)化問題（對應的編碼3 eLO）可以滿足NP-完全性定義的第2條 要求：VLeNP，都有LWp L0。滿足上述條件的問題被稱為NP-hard問題。引入NP-完全性概念有什么意

50、義？列舉20個NP-完全性或NP-hard問題。 答：如果存在一臺DTM在多項式時間里接受某個NP-C語言， 則所有NP類語言均可找到DTM在多項式時間里接受，從而有P=NP。如果某個NP類語言不存在DTM在多項式時間里接受（即PHNP）,則所有NP-C語言都不存在DTM在多項式時間里接受，即有 NP-cnp=0。什么是算法A對于實例I的近似比、A的絕對近似比和漸進近似比？答：算法A對于實例I的近似比(ratio factor) =RA(I)=maxA(I)/OPT(I),OPT(I)/A(I)由于是取max,故近似比總是大于等于1的。絕對近似比rA=InfRA(I)對一切 即算法A對于一切實

51、例I的近似比的最 小上界(相當于最大值)。漸進近似比rA二supr$l|存在正整數(shù)n0,使得對于所有OPT(I)$nO的實 例，都有Wr即反映了近似比的收斂情況，它允許OPT(I)較小的實例的近似比 大于rA。什么是多項式時間近似方案(PTAS)?什么是完全多項式時間近似方案 (FPTAS，F(xiàn)PAS)？答：多項式時間近似方案(PTAS, Polynomial Time Approximation Scheme)設是求解某類問題的多項式時間近似算法， 0也作為該算法的輸入。如果對每一個給定的 ,的絕對近似比Wl + ，則稱A是一個PTAS。完全多項式時間近似方案 (FPTAS，F(xiàn)PAS, Ful

52、ly Polynomial Time Approximation Scheme)如果一個PTAS以某個二元多項式函數(shù)p(|I|,1/ )為時間復雜度上界，則稱是一個FPTAS。什么是偽多項式時間的算法？如何用動態(tài)規(guī)劃法求解背包問題？答：定義：設實例I的輸入規(guī)模為n，實例中的最大數(shù)為max(I)，若算法 的時間復雜性以某個二元多項式p(n,max(I)為上界，則稱該算法是偽多項式 時間的算法。動態(tài)規(guī)劃法。對0WkWn，0WbWB，設f(b)為：裝前k件物品中若干件、且體積和不超過b時可得到的最大價值。因此，f(B)就是該問題的最優(yōu)解。根據(jù)f(b)的定義可知子問題具有最優(yōu)子結構性質。另外，引入初值

53、均為0的二維數(shù)組x,每一個數(shù)組元素xk,b記錄： 當體積限制為b時，uk是否被選中，1為被選中，0為未被選中。 初始當k=0時，有(b)=0 (OWbWB)，此為遞推計算的基礎值。設對bwO,B, (b)， (b)， f(b)均已計算出來，此時需要對區(qū)間0,B中的整數(shù)b (即0WbWB)，逐一求出(b)。 考慮b與sk的關系。若b (b)，則物品uk應裝入，即此時要執(zhí)行 xk,bl，以及 fk (b)jfk-1 (b-sk)+ck。否則應執(zhí)行xk,b0,以及fk (b)jfk-1 (b)。按上述方法，當執(zhí)行到k=n, b=B時，最優(yōu)解的值即為(B)。這部分算法的時間復雜度為O(nB)。上述計算

54、完畢之后，再根據(jù)x數(shù)組內容，找出應取哪幾件物品。置初值b=B，循環(huán)從j=n開始，檢查xj,b:若xj,b=0,則表示uj未被選中，故不做動作，直接執(zhí)行j-j-1； 若xj,b = 1,則表示uj被選中，把j放入集合S中(S初始為空)，然后執(zhí)行bb-sj以及j Jj-l。循環(huán)一直執(zhí)行到j=l的判斷完成后為止。算法時間復雜度為O(n)。從而整個算法的時間復雜度為O(nB)。注意B與輸入規(guī)模n無關，故nB不是輸入規(guī)模的多項式函數(shù)。 因此，算法是偽多項式時間的算法。NP的假定之下，可以分成哪4類(舉例)？ NP-hard問題在P答：NP-hard問題在PHNP的假定之下，可以分成4類：1、有 FPTA

55、S (e.g.Knapsack)2、有 PTAS 而沒有 FPTAS (e.g. k-Knapsack)3、沒有PTAS，但有絕對近似比為常數(shù)的近似算法(Bin-Packing)4、沒有絕對近似比為常數(shù)的近似算法(e.g. TSP)為什么當kM2, k背包問題不存在FPTAS,除非P=NP?答：反證法：設A是該問題的FPTAS，時間復雜度上界為P(|l|,1/ ),對每個實例I,令 =1/2ncmax，將I和作為A的輸入，由于 A 是 FPTAS，故有 OPT(I)W(l+ )A(I)， OWOPT(I)-A(I)W A(I)Wncmax二。但OPT(I)和A(I)都是正整數(shù)，OPT(I)=A

56、(I)，故A(I)是最優(yōu)化算法，其時間復雜度上界為p(n，2ncmax)。利用算法A來構造k等分割問題的算法A:對于k等分割的任一實例I，即n個正整數(shù)sj (lWjWn)，構造k背包問題的實例I:物品j的體積為sj，價值 cj=l(lWjWn)，背包容量 Bi=(lWiWk)。將該實例I和 =作為A的輸入，求得I的最優(yōu)解A(I)；當且僅當OPT(I)=n (把所有物品均裝入k個背包)時，A對I回答為Yes。注意，k等分割有解iff A回答為Yes由于根據(jù)I構造I僅需O(n)時間，|I| = |I|二n, 8 =,而A算法的時間復雜度上界不超過p(n,)二p(n,2n),是關于n的多項式，A是k

57、等分割問題的多項式時間算法,即找到了一個求解 NP-C 問題的多項式時間算法，P二NP，與PHNP矛盾。結論：假設PHNP，則k背包問題沒有FPTAS。2014 算法設計與分析課程試題題庫含答案1、一個算法應有哪些主要特征？又窮性，確定性，可行性，0 個或多個輸入，一個或多個輸出2、分治法(Divide and Conquer)與動態(tài)規(guī)劃(Dynamic Programming)有什么不 同？分治算法會重復的求解公共子問題，會做許多不必要的工作，而動態(tài)規(guī)劃對每個 子問題之求解一次，將其結果存入一張表中，從而避免了每次遇到各個子問題有 從新求解。3、試舉例說明貪心算法對有的問題是有效的，而對一些

58、問題是無效的。貪心算有效性：最小生成樹、哈弗曼、活動安排、單元最短路徑。無效反例：01 背包問題，無向圖找最短路徑問題。4、求解方程 f(n)=f(n-1)+f(n-2)，f(1)=f(2)=1。由 f(n)=f(n-l)+f(n-2)可得f(n)-f(n-l)-f(n-2)=0,可得方程的特征方程為x2 - x -1 = 0,設特征方程的2個根本分別為x , x ,則可得12x = x = 1 5,貝U有1 2 2()(1 +15、丄(1屮5、 TOC o 1-5 h z f (n) = c () n + c () n1 2 2 2又f (1) = f=1可得r(1)1 +5 丄 1-戀51

59、f (1) =c +c = 112 J1 +5、 J 5f =()2 c + ()2 c = 12122可得c= a, c = b1 21 +、： 51 一壬 5、f (n) = a (2)n + b(?)n5、求解方程 T(n)=2T(n/2)+1, T(1)=1，設 n=2k。T(n) 2T(n/2) +12T(n/2) 22T(n/22) + 222T(n/22) 23T(n/23) + 222k-1T(n/2k-1) 2kT(n/2k ) + 2k-1 上面所有式子相加，相消得T (n) = 2k T (1) + 2 + 21 + 22 + 2k-12k + 1*2 k +1 - 16

60、、 編寫一個 Quick Sorting 算法，并分析時間復雜性。 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);快速排序時間復雜度最壞情況為O(n2),平均為O(nlogn);7、 利用 Quic