(完整word版)算法分析與設(shè)計(jì)習(xí)題集整理

1、算法分析與設(shè)計(jì)習(xí)題集整理 第一章算法引論 一、填空題：1、算法運(yùn)行所需要的計(jì)算機(jī)資源的量，稱為算法復(fù)雜性，主要包括時(shí)間復(fù)雜度和空間復(fù)雜 匪。2、多項(xiàng)式 A(n) =amnm+&n+a0 的上界為 O(nm)。3、算法的基本特征：輸入、輸出、確定性、有限性 、可行性 。4、如何從兩個(gè)方面評(píng)價(jià)一個(gè)算法的優(yōu)劣：時(shí)間復(fù)雜度、空間復(fù)雜度。5、計(jì)算下面算法的時(shí)間復(fù)雜度記為：O(n 3)qfor(i=1;i<=n;i+)for(j=1;j<=n;j+)cij=0；for(k=1;k<=n;k+)cij= cij+aik*bkj；6、描述算法常用的方法：自然語言、偽代碼、程序設(shè)計(jì)語言

2、、流程圖、盒圖、PAD圖。7、算法設(shè)計(jì)的基本要求：正確性 和 可讀性。8、計(jì)算下面算法的時(shí)間復(fù)雜度記為：O(n 2)qfor (i = 1; i<n; i+ )y=y+1;for (j =0; j <=2n ; j+ ) x + +;9、計(jì)算機(jī)求解問題的步驟：問題分析、數(shù)學(xué)模型建立、算法設(shè)計(jì)與選擇、算法表示、算法 分析、算法實(shí)現(xiàn)、程序調(diào)試、結(jié)果整理文檔編制。10、算法是指解決問題的方法或過程。11、算法由操作、控制結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)三要素組成。二、簡答題：1、按照時(shí)間復(fù)雜度從低到高排列：O( 4n2)、O( logn)、O( 3n)、O( 20n)、O( 2)、O( n2/3),O(

3、n!)應(yīng)該排在哪一位？答：O( 2) , O( logn) , O( n2/3), O( 20n) , O( 4n 2) , O( 3 n) , O( n!)2、什么是算法？算法的特征有哪些？答：1)算法：指在解決問題時(shí)，按照某種機(jī)械步驟一定可以得到問題結(jié)果的處理過程。 通俗講，算法：就是解決問題的方法或過程。2)特征：1)算法有零個(gè)或多個(gè)輸入；2)算法有一個(gè)或多個(gè)輸出；3)確定性；4)有窮性3、給出算法的定義？何謂算法的復(fù)雜性？計(jì)算下例在最壞情況下的時(shí)間復(fù)雜性？for(j=1;j<=n;j+)for(i=1;i<=n;i+)(2)cij=0；(3)for(k=1;k<=n;

4、k+)(4)cij= cij+aik*bkj； (5)答：1)定義：指在解決問題時(shí)，按照某種機(jī)械步驟一定可以得到問題結(jié)果的處理過程。2 )算法的復(fù)雜性：指的是算法在運(yùn)行過程中所需要的資源(時(shí)間、空間)多少。 所需資源越多，表明算法的復(fù)雜性越高3 )該算法的主要元操作是語句5,其執(zhí)行次數(shù)是n3次。故該算法的時(shí)間復(fù)雜度記為 O(n3).4、算法A和算法B解同一問題，設(shè)算法A的時(shí)間復(fù)雜性滿足遞歸方程'T(n) =1 , n =1T(n) =4T(n/2) +n , n >1算法B的時(shí)間復(fù)雜性滿足遞歸方程3 T")=1 , n =1,若要使得算法 A時(shí)間復(fù)雜T(n) =aT(n

5、/4) +n , n >1性的階高于算法 B時(shí)間復(fù)雜性的階，a的最大整數(shù)值可取多少？答：分別記算法A和算法B的時(shí)間復(fù)雜性為TA(n)和TB(n),解相應(yīng)的遞歸方程得：TA(n) =O(n2)O(n) , a < 4TB(n) = <O(n log n) ,a=4log 4a.0(n) , a >4依題意，要求最大的整數(shù)a使彳11TB (n)TA(n)。顯然，當(dāng)a<=4時(shí)，TB(n)TA(n)；當(dāng) a>4 時(shí)，TB(n) < TA(n) u 10g4a m2 u a<42=16。所以，所求的a的最大整數(shù)值為15。5、算法分析的目的？答：1)為了對(duì)算

6、法的某些特定輸入，估算該算法所需的內(nèi)存空間和運(yùn)行時(shí)間；2)是為了建立衡量算法優(yōu)劣的標(biāo)準(zhǔn)，用以比較同一類問題的不同算法。6、算法設(shè)計(jì)常用的技術(shù)？(寫5種)答：分治法；回溯法；貪心法；動(dòng)態(tài)規(guī)劃法分治限界法；蠻力法；倒推法三、算法設(shè)計(jì)題1、蠻力法：百雞百錢問題？2、倒推法：穿越沙漠問題？第二章分治算法（1）-遞歸循環(huán)一、填空題：1、直接或間接地調(diào)用自身的算法稱為遞歸算法 ，用函數(shù)自身給出定義的函數(shù)稱為 _遞歸函數(shù) 。2、遞歸方程 和 約束函數(shù)（遞歸終止條件 ）是遞歸函數(shù)的兩個(gè)要素。二、判斷題：1、所有的遞歸函數(shù)都能找到對(duì)應(yīng)的非遞歸定義。（V ）2、定義遞歸函數(shù)時(shí)可以沒有初始值。（X ）三、簡答題：1

