算法設(shè)計(jì)與分析復(fù)習(xí)題目及答案

1、分治法1、二分搜索算法是利用（分治策略）實(shí)現(xiàn)的算法。9. 實(shí)現(xiàn)循環(huán)賽日程表利用的算法是（分治策略 ）27、Strassen矩陣乘法是利用（分治策略）實(shí)現(xiàn)的算法。 34實(shí)現(xiàn)合并排序利用的算法是（分治策略 ）。 實(shí)現(xiàn)大整數(shù)的乘法是利用的算法（分治策略 ）。 17實(shí)現(xiàn)棋盤覆蓋算法利用的算法是（分治法 ）。 29、使用分治法求解不需要滿足的條件是（子問(wèn)題必須是一樣的）。不可以使用分治法求解的是（ 0/1背包問(wèn)題 ）。動(dòng)態(tài)規(guī)劃 下列不是動(dòng)態(tài)規(guī)劃算法基本步驟的是（ 構(gòu)造最優(yōu)解 ） 下列是動(dòng)態(tài)規(guī)劃算法基本要素的是（子問(wèn)題重疊性質(zhì) ）。 下列算法中通常以自底向上的方式求解最優(yōu)解的是（動(dòng)態(tài)規(guī)劃法） 備忘錄方法是

2、那種算法的變形。 （ 動(dòng)態(tài)規(guī)劃法 ） 最長(zhǎng)公共子序列算法利用的算法是（動(dòng)態(tài)規(guī)劃法 ）。矩陣連乘問(wèn)題的算法可由（動(dòng)態(tài)規(guī)劃算法 B）設(shè)計(jì)實(shí)現(xiàn)。 實(shí)現(xiàn)最大子段和利用的算法是（動(dòng)態(tài)規(guī)劃法 ）。貪心算法 能解決的問(wèn)題：?jiǎn)卧醋疃搪窂絾?wèn)題，最小花費(fèi)生成樹問(wèn)題，背包問(wèn)題，活動(dòng)安排 問(wèn)題，不能解決的問(wèn)題：N皇后問(wèn)題，0/1背包問(wèn)題 是貪心算法的基本要素的是（貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)） ?；厮莘?回溯法解旅行售貨員問(wèn)題時(shí)的解空間樹是（ 排列樹 ）。 剪枝函數(shù)是回溯法中為避免無(wú)效搜索采取的策略 回溯法的效率不依賴于下列哪些因素（ 確定解空間的時(shí)間） 分支限界法 最大效益優(yōu)先是（分支界限法 ）的一搜索方式。 分支

3、限界法解最大團(tuán)問(wèn)題時(shí)，活結(jié)點(diǎn)表的組織形式是（最大堆 ）。 分支限界法解旅行售貨員問(wèn)題時(shí)，活結(jié)點(diǎn)表的組織形式是（ 最小堆 ） 優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是（ 結(jié)點(diǎn)的優(yōu)先級(jí) ） 在對(duì)問(wèn)題的解空間樹進(jìn)行搜索的方法中 ,一個(gè)活結(jié)點(diǎn)最多有一次機(jī)會(huì)成為活結(jié)點(diǎn) 的是 （ 分支限界法 ）.從活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)的不同方式將導(dǎo)致不同的分支限界法,以下除（ 棧式分支限界法 ）之外都是最常見(jiàn)的方式 .（1）隊(duì)列式（FIFO分支限界法：按照隊(duì)列先進(jìn)先出（FIFO原則選取下一個(gè)節(jié)點(diǎn) 為擴(kuò)展節(jié)點(diǎn)。（2）優(yōu)先隊(duì)列式分支限界法：按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的 節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。（最優(yōu)子結(jié)構(gòu)

4、性質(zhì)）是貪心算法與動(dòng)態(tài)規(guī)劃算法的共同點(diǎn)。 貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是（貪心選擇性質(zhì) ）。 回溯算法和分支限界法的問(wèn)題的解空間樹不會(huì)是 （ 無(wú)序樹 ）.14哈弗曼編碼的貪心算法所需的計(jì)算時(shí)間為（ B ）。A、O（ n2n）B、 O（ nlogn）C、O（ 2n）D、O（ n）21、下面關(guān)于 NP 問(wèn)題說(shuō)法正確的是（ B ）A NP 問(wèn)題都是不可能解決的問(wèn)題B P類問(wèn)題包含在NP類問(wèn)題中C NP完全問(wèn)題是P類問(wèn)題的子集D NP類問(wèn)題包含在P類問(wèn)題中40、背包問(wèn)題的貪心算法所需的計(jì)算時(shí)間為（ B ）A、O (n2n)B、O (nlogn) C、O (2n)D、O (n)42. 0-1背包問(wèn)題

