算法設(shè)計(jì)與分析考點(diǎn)精講串燒

1、一、選擇題(每小題3分，共15分)算法與程序的主要區(qū)別在于算法具有()。A.能行性B.確定性C.有限性。.輸入和輸出答案：C。對(duì)一個(gè)有序序列，以比較為基礎(chǔ)的搜索算法的最壞情況時(shí)間復(fù)雜性的下界為()。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)。該問題 的最大價(jià)值為()。A. 101 B. 110 C. 115 D. 120答案：C。矩陣連乘積問題：Mi(5x10), M2(10 x4), M3(4x6)0矩陣鏈乘MM

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

3、2 , , xn)，這里xiG0,1，1i %,有fn)cf(n)。類似地，對(duì)于任意gi (n) g O(g(n)，存在正常數(shù)c2和自然數(shù)n2,使得對(duì)所有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分)用動(dòng)態(tài)規(guī)劃解決0-1背包問題的改進(jìn)算法求解如下實(shí)例：n=4, c=12, v= (18, 15

4、, 8, 12), w= (10, 2, 3, 4)。(要求：先寫出計(jì)算公式，再寫具體的求解過程，指出最 優(yōu)值和最優(yōu)解)解：pn+1 = (0,0)pi=pi+1Upi+1代工)去掉受控點(diǎn)。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)要求：步驟描述寫清每一迭代步的選擇，單純形表，可行解及可行解對(duì)應(yīng)的目標(biāo)函數(shù)的值。解：線性規(guī)劃的約束標(biāo)準(zhǔn)型為：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轉(zhuǎn)軸變換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轉(zhuǎn)軸變換Cx1x6x4z11-1/5-4/5-12/5x242/51/104/5x5111-1/210 x351/53/102/5Z行非基變量的系數(shù)全部為負(fù)，迭代結(jié)束，最大值為11,最優(yōu)解為(0,4,5,0,11,0)(10分)單源最短路徑問題：在下圖實(shí)例上指定源點(diǎn)為!，目標(biāo)點(diǎn)為6,應(yīng)用優(yōu)先隊(duì)列式分支限界法找出1到6的最短路徑。(要求寫明優(yōu)先級(jí)，畫出搜索樹，標(biāo)出最短路徑)解：優(yōu)先級(jí)：當(dāng)前結(jié)點(diǎn)所代表的最短路徑長度，長度越小，優(yōu)先級(jí)越高搜索樹：01|

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

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

9、，哪幾種使用了分治策略？請(qǐng)簡(jiǎn)述之。 答：合并排序和快速排序使用了分治的策略。合并排序：對(duì)要排序的數(shù)組Alow.high，令mid=（low+high）/2，用 Amid把原數(shù)組 Alow.high 分成兩個(gè)子數(shù)組，然后對(duì)兩個(gè)子數(shù)組進(jìn)行排序，在合并兩個(gè)已牌子徐的子數(shù)組， 產(chǎn)生排序數(shù)組。快速排序：對(duì)要排序的數(shù)組Alow.high,先使用算法SPLIT重新排列元素，使得原先在 Alow中的祝愿占據(jù)其正確的位置Aw，并且所有小于或等于Aw的元素所處的位置為 Alow.w-1，而所有大于Aw的元素所處的位置是Aw+1.high。在對(duì)子數(shù)組Alow.w-1 和Aw+1.high遞歸地排序，產(chǎn)生整個(gè)排序數(shù)組

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

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

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

13、在分 支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次 性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍 棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)， 并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個(gè)過程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。補(bǔ)充：分支限界法與回溯法求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界 法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義 下的最優(yōu)解搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu) 先或

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

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

16、性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。何謂P、NP、NPC問題簡(jiǎn)述二分檢索(折半查找)算法的基本過程。設(shè)輸入是一個(gè)按非降次序排列的元素表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。上述過程被反復(fù)遞歸調(diào)用。什么是算法？算法的特征有哪些? 算法是解決某類問題的一系列運(yùn)算的集合【2分】。具有有窮行、可行性、確定性、0個(gè)或者 多個(gè)輸入、1個(gè)或者多個(gè)輸出【8分】。什么是P類問題？什么是NP類問題？什么是NPC問題?請(qǐng)描述集合覆蓋問題的近似算法 的基本思想。用確定的

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

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