7、、什么是遞歸算法？遞歸算法的特點(diǎn)？答：1 ）遞歸算法：是一個(gè)模塊（函數(shù)、過程）除了可調(diào)用其它模塊（函數(shù)、過程）外，還可 以直接或間接地調(diào)用自身的算法。2）遞歸算法特點(diǎn)：每個(gè)遞歸函數(shù)都必須有非遞歸定義的初值；否則，遞歸函數(shù)無法計(jì)算；（遞歸終止條件）遞歸中用較小自變量函數(shù)值來表達(dá)較大自變量函數(shù)值；（遞歸方程式）2、比較循環(huán)與遞歸的異同？答：1）相同：遞歸與循環(huán)都是解決“重復(fù)操作”的機(jī)制。2）不同：就效率而言，遞歸算法的實(shí)現(xiàn)往往要比迭代算法耗費(fèi)更多的時(shí)間（調(diào)用和返回均需要額外的時(shí)間）與存貯空間（用來保存不同次調(diào)用情況下變量的當(dāng)前值的棧?？臻g），也限制了遞歸的深度。每個(gè)迭代算法原則上總可以轉(zhuǎn)換成與它等

8、價(jià)的遞歸算法；反之不然。遞歸的層次是可以控制的，而循環(huán)嵌套的層次只能是固定的，因此遞歸是比循環(huán)更靈活 的重復(fù)操作的機(jī)制。3、遞歸算法解題通常有三個(gè)步驟？答：1）分析問題、尋找遞歸：找出大規(guī)模問題與小規(guī)模問題的關(guān)系，這樣通過遞歸使問題 的規(guī)模逐漸變小。2）設(shè)置邊界、控制遞歸：找出停止條件，即算法可解的最小規(guī)模問題。3）設(shè)計(jì)函數(shù)、確定參數(shù)：和其它算法模塊一樣設(shè)計(jì)函數(shù)體中的操作及相關(guān)參數(shù)。四、算法設(shè)計(jì)題：1、樓梯上有n個(gè)臺(tái)階，上樓時(shí)可以上1步，也可以上2步，設(shè)計(jì)一遞歸算法求出共有多少種上樓方法F(n)。寫出F(n)的遞歸表達(dá)式？并寫出其相應(yīng)的遞歸算法？解：寫出F(n)的遞歸表達(dá)式分析：到n階有兩種走

9、法：1 ) n-1階到n階；2 ) n-2階到n階；1n=1F(n) = 2n=2F(n-1) + F(n-2)n>2寫出其相應(yīng)的遞歸算法？Int F(int n)if(n=1) return 1;else if(n=2)return 2;elsereturn F(n-1)+ F(n-2);2、設(shè)a,b,c是3個(gè)塔座。開始時(shí)，在塔座a上有一疊共n個(gè)圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號(hào)為1,2,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動(dòng)圓盤時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：規(guī)則1:每次只能移動(dòng)1個(gè)圓盤；規(guī)則2：任何時(shí)刻都不允許將較大的圓盤壓在較小

10、的圓盤之上；規(guī)則3:在滿足移動(dòng)規(guī)則 1和2的前提下，可將圓盤移至 a,b,c中任一塔座上。寫出該問題的解題步驟？并寫出其相應(yīng)的遞歸算法？解：第一步：將n1個(gè)盤子看成一個(gè)整體，從A移到C;第二步：將第n個(gè)盤子移到B;第三步：將n1個(gè)盤子看成一個(gè)整體，從C移到B;寫出其相應(yīng)的遞歸算法：void hanoi(int n, int a, int b, int c)if (n > 0)hanoi(n-1, a, c, b);move(a,b);hanoi(n-1, c, b, a);第二章分治算法(2)分治算法一、填空題：1、在快速排序、插入排序和合并排序算法中，插入排序 算法不是分治算法。2、合

11、并排序算法使用的是分治算法設(shè)計(jì)的思想。3、二分搜索算法是利用分治算法思想設(shè)計(jì)的。二、簡答題：1、適合用分治算法求解的問題具有的基本特征？答：1)該問題的規(guī)模縮小到一定的程度就可以容易解決；2)該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；3 )該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。4)利用該問題分解出子問題解可以合并為該問題解； 2、分治算法基本思想，解題步驟?三、算法設(shè)計(jì)題：1、改寫二分查找算法：設(shè)a1n是一個(gè)已經(jīng)排好序的數(shù)組，改寫二分查找算法，使得當(dāng)搜索元素 x不在數(shù)組 中時(shí)，返回小于 x的最大元素位置i,和大于x的最小元素位置j;

