《算法分析與設(shè)計(jì)》期末考試復(fù)習(xí)題綱

1、優(yōu)選文檔算法分析與設(shè)計(jì)期末復(fù)習(xí)題一、選擇題1.算法必定具備輸入、輸出和（D）等4個(gè)特點(diǎn)。A可行性和安全性B確定性和易讀性C有窮性和安全性D有窮性和確定性2.算法分析中，記號(hào)O表示（B），記號(hào)表示（A）A.漸進(jìn)下界B.漸進(jìn)上界C.非緊上界D.緊漸進(jìn)界假定某算法在輸入規(guī)模為n時(shí)的計(jì)算時(shí)間為T(n)=3*2n。在某臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)并達(dá)成概算法的時(shí)間為t秒?，F(xiàn)有另一臺(tái)計(jì)算機(jī)，其運(yùn)行速度為第一臺(tái)的64倍，那么在這臺(tái)新機(jī)器上用同一算法在t秒內(nèi)能解輸入規(guī)模為多大的問題？（B）解題方法：3*2n*64=3*2xAn+8Bn+6Cn+7Dn+54.設(shè)問題規(guī)模為N時(shí)，某遞歸算法的時(shí)間復(fù)雜度記為T(N)，已知T(1)

2、=1，T(N)=2T(N/2)+N/2，用O表示的時(shí)間復(fù)雜度為（C）。AO(logN)BO(N)CO(NlogN)DO(N2logN)5.直接或間接調(diào)用自己的算法稱為（B）。A貪心算法B遞歸算法C迭代算法D回溯法6.Fibonacci數(shù)列中，第4個(gè)和第11個(gè)數(shù)分別是（D）。A5，89B3，89C5，144D3，1447.在有8個(gè)極點(diǎn)的凸多邊形的三角剖分中，恰有（B）。A6條弦和7個(gè)三角形B5條弦和6個(gè)三角形C6條弦和6個(gè)三角形D5條弦和5個(gè)三角形8.一個(gè)問題可用動(dòng)向規(guī)劃算法或貪心算法求解的重點(diǎn)特點(diǎn)是問題的（B）。A重疊子問題B最優(yōu)子結(jié)構(gòu)性質(zhì)C貪心選擇性質(zhì)D定義最優(yōu)解9.以下哪個(gè)問題不用貪心法求

3、解（C）。A哈夫曼編碼問題B單源最短路徑問題C最大團(tuán)問題D最小生成樹問題10.以下算法中平常以自底向上的方式求解最優(yōu)解的是（B）。A備忘錄法B動(dòng)向規(guī)劃法C貪心法D回溯法以下算法中不能夠解決0/1背包問題的是（A）。A貪心法B動(dòng)向規(guī)劃C回溯法D分支限界法12.以下哪個(gè)問題能夠用貪心算法求解（D）。.優(yōu)選文檔ALCS問題B批辦理作業(yè)問題C0-1背包問題D哈夫曼編碼問題13.用回溯法求解最優(yōu)裝載問題時(shí)，若待選物品為m種，則該問題的解空間樹的結(jié)點(diǎn)個(gè)數(shù)為（）。Am!B2m+1C2m+1-1D2m14.二分找尋算法是利用（A）實(shí)現(xiàn)的算法。A分治策略B動(dòng)向規(guī)劃法C貪心法D回溯法15.以下不是動(dòng)向規(guī)劃算法基本

4、步驟的是（B）。P44A找出最優(yōu)解的性質(zhì)B結(jié)構(gòu)最優(yōu)解C算出最優(yōu)解(應(yīng)該是最優(yōu)值)D定義最優(yōu)解16.下面問題（B）不能夠使用貪心法解決。A單源最短路徑問題BN皇后問題C最小開銷生成樹問題D背包問題使用二分找尋算法在n個(gè)有序元素表中找尋一個(gè)特定元素，在最好情況和最壞情況下找尋的時(shí)間復(fù)雜性分別為（A）。P17AO(1)，O(logn)BO(n)，O(logn)CO(1)，O(nlogn)DO(n)，O(nlogn)18.優(yōu)先行列式分支限界法采納擴(kuò)展結(jié)點(diǎn)的原則是（C）。P162A先進(jìn)先出B后進(jìn)先出C結(jié)點(diǎn)的優(yōu)先級(jí)D隨機(jī)19.下面不是分支界線法找尋方式的是（D）。P161A廣度優(yōu)先B最小耗資優(yōu)先C最大效益

