算法設計與分析考點精講串燒

1、一、選擇題(每小題3分，共15分)算法與程序的主要區(qū)別在于算法具有()。A.能行性B.確定性C.有限性。.輸入和輸出答案：C。對一個有序序列，以比較為基礎的搜索算法的最壞情況時間復雜性的下界為()。A. Q (n)B. Q (n2)C. Q (nlogn)D. Q (logn)答案：D。背包問題：n=6, C=10, V(1：6) = (15,59,21,30,60,5), W(1：6) = (1,5,2,3,6,1)。該問題 的最大價值為()。A. 101 B. 110 C. 115 D. 120答案：C。矩陣連乘積問題：Mi(5x10), M2(10 x4), M3(4x6)0矩陣鏈乘MM

2、2M3需要的最少乘法次數為 ()。A. 348 B. 328 C. 720 D. 320答案：Do用貪心策略設計算法的關鍵是()。A.將問題分解為多個子問題來分別處理B.選好貪心策略C.獲取各階段間的遞推關系式D.滿足最優(yōu)性原理答案：Bo二、填空題(每小題4分，共20分)某算法的計算時間T(n)滿足遞歸關系式：T(n)=2T(n-1)+O(1), n1； T=1。則T(n)=。答案：2n-1。 用 方法對狀態(tài)空間樹進行搜索時，每個結點有可能多次成為擴 展結點。子集和數問題一般陳述如下：已知n+1個正數：w (IWiWn)和M，要求找出Wj的和數是M的所有子集。其解可以表示為n-元組(X , x

3、2 , , xn)，這里xiG0,1，1i %,有fn)cf(n)。類似地，對于任意gi (n) g O(g(n)，存在正常數c2和自然數n2,使得對所有n n2, 有 gi (n) 氣，有f(n) +gi (n) =N1,有：F (N) =N2,有：G(N)=N3,有FN=C1f(N)=C3f(N);GN=C2f(N)=C3g(N);故有：O(f)+O(g)=F(N)+G(N)=C3f(N)+C3g(N)=C3(f(N)+g(N)=O(f+g);因此有：O(f)+ O(g)= O(f+g) (8分)用動態(tài)規(guī)劃解決0-1背包問題的改進算法求解如下實例：n=4, c=12, v= (18, 15

4、, 8, 12), w= (10, 2, 3, 4)。(要求：先寫出計算公式，再寫具體的求解過程，指出最 優(yōu)值和最優(yōu)解)解：pn+1 = (0,0)pi=pi+1Upi+1代工)去掉受控點。P5 = (0,0)P4 = (0,0),(4,12)P3 = (0,0),(3,8),(4,12),(7,20)P2 = (0,0),(2,15),(5,23),(6,27),(9,35)P1 = (0,0),(2,15),(5,23),(6,27),(9,35)最優(yōu)值為35,最優(yōu)解為(0,1,1,1)(10分)用單純性算法求解下面線性規(guī)劃問題：max z=-x2+3x3-2x4s.t . X+3x2-

5、x3+2x4= 7-4x2+3x3 +8%W102x2-4x3 3T2x.0 (i=1,2,3,4)要求：步驟描述寫清每一迭代步的選擇，單純形表，可行解及可行解對應的目標函數的值。解：線性規(guī)劃的約束標準型為：max z=-x2+3x3-2x4s.t . x1+3x2- x3+2x4= 7x5-4x2+3x3 +8x4= 10 x6-2x2+4x3 =12xi0 (i=1,2,3,4,5,6)初始單純形表Cx2x3x4z0-13-2x173-12x510-438x612-240z=0,x=(7,0,0,0,10,12)第一步迭代選入基變量x3選離基變量x6轉軸變換Cx2x6x4z91/2-3/4

6、-2x1105/21/42x51-5/2-3/48x33-1/21/40z=9,x=(10,0,3,0,1,0)第二步迭代選入基變量x2選離基變量x1轉軸變換Cx1x6x4z11-1/5-4/5-12/5x242/51/104/5x5111-1/210 x351/53/102/5Z行非基變量的系數全部為負，迭代結束，最大值為11,最優(yōu)解為(0,4,5,0,11,0)(10分)單源最短路徑問題：在下圖實例上指定源點為!，目標點為6,應用優(yōu)先隊列式分支限界法找出1到6的最短路徑。(要求寫明優(yōu)先級，畫出搜索樹，標出最短路徑)解：優(yōu)先級：當前結點所代表的最短路徑長度，長度越小，優(yōu)先級越高搜索樹：01|

7、9 23 421 4 13 52 8 5 174,州爭5 1317 29 2016 （46 28618五、算法設計（共13分）：說明：任意選擇所使用的算法策略。要求：說明所使用的算法策略；寫出算法實現的主要步驟；題目：n后問題策略1：回溯法（定義解的結構，確定解空間樹，確定約束函數，深度優(yōu)先方式搜索，判斷 當前是否到葉子節(jié)點，若到了葉子節(jié)點，則找到了一種著色方案，將其方案輸出，并將方案 個數加1，若是中間節(jié)點，判斷是否滿足約束條件，若滿足，則深一步搜索，否則剪枝。） 策略2：分支限界法（定義解的結構，確定解空間樹，確定約束函數，以廣度優(yōu)先方式搜索，判斷當前是否到葉子節(jié)點，若到了葉子節(jié)點，則找到

8、了一種放置方案，方案個數累加1，并且輸出對應的方案，若是中間節(jié)點，判斷有沒有合適的放置位置，若有，則擴展該節(jié)點，將其可行的孩子節(jié)點加入到活節(jié)點表中，若沒有，則從活節(jié)點表中取下一個活節(jié)點）簡答題：1操作系統(tǒng)是算法嗎？請說說算法和程序的區(qū)別。答：不是。算法是滿足下述性質的指令序列：（1）輸入：有零個或多個外部量作為算法的輸入。（2）輸出：算法產生至少一個量作為輸出。（3）確定性：組成算法的每條指令清晰、無歧義。（4）有限性：算法中每條指令的執(zhí)行次數有限，執(zhí)行每條指令的時間也有限程序是算法用某種程序設計語言的具體實現。程序可以不滿足算法的性質（4）即有限性。2、插入排序、合并排序和快速排序這三種算法

9、，哪幾種使用了分治策略？請簡述之。 答：合并排序和快速排序使用了分治的策略。合并排序：對要排序的數組Alow.high，令mid=（low+high）/2，用 Amid把原數組 Alow.high 分成兩個子數組，然后對兩個子數組進行排序，在合并兩個已牌子徐的子數組， 產生排序數組?？焖倥判颍簩σ判虻臄到MAlow.high,先使用算法SPLIT重新排列元素，使得原先在 Alow中的祝愿占據其正確的位置Aw，并且所有小于或等于Aw的元素所處的位置為 Alow.w-1，而所有大于Aw的元素所處的位置是Aw+1.high。在對子數組Alow.w-1 和Aw+1.high遞歸地排序，產生整個排序數組

10、。歸并排序要好于插入排序，插入排序要好于冒泡排序。分治法適合求解的問題一般具有那些特征？分治法可分為哪三個主要步驟？答：適合分治法求解的問題一般具有以下特征：圖（1）問題的規(guī)模縮小到一定程度就可以容易地解決圖（2）問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結構性質（3）基于子問題的解可以合并為原問題的解圖（4）問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。 分治法可分為以下三個步驟：圖分解（Divide）：將原問題分解為子問題圖解決（Conquer）：求解子問題圖合并（Combine）：組合子問題的解得到原問題的解。貪心算法的基本思想是什么？貪心算法適合

11、求解的問題具有哪些特征？貪心算法求解的 問題一定可以獲得最優(yōu)解碼？答：貪心算法的基本思想：適用于求解最優(yōu)化問題的算法往往包含一系列步驟，每一步都有一組選擇。貪心算法總 是作出在當前看來是最好的選。擇貪心算法并不從整體最優(yōu)上加以考慮，它所作出的選擇只 是在某種意義上的局部最優(yōu)選擇。貪心算法適合求解的問題具有的特征：1）最優(yōu)子結構性質：整體最優(yōu)一定包括子問題最優(yōu)2）貪心選擇性質：所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇獲得貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產生整體最優(yōu)解。在一 些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結果卻是最優(yōu)解的很好近似。合并排序算法是根據

12、分治策略來設計的，簡述其基本思想。將待排序元素分成大小大致相同的兩個子集合，分別對兩個子集合進行排序，最終將排好序 的子集合合并成所要求的排好序的集合。算法復雜度為：O（nlogn）簡述拉斯韋加斯算法的算法特點及提高拉斯韋加斯算法得到解得概率的方法？（1）絕不返回錯誤的解，一旦找到一個解，那么這個解一定是正確的，也可能找不到 解。（2）由于得到正確解的概率歲算法執(zhí)行時間的增加而提高。對于所求解的問題的任一 實例，只要用同一拉斯韋加斯算法對該實例反復求解足夠多得次數，可使求解失效的概率任 意小。簡述分枝限界法的基本思想。分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。

13、在分 支限界法中，每一個活結點只有一次機會成為擴展結點?；罱Y點一旦成為擴展結點，就一次 性產生其所有兒子結點。在這些兒子結點中，導致不可行解或導致非最優(yōu)解的兒子結點被舍 棄，其余兒子結點被加入活結點表中。此后，從活結點表中取下一結點成為當前擴展結點， 并重復上述結點擴展過程。這個過程一直持續(xù)到找到所需的解或活結點表為空時為止。補充：分支限界法與回溯法求解目標：回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界 法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義 下的最優(yōu)解搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu) 先或