12、當(dāng)搜索元素x在數(shù)組中 時(shí)，i和j相同，均為x在數(shù)組中的位置。并分析其時(shí)間復(fù)雜度？解：int binsearch( int an, int x ,) /x待查數(shù)據(jù)int mid, i, j; low=1;int high=n;while(low<=high)mid=(low+high)/2;if(amid=x) return i=j=mid;if(amid>x) high=mid-1; /繼續(xù)在左邊查找else/ (amid<x)low=mid+1; /繼續(xù)在右邊查找 i=right; j=left; return 0; /low 大于high查找區(qū)間為空，查找失敗計(jì)算時(shí)間復(fù)雜

13、性為O(logn) 2、棋盤覆蓋 在一個(gè)2kx 2k個(gè)方格組成的棋盤中，恰有一個(gè)方格與其它方格不同，稱該方 格為一特殊方格，且稱該棋盤為一特殊棋盤。 在棋盤覆蓋問題中， 要用圖示的4種不同形態(tài) 的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格， 且任何2個(gè)L型骨牌不得重 疊覆蓋。求：簡述分治算法的基本思想？設(shè)計(jì)該棋盤覆蓋問題的分治算法？計(jì)算所設(shè)計(jì)算法的時(shí)間復(fù)雜度？（要求寫出遞推公式）解：分解：將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同子問題，以便各個(gè)擊破，分而治之。對(duì)這k個(gè)子問題分別求解：如果子問題的規(guī)模仍然 不夠小,則再劃分為k個(gè)子問題，如此遞歸的進(jìn)行下去， 直到問題規(guī) 模足

14、夠小，很容易求出其解為止 求小問題解、合并：將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。、3、金塊問題（求最大最小兀問題）老板有一袋金塊（共n塊），最優(yōu)秀的雇員得到其中最重的一塊，最差的雇員得到其中最輕的一塊。假設(shè)有一臺(tái)比較重量的儀器，我們希望用最少的比較次數(shù)找出最重的金塊。求：簡述分治算法的基本思想？設(shè)計(jì)該金塊問題的分治算法？計(jì)算所設(shè)計(jì)算法的時(shí)間復(fù)雜度？（要求寫出遞推公式）答：簡述分治算法的基本思想：問題可以簡化為：在含 n （n是2的哥（n>=2）個(gè)元素的集合中尋找極大元和極小元。用分治法（二分法）可以用較少比較次數(shù)地解決上述問題：1）將數(shù)據(jù)等

15、分為兩組（兩組數(shù)據(jù)可能差1）,目的是分別選取其中的最大（?。┲怠?）遞歸分解直到每組元素的個(gè)數(shù)w 2,可簡單地找到最大（?。┲?3）回溯時(shí)將分解的兩組解大者取大，小者取小，合并為當(dāng)前問題的解。、第三章動(dòng)態(tài)規(guī)劃算法一、填空題：1、動(dòng)態(tài)規(guī)劃算法中存儲(chǔ)子問題的解是為了避免重復(fù)求解子問題。2、（最優(yōu)子結(jié)構(gòu) ）是問題能用動(dòng)態(tài)規(guī)劃算法求解的前提。3、矩陣連乘問題的算法可由（動(dòng)態(tài)規(guī)劃）算法設(shè)計(jì)實(shí)現(xiàn)。二、判斷題：1、動(dòng)態(tài)規(guī)劃算法基本要素的是最優(yōu)子結(jié)構(gòu)。（V ）2、最優(yōu)子結(jié)構(gòu)性質(zhì)是指原問題的最優(yōu)解包含其子問題的最優(yōu)解。（V ）3、動(dòng)態(tài)規(guī)劃算法求解問題時(shí)，分解出來的子問題相互獨(dú)立。（X）三、簡答題：1、動(dòng)態(tài)規(guī)劃算

16、法解題步驟？答：找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征；（即原問題的最優(yōu)解，包含了子問題的最優(yōu)解）遞歸地定義最優(yōu)值；（即子問題具有重疊性，由子問題定義原問題）以自底向上的方式計(jì)算出最優(yōu)值 ；根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解；2、動(dòng)態(tài)規(guī)劃算法基本思想？答：動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題；但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。不同子問題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次；如果能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。3、動(dòng)態(tài)規(guī)劃與分治算法異同點(diǎn)?4、

17、動(dòng)態(tài)規(guī)劃算法的基本要素?四、算法設(shè)計(jì)與計(jì)算題：1、X =a,X2,L ,XmN Y =yi, y2,L , yn的最長公共子序列為Z=z1，z2,L ,zj。問：若用cij記錄序列Xi =%,x2,L，x 和丫 =y1,y2,L ,力公共子序列長度。求:用動(dòng)態(tài)規(guī)劃法求解時(shí)，計(jì)算最優(yōu)值的遞歸公式？設(shè)計(jì)計(jì)算最優(yōu)值的算法？以及構(gòu)造最優(yōu)解的算法？2、長江游艇俱樂部在長江上設(shè)置了n個(gè)游艇出租站1,2n.游客可在這些游艇出租站租用游艇，并在下游的任何一個(gè)游艇出租站歸還游艇。游艇出租站i到游艇出租站j之間的租金為r(i , j),其中1<=i<j<=n ;求：用動(dòng)態(tài)規(guī)劃法求解時(shí)，計(jì)算最優(yōu)值