5、優(yōu)先D深度優(yōu)先20.分支限界法解最大團(tuán)問題時(shí)，活結(jié)點(diǎn)表的組織形式是（B）。A最小堆B最大堆C棧D數(shù)組21.以下對(duì)于計(jì)算機(jī)算法的描繪不正確的選項(xiàng)是（C）。P1A算法是指解決問題的一種方法或一個(gè)過程B算法是若干指令的有窮序列算法必定要有輸入和輸出D算法是編程的思想22.以下對(duì)于凸多邊形最優(yōu)三角剖分問題描繪不正確的選項(xiàng)是（A）。An+1個(gè)矩陣連乘的完好加括號(hào)和n個(gè)點(diǎn)的凸多邊形的三角剖分對(duì)應(yīng)B在有n個(gè)極點(diǎn)的凸多邊形的三角剖分中，恰有n-3條弦C該問題能夠用動(dòng)向規(guī)劃法來求解D在有n個(gè)極點(diǎn)的凸多邊形的三角剖分中，恰有n-2個(gè)三角形23.動(dòng)向規(guī)劃法求解問題的基本步驟不包括（C）。P44A遞歸地定義最優(yōu)值B分

6、析最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特點(diǎn)C依照計(jì)算最優(yōu)值時(shí)獲取的信息，結(jié)構(gòu)最優(yōu)解(能夠省去的)D以自底向上的方式計(jì)算出最優(yōu)值24.分治法所能解決的問題應(yīng)擁有的重點(diǎn)特點(diǎn)是（C）。P16.優(yōu)選文檔A該問題的規(guī)模減小到必然的程度就能夠簡(jiǎn)單地解決B該問題能夠分解為若干個(gè)規(guī)模較小的相同問題C利用該問題分解出的子問題的解能夠歸并為該問題的解D該問題所分解出的各個(gè)子問題是互相獨(dú)立的25.以下對(duì)于回溯法的描繪不正確的選項(xiàng)是（D）。P114A回溯法也稱為試試法B回溯法有“通用解題法”之稱C回溯法是一種能防范不用要找尋的窮舉式找尋法D用回溯法對(duì)解空間作深度優(yōu)先找尋時(shí)只能用遞歸方法實(shí)現(xiàn)26.常有的兩種分支限界法為（D）。P

7、161廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法；行列式（FIFO）分支限界法與貨倉(cāng)式分支限界法；排列樹法與子集樹法；行列式（FIFO）分支限界法與優(yōu)先行列式分支限界法；二、填空題1.f(n)=3n2+10的漸近性態(tài)f(n)=O(n2)，g(n)=10log3n的漸近性態(tài)g(n)=O(n)。2.一個(gè)“好”的算法應(yīng)擁有正確性、可讀性、強(qiáng)健性和高效率和低儲(chǔ)藏量需求等特點(diǎn)。3.算法的時(shí)間復(fù)雜性函數(shù)表示為C=F(N,I,A)，分析算法復(fù)雜性的目的在于比較求解贊成問題的兩個(gè)不相同算法的效率的效率。4.組成遞歸式的兩個(gè)基本要素是遞歸的界線條件和遞歸的定義。5.單源最短路徑問題可用分支限界法和貪心算法求解。6.