5、的回溯算法所需的計(jì)算時(shí)間為(A )A、O (n2n)B O (nlogn)C O(2n)D、O (n)47.背包問(wèn)題的貪心算法所需的計(jì)算時(shí)間為(B ) oA、O (n2n)B O (nlogn)C O(2n) D、O (n)53 采用貪心算法的最優(yōu)裝載問(wèn)題的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法的時(shí)間復(fù)雜度為( B) oA、O (n2n)B O (nlogn)C O (2n) D O (n)56、算法是由若干條指令組成的有窮序列，而且滿足以下性質(zhì)( D )(1) 輸入：有0個(gè)或多個(gè)輸入(2) 輸出：至少有一個(gè)輸出(3) 確定性：指令清晰，無(wú)歧義(4) 有限性：指令執(zhí)行次數(shù)有限，而且

6、執(zhí)行時(shí)間有限AB(2)C(3)D57、函數(shù)32n+10nlo的漸進(jìn)表達(dá)式是(B ).A. 2 B. 32 C. n logD. 10 nlo59、用動(dòng)態(tài)規(guī)劃算法解決最大字段和問(wèn)題，其時(shí)間復(fù)雜性為(B ).61、設(shè)f(N),g(N)是定義在正數(shù)集上的正函數(shù)，如果存在正的常數(shù)C和自然數(shù)No,使得當(dāng)NNo時(shí)有f(N) Cg(則稱函數(shù)f(N)當(dāng)N充分大時(shí)有下界g(N),記作f(N)O (g(N)即 f(N)的階( A )g(N)的階.A.不高于B.不低于C等價(jià)于D.逼近填空題2、程序是 某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。3、算法的確定性”指的是組成算法的每條指令 是清晰的，無(wú)歧義的&算法是指解決問(wèn)題的或一個(gè)

7、過(guò)程 o 7、從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的程序一般是 涕歸算法11、計(jì)算一個(gè)算法時(shí)間復(fù)雜度通常可以計(jì)算循環(huán)次數(shù)、基本操作的頻率或計(jì)算步。14、解決0/1背包問(wèn)題可以使用動(dòng)態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是動(dòng)態(tài)規(guī)劃，需要排序的是回溯法 ，分支限界法。15、 使用回溯法進(jìn)行狀態(tài)空間樹裁剪分支時(shí)一般有兩個(gè)標(biāo)準(zhǔn)：約束條件和目標(biāo)函數(shù)的界，N皇后問(wèn)題和0/1背包問(wèn)題正好是兩種不同的類型，其中同時(shí)使用約束 條件和目標(biāo)函數(shù)的界進(jìn)行裁剪的是0/1背包問(wèn)題，只使用約束條件進(jìn)行裁剪的是N皇后問(wèn)題。30.回溯法是一種既帶有系統(tǒng)性 又帶有跳躍性的搜索算法。33 回溯法搜索解空間樹時(shí)，常用的兩

8、種剪枝函數(shù)為約束函數(shù)和 限界函數(shù)。34. 任何可用計(jì)算機(jī)求解的問(wèn)題所需的時(shí)間都與其規(guī)模 有關(guān)。35. 快速排序算法的性能取決于劃分的對(duì)稱性。36. Prim算法利用策略求解冋題，其時(shí)間復(fù)雜度是 O(n背包問(wèn)題的回溯算法所需的計(jì)算時(shí)間為o(n *2n)用動(dòng)態(tài)規(guī)劃算法所需的計(jì)算時(shí)間為o(minnc,23。二、綜合題(50分) 寫出設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的主要步驟。 問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；構(gòu)造最優(yōu)值的遞歸關(guān)系表達(dá)式；3最優(yōu)值的算法描述；構(gòu)造最優(yōu)解； 流水作業(yè)調(diào)度問(wèn)題的johnson算法的思想。令N1=i|ai=b；將N中作業(yè)按a的非減序排序得到 N，將 N2中作業(yè)按bi的非增序排序得到N2；N1中作業(yè)接

9、N2 中作業(yè)就構(gòu)成了 滿足Johnson法則的最優(yōu)調(diào)度。)。37. 圖的m著色問(wèn)題可用 回溯法求解，其解空間樹中葉子結(jié)點(diǎn)個(gè)數(shù)是mn_，解空間樹中每個(gè)內(nèi)結(jié)點(diǎn)的孩子數(shù)是m 。4.若序列X=B,C,A,D,B,CQY=A,C,B,A,B,D,C,D請(qǐng)給出序列X和丫的一個(gè)最長(zhǎng)公 共子序列BABCD或CABCD或CADCD。5用回溯法解問(wèn)題時(shí)，應(yīng)明確定義問(wèn)題的解空間，問(wèn)題的解空間至少應(yīng)包含一個(gè)(最優(yōu))解3.若n=4,在機(jī)器 M1和M2上加工作業(yè)i所需的時(shí)間分別為a和bi，且(31,82,33,84) = (4,5,12,10), 時(shí)2內(nèi)4)= (8,2,15,9求4個(gè)作業(yè)的最優(yōu)調(diào)度方案，并計(jì) 算最優(yōu)值。

10、步驟為：N1=1, 3，N2=2, 4；Ni =1, 3， N2 =4, 2；最優(yōu)值為：384.使用回溯法解0/1背包問(wèn)題：n=3, C=9, V=6,10,3, W=3,4,4,其解空間有長(zhǎng)度為3的0-1向量組成，要求用一棵完全二叉樹表示其解空間(從根出發(fā)，左 1 右0),并畫出其解空間樹，計(jì)算其最優(yōu)值及最優(yōu)解。解空間為(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)卜解空間樹為：A10CB1010GDEF11100100ONHJKM該問(wèn)題的最優(yōu)值為：16 最優(yōu)解為：(1, 1, 0)5.設(shè)S=X1, X2, ，X

11、n是嚴(yán)格遞增的有序集，利用二叉樹的結(jié)點(diǎn)來(lái)存儲(chǔ)S中的元素，在表示S的二叉搜索樹中搜索一個(gè)元素 X,返回的結(jié)果有兩種情形，(1) 在二叉搜索樹的內(nèi)結(jié)點(diǎn)中找到 X=X,其概率為bi。(2)在二叉搜索樹的葉結(jié)點(diǎn)中 確定X(X, X+1),其概率為aio在表示S的二叉搜索樹T中，設(shè)存儲(chǔ)元素X 的結(jié)點(diǎn)深度為C;葉結(jié)點(diǎn)(X, X+1)的結(jié)點(diǎn)深度為di ,則二叉搜索樹T的平均路 長(zhǎng)p為多少假設(shè)二叉搜索樹Tij= X , X+1 ,X最優(yōu)值為mij , Wij= ai-1+bi+b+aj ,則mij(1=i=j=n)遞歸關(guān)系表達(dá)式為什么nn二叉樹T的平均路長(zhǎng)P= bi * (1 Ci) + aj* dji 1j

12、 0mij=Wij+minmik+mk+1j (1=i=jj)6.描述0-1背包問(wèn)題。已知一個(gè)背包的容量為C,有n件物品，物品i的重量為Wi，價(jià)值為V ,求應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價(jià)值最大。三、簡(jiǎn)答題(30分)1流水作業(yè)調(diào)度中，已知有n個(gè)作業(yè)，機(jī)器M1和M2上加工作業(yè)i所需的時(shí)間 分別為ai和bi,請(qǐng)寫出流水作業(yè)調(diào)度問(wèn)題的johnson法則中對(duì)a和bi的排序算法。(函數(shù)名可寫為sort(s,n)2最優(yōu)二叉搜索樹問(wèn)題的動(dòng)態(tài)規(guī)劃算法(設(shè)函數(shù)名bin arysearchtree)1.void sort(flowjope s,i nt n)int i,k,j,l;for(i=

13、1;in) break;ag=0)if(sk.asj.a) k=j;swap(si.i ndex,sk.i ndex);swap(si.tag,sk.tag); l=i;sj.b) k=j;swap(si.i ndex,sk.i ndex); ag,sk.tag);2.void bin arysearchtree(i nt a,i nt b,i nt n ,i nt *m,i nt *s,i nt *w) int i,j,k,t,l; for(i=1;i=n+1;i+) wii-1=ai-1;mii-1=0;for(l=0;ldo u=min(Q)S=SJ ufor each vertex3，

14、現(xiàn)設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表:do 4四、算法理解題(本題10分)根據(jù)優(yōu)先隊(duì)列式分支限界法，求 下圖中從v1點(diǎn)到v9點(diǎn)的單源最 短路徑，請(qǐng)畫出求得最優(yōu)解的解 空間樹。要求中間被舍棄的結(jié)點(diǎn) 用x標(biāo)記，獲得中間解的結(jié)點(diǎn)用 單圓圈O框起，最優(yōu)解用雙圓圈 框起。五、算法理解題(本題5分)設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行循環(huán)賽每個(gè)選手必須與其他 n-1 名選手比賽各一次； 每個(gè)選手一天至多只能賽一次； 循環(huán)賽要在最短時(shí)間內(nèi)完成。（1）如果n=2k，循環(huán)賽最少需要進(jìn)行幾天；（ 2）當(dāng) n=23=8 時(shí)，請(qǐng)畫出循環(huán)賽日程表。六、算法設(shè)計(jì)題（本題 15 分） 分別用貪心算法、動(dòng)態(tài)規(guī)劃法、回溯法設(shè)計(jì) 0-1 背

15、包問(wèn)題。要求：說(shuō)明所使 用的算法策略；寫出算法實(shí)現(xiàn)的主要步驟；分析算法的時(shí)間。七、算法設(shè)計(jì)題（本題 10 分）通過(guò)鍵盤輸入一個(gè)高精度的正整數(shù) n（n的有效位數(shù)w 240），去掉其中任意s 個(gè)數(shù)字后，剩下的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。 編程對(duì)給定的 n 和 s,尋找一種方案，使得剩下的數(shù)字組成的新數(shù)最小?！緲永斎搿?78543S=4【樣例輸出】13二、簡(jiǎn)答題（本題 25 分，每小題 5 分）1、分治法的基本思想是將一個(gè)規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn) 題，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題相同；對(duì)這 k 個(gè)子問(wèn)題分別求解。如 果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為 k 個(gè)子問(wèn)題，如此遞

16、歸的進(jìn)行下 去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止；將求出的小規(guī)模的問(wèn)題 的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。2、“最優(yōu)化原理 ”用數(shù)學(xué)化的語(yǔ)言來(lái)描述：假設(shè)為了解決某一優(yōu)化問(wèn)題，需要依次作出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)的。3、某個(gè)問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。這種性質(zhì)稱為 最優(yōu)子結(jié)構(gòu) 性質(zhì)。4、回溯法的基本思想 是在一棵含有問(wèn)題全部可能解的狀態(tài)空間樹上進(jìn)行深 度優(yōu)先搜索