18、(最少租金)的遞歸公式？設(shè)計(jì)計(jì)算最優(yōu)值(最少租金)的算法？并分析其時(shí)間復(fù)雜度？解：0i 二 jri, j min ri, k rk 1, j i j .i _k ：；：j計(jì)算最優(yōu)值算法public static void matrixChain(int p, int m, int s) int n=p.length-1;for (int i = 1; i <= n; i+)mii = 0;/1 個(gè)站for (int r = 2; r <= n; r+)for (int i = 1; i <= n - r+1; i+) int j=i+r-1;m i j = mii + mi+

19、1 j;s i j = i;/斷點(diǎn)位置在i處for (int k = i+1; k < j; k+)int t = m i k + mk+1 j; if (t < mij) m i j = t; s i j = k; 構(gòu)造最優(yōu)解算法public void traceback( int s,int I,int j) if(i=j) return;traceback( s, i, s i j);traceback( s, s i j+1, j );System.out.println("A" + i + ”, " + s i j +«A + s

20、i j+1 + j)/(m i, s i j ) (m s i j+1, j )時(shí)間復(fù)雜度：O(n3)第4章貪心算法一、填空題:1、某單位給每個(gè)職工發(fā)工資（精確到元）。為了保證不要臨時(shí)兌換零錢，且取款的張數(shù)最少,統(tǒng)計(jì)所需各種幣值（100,50,20,10,5,2,1 元共七種）的張數(shù)。應(yīng)發(fā)工資貪心算法如下：void greedy_zhaoling ( float GZ, int B , int S )GZ for( j=1, j<=7;j+)/ A= GZ/B j ;/AS j= S j +A ；S jGZ= GZ-A*B j ; for(i=1;i<=7;i+) print( B

21、 i , 貪心選擇，依次給最大幣種 表不又應(yīng)j幣種張數(shù)存放對(duì)應(yīng)j幣種總張數(shù)“-:S i );/輸出幣種和對(duì)應(yīng)張數(shù)if ( w i<=mm )/計(jì)算當(dāng)前總價(jià)值，mmF包剩余載重; /計(jì)算物品單位價(jià)值ww初始化按單位價(jià)值將物品排序，便于貪心選擇貪心選擇，總是選擇價(jià)值最大放入背包當(dāng)前物品小于背包剩余載重2、貪心算法的兩個(gè)基本要素是（貪心選擇性）和（ 最優(yōu)子結(jié)構(gòu) ）。3、給定n種物品和一個(gè)背包。物品 i的重量是 Wi,其價(jià)值為Vi,背包的容量為 M應(yīng)如何 選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大。貪心算法如下：float greedy_knapsack ( float M, float

22、 w , float p , float x)/ x背包問題最優(yōu)解，w物品重量，P 物品價(jià)值 int n=w.length;float pp=0;float mm = M; /ppfor( int i=1;i<=n; i+ )float ww i= p i / w ix i=0;/Mergesort ( w , n );/for( int i=1; i<=n; i+ )/x i=1;mm= mm - w i ;pp= pp + p i ; elsex i=mm/w i;PP= PP + x i*p i;break; /i部分放入背包return pp;二、判斷題：1、滿足貪心選擇性

23、質(zhì)必滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。（X ）三、簡答題：1、貪心算法的基本思想？2、貪心算法的基本要素？3、貪心算法與動(dòng)態(tài)規(guī)劃算法的異同？四、算法設(shè)計(jì)題：1、假設(shè)有7個(gè)物品，它們的重量和價(jià)值如下表所示。若這些物品均可以被分割，且背包容 量七150,如果使用貪心方法求解此背包問題（背包不超載的前提下，裝載的物品價(jià)值達(dá) 到最大）。物品ABCDEFG35306050401025價(jià)值10403050354030利用貪心算法求解該問題時(shí)，為了進(jìn)行貪心選擇，首先應(yīng)該做什么？ 然后進(jìn)行貪心裝載，給出一種正確的物品裝載順序？并給出其最優(yōu)裝載方案？利用貪心思想設(shè)計(jì)該普通背包問題的貪心算法？分析其時(shí)間復(fù)雜度？解：1 ）依據(jù)不

24、同的標(biāo)準(zhǔn)對(duì)這些物品進(jìn)行排序，標(biāo)準(zhǔn)有重量、價(jià)值、單位價(jià)值；2）重量從小到大：FGBAEDC得到的貪心解為：FGBAE全部放入，D放入20%,得到價(jià)值為165;價(jià)值從大到小 ：DFBEGCA得到的貪心解為：DFBE全部放入,G放入80%,得到 價(jià)值為189;單位價(jià)值從大到小 ：FBGDECA得到的貪心解為：FBGD全部放入,E放入87.5% , 得到價(jià)值為190.625 ;3）顯然使用單位價(jià)值得出最佳轉(zhuǎn)載方案。2、設(shè)有n個(gè)活動(dòng)集合，其中每個(gè)活動(dòng)都要求使用同一資源，如足球場(chǎng)，而在同一時(shí)間只能有一個(gè)活動(dòng)使用該資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源起始時(shí)間si和結(jié)束時(shí)間fi ,且si < fi ;