8、用分治法實(shí)現(xiàn)迅速排序算法時(shí)，最好情況下的時(shí)間復(fù)雜性為O(nlogn)，最壞情況下的時(shí)間復(fù)雜性為O(n2)，該算法所需的時(shí)間與運(yùn)行時(shí)間和區(qū)分兩方面要素有關(guān)。P267.0-1背包問題的解空間樹為完好二叉樹；n后問題的解空間樹為排列樹；8.常有的分支限界法有行列式（FIFO）分支限界法和優(yōu)先行列式分支限界法。9.回溯法找尋解空間樹常常用的兩種剪枝函數(shù)為拘束函數(shù)和剪枝函數(shù)。10.分支限界法解最大團(tuán)問題時(shí)，活結(jié)點(diǎn)表的組織形式是最大堆；分支限界法解單源最短路徑問題時(shí)，活結(jié)點(diǎn)表的組織形式是最小堆。三、算法填空題遞歸求解Hanoi塔問題/階乘問題。例1:階乘函數(shù)n!P12階乘的非遞歸方式定義：n!n(n1)(

9、n2)21試寫出階乖的遞歸式及算法。遞歸式為：1n0界線條件n!n(n1)!n0.優(yōu)選文檔遞歸方程遞歸算法：intfactorial(intn)if(n=0)return1;遞歸出口returnn*factorial(n-1);遞歸調(diào)用例2:用遞歸技術(shù)求解Hanoi塔問題,Hanoi塔的遞歸算法。P15其中Hanoi(intn,inta,intc,intb)表示將塔座A上的n個(gè)盤子移至塔座C，以塔座B為協(xié)助。Move(a,c)表示將塔座a上編號(hào)為n的圓盤移至塔座c上。voidhanoi(intn,inta,intc,intb)if(n0)hanoi(n-1,a,b,c);move(a,c);h

10、anoi(n-1,b,c,a);用分治法求解迅速排序問題。迅速排序算法P25、作業(yè)、課件第2章（2）42頁-50頁templatevoidQuickSort(Typea,intp,intr)if(pr)intq=Partition(a,p,r);QuickSort(a,p,q-1);QuickSort(a,q+1,r)；.優(yōu)選文檔Partition函數(shù)的詳細(xì)實(shí)現(xiàn)templateintPartition(Typea,intp,intr)inti=p,j=r+1;Typex=ap;將x的元素互換到右邊地區(qū)while(true)while(a+ix&ix);if(i=j)break;Swap(ai,

11、aj);ap=aj;aj=x;returnj;用貪心算法求解最優(yōu)裝載問題。最優(yōu)裝載問題P95課件第4章(2)第3-8頁templatevoidLoading(intx,Typew,Typec,intn)int*t=newintn+1;Sort(w,t,n);for(inti=1;i=n;i+)xi=0;for(intj=1;j=n&wtj=c;j+)xti=1;c-=wtj;.優(yōu)選文檔用回溯法求解0-1背包/批辦理作業(yè)調(diào)動(dòng)/最大團(tuán)問題，要會(huì)畫解空間樹。例1：用回溯法求解0-1背包P133課件第5章(2)第24-38頁templateclassKnapprivate:TypepBound(int

12、i);/計(jì)算上界voidBacktrack(inti);Typewc;/背包括量intn;/物品數(shù)Typew*w;/物品重量數(shù)組Typep*p;/物品價(jià)值數(shù)組Typewcw;/目前重量Typepcp;/目前價(jià)值Typepbestp;/目前最優(yōu)價(jià)值;voidKnap:Backtrack(inti)if(in)bestp=cp;return;if(cw+wibestp)/進(jìn)入右子樹Backtrack(i+1);TypepKnap:Bound(inti)Typewcleft=c-cw;/節(jié)余的背包括量Typepb=cp;/b為目前價(jià)值依次裝入單位重量?jī)r(jià)值高的整個(gè)物品.優(yōu)選文檔while(i=n&wi

13、=cleft)cleft-=wi;b+=pi;i+;if(i=n)/裝入物品的一部分b+=pi*cleft/wi;returnb;/返回上界classObject/物品類friendintKnapsack(int*,int*,int,int);public:intoperator=a.d);intID;/物品編號(hào)floatd;/單位重量?jī)r(jià)值;TypepKnapsack(Typepp,Typeww,Typewc,intn)/為TypepKnapsack初始化TypewW=0;/總重量TypepP=0;/總價(jià)值Object*Q=newObjectn;/創(chuàng)辦物品數(shù)組，下標(biāo)從0開始for(inti=1

14、;i=n;i+)/初始物品數(shù)組數(shù)據(jù)Qi-1.ID=i;Qi-1.d=1.0*pi/wi;P+=pi;W+=wi;if(W=c)/能裝入所有物品returnP;if(W=c)/能裝入所有物品returnP;QuickSort(Q,0,n-1);/依物品單位重量?jī)r(jià)值非增排序.優(yōu)選文檔KnapK;K.p=newTypepn+1;K.w=newTypewn+1;for(inti=1;in)for(intj=1;j=n;j+)bestxj=xj;bestf=f;elsefor(intj=i;jf1)?f2i-1:f1)+mxj2;f+=f2i;if(fn)for(intj=1;j=n;j+)bestxj