17、，解為葉子結(jié)點(diǎn)。搜索過(guò)程中，每到達(dá)一個(gè)結(jié)點(diǎn)時(shí)，則判斷該 結(jié)點(diǎn)為根的子樹是否含有問(wèn)題的解，如果可以確定該子樹中不含有問(wèn)題的 解，則放棄對(duì)該子樹的搜索，退回到上層父結(jié)點(diǎn)，繼續(xù)下一步深度優(yōu)先搜 索過(guò)程。在回溯法中，并不是先構(gòu)造出整棵狀態(tài)空間樹，再進(jìn)行搜索，而 是在搜索過(guò)程，逐步構(gòu)造出狀態(tài)空間樹，即邊搜索，邊構(gòu)造。5、P（Poly nomia I問(wèn)題）：也即是多項(xiàng)式復(fù)雜程度的問(wèn)題。NP 就是 Non-deterministicPolynomial 的問(wèn)題，也即是多項(xiàng)式復(fù)雜程度的非確 定性問(wèn)題。NPC（NP Complete問(wèn)題，這種問(wèn)題只有把解域里面的所有可能都窮舉了之后NPC問(wèn)才能得出答案，這樣的冋

18、題是 NP里面最難的冋題，這種冋題就是 題。三、算法填空（本題20分，每小題5分）1、n后冋題回溯算法!Mj&!Li+j&!Ri-j+N(2) Mj=Li+j=Ri-j+N=1; try(i+1,M,L,R,A) Aij=0(5) Mj=Li+j=Ri-j+N=02、數(shù)塔問(wèn)題。(1) c=r trc+=tr+1c(3) trc+=tr+1c+13、Hanoi 算法(1) move(a,c)(2) Hanoi(n-1, a, c , b)(3) Move(a,c)4、(1) pv=NIL(2) pv=u(3) v adju(4) Relax(u,v,w)五、（1） 8天（2分）;（2）當(dāng)n=23