25、如果選擇了活動(dòng)i ,則它在半開區(qū)間si , fi） 占用資源。若兩個(gè)活動(dòng)si , fi）與sj, fj）不相交，則稱活動(dòng)i與活動(dòng)j是相容的；活動(dòng)安排問題：就是在所給的活動(dòng)集合中選出最大相容活動(dòng)子集合；求：利用貪心算法求解該問題的基本思想？設(shè)計(jì)該活動(dòng)安排問題的貪心算法？并分析其時(shí)間復(fù)雜度？3、給定下圖G=（V, E）是一個(gè)無向連通圖，對(duì)每一條邊（v, w）,其權(quán)彳1為c（ v, w）;求：利用prim算法構(gòu)造其最小生成樹，畫出其選邊的過程？并構(gòu)造其算法？并分析其時(shí)間復(fù)雜度？利用kruskal算法構(gòu)造其最小生成樹，畫出其選邊的過程?并構(gòu)造其算法？并分析其時(shí)間復(fù)雜度？4、對(duì)下圖中的有向圖，應(yīng)用Dij

26、kstra算法計(jì)算從源（頂點(diǎn)1）到其它頂點(diǎn)間最短路徑的過程要求：給出Dijkstra 算法的迭代過程，計(jì)算源到給個(gè)頂點(diǎn)的最短路徑？（用表表示）解：見課本123頁 表4-2解：迭代過程:迭代SUdist2dist 3Jdlst 4dist 5新骷(1)10ma xinI3010011,22603010021,2, 4)4509031,2,4, 3360411, 2, 4, 3, 5)510P 503060Dijkstra算法的迭代過程;= 士_絲棗二二；V-S第5章回溯算法一、填空題1、回溯法與分支限界法搜索方式不同，回溯法按深度優(yōu)先 搜索解空間,分支限界法按廣度優(yōu)先或最小耗費(fèi)優(yōu)先搜索解空間。二

27、、判斷題1、回溯法中限界函數(shù)的目的是剪去得不到最優(yōu)解的子樹。（V ）2、分支限界法類似于回溯法，也是一種在問題的解空間樹T上搜索問題解的算法，兩者的搜索方式是相同的。（X ） 三、簡答題1、簡述回溯法和分支限界法的相同點(diǎn)和不同點(diǎn)？2、什么是子集樹？什么是排列樹？什么叫滿 m叉樹？3、回溯算法的基本思想？回溯算法的解題步驟 ？ 四、算法設(shè)計(jì)題1、n皇后問題在4X4格的棋盤上放置彼此不受攻擊的 4個(gè)皇后。按照國際象棋的規(guī)則，皇后可以攻擊 與之處在同一行或同一列或同一斜線上的棋子。用回溯算法解決4皇后問題：構(gòu)造求解該問題的解空間樹？設(shè)計(jì)該4皇后問題的回溯算法？解：解空間樹2、01背包問題：假設(shè)有3個(gè)

28、物品，它們的重量和價(jià)值如下表所示。若這些物品均不可以被分割，且背包容量M= 10,問應(yīng)該如何裝入使背包中物品的總價(jià)值最大？用回溯算法求解該 01背包問題：構(gòu)造求解該問題的解空間樹？設(shè)計(jì)該01背包問題的回溯算法？解：1）解空間樹；物品ABC重量655價(jià)值4225302) 3、圖的著色問題：如下圖給定無向連通圖G和m種不同的顏色；用這m種顏色為圖G的各個(gè)頂點(diǎn)著色，是否有一種方法使得圖 G中每一條邊的兩個(gè)頂點(diǎn) 著不同顏色；求：構(gòu)造求解該問題的解空間樹？設(shè)計(jì)該圖的著色問題回溯算法？解：1）解空間樹:2 )算法：double mcoloring(int mm)int m=mm;double sum=0;

29、backtrack( 1 );return sum;/m/sum/可用顏色數(shù)當(dāng)前著色方案數(shù)深度優(yōu)先搜索解空間void backtrack( int t) if ( t>n ) / sum+;/搜索到葉子節(jié)點(diǎn)著色方案數(shù)加1for (int i=1; i<=n; i+) system.out.print( x i);"/輸出解，頂點(diǎn)i著顏色 else / 搜索到中間節(jié)點(diǎn) for(int i=1; i<=m; i+)x i x t=i;if( ok( t )/backtrack(t+1);頂點(diǎn)t著顏色i=1 m當(dāng)前著色頂點(diǎn)與以前相鄰頂點(diǎn)是否同色boolean ok( in