15、=xj;bestn=cn;return;/判斷第i個(gè)極點(diǎn)可否與已選極點(diǎn)都有邊相連intOK=1;for(intj=1;jbestn)/如有可能在右子樹中找到更大的團(tuán)，則進(jìn)入右子樹xi=0;Backtrack(i+1);計(jì)算時(shí)間：O(n2n)四、簡(jiǎn)答題1.請(qǐng)簡(jiǎn)述使用動(dòng)向規(guī)劃算法解題的基本步驟。P44動(dòng)向規(guī)劃的設(shè)計(jì)分為以下4個(gè)步驟：(1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特點(diǎn)。(2)遞歸地定義最優(yōu)值。(3)以自底向上的方式計(jì)算出最優(yōu)值。(4)依照計(jì)算最優(yōu)值時(shí)獲取的信息，結(jié)構(gòu)最優(yōu)解。2.簡(jiǎn)述動(dòng)向規(guī)劃方法與分治法的異同。P44相同點(diǎn)：動(dòng)向規(guī)劃算法與分治法近似，其基本思想也是將待求解問題分解成若干個(gè)子問題,

16、爾后從這些子問題的解獲取原問題的解。不相同點(diǎn)：分治法的子問題互相獨(dú)立且與原問題相同。與分治法不相同的是，適合于動(dòng)向規(guī)劃求解的問題，經(jīng)分解獲取的子問題常常不是互相獨(dú)立的。也就是各個(gè)子問題包括公共的子子問題。3.試比較Prim算法與Kruskal算法的異同。105-P107.優(yōu)選文檔相同點(diǎn)：Prim(普里姆)算法和Kruskal(克魯斯卡爾)算法都能夠看作是應(yīng)用貪心算法結(jié)構(gòu)最小生成樹的例子。利用了最小生成樹性質(zhì)。不相同點(diǎn)：Prim(普里姆)算法：在這個(gè)過程中采納到的所有邊恰巧組成G的一棵最小生成樹T，T中包含G的n-1條邊，且不形成回路。Kruskal(克魯斯卡爾)算法：是結(jié)構(gòu)最小生成樹的另一個(gè)常

17、用算法。該算法不是經(jīng)過擴(kuò)大連通子集來進(jìn)行貪心選擇。而是經(jīng)過選擇擁有最小權(quán)的邊的會(huì)合來進(jìn)行貪心選擇。在選擇的同時(shí)能夠進(jìn)行連通操作以便形成生成樹。4.請(qǐng)簡(jiǎn)述分支限界法的找尋策略。P161課件第6章(1)第6頁分支限界法以廣度優(yōu)先或以最小耗資（最大效益）優(yōu)先的方式找尋問題的解空間樹。每一個(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)中，致使不能行解或致使非最優(yōu)解的兒子結(jié)點(diǎn)被舍棄，其他兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為目前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個(gè)過程素來連續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。5.試比較分支限界法與回溯法的

18、異同。P161課件第6章(1)第5頁不相同點(diǎn)：求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中知足拘束條件的所有解，而分支限界法的求解目標(biāo)則是找出知足拘束條件的一個(gè)解，或是在知足拘束條件的解中找出在某種意義下的最優(yōu)解。找尋方式：回溯法以深度優(yōu)先的方式找尋解空間樹，而分支限界法例以廣度優(yōu)先或以最小耗資優(yōu)先的方式找尋解空間樹。五、算法應(yīng)用題用動(dòng)向規(guī)劃求解凸多邊形最優(yōu)三角剖分問題。三角剖分的結(jié)構(gòu)及其有關(guān)問題P61語法樹與完好加括號(hào)方式一個(gè)表達(dá)式的完好加括號(hào)方式相應(yīng)于一棵完好二叉樹，稱為表達(dá)式的語法樹。比方，完好加括號(hào)的矩陣連乘積(A1(A2A3)(A4(A5A6)所相應(yīng)的語法樹如圖(a)所示。.優(yōu)選文檔(

19、2)語法樹與凸多邊形三角剖分凸多邊形P=v0,v1,vn-1的三角剖分也能夠用語法樹表示。如圖：根結(jié)點(diǎn)是邊v0v6(能夠任選)。其他邊則是語法樹的葉子節(jié)點(diǎn)。v0v6是三角形v0v3v6的一條邊。2、三角剖分與矩陣連乘P61一般來說，凸多邊形的三角剖分和有n-1個(gè)葉節(jié)點(diǎn)的語法樹存在一一對(duì)應(yīng)關(guān)系。(2)N個(gè)矩陣連乘的完好加括號(hào)和有n個(gè)葉節(jié)點(diǎn)的語法樹也存在一一對(duì)應(yīng)關(guān)系。因此，n個(gè)矩陣連乘的完好加括號(hào)和有n+1個(gè)節(jié)點(diǎn)的凸多邊形的三角剖分也存在一一對(duì)應(yīng)關(guān)系。.優(yōu)選文檔(4)矩陣連乘積中A1A2An中的每個(gè)矩陣Ai對(duì)應(yīng)于凸(n+1)邊形中的一條邊vi-1vi。三角剖分中的一條弦vivj，ibestp.(3

20、).連續(xù)向下找尋生成結(jié)點(diǎn)F，獲取可行解(1,1,1,0,0)，獲取價(jià)值為86，更新bestp=86(如圖第3步).優(yōu)選文檔.優(yōu)選文檔第3步第5步第8步(4).回溯：沿E回溯到左孩子D，生成相應(yīng)右孩子G，獲取部分解(1,1,0,1),此時(shí)b=93.1bbestp,能夠生成右子樹（第4步在第5步的基礎(chǔ)上沒有H和I的圖形）(5).連續(xù)生成結(jié)點(diǎn)H,I，獲取可行解(1,1,0,1,0),價(jià)值為88，更新bestp=88(如圖第5步)(6).回溯H生成J，獲取部分解(1,1,0,0),估計(jì)部分解b=9288（第6步在第8步的基礎(chǔ)上沒有K和L的圖形）(7).連續(xù)生成結(jié)點(diǎn)K，獲取可行解(1,1,0,0,1),

21、價(jià)值為92，更新bestp=92（第7步在第8步的基礎(chǔ)上沒有L的圖形）(8).K是左孩子，生成其對(duì)應(yīng)的右孩子L，獲取可行解(1,1,0,0,0)(如圖第8步)(9).回溯,沿結(jié)點(diǎn)L向上回溯到結(jié)點(diǎn)B,生成結(jié)點(diǎn)M,獲取部分解(1,0),估計(jì)部分解b=9092,回溯（第9步在第10步的基礎(chǔ)上沒有N的圖形）(10).向上連續(xù)回溯生成結(jié)點(diǎn)N，獲取部分解(0)，此時(shí)獲取的b=74+10*(46/27)=91.0392,回溯，此時(shí)已回到根結(jié)點(diǎn)，結(jié)束。最優(yōu)解(1,1,0,0,1),價(jià)值為92.(如圖第10步).優(yōu)選文檔練習(xí)n=8,M=110，W=(1,11,21,23,33,43,45,55)P=(11,21,31,33,43,53,55,65)用回溯法求此0-1背包問題的最優(yōu)解。最優(yōu)裝載問題P119課件第P37-P54頁假定n=4，w=8,6,2,3，c1=c2=12.試依照改良后的最優(yōu)裝載算法找出最優(yōu)裝載量及相應(yīng)的最優(yōu)裝載方案。要求：列出問題的解空間。結(jié)構(gòu)解空間樹。依照遞歸回溯算法求出最優(yōu)解和最優(yōu)值。.優(yōu)選文檔六、算法設(shè)計(jì)題使用貪心算法求解。題型一：開會(huì)問題：某企業(yè)的會(huì)議好多，致使于全企業(yè)唯一的會(huì)議室不夠用?，F(xiàn)在給出這段時(shí)期的會(huì)議時(shí)間表，要求你適合刪除一些會(huì)議，使得節(jié)余的會(huì)議在時(shí)間上互不矛盾，要求刪除的會(huì)議數(shù)最少。解題算法:templatevoidGS(intn,Types,Typef,bo