14、以最小耗費優(yōu)先的方式搜索解空間樹。當前節(jié)點的擴展方式不同：回溯法每個活結點有可能多次成為擴展結點，而分支限界 法的每一個活結點最多只有一次機會變成擴展結點。簡述最小生成樹的Prim算法的基本思想設G=(V,E)是連通帶權圖，V=1,2，,n。構造G的最小生成樹的Prim算法 的基本思想是：置 S=1只要S是V的真子集，就作如下的貪心選擇選取滿足條件i e S，j e V-S，且cij最小的邊，將頂點j添加到S中。 一直到S=V時為止。選取到的所有邊恰好構成G的一棵最小生成樹。簡單描述分治法的基本思想。將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題 相同；對這k個子

15、問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問 題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容易求出其解為止；將求出的小規(guī) 模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。簡述動態(tài)規(guī)劃方法所運用的最優(yōu)化原理。最優(yōu)化原理”用數學化的語言來描述：假設為了解決某一優(yōu)化問題，需要依次作出n個 決策D1，D2,，Dn，如若這個決策序列是最優(yōu)的，對于任何一個整數k，1 k n, 不論前面k個決策是怎樣的，以后的最優(yōu)決策只取決于由前面決策所確定的當前狀態(tài)， 即以后的決策Dk+1，Dk+2，Dn也是最優(yōu)的。何謂最優(yōu)子結構性質？某個問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種