30、t k) / for(int j=1; j<=n; j+)if( a k j&&( x j=x k ) )/當(dāng)前頂點(diǎn)k 到 j 有邊： a k j/ 數(shù)組 a 是圖的鄰接矩陣x j=x kreturn false; else return true;算法分析(m種顏色，n個(gè)節(jié)點(diǎn))計(jì)算限界函數(shù)，一重for 循環(huán)時(shí)間復(fù)雜度：O(n);在 最 壞 的 情 況 下 每 一 個(gè) 內(nèi) 節(jié) 點(diǎn) 都 需 要 判 斷 約 束 ， 內(nèi) 節(jié) 點(diǎn) 個(gè) 數(shù) ：1+m+m2+n3+mn-1=(mn-1)/(m-1) 個(gè)；故圖的m著色問題的回溯算法，時(shí)間復(fù)雜度為：O(n*mn)。第六章分支限界算法一、

31、填空題1、按照活結(jié)點(diǎn)表的組織方式的不同，分支限界法包括 隊(duì)列式分支限界算法和 優(yōu)先隊(duì)列式分支限界算法兩種形式。2、回溯法與分支限界法搜索方式不同，回溯法按深度優(yōu)先 搜索解空間,分支限界法按廣度優(yōu)先或最小耗費(fèi)優(yōu)先搜索解空間。3、隊(duì)列分支限界算法中，通常用 隊(duì)列 實(shí)現(xiàn),體現(xiàn) 先進(jìn)先出原則 的原則。4、優(yōu)先隊(duì)列式分支限界算法，通常采用堆 實(shí)現(xiàn)。6、回溯法與分支限界算法求解問題時(shí)，需要構(gòu)造對(duì)該問題的解空間結(jié)構(gòu)，其解空間結(jié)構(gòu)通常有3種形式，分別是 子集樹 、 排列樹 、滿m叉樹。二、判斷題1、分支限界法類似于回溯法，也是一種在問題的解空間樹T上搜索問題解的算法，兩者的搜索方式是相同的。（X）三、簡答題1

32、、簡述分支限界法的基本思想與解題步驟？2、分支限界算法與回溯算法異同點(diǎn)？四、算法設(shè)計(jì)題1、01背包問題：假設(shè)有3個(gè)物品，它們的重量和價(jià)值如下表所示。若這些物品均不可以被分割，且背包 容量M= 10,問應(yīng)該如何裝入使背包中物品的總價(jià)值最大?物品ABC重量655價(jià)值422530用分支限界算法求解該 0-1背包問題:構(gòu)造求解該問題的解空間樹？給出隊(duì)列式分支限界算法的求解過程？ 如法1 :隊(duì)列式 （FIFO先進(jìn)先出）分支限界法? 從根結(jié)點(diǎn)1開始；將活結(jié)點(diǎn)組織成一個(gè)隊(duì)列；? 初始時(shí)活結(jié)點(diǎn)隊(duì)列為空，結(jié)點(diǎn)1加入隊(duì)列，結(jié)點(diǎn)1為當(dāng)前擴(kuò)展結(jié)點(diǎn)；1? 結(jié)點(diǎn) 1的孩子結(jié)點(diǎn)2、 9為可行結(jié)點(diǎn)，故舍棄當(dāng)前結(jié)點(diǎn)1,將2、

33、9加入活結(jié)點(diǎn)隊(duì)列：|2 |9 |-|? 先進(jìn)先出原則，2作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，其孩子2點(diǎn)3、 6;由于結(jié)點(diǎn)3是不可行結(jié)點(diǎn)舍棄；將結(jié)點(diǎn)6加入活結(jié)點(diǎn)隊(duì)列；1 J9 |6 1|1|1| -|? 先進(jìn)先出原則，9作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，其孩子結(jié)點(diǎn)10、 13;結(jié)點(diǎn) 10、 13 是可行結(jié)聲加入活結(jié)總隊(duì)列.；.一I I 16 10 |13 | I丁 I|設(shè)計(jì)該0-1背包問題的分支限界算法？并分析其時(shí)間復(fù)雜度?（隊(duì)列式分支限界，帶上界函數(shù)）2、多段圖最短路徑問題多段豌文:有句連通酷權(quán)圉G=（VRW，質(zhì)點(diǎn)集合劃分成K個(gè)不相好集1=<i<=k.，使得其中的邊S必有以三匕，） w I'i ，叱=1；稱

34、為多輜。令匕. I t - h稱為J <工源點(diǎn)，M *嘰為收點(diǎn)”事*岸麗 君次魅渤峰點(diǎn)由遍H 碼的求：構(gòu)造求解該問題的解空間樹?給出隊(duì)列式分支限界算法的求解過程？設(shè)計(jì)該問題的分支限界算法？并分析其時(shí)間復(fù)雜度?（隊(duì)列式分支限界，帶上界函數(shù)）解：/定義并組織問題的解空間如下:2）求解過程:法心 血血4 （FIFO 先迸先出）分支 限界法從根多苦點(diǎn)i開好”將適結(jié)點(diǎn)組組或一金鼠到二初始時(shí)也生i必在為空.結(jié)點(diǎn)】力II入隊(duì)列.結(jié)點(diǎn)1為當(dāng)前獷結(jié)點(diǎn)】的孩子結(jié)點(diǎn)7. 3、4為可行結(jié)點(diǎn)，故舍棄當(dāng)前結(jié)點(diǎn)1 , 棉N、3r 4力口入酒結(jié)點(diǎn)血物|n|R/| | | | | | | | | 先進(jìn)先出原則.苣作為當(dāng)前