19、=8時(shí)，循環(huán)賽日程表六、算法設(shè)計(jì)題（本題15分）（1）貪心算法 O （nlog （n）1 2 3 45 6 7 82 1 4 36 5 8 73 4 1 27 8 5 64 3 2 18 7 6 55 6 7 81 2 3 43 分）。6 5 8 72 1 4 37 8 5 63 4 1 28 7 6 54 3 2 1四、算法理解題(本題10 分)將盡首先計(jì)算每種物品單位重量的價(jià)值 Vi/Wi，然后，依貪心選擇策略,可能多的單位重量?jī)r(jià)值最高的物品裝入背包。 若將這種物品全部裝入背包 后，背包內(nèi)的物品總重量未超過(guò) C,則選擇單位重量?jī)r(jià)值次高的物品并盡 可能多地裝入背包。依此策略一直地進(jìn)行下去，直

20、到背包裝滿為止。具體算法可描述如下：void Kn apsack(i nt n,float M,float v,float w,float x)Sort( n,v,w);int i;for (i=1;i=n ;i+) xi=0;float c=M;for (i=1;ic) break;xi=1;c-=wi;if (i=n) xi=c/wi;(2) 動(dòng)態(tài)規(guī)劃法0( nc)m(i, j)是背包容量為j,可選擇物品為i, i+1,，n時(shí)0-1背包問(wèn)題的最優(yōu) 值。由0-1背包問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i, j)的遞歸式如下。maxm(i 1, j),m(i 1, j wj w j Wjm(

21、i, j)m(i 1, j)0 jWim(n, j)VnWnWnvoid Kn apSack(i nt v,i nt w,i nt c,i nt n,i nt m11)int jMax=mi n(w n-1,c);for (j=0;j=jMax;j+)/*m( n,j)=00=j=w n*/m nj=v n;for (i=n-1;i1;i-) int jMax=mi n(wi-1,c);for (j=0;j=jMax;j+)/*m(i,j)=m(i+1,j)0=jwi*/mij=mi+1j;for (j=wi;j=w n*/mij=max(mi+1j,mi+1j-wi+vi);m1c=m2c;

22、if(c=w1)m1c=max(m1c,m2c-w1+v1);(3)回溯法0(2n) cw:當(dāng)前重量 cp:當(dāng)前價(jià)值 bestp：當(dāng)前最優(yōu)值 voidbacktrackQ nt i)包冋題的貪心算法void Knapsack(int n,float M,float v,float w,float x)Sort( n,v,w);int i;for (i=1;i=n ;i+) xi=0;float c=M;for (i=1;ic) break;xi=1;c - =wi;if (ivoid Quicksort (Type a, int p, int r)if (pr) int q=Partiti o

23、n( a,p,r);Quicksort (a,p,q-1):列問(wèn)題Template void perm(Type list, int k, int m )定已按升序排好序的n個(gè)元素a0:n-1，現(xiàn)要在這n個(gè)元素中找出一特定元素 據(jù)此容易設(shè)計(jì)出二分搜索算法：templatevclass Typeint Bin arySearch(Type a, const Type& x, int l, i nt r)while (l=r )int m = (l+r);if (x = am) return m;if (x void Mergesort(Type a , i nt left, int right)

24、if (leftvright)int i=( left+right)/2;Mergesort(a, left, i ); Mergesort(a, i+1, right);Merge(a,b, left,i,right);計(jì)算機(jī)求解問(wèn)題的步驟：1、問(wèn)題分析2、數(shù)學(xué)模型建立3、算法設(shè)計(jì)與選擇4、算法指標(biāo)5、算法分析 6算法實(shí)現(xiàn)7、程序調(diào)試8、結(jié)果整理文檔編制2. 算法定義：算法是指在解決問(wèn)題時(shí)，按照某種機(jī)械步驟一定可以得到問(wèn)題結(jié)果的處理過(guò)程3算法的三要素1、操作2、控制結(jié)構(gòu)3、數(shù)據(jù)結(jié)構(gòu)13.分治法與動(dòng)態(tài)規(guī)劃法的相同點(diǎn)是：將待求解的問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)

25、題的解兩者的不同點(diǎn)是：適合于用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題，經(jīng)分解得到的子問(wèn)題往 往不是互相獨(dú)立的。而用分治法求解的問(wèn)題，經(jīng)分解得到的子問(wèn)題往往是互相獨(dú) 立的。回溯法中常見(jiàn)的兩類典型的解空間樹是子集樹和排列樹。22.請(qǐng)敘述動(dòng)態(tài)規(guī)劃算法與貪心算法的異同。 共同點(diǎn)：都需要最優(yōu)子結(jié)構(gòu)性質(zhì)，都用來(lái)求有優(yōu)化問(wèn)題。 不同點(diǎn)：動(dòng)態(tài)規(guī)劃：每一步作一個(gè)選擇 一依賴于子問(wèn)題的解。貪心方法：每一步作一個(gè)選擇 一不依賴于子問(wèn)題的解。動(dòng)態(tài)規(guī)劃方法的條件：子問(wèn)題的重疊性質(zhì)?？捎秘澬姆椒ǖ臈l件：最優(yōu)子結(jié)構(gòu)性質(zhì)；貪心選擇性質(zhì)。動(dòng)態(tài)規(guī)劃：自底向上求解；貪心方法：自頂向下求解?？捎秘澬姆〞r(shí)，動(dòng)態(tài)規(guī)劃方法可能不適用；可用動(dòng)態(tài)規(guī)劃方法時(shí)，貪

26、心法可能不適用。23請(qǐng)說(shuō)明動(dòng)態(tài)規(guī)劃方法為什么需要最優(yōu)子結(jié)構(gòu)性質(zhì)。答：最優(yōu)子結(jié)構(gòu)性質(zhì)是指大問(wèn)題的最優(yōu)解包含子問(wèn)題的最優(yōu)解。動(dòng)態(tài)規(guī)劃方法是自底向上計(jì)算各個(gè)子問(wèn)題的最優(yōu)解，即先計(jì)算子問(wèn)題的最優(yōu)解，然后再利用子問(wèn)題的最優(yōu)解構(gòu)造大問(wèn)題的最優(yōu)解，因此需要最優(yōu)子結(jié)構(gòu)24.請(qǐng)說(shuō)明：(1) 優(yōu)先隊(duì)列可用什么數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)(2) 優(yōu)先隊(duì)列插入算法基本思想(3) 優(yōu)先隊(duì)列插入算法時(shí)間復(fù)雜度答：(1)堆。(2)在小根堆中，將元素x插入到堆的末尾， 然后將元素x的關(guān)鍵字與其雙親的關(guān)鍵字比較， 若元素x的關(guān)鍵字小于其雙親的關(guān)鍵字， 則將元素x與其雙親交換，然后再將元素x與其新雙親的關(guān)鍵字相比, 直到元素x的關(guān)鍵字大于雙親的

27、關(guān)鍵字，或元素 x到根為止。(3)O( log n)26.在算法復(fù)雜性分析中，O、Q、E這三個(gè)記號(hào)的意義是什么在忽略常數(shù)因子的情況下，O、Q、E分別提供了算法運(yùn)行時(shí)間的什么界答：如果存在兩個(gè)正常數(shù)c和NO,對(duì)于所有的NA NO,有|f(N)| C|g(N)|，則記作：f(N)= O(g(N)。這時(shí)我們說(shuō)f(N)的階不高于g(N)的階。若存在兩個(gè)正常數(shù)C和自然數(shù)NO,使得當(dāng)N A NO時(shí)有| f(N)| A qg(N)|，記為 f(N)=(g(N)。這時(shí)我們說(shuō)f(N)的階不低于g(N)的階。如果存在正常數(shù) cl，c2和n0，對(duì)于所有的 n An0，有c1|g(N)| |f(N)| 000B0 0

28、11C0 01D0 012f2A0 11212最長(zhǎng)公共子序列：BC2.對(duì)下列各組函數(shù) f (n)和 g (n),確定 f (n) = O (g (n)或 f (n) =Q (g (n)或 f(n)=9 (g(n),并簡(jiǎn)要說(shuō)明理由(1) f(n )=2n;g( n)=n!(2) f(n)- n ;g (n)=log n2 f(n )=100;g(n )=log100 f(n)=n3;g( n)=印 f(n)=3 n;g(n )=2n答：(1) f(n) = O(g(n)因?yàn)間(n)的階比f(wàn)(n)的階高。 f(n) = Q (g(n)因?yàn)間(n)的階比f(wàn)(n)的階低。 f(n) = 9 (g(n)

29、因?yàn)間(n)與f(n)同階。 f(n) = O(g(n)因?yàn)間(n)的階比f(wàn)(n)的階高。 f(n) = Q (g(n)因?yàn)間(n)的階比f(wàn)(n)的階低。3.對(duì)下圖所示的連通網(wǎng)絡(luò) G，用克魯斯卡爾(Kruskal算法求G的最小生成樹T, 請(qǐng)寫出在算法執(zhí)行過(guò)程中，依次加入 T的邊集TE中的邊。說(shuō)明該算法的貪心策 略和算法的基本思想，并簡(jiǎn)要分析算法的時(shí)間復(fù)雜度。答：TE=(3,4), (2,3),(1,5),(4,6) (4,5) 貪心策略是每次都在連接兩個(gè)不同連通分量的邊中選權(quán)值最小的邊?；舅枷耄菏紫葘D中所有頂點(diǎn)都放到生成樹中，然后每次都在連接兩個(gè)不 同連通分量的邊中選權(quán)值最小的邊，將其放入

30、生成樹中，直到生成樹中有n-1條邊。時(shí)間復(fù)雜度為：O(eloge)4請(qǐng)用分治策略設(shè)計(jì)遞歸的歸并排序算法，并分析其時(shí)間復(fù)雜性(要求：分別 給出divide、conquer、combine這三個(gè)階段所花的時(shí)間，并在此基礎(chǔ)上列出遞歸1234567方程，最后用套用公式法求出其解的漸進(jìn)階） 答 ： Template void MergeSort (Type a , int left, int right) if (leftright) int i=(left+right ) /2;MergeSort(a, left, i) ; MergeSort(a, i+1, right) ;Merge(a, b,

31、left, right);Copy(a, b, left, right);Divide 階段的時(shí)間復(fù)雜性：O(1)Conquer 階段的時(shí)間復(fù)雜性：2T(n)Combine階段的時(shí)間復(fù)雜性： (n)T(n)02T(n/2)0 (n)用套用公式法：a=2, b=2, nog ba = n , f(n)=n, 因?yàn)?f(n)與 nlog ba 同階, T(n) =0 (n log n)12345678214365873412785643218765567812346587214378563412876543215、設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行循環(huán)賽，現(xiàn)設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表： 每個(gè)選手必須

32、與其他n-1名選手比賽各一次；每個(gè)選手一天至多只能賽一次； 循環(huán)賽要在最短時(shí)間內(nèi)完成.（1）（ 4分）循環(huán)賽最少需要進(jìn)行（n-1 ）天.（2）（6分）當(dāng)n=23=8時(shí)，請(qǐng)畫出循環(huán)賽日程表：&考慮用哈夫曼算法來(lái)找字符a,b,c,d,e,f的最優(yōu)編碼。這些字符出現(xiàn)在文件中 的頻數(shù)之比為 20:10:6:4:44:16。要求：（1）（ 4分）簡(jiǎn)述使用哈夫曼算法構(gòu)造最優(yōu)編碼的基本步驟；（2） （5分）構(gòu)造對(duì)應(yīng)的哈夫曼樹，并據(jù)此給出a,b,c,d,e,f的一種最優(yōu)編碼。解：1）、哈夫曼算法是構(gòu)造最優(yōu)編碼樹的貪心算法。其基本思想是，首先所有字符對(duì)應(yīng)n棵樹構(gòu)成的森林，每棵樹只有一個(gè)結(jié)點(diǎn)，根權(quán)為對(duì)應(yīng)字符的頻率。 然后，重復(fù)下列過(guò)程n-1次：將森林中的根權(quán)最小的兩棵樹進(jìn)行合并產(chǎn)生一個(gè)新樹，該新樹根的兩個(gè)子樹分別是參