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

PAGEPAGE22《算法分析與設(shè)計(jì)》期末復(fù)習(xí)題一、選擇題算法必須具備輸入、輸出和（ D ）等4個(gè)特性。A．可行性和安全性 B．確定性和易讀C．有窮性和安全性 D．有窮性和確定性算法分析中，記號(hào)O表示（ B ），記號(hào)Ω表示（ A A.漸進(jìn)下界 B.漸進(jìn)上界C.非緊上界 進(jìn)界假設(shè)某算法在輸入規(guī)模為n時(shí)的計(jì)算時(shí)間為T(n)=3*2^n。在某臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)并完成概算法的時(shí)間為t秒。現(xiàn)有另一臺(tái)計(jì)算機(jī)，其運(yùn)行速度為第一臺(tái)的64倍，那么在這臺(tái)新機(jī)器上用同一算法在tB解題方法：3*2^n*64=3*2^xA．n+8 B．n+6C．n+7 D．n+5設(shè)問(wèn)題規(guī)模為N時(shí)，某遞歸算法的時(shí)間復(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個(gè)和第11個(gè)數(shù)分別是（ D ）A．5，89 B．3，89C．5，144 D．3，144在有8個(gè)頂點(diǎn)的凸多邊形的三角剖分中，恰有（ B ）。A．6條弦和7個(gè)三角形 B．5條弦和6個(gè)三角形C．6條弦和6個(gè)三角形 D．5條弦和5個(gè)三角形一個(gè)問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問(wèn)題的（ B ）A．重疊子問(wèn)題 B．最優(yōu)子結(jié)構(gòu)性質(zhì)C．貪心選擇性質(zhì) D．定義最優(yōu)解下列哪個(gè)問(wèn)題不用貪心法求解（ C ）。A．哈夫曼編碼問(wèn)題 B．單源最短路徑問(wèn)題C．最大團(tuán)問(wèn)題 D．最小生成樹(shù)問(wèn)下列算法中通常以自底向上的方式求解最優(yōu)解的是（ B ）A．備忘錄法 B．動(dòng)態(tài)規(guī)劃法C．貪心法 D．回溯法下列算法中不能解決0/1背包問(wèn)題的是（ A ）A．貪心法 B．動(dòng)態(tài)規(guī)劃C．回溯法 D．分支限界法下列哪個(gè)問(wèn)題可以用貪心算法求解（ D ）。A．LCS問(wèn)題 B．批處理作業(yè)問(wèn)題C．0-1背包問(wèn)題 D．哈夫曼編碼問(wèn)題用回溯法求解最優(yōu)裝載問(wèn)題時(shí)，若待選物品為m種，則該問(wèn)題的解空間樹(shù)的結(jié)個(gè)數(shù)為（ ）。A．m! B．2m+1C．2m+1-1 D．2m二分搜索算法是利用（ A ）實(shí)現(xiàn)的算法。A．分治策略 B．動(dòng)態(tài)規(guī)劃C．貪心法 D．回溯法下列不是動(dòng)態(tài)規(guī)劃算法基本步驟的是（ B P44A．找出最優(yōu)解的性質(zhì) B．構(gòu)造最優(yōu)解C．算出最優(yōu)應(yīng)該是最優(yōu)) D．定義最優(yōu)下面問(wèn)題（ B ）不能使用貪心法解決。A．單源最短路徑問(wèn)題 B．N皇后問(wèn)C．最小花費(fèi)生成樹(shù)問(wèn)題 D．背包問(wèn)題使用二分搜索算法在n個(gè)有序元素表中搜索一個(gè)特定元素，在最好情況和最壞情況下搜索的時(shí)間復(fù)雜性分別為（A）。P17A．O(1)，O(logn)B．O(n)，O(logn)C．O(1)，O(nlogn)D．O(n)，O(nlogn)優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是（ C 。A．先進(jìn)先出 B．后進(jìn)先出C．結(jié)點(diǎn)的優(yōu)先級(jí) D．隨機(jī)下面不是分支界限法搜索方式的是（ D ）P161A．廣度優(yōu)先 B．最小耗費(fèi)優(yōu)C．最大效益優(yōu)先 D．深度優(yōu)先分支限界法解最大團(tuán)問(wèn)題時(shí)，活結(jié)點(diǎn)表的組織形式是（ B ）A．最小堆 B．最大堆C．棧 D．?dāng)?shù)組下列關(guān)于計(jì)算機(jī)算法的描述不正確的是（C ）A．算法是指解決問(wèn)題的一種方法或一個(gè)過(guò)程B．算法是若干指令的有窮序列C.算法必須要有輸入和輸出D．算法是編程的思想下列關(guān)于凸多邊形最優(yōu)三角剖分問(wèn)題描述不正確的是（ A ）。A．n+1個(gè)矩陣連乘的完全加括號(hào)和n個(gè)點(diǎn)的凸多邊形的三角剖分對(duì)B．在有n個(gè)頂點(diǎn)的凸多邊形的三角剖分中，恰有n-3條弦C．該問(wèn)題可以用動(dòng)態(tài)規(guī)劃法來(lái)求解D．在有n個(gè)頂點(diǎn)的凸多邊形的三角剖分中，恰有n-2個(gè)三角形動(dòng)態(tài)規(guī)劃法求解問(wèn)題基本步不包括（ C ）P44A．遞歸地定義最優(yōu)值B．分析最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征C．根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解可以省去D．以自底向上的方式計(jì)算出最優(yōu)值分治法所能解決的問(wèn)題應(yīng)具有的關(guān)鍵特征是（ C ）A．該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決B．該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題C．利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解D．該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的下列關(guān)于回溯法的描述不正確的是（ D ）A．回溯法也稱為試探法B．回溯法有“通用解題法”之稱C．回溯法是一種能避免不必要搜索的窮舉式搜索法D．用回溯法對(duì)解空間作深度優(yōu)先搜索時(shí)只能用遞歸方法實(shí)現(xiàn)常見(jiàn)的兩種分支限界法為（ D ）P161廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法；隊(duì)列式（FIFO）分支限界法與堆棧式分支限界法；排列樹(shù)法與子集樹(shù)法；隊(duì)列式分支限界法與優(yōu)先隊(duì)列式分支限界法；二、填空題1. f(n)=3n2+10的漸近性態(tài)f(n)=O( n2 )，g(n)=10log3n的漸近性態(tài)g(n)=O( n )。一個(gè)“好”的算法應(yīng)具有正確性、 可讀性 、 健壯性 和高效率和存儲(chǔ)量需求等特性。算法的時(shí)間復(fù)雜性函數(shù)表示為 C=F(N,I,A) ，分析算法復(fù)雜性的目的在于比求解同意問(wèn)題的兩個(gè)不同算法的效率 的效率。構(gòu)成遞歸式的兩個(gè)基本要素是遞歸的邊界條件和 遞歸的定義 。單源最短路徑問(wèn)題可用分支限界法和 貪心算法 求解。用分治法實(shí)現(xiàn)快速排序算法時(shí)最好情況下的時(shí)間復(fù)雜性為O(nlogn) 最壞情況的時(shí)間復(fù)雜性為 O(n^2) ，該算法所需的時(shí)間與運(yùn)行時(shí)間 和劃分 兩方面因素有關(guān)P260-1背包問(wèn)題的解空間樹(shù)為完全二叉樹(shù)；n后問(wèn)題的解空間樹(shù)為排列樹(shù)；常見(jiàn)的分支限界法有隊(duì)列式分支限界法和優(yōu)先隊(duì)列式分支限界法。回溯法搜索解空間樹(shù)時(shí)常用的兩種剪枝函數(shù)為 約束函數(shù) 和剪枝函數(shù)。分支限界法解最大團(tuán)問(wèn)題時(shí)，活結(jié)點(diǎn)表的組織形式是 最大堆 ；分支限界解單源最短路徑問(wèn)題時(shí)，活結(jié)點(diǎn)表的組織形式是 最小堆。三、算法填空題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塔問(wèn)題,Hanoi塔的遞歸算法。P15其中it,t,t,t表示將塔座A上的n個(gè)盤子移至塔座CB為輔助。Move(a,ca上編號(hào)為n的圓盤移至塔座cvoidhanoi(intn,inta,intc,intb){if(n>0){hanoi(n-1,a,b,c);move(a,c);hanoi(n-1,b,c,a);}}用分治法求解快速排序問(wèn)題?？焖倥判蛩惴?P25、作業(yè)、課件第2章（2）42頁(yè)-50頁(yè)template<classType>voidQuickSort(Typea[],intp,intr){if(p<r){intq=Partition(a,p,r);QuickSort(a,p,q-1);QuickSort}}Partition函數(shù)的具體實(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)裝載問(wèn)題。最優(yōu)裝載問(wèn)題P95課件第4章(2)第3-8頁(yè)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)度最大團(tuán)問(wèn)題，要會(huì)畫(huà)解空間樹(shù)例1：用回溯法求解0-1背包 P133課件第5章第24-38頁(yè)template<typenameTypew,typenameTypep>classKnap{private:TypepBound(inti); //voidBacktrack(inti);Typewc; //背包容intn; 物品數(shù)Typew*w; //物品重量數(shù)Typep*p; 物品價(jià)值數(shù)組Typewcw; //當(dāng)前重量Typepcp; //當(dāng)前價(jià)值Typepbestp; 當(dāng)前最優(yōu)價(jià)值};voidKnap<Typew,Typep>::Backtrack(inti){ if(i>n) { bestp=cp; return; if(cw+w[i]<=c) 進(jìn)入左子樹(shù){ cw+=w[i];cp+=p[i];Backtrack(i+1);cw-=w[i];cp-=p[i]; }if(Bound(i+1)>bestp)進(jìn)入右子樹(shù)Backtrack(i+1);}TypepKnap<Typew,Typep>::Bound(inti){Typewcleft=c-cw; 剩余的背包容Typepb=cp; //b為當(dāng)前價(jià)值//依次裝入單位重量?jī)r(jià)值高的整個(gè)物品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; //物品編號(hào)floatd; //單位重量?jī)r(jià)值};TypepKnapsack(Typepp[],Typeww[],Typewc,intn){ //為TypepKnapsack初始化TypewW=0;總重量TypepP=0;總價(jià)值Object*Q=newObject[n];//創(chuàng)建物品數(shù)組，下標(biāo)從0開(kāi)始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);//依物品單位重量?jī)r(jià)值非增排序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問(wèn)題描,課本P125-127解空間：排列樹(shù)算法描述：classFlowshop{static int [][]m, //各作業(yè)所需的處理時(shí)[]x, //當(dāng)前作業(yè)調(diào)度[]bestx,//當(dāng)前最優(yōu)作業(yè)調(diào)度[]f2, //機(jī)器2完成處理時(shí)間f1, //機(jī)器1完成處理時(shí)f, //完成時(shí)間和bestf, //當(dāng)前最優(yōu)的完成時(shí)間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個(gè)作業(yè)在第一臺(tái)機(jī)器上所需時(shí)間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：最大團(tuán)問(wèn)題，要會(huì)畫(huà)解空間樹(shù)。classClique{friendintMaxClique(int**,int[],int);public:voidPrint(); //輸最優(yōu)解private:voidBacktrack(inti);int**a; //圖G的鄰接矩陣，下標(biāo)從1開(kāi)intn; 圖G的頂點(diǎn)數(shù)int*x; //當(dāng)前解int*bestx; 當(dāng)前最優(yōu)int; 當(dāng)前團(tuán)的頂點(diǎn)數(shù)intbestn; //當(dāng)前最大團(tuán)的頂點(diǎn)數(shù)};voidClique::Backtrack(inti){ if(i>n){for(intj=1;j<=n;j++)bestx[j]=x[j];bestn=cn;return;}//判斷第i個(gè)頂點(diǎn)是否與已選頂點(diǎn)都有邊相連intOK=1;for(intj=1;j<i;j++)//x[1:i-1]，已入選的頂點(diǎn)集if(x[j]&&a[i][j]==0)//i與當(dāng)前團(tuán)中的頂點(diǎn)無(wú)邊相連{ OK=0; break;} //只要與當(dāng)前團(tuán)中一個(gè)頂點(diǎn)無(wú)邊相連，則中if(OK) //進(jìn)入左子樹(shù){ x[i]=1; ++; Backtrack(i+1); x[i]=0; --; }if(cn+n-i>bestn) //{ x[i]=0; Backtrack(i+1); }}計(jì)算時(shí)間：O(n2n)四、簡(jiǎn)答題P44動(dòng)態(tài)規(guī)劃的設(shè)計(jì)分為以下4個(gè)步驟：(1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(2)遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。P44然后從這些子問(wèn)題的解得到原問(wèn)題的解。題。PrimKruskal105-P107不同點(diǎn)：Prim(普里姆)算法：在這個(gè)過(guò)程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹(shù)T，T中包含G的n-1條邊，且不形成回路。Kruskal可以進(jìn)行連通操作以便形成生成樹(shù)。P161課件第6(16(1)分支限界法以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問(wèn)題的解空間樹(shù)。(2)每一個(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)表中。直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。試比較分支限界法與回溯法的異同P161 課件第6章(1)第5頁(yè)不同點(diǎn)：求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹(shù)中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解的最優(yōu)解。小耗費(fèi)優(yōu)先的方式搜索解空間樹(shù)。五、算法應(yīng)用題P61語(yǔ)法樹(shù)與完全加括號(hào)方式一個(gè)表達(dá)式的完全加括號(hào)方式相應(yīng)于一棵完全二叉樹(shù)，稱為表達(dá)式的語(yǔ)法樹(shù)。例如，完全加括號(hào)的矩陣連乘積((A1(A2A3))(A4(A5A6)))所相應(yīng)的語(yǔ)法樹(shù)如圖(a)所示。語(yǔ)法樹(shù)與凸多邊形三角剖分凸多邊形P={v0,v1,…vn-1}的三角剖分也可以用語(yǔ)法樹(shù)表示。如圖：根結(jié)點(diǎn)是邊v0v6(可以任選)。其他邊則是語(yǔ)法樹(shù)的葉子節(jié)點(diǎn)。v0v6是三角形v0v3v6的一條邊。2、三角剖分與矩陣連乘P61(1)一般來(lái)說(shuō)，凸多邊形的三角剖分和有n-1個(gè)葉節(jié)點(diǎn)的語(yǔ)法樹(shù)存在一一對(duì)應(yīng)關(guān)系。(2)N個(gè)矩陣連乘的完全加括號(hào)和有n個(gè)葉節(jié)點(diǎn)的語(yǔ)法樹(shù)也存在一一對(duì)應(yīng)關(guān)系。所以，n個(gè)矩陣連乘的完全加括號(hào)和有n+1應(yīng)關(guān)系。A1A2…AnAi(n+1vi-1vivivj，i<jA[i+1:j]。矩陣連乘積的最優(yōu)計(jì)算次序問(wèn)題是凸多邊形最優(yōu)三角剖分問(wèn)題的特殊情況。課后習(xí)題（第3章小結(jié)**）對(duì)于如下矩陣鏈/哈夫曼編碼問(wèn)題。貪心算法求解活動(dòng)安排問(wèn)題例：設(shè)待安排的11個(gè)活動(dòng)的開(kāi)始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：最小生成樹(shù)問(wèn)題P103-P105哈夫曼編碼問(wèn)題，前綴碼二叉樹(shù)表示法例子：圖a圖b0-1/最優(yōu)裝載問(wèn)題。用回溯法求0-1背包問(wèn)題。P133，實(shí)例:n=5,M=50N12345W155252730P3012444650P/W22.41.761.701.67(1).令bestp=0,將物體的序號(hào)按價(jià)值體積比排序結(jié)果是（2,1,3,4,5）N21345W515252730P1230444650P/W2.421.761.701.67(2).根據(jù)排序得到部分解 (1,1,1,0)，估計(jì)當(dāng)前部分解的價(jià)值 b>bestp.繼續(xù)向下搜索生成結(jié)點(diǎn)F(1,1,1,0,0)，得到價(jià)值為86，更新bestp=86(如3第3步 第5步 第8步回溯：沿E回溯到左孩子，生成相應(yīng)右孩子G，得到部分解(1,1,0,1),此時(shí)b=93.1b>bestp（45步的基礎(chǔ)上沒(méi)有HI）繼續(xù)生成結(jié)點(diǎn)H,I，得到可行解(1,1,0,1,0),價(jià)值為88，更新bestp=88(如圖第5步)(6).回溯H生成J，1,1,0,0第6步在第8步的基礎(chǔ)上沒(méi)有K和L）繼續(xù)生成結(jié)點(diǎn)K，得到可行解(1,1,0,0,1),價(jià)值為92，更新bestp=92（第7步在第8步的基礎(chǔ)上沒(méi)有L）K是左孩子，生成其對(duì)應(yīng)的右孩子L1,1,0,0,08回溯,沿結(jié)點(diǎn)L向上回溯到結(jié)點(diǎn),生成結(jié)點(diǎn),得到部分解(1,0),估計(jì)部分解b=90<92,回溯（910步的基礎(chǔ)上沒(méi)有N）(10).向上繼續(xù)回溯生成結(jié)點(diǎn)(0)回溯，此時(shí)已回到根結(jié)點(diǎn)，結(jié)束。最優(yōu)解(1,1,0,0,1),價(jià)值為92.(如圖第10步)練習(xí)n=8,M=110，W=(1,11,2