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

PAGEPAGE22《算法分析與設(shè)計》期末復(fù)習(xí)題一、選擇題算法必須具備輸入、輸出和（ D ）等4個特性。A．可行性和安全性 B．確定性和易讀C．有窮性和安全性 D．有窮性和確定性算法分析中，記號O表示（ B ），記號Ω表示（ A A.漸進下界 B.漸進上界C.非緊上界 進界假設(shè)某算法在輸入規(guī)模為n時的計算時間為T(n)=3*2^n。在某臺計算機上實現(xiàn)并完成概算法的時間為t秒。現(xiàn)有另一臺計算機，其運行速度為第一臺的64倍，那么在這臺新機器上用同一算法在tB解題方法：3*2^n*64=3*2^xA．n+8 B．n+6C．n+7 D．n+5設(shè)問題規(guī)模為N時，某遞歸算法的時間復(fù)雜度記為T(NT(1)=1O（C）。A．O(logN) B．O(N)C．O(NlogN) D．O(NlogN)直接或間接調(diào)用自身的算法稱為（ B ）。A．貪心算法 B．遞歸算C．迭代算法 D．回溯法Fibonacci數(shù)列中，第4個和第11個數(shù)分別是（ D ）A．5，89 B．3，89C．5，144 D．3，144在有8個頂點的凸多邊形的三角剖分中，恰有（ B ）。A．6條弦和7個三角形 B．5條弦和6個三角形C．6條弦和6個三角形 D．5條弦和5個三角形一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的（ B ）A．重疊子問題 B．最優(yōu)子結(jié)構(gòu)性質(zhì)C．貪心選擇性質(zhì) D．定義最優(yōu)解下列哪個問題不用貪心法求解（ C ）。A．哈夫曼編碼問題 B．單源最短路徑問題C．最大團問題 D．最小生成樹問下列算法中通常以自底向上的方式求解最優(yōu)解的是（ B ）A．備忘錄法 B．動態(tài)規(guī)劃法C．貪心法 D．回溯法下列算法中不能解決0/1背包問題的是（ A ）A．貪心法 B．動態(tài)規(guī)劃C．回溯法 D．分支限界法下列哪個問題可以用貪心算法求解（ D ）。A．LCS問題 B．批處理作業(yè)問題C．0-1背包問題 D．哈夫曼編碼問題用回溯法求解最優(yōu)裝載問題時，若待選物品為m種，則該問題的解空間樹的結(jié)個數(shù)為（ ）。A．m! B．2m+1C．2m+1-1 D．2m二分搜索算法是利用（ A ）實現(xiàn)的算法。A．分治策略 B．動態(tài)規(guī)劃C．貪心法 D．回溯法下列不是動態(tài)規(guī)劃算法基本步驟的是（ B P44A．找出最優(yōu)解的性質(zhì) B．構(gòu)造最優(yōu)解C．算出最優(yōu)應(yīng)該是最優(yōu)) D．定義最優(yōu)下面問題（ B ）不能使用貪心法解決。A．單源最短路徑問題 B．N皇后問C．最小花費生成樹問題 D．背包問題使用二分搜索算法在n個有序元素表中搜索一個特定元素，在最好情況和最壞情況下搜索的時間復(fù)雜性分別為（A）。P17A．O(1)，O(logn)B．O(n)，O(logn)C．O(1)，O(nlogn)D．O(n)，O(nlogn)優(yōu)先隊列式分支限界法選取擴展結(jié)點的原則是（ C 。A．先進先出 B．后進先出C．結(jié)點的優(yōu)先級 D．隨機下面不是分支界限法搜索方式的是（ D ）P161A．廣度優(yōu)先 B．最小耗費優(yōu)C．最大效益優(yōu)先 D．深度優(yōu)先分支限界法解最大團問題時，活結(jié)點表的組織形式是（ B ）A．最小堆 B．最大堆C．棧 D．?dāng)?shù)組下列關(guān)于計算機算法的描述不正確的是（C ）A．算法是指解決問題的一種方法或一個過程B．算法是若干指令的有窮序列C.算法必須要有輸入和輸出D．算法是編程的思想下列關(guān)于凸多邊形最優(yōu)三角剖分問題描述不正確的是（ A ）。A．n+1個矩陣連乘的完全加括號和n個點的凸多邊形的三角剖分對B．在有n個頂點的凸多邊形的三角剖分中，恰有n-3條弦C．該問題可以用動態(tài)規(guī)劃法來求解D．在有n個頂點的凸多邊形的三角剖分中，恰有n-2個三角形動態(tài)規(guī)劃法求解問題基本步不包括（ C ）P44A．遞歸地定義最優(yōu)值B．分析最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征C．根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解可以省去D．以自底向上的方式計算出最優(yōu)值分治法所能解決的問題應(yīng)具有的關(guān)鍵特征是（ C ）A．該問題的規(guī)模縮小到一定的程度就可以容易地解決B．該問題可以分解為若干個規(guī)模較小的相同問題C．利用該問題分解出的子問題的解可以合并為該問題的解D．該問題所分解出的各個子問題是相互獨立的下列關(guān)于回溯法的描述不正確的是（ D ）A．回溯法也稱為試探法B．回溯法有“通用解題法”之稱C．回溯法是一種能避免不必要搜索的窮舉式搜索法D．用回溯法對解空間作深度優(yōu)先搜索時只能用遞歸方法實現(xiàn)常見的兩種分支限界法為（ D ）P161廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法；隊列式（FIFO）分支限界法與堆棧式分支限界法；排列樹法與子集樹法；隊列式分支限界法與優(yōu)先隊列式分支限界法；二、填空題1. f(n)=3n2+10的漸近性態(tài)f(n)=O( n2 )，g(n)=10log3n的漸近性態(tài)g(n)=O( n )。一個“好”的算法應(yīng)具有正確性、 可讀性 、 健壯性 和高效率和存儲量需求等特性。算法的時間復(fù)雜性函數(shù)表示為 C=F(N,I,A) ，分析算法復(fù)雜性的目的在于比求解同意問題的兩個不同算法的效率 的效率。構(gòu)成遞歸式的兩個基本要素是遞歸的邊界條件和 遞歸的定義 。單源最短路徑問題可用分支限界法和 貪心算法 求解。用分治法實現(xiàn)快速排序算法時最好情況下的時間復(fù)雜性為O(nlogn) 最壞情況的時間復(fù)雜性為 O(n^2) ，該算法所需的時間與運行時間 和劃分 兩方面因素有關(guān)P260-1背包問題的解空間樹為完全二叉樹；n后問題的解空間樹為排列樹；常見的分支限界法有隊列式分支限界法和優(yōu)先隊列式分支限界法。回溯法搜索解空間樹時常用的兩種剪枝函數(shù)為 約束函數(shù) 和剪枝函數(shù)。分支限界法解最大團問題時，活結(jié)點表的組織形式是 最大堆 ；分支限界解單源最短路徑問題時，活結(jié)點表的組織形式是 最小堆。三、算法填空題n(nn(n1)(n2)21階乘的非遞歸方式定義：試寫出階乖的遞歸式及算法。遞歸式為：

1 n

邊界條件遞歸算法：intfactorial(intn)

n(n1)!n0

遞歸方程{if(n==0)return1; 遞歸出口returnn*factorial(n-1); 遞歸調(diào)用}例2:用遞歸技術(shù)求解Hanoi塔問題,Hanoi塔的遞歸算法。P15其中it,t,t,t表示將塔座A上的n個盤子移至塔座CB為輔助。Move(a,ca上編號為n的圓盤移至塔座cvoidhanoi(intn,inta,intc,intb){if(n>0){hanoi(n-1,a,b,c);move(a,c);hanoi(n-1,b,c,a);}}用分治法求解快速排序問題?？焖倥判蛩惴?P25、作業(yè)、課件第2章（2）42頁-50頁template<classType>voidQuickSort(Typea[],intp,intr){if(p<r){intq=Partition(a,p,r);QuickSort(a,p,q-1);QuickSort}}Partition函數(shù)的具體實現(xiàn)template<classType>intPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];//將<x的元素交換到左邊區(qū)域//將>x的元素交換到右邊區(qū)域while(true){while(a[++i]<x&&i<r);while(a[--j]>x);if(i>=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}用貪心算法求解最優(yōu)裝載問題。最優(yōu)裝載問題P95課件第4章(2)第3-8頁template<classType>voidLoading(intx[], Typew[],Typec,intn){int*t=newint[n+1];Sort(w,t,n);for(inti=1;i<=n;i++)x[i]=0;for(intj=1;j<=n&&w[t[j]]<=c;j++){x[t[i]]=1;c-=w[t[j]];}}用回溯法求解0-1背包批處理作業(yè)調(diào)度最大團問題，要會畫解空間樹例1：用回溯法求解0-1背包 P133課件第5章第24-38頁template<typenameTypew,typenameTypep>classKnap{private:TypepBound(inti); //voidBacktrack(inti);Typewc; //背包容intn; 物品數(shù)Typew*w; //物品重量數(shù)Typep*p; 物品價值數(shù)組Typewcw; //當(dāng)前重量Typepcp; //當(dāng)前價值Typepbestp; 當(dāng)前最優(yōu)價值};voidKnap<Typew,Typep>::Backtrack(inti){ if(i>n) { bestp=cp; return; if(cw+w[i]<=c) 進入左子樹{ cw+=w[i];cp+=p[i];Backtrack(i+1);cw-=w[i];cp-=p[i]; }if(Bound(i+1)>bestp)進入右子樹Backtrack(i+1);}TypepKnap<Typew,Typep>::Bound(inti){Typewcleft=c-cw; 剩余的背包容Typepb=cp; //b為當(dāng)前價值//依次裝入單位重量價值高的整個物品while(i<=n&&w[i]<=cleft){ cleft-=w[i]; b+=p[i]; i++; if(i<=n) //裝入物品的一部分returnb; //返回上界}classObject //物品類{friendintKnapsack(int*,int*,int,int);public:intoperator<(Objecta)const{return(d>=a.d);}intID; //物品編號floatd; //單位重量價值};TypepKnapsack(Typepp[],Typeww[],Typewc,intn){ //為TypepKnapsack初始化TypewW=0;總重量TypepP=0;總價值Object*Q=newObject[n];//創(chuàng)建物品數(shù)組，下標(biāo)從0開始for(inti=1;i<=n;i++)//初始物品數(shù)組數(shù)據(jù){ Q[i-1].ID=i;Q[i-1].d=1.0*p[i]/w[i];P+=p[i]; }if(W<=c) //returnP;if(W<=c) //returnP;QuickSort(Q,0,n-1);//依物品單位重量價值非增排序Knap<Typew,Typep>K;K.p=newTypep[n+1];K.w=newTypew[n+1];for(inti=1;i<=n;i++){ K.p[i]=p[Q[i-1].ID]; K.w[i]=w[Q[i-1].ID]; K.cp=0; K.cw=0; K.c=c;K.n=n; K.bestp=0; delete[]Q; delete[]K.w;delete[]K.p; returnK.bestp;}例2：批處理作業(yè)調(diào)度 課件第5章(2)P2-5問題描,課本P125-127解空間：排列樹算法描述：classFlowshop{static int [][]m, //各作業(yè)所需的處理時[]x, //當(dāng)前作業(yè)調(diào)度[]bestx,//當(dāng)前最優(yōu)作業(yè)調(diào)度[]f2, //機器2完成處理時間f1, //機器1完成處理時f, //完成時間和bestf, //當(dāng)前最優(yōu)的完成時間n; //作業(yè)數(shù)staticvoidBacktrack(inti){if(i>n){for(intj=1;j<=n;j++) bestx[j]=x[j]; bestf=f; }elsefor(intj=i;j<=n;j++){f1+=m[x[j]][1];//第j個作業(yè)在第一臺機器上所需時間f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+m[x[j]][2];f+=f2[i];if(f<bestf)//約束函數(shù){Swap(x[i],x[j]); Backtrack(i+1); Swap(x[i],x[j]); f1-=m[x[j]][1];f-=f2[i];}}例3：最大團問題，要會畫解空間樹。classClique{friendintMaxClique(int**,int[],int);public:voidPrint(); //輸最優(yōu)解private:voidBacktrack(inti);int**a; //圖G的鄰接矩陣，下標(biāo)從1開intn; 圖G的頂點數(shù)int*x; //當(dāng)前解int*bestx; 當(dāng)前最優(yōu)int; 當(dāng)前團的頂點數(shù)intbestn; //當(dāng)前最大團的頂點數(shù)};voidClique::Backtrack(inti){ if(i>n){for(intj=1;j<=n;j++)bestx[j]=x[j];bestn=cn;return;}//判斷第i個頂點是否與已選頂點都有邊相連intOK=1;for(intj=1;j<i;j++)//x[1:i-1]，已入選的頂點集if(x[j]&&a[i][j]==0)//i與當(dāng)前團中的頂點無邊相連{ OK=0; break;} //只要與當(dāng)前團中一個頂點無邊相連，則中if(OK) //進入左子樹{ x[i]=1; ++; Backtrack(i+1); x[i]=0; --; }if(cn+n-i>bestn) //{ x[i]=0; Backtrack(i+1); }}計算時間：O(n2n)四、簡答題P44動態(tài)規(guī)劃的設(shè)計分為以下4個步驟：(1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(2)遞歸地定義最優(yōu)值。以自底向上的方式計算出最優(yōu)值。根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。P44然后從這些子問題的解得到原問題的解。題。PrimKruskal105-P107不同點：Prim(普里姆)算法：在這個過程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹T，T中包含G的n-1條邊，且不形成回路。Kruskal可以進行連通操作以便形成生成樹。P161課件第6(16(1)分支限界法以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。(2)每一個活結(jié)點只有一次機會成為擴展結(jié)點?；罱Y(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。結(jié)點表中。直持續(xù)到找到所需的解或活結(jié)點表為空時為止。試比較分支限界法與回溯法的異同P161 課件第6章(1)第5頁不同點：求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個解的最優(yōu)解。小耗費優(yōu)先的方式搜索解空間樹。五、算法應(yīng)用題P61語法樹與完全加括號方式一個表達式的完全加括號方式相應(yīng)于一棵完全二叉樹，稱為表達式的語法樹。例如，完全加括號的矩陣連乘積((A1(A2A3))(A4(A5A6)))所相應(yīng)的語法樹如圖(a)所示。語法樹與凸多邊形三角剖分凸多邊形P={v0,v1,…vn-1}的三角剖分也可以用語法樹表示。如圖：根結(jié)點是邊v0v6(可以任選)。其他邊則是語法樹的葉子節(jié)點。v0v6是三角形v0v3v6的一條邊。2、三角剖分與矩陣連乘P61(1)一般來說，凸多邊形的三角剖分和有n-1個葉節(jié)點的語法樹存在一一對應(yīng)關(guān)系。(2)N個矩陣連乘的完全加括號和有n個葉節(jié)點的語法樹也存在一一對應(yīng)關(guān)系。所以，n個矩陣連乘的完全加括號和有n+1應(yīng)關(guān)系。A1A2…AnAi(n+1vi-1vivivj，i<jA[i+1:j]。矩陣連乘積的最優(yōu)計算次序問題是凸多邊形最優(yōu)三角剖分問題的特殊情況。課后習(xí)題（第3章小結(jié)**）對于如下矩陣鏈/哈夫曼編碼問題。貪心算法求解活動安排問題例：設(shè)待安排的11個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下：最小生成樹問題P103-P105哈夫曼編碼問題，前綴碼二叉樹表示法例子：圖a圖b0-1/最優(yōu)裝載問題。用回溯法求0-1背包問題。P133，實例:n=5,M=50N12345W155252730P3012444650P/W22.41.761.701.67(1).令bestp=0,將物體的序號按價值體積比排序結(jié)果是（2,1,3,4,5）N21345W515252730P1230444650P/W2.421.761.701.67(2).根據(jù)排序得到部分解 (1,1,1,0)，估計當(dāng)前部分解的價值 b>bestp.繼續(xù)向下搜索生成結(jié)點F(1,1,1,0,0)，得到價值為86，更新bestp=86(如3第3步 第5步 第8步回溯：沿E回溯到左孩子，生成相應(yīng)右孩子G，得到部分解(1,1,0,1),此時b=93.1b>bestp（45步的基礎(chǔ)上沒有HI）繼續(xù)生成結(jié)點H,I，得到可行解(1,1,0,1,0),價值為88，更新bestp=88(如圖第5步)(6).回溯H生成J，1,1,0,0第6步在第8步的基礎(chǔ)上沒有K和L）繼續(xù)生成結(jié)點K，得到可行解(1,1,0,0,1),價值為92，更新bestp=92（第7步在第8步的基礎(chǔ)上沒有L）K是左孩子，生成其對應(yīng)的右孩子L1,1,0,0,08回溯,沿結(jié)點L向上回溯到結(jié)點,生成結(jié)點,得到部分解(1,0),估計部分解b=90<92,回溯（910步的基礎(chǔ)上沒有N）(10).向上繼續(xù)回溯生成結(jié)點(0)回溯，此時已回到根結(jié)點，結(jié)束。最優(yōu)解(1,1,0,0,1),價值為92.(如圖第10步)練習(xí)n=8,M=110，W=(1,11,2