35、擴(kuò)展結(jié)點(diǎn)其筱于結(jié)點(diǎn)5.6均 是 E 行姑點(diǎn)*將結(jié)點(diǎn)5、G力口入活結(jié)點(diǎn)血叁|3|4|5|后| 先進(jìn)先山原則，3作為當(dāng)?shù)趺鏍t展結(jié)點(diǎn)，共孩子結(jié)點(diǎn)4- 3. 6. 日均昆Rf行結(jié)點(diǎn)，加入活結(jié)點(diǎn)以尊；-肖至U抽后隊(duì)列為空。3 )算法描述： 法1 :隊(duì)列式分支限界法double shortest( int i) while (true) /隊(duì)列不空，搜索問題的解空間 for ( int j=1; j<=n;j+)兒子結(jié)點(diǎn)入隊(duì) if (a i j < Float.MAX_VALUE) 頂點(diǎn) i 到頂點(diǎn) j 可達(dá) dist j= dist i +a i j;/ dist i記錄源到頂點(diǎn) i 的距離

36、p j=enode.i; / p j記錄頂點(diǎn)j的前驅(qū)enQueue(v j, j); /結(jié)點(diǎn) j 加入隊(duì)列ew = (Integer) queue.remove().intValue();/ 取隊(duì)首下一擴(kuò)展結(jié)點(diǎn)if (ew = -1)/同一層尾部標(biāo)記ew = -1 :同一層結(jié)點(diǎn)處理結(jié)束 if (queue.isEmpty()return dist i;判斷隊(duì)歹U是否為空else queue.put(new Integer(-1); /同層結(jié)點(diǎn)尾部標(biāo)志ew = (Integer) queue.remove().intValue(); 取下一擴(kuò)展結(jié)點(diǎn)i+;/進(jìn)入下一層 時(shí)間復(fù)雜度：第七章概率算法1

37、、什么叫概率算法？答：概率算法允許算法在執(zhí)行的過程中隨機(jī)選擇下一個(gè)計(jì)算步驟。2、概率算法有一個(gè)基本特征？答：基本特征是對(duì)所求解問題的同一實(shí)例用同一概率算法求解兩次可能得到完全 不同的效果。3、概率算法可以分為哪4類？答：1）數(shù)值概率算法2）蒙特卡羅算法3）拉斯維加斯算法4）舍伍德算法4、在概率算法中使用的 隨機(jī)數(shù)都是一定程度上隨機(jī)的，即偽隨機(jī)數(shù)；一般隨機(jī) 數(shù)通過 線性同余法方法產(chǎn)生。第八章NP完全性理論1、什么是易解問題？什么是難解問題？難解問題分為哪兩類？答：1）易解問題：人們將存在多項(xiàng)式時(shí)間算法的問題稱為易解問題；2）難解問題：將需要在指數(shù)時(shí)間內(nèi)解決的問題稱為難解問題；3）難解問題有兩類：

38、1 ）不可判定問題 2 ）非決定的難處理問題 2、什么是不可判定問題？什么是非決定的難處理問題？答：1）不可判定問題：該類問題是不能解問題，它們太難了，以至于根本就不存在能求解 它們的任何算法。2）非決定的難處理問題：這類問題是可判定的（即可解的）。但是，這類問題即使使用非決定的計(jì)算機(jī)，也不能在多項(xiàng)式時(shí)間內(nèi)求解它們。3、什么是P類問題？什么是NP完全問題？答：1） P類問題：是一類能夠用確定性算法在多項(xiàng)式時(shí)間內(nèi)求解的判斷問題。事實(shí)上，所 有易解問題都屬于 P類問題。2） NP完全問題：對(duì)于某問題，很難找到其多項(xiàng)式時(shí)間的算法（或許根本不存在），但是如果給了該問題的一個(gè)答案，則可以在多項(xiàng)式時(shí)間內(nèi)判

39、定或驗(yàn)證這個(gè)答案是否正確。這種可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證一個(gè)解是否正確的問題稱為NP問題。4、列出幾個(gè)典型的 NP完全問題？答：（1）圖著色問題 COLORING（2）路徑問題 LONG-PATH（3）頂點(diǎn)覆蓋問題 VERTEX-COVER（4）子集和問題 SUBSET-SUM（5）哈密爾頓回路問題 HAM-CYCLE（6）旅行商問題TSP（7）裝箱問題BIN-PACKING , 能否用k個(gè)箱子來裝n個(gè)物品；第九章近似算法1、所有NP完全問題都還沒有多項(xiàng)式時(shí)間的算法，然而許多NP完全問題都具有很重要的意義，對(duì)于這類問題通常可以采取以下幾種解題策略？答：1 ）只對(duì)問題的特殊實(shí)例求解；2）用動(dòng)態(tài)規(guī)劃或

40、分支限界法求解。3）啟發(fā)式方法求解4）只求近似解2、利用近似算法求解 NP完全問題時(shí)，近似算法應(yīng)該滿足下面兩個(gè)基本的要求？答： 1）算法的時(shí)間復(fù)雜性：要求算法能在n 的多項(xiàng)式時(shí)間內(nèi)完成。2）解的近似程度：算法的近似解應(yīng)滿足一定的精度。通常，用來衡量精度的標(biāo)準(zhǔn)有近似比和相對(duì)誤差。1、二分搜索算法是利用（A ）實(shí)現(xiàn)的算法。A、分治策略B、動(dòng)態(tài)規(guī)劃法C 、貪心法D 、回溯法2、下列不是動(dòng)態(tài)規(guī)劃算法基本步驟的是（A ）。A找出最優(yōu)解的性質(zhì) B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、定義最優(yōu)解3、最大效益優(yōu)先是（A ）的一搜索方式。A分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法4、最長公共子序列算法利用的算法是（

41、B ）。A 、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D回溯法5.回溯法解TSP問題時(shí)的解空間樹是（A ）A、子集樹B、排列樹C、深度優(yōu)先生成樹D廣度優(yōu)先生成樹6下列算法中通常以自底向上的方式求解最優(yōu)解的是（B ）。A 、備忘錄法B、動(dòng)態(tài)規(guī)劃法C、貪心法D回溯法7、衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（C ）。A 運(yùn)行速度快B 占用空間少C 時(shí)間復(fù)雜度低D 代碼短8、以下不可以使用分治法求解的是（D ）。A 棋盤覆蓋問題B 選擇問題C 歸并排序D 0/1 背包問題9. 實(shí)現(xiàn)循環(huán)賽日程表利用的算法是（A ）。A 、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D回溯法10、實(shí)現(xiàn)最長公共子序列利用的算法是（B ）。A、分治策略B

42、、動(dòng)態(tài)規(guī)劃法C、貪心法D回溯法11 下面不是分支界限法搜索方式的是（D ）。A 、廣度優(yōu)先B、最小耗費(fèi)優(yōu)先C、最大效益優(yōu)先D深度優(yōu)先12下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是（D ）。A、備忘錄法B、動(dòng)態(tài)規(guī)劃法C、貪心法13. 一個(gè)問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的（BA 、重疊子問題B、最優(yōu)子結(jié)構(gòu)性質(zhì)C、貪心選擇性質(zhì)D、定義最優(yōu)解14廣度優(yōu)先是（A ）的一搜索方式。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法15 背包問題的貪心算法所需的計(jì)算時(shí)間為（B ）。A、 O（ n2） nB、 O（ nlogn ） C、 O（ 2） nD、 O（ n）16實(shí)現(xiàn)最大子段和利

43、用的算法是（B ）。A 、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D回溯法17實(shí)現(xiàn)棋盤覆蓋算法利用的算法是（A ）。A 、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D回溯法18. 下面是貪心算法的基本要素的是（C ）。A 、重疊子問題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D定義最優(yōu)解19. 回溯法的效率不依賴于下列哪些因素（D ）A. 滿足顯約束的值的個(gè)數(shù)C. 計(jì)算限界函數(shù)的時(shí)間B. 計(jì)算約束函數(shù)的時(shí)間D. 確定解空間的時(shí)間20. 下面哪種函數(shù)是回溯法中為避免無效搜索采取的策略（B ）A.遞歸函數(shù)B.剪枝函數(shù)C。隨機(jī)數(shù)函數(shù)D.搜索函數(shù)21、以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為（ D ）。A、分支界限算法B、概率算法C、

44、貪心算法 D回溯算法22、貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是（B ）。A 、最優(yōu)子結(jié)構(gòu)B、貪心選擇性質(zhì)C、構(gòu)造最優(yōu)解D定義最優(yōu)解23. 采用最大效益優(yōu)先搜索方式的算法是（A ）。A 、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D回溯法24. （ D ）是貪心算法與動(dòng)態(tài)規(guī)劃算法的共同點(diǎn)。A 、重疊子問題B 、構(gòu)造最優(yōu)解C 、貪心選擇性質(zhì)D最優(yōu)子結(jié)構(gòu)性質(zhì)25. 矩陣連乘問題的算法可由（B ）設(shè)計(jì)實(shí)現(xiàn)。A、分支界限算法B、動(dòng)態(tài)規(guī)劃算法 C、貪心算法D、回溯算法26. 0-1 背包問題的回溯算法所需的計(jì)算時(shí)間為（A ） A、 O（ n2n）B、 O（ nlogn ）C、 O（ 2n）D、 O（ n）27、背包問題的貪心算法所需的計(jì)算時(shí)間為（B ）A、O（n2）B、O（nlogn ）C、O（2）D、O（n）29、使用分治法求解不需要滿足的條件是（A ）。A