16、性質稱為最優(yōu)子結構性質。何謂P、NP、NPC問題簡述二分檢索(折半查找)算法的基本過程。設輸入是一個按非降次序排列的元素表Ai： j和x，選取A(i+j)/2與x比較，如果 A(i+j)/2=x，則返回(i+j)/2,如果A(i+j)/2x，則 Ai： (i+j)/2-1找 x，否則在 A (i+j)/2+1： j找x。上述過程被反復遞歸調用。什么是算法？算法的特征有哪些? 算法是解決某類問題的一系列運算的集合【2分】。具有有窮行、可行性、確定性、0個或者 多個輸入、1個或者多個輸出【8分】。什么是P類問題？什么是NP類問題？什么是NPC問題?請描述集合覆蓋問題的近似算法 的基本思想。用確定的

17、圖靈機可以在多項式實踐內可解的判定問題稱為P類問題【2分】。用不確定 的圖靈機在多項式實踐內可解的判定問題稱為NP類問題?！?分】只有把解域里面的 所有可能都窮舉了之后才能得出答案，這樣的問題是NP里面最難的問題，這種問題 就是NPC問題。集合覆蓋問題的近似算法采用貪心思想：對于問，每次選擇F中覆蓋了盡可能 多的未被覆蓋元素的子集S，然后將U中被S覆蓋的元素刪除，并將S加入C中，最后得到 的C就是近似最優(yōu)解。【6分】補充算法思想貪心法：基本思想：適用于求解最優(yōu)化問題的算法往往包含一系列步驟，每一步都有一組選擇。貪心 算法總是作出在當前看來是最好的選。擇貪心算法并不從整體最優(yōu)上加以考慮，它所作出

18、的 選擇只是在某種意義上的局部最優(yōu)選擇。貪心算法的基本要素：1）最優(yōu)子結構性質：整體最優(yōu)一定包括子問題最優(yōu)2）貪心選擇性質：所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇獲得單源最短路徑問題算法的思想：先求出長度最短的一條路徑，再參照它求出長度次短的一條路徑，以此類推，直到從源點到其他各個定點的最短路徑全部求出為止，該算法俗稱Dijkstra算法。動態(tài)規(guī)劃：基本思想：實質是分治思想和解決冗余。將待求解問題分解為更小的、相同的子問題，然后 對子問題進行求解，最終產生一個整體最優(yōu)解。求解步驟：分析最優(yōu)解的性質，刻畫最優(yōu)解的結構特征。最優(yōu)子結構的性質分析（整體最優(yōu)包含子問題最優(yōu)）遞歸定義最優(yōu)值。建立最優(yōu)值的遞歸關系式3以自底向上的方式計算出最優(yōu)值，并記錄相關信息。根據計算最優(yōu)值時得到的信息，構造出最優(yōu)解?；疽兀鹤顑?yōu)子結構性質子問題重疊性質自底向上的求解方法Prim算法與Kruskal算法的比較設無向連通帶權圖G具有n個頂點和e條邊從算法的思想上說，如果G