算法分析與設(shè)計習(xí)題集整理(共30頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上算法分析與設(shè)計習(xí)題集整理第一章算法引論一、填空題：1、算法運行所需要的計算機(jī)資源的量，稱為算法復(fù)雜性，主要包括時間復(fù)雜度和空間復(fù)雜度。2、多項式的上界為O(nm)。3、算法的基本特征：輸入、輸出、確定性、有限性 、可行性 。4、如何從兩個方面評價一個算法的優(yōu)劣：時間復(fù)雜度、空間復(fù)雜度。5、計算下面算法的時間復(fù)雜度記為： O(n3) 。for(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è)計語言、流程圖、盒圖、

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

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

4、kj; (5)答：1）定義：指在解決問題時，按照某種機(jī)械步驟一定可以得到問題結(jié)果的處理過程。 2）算法的復(fù)雜性：指的是算法在運行過程中所需要的資源（時間、空間）多少。 所需資源越多，表明算法的復(fù)雜性越高 3）該算法的主要元操作是語句5，其執(zhí)行次數(shù)是n3次。故該算法的時間復(fù)雜度記為O(n3). 4、算法A和算法B解同一問題，設(shè)算法A的時間復(fù)雜性滿足遞歸方程，算法B的時間復(fù)雜性滿足遞歸方程，若要使得算法A時間復(fù)雜性的階高于算法B時間復(fù)雜性的階，a的最大整數(shù)值可取多少？答：分別記算法A和算法B的時間復(fù)雜性為和，解相應(yīng)的遞歸方程得： 依題意，要求最大的整數(shù)a使得。顯然，當(dāng)a<=4時，；當(dāng)a>

5、;4時， a<=16。所以，所求的a的最大整數(shù)值為15。5、算法分析的目的？答：1)為了對算法的某些特定輸入，估算該算法所需的內(nèi)存空間和運行時間；2)是為了建立衡量算法優(yōu)劣的標(biāo)準(zhǔn)，用以比較同一類問題的不同算法。6、算法設(shè)計常用的技術(shù)？（寫種） 答： 分治法; 回溯法； 貪心法； 動態(tài)規(guī)劃法分治限界法 ； 蠻力法； 倒推法三、算法設(shè)計題 1、蠻力法：百雞百錢問題？2、倒推法：穿越沙漠問題？第二章 分治算法（1）-遞歸循環(huán)一、填空題：1、直接或間接地調(diào)用自身的算法稱為 遞歸算法 ，用函數(shù)自身給出定義的函數(shù)稱為 遞歸函數(shù) 。2、遞歸方程 和 約束函數(shù)（遞歸終止條件）是遞歸函數(shù)的兩個要素。二、判

6、斷題：1、所有的遞歸函數(shù)都能找到對應(yīng)的非遞歸定義。 （ ）2、定義遞歸函數(shù)時可以沒有初始值。 （ X ）三、簡答題：1、什么是遞歸算法？遞歸算法的特點？答：1 )遞歸算法:是一個模塊（函數(shù)、過程）除了可調(diào)用其它模塊（函數(shù)、過程）外，還可以直接或間接地調(diào)用自身的算法。2) 遞歸算法特點：每個遞歸函數(shù)都必須有非遞歸定義的初值；否則，遞歸函數(shù)無法計算；（遞歸終止條件）遞歸中用較小自變量函數(shù)值來表達(dá)較大自變量函數(shù)值；（遞歸方程式）2、比較循環(huán)與遞歸的異同？答：1) 相同：遞歸與循環(huán)都是解決“重復(fù)操作”的機(jī)制。2) 不同：就效率而言，遞歸算法的實現(xiàn)往往要比迭代算法耗費更多的時間（調(diào)用和返回均需要額外的時

7、間）與存貯空間（用來保存不同次調(diào)用情況下變量的當(dāng)前值的棧?？臻g），也限制了遞歸的深度。每個迭代算法原則上總可以轉(zhuǎn)換成與它等價的遞歸算法；反之不然 。遞歸的層次是可以控制的，而循環(huán)嵌套的層次只能是固定的，因此遞歸是比循環(huán)更靈活的重復(fù)操作的機(jī)制。3、遞歸算法解題通常有三個步驟？答： 1）分析問題、尋找遞歸：找出大規(guī)模問題與小規(guī)模問題的關(guān)系，這樣通過遞歸使問題的規(guī)模逐漸變小。2）設(shè)置邊界、控制遞歸：找出停止條件，即算法可解的最小規(guī)模問題。3）設(shè)計函數(shù)、確定參數(shù)：和其它算法模塊一樣設(shè)計函數(shù)體中的操作及相關(guān)參數(shù)。 四、算法設(shè)計題：1、樓梯上有n個臺階，上樓時可以上1步，也可以上2步，設(shè)計一遞歸算法求出共

8、有多少種上樓方法F(n)。寫出F(n)的遞歸表達(dá)式？ 并寫出其相應(yīng)的遞歸算法？ 解：寫出F(n)的遞歸表達(dá)式分析：到n階有兩種走法： 1）n-1階到n階； 2）n-2階到n階； 1 n=1 F(n) 2 n=2 F(n-1) + F(n-2) n>2寫出其相應(yīng)的遞歸算法？Int F(int n) if(n=1) return 1; else if(n=2) return 2; else return F(n-1)+ F(n-2);2、設(shè)a,b,c是3個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為1,2,n,現(xiàn)要求將塔座a上的這一疊圓

9、盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應(yīng)遵守以下移動規(guī)則：規(guī)則1：每次只能移動1個圓盤；規(guī)則2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上；規(guī)則3：在滿足移動規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。寫出該問題的解題步驟？ 并寫出其相應(yīng)的遞歸算法？ 解：第一步：將n1個盤子看成一個整體，從A移到C； 第二步：將第n個盤子移到B; 第三步：將n1個盤子看成一個整體，從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); h

10、anoi(n-1, c, b, a); 第二章 分治算法（2）分治算法一、填空題：1、在快速排序、插入排序和合并排序算法中， 插入排序 算法不是分治算法。2、合并排序算法使用的是 分治 算法設(shè)計的思想。3、二分搜索算法是利用 分治 算法思想設(shè)計的。二、簡答題：1、適合用分治算法求解的問題具有的基本特征？答：1)該問題的規(guī)模縮小到一定的程度就可以容易解決;2)該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)； 3）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。 4）利用該問題分解出子問題解可以合并為該問題解;2、分治算法基本思想，解題步驟？ 三、算法

11、設(shè)計題：1、改寫二分查找算法：設(shè)a1n是一個已經(jīng)排好序的數(shù)組，改寫二分查找算法，使得當(dāng)搜索元素x不在數(shù)組中時，返回小于x的最大元素位置i，和大于x的最小元素位置j；當(dāng)搜索元素x在數(shù)組中時，i和j相同，均為x在數(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 / (

12、amid<x) low=mid+1; /繼續(xù)在右邊查找 i=right; j=left; return 0；/low大于high查找區(qū)間為空，查找失敗 計算時間復(fù)雜性為O(logn)2、棋盤覆蓋在一個2k×2k 個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。 求：簡述分治算法的基本思想？ 設(shè)計該棋盤覆蓋問題的分治算法？ 計算所設(shè)計算法的時間復(fù)雜度？（要求寫出遞推公式） 解：分解：將一個難以直接解決的大問題

13、，分割成一些規(guī)模較小的相同子問題，以便各個擊破，分而治之。對這k個子問題分別求解：如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止求小問題解、合并：將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。、 3、金塊問題（求最大最小元問題）老板有一袋金塊(共n塊)，最優(yōu)秀的雇員得到其中最重的一塊，最差的雇員得到其中最輕的一塊。假設(shè)有一臺比較重量的儀器，我們希望用最少的比較次數(shù)找出最重的金塊。求：簡述分治算法的基本思想？ 設(shè)計該金塊問題的分治算法？ 計算所設(shè)計算法的時間復(fù)雜度？（要求寫出遞推公式）答：簡述分治

14、算法的基本思想：問題可以簡化為：在含n（n是2的冪（n>=2）個元素的集合中尋找極大元和極小元。用分治法（二分法）可以用較少比較次數(shù)地解決上述問題：1）將數(shù)據(jù)等分為兩組（兩組數(shù)據(jù)可能差1），目的是分別選取其中的最大（?。┲?。2)遞歸分解直到每組元素的個數(shù)2,可簡單地找到最大(小)值.3）回溯時將分解的兩組解大者取大，小者取小，合并為當(dāng)前問題的解。 、 第三章動態(tài)規(guī)劃算法一、填空題：1、動態(tài)規(guī)劃算法中存儲子問題的解是為了 避免重復(fù)求解子問題 。2、（ 最優(yōu)子結(jié)構(gòu) ）是問題能用動態(tài)規(guī)劃算法求解的前提。3、矩陣連乘問題的算法可由（    動態(tài)規(guī)劃

15、0;      ）算法設(shè)計實現(xiàn)。二、判斷題：1、動態(tài)規(guī)劃算法基本要素的是最優(yōu)子結(jié)構(gòu)。 （ ）2、最優(yōu)子結(jié)構(gòu)性質(zhì)是指原問題的最優(yōu)解包含其子問題的最優(yōu)解。 （ ）3、動態(tài)規(guī)劃算法求解問題時，分解出來的子問題相互獨立。 （ X）三、簡答題：1、動態(tài)規(guī)劃算法解題步驟？答：找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征;（即原問題的最優(yōu)解，包含了子問題的最優(yōu)解）遞歸地定義最優(yōu)值;（即子問題具有重疊性，由子問題定義原問題）以自底向上的方式計算出最優(yōu)值;根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解;2、動態(tài)規(guī)劃算法基本思想？答：動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解

16、問題分解成若干個子問題；但是經(jīng)分解得到的子問題往往不是互相獨立的。不同子問題的數(shù)目常常只有多項式量級。在用分治法求解時，有些子問題被重復(fù)計算了許多次；如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復(fù)計算，從而得到多項式時間算法。3、動態(tài)規(guī)劃與分治算法異同點？4、動態(tài)規(guī)劃算法的基本要素？ 四、算法設(shè)計與計算題：1、和的最長公共子序列為。問：若用記錄序列和公共子序列長度。求：用動態(tài)規(guī)劃法求解時,計算最優(yōu)值的遞歸公式？ 設(shè)計計算最優(yōu)值的算法？以及構(gòu)造最優(yōu)解的算法？2、長江游艇俱樂部在長江上設(shè)置了n個游艇出租站1,2n.游客可在這些游艇出租站租用游艇，并在下游的任何一

17、個游艇出租站歸還游艇。游艇出租站i到游艇出租站j之間的租金為r(i，j)，其中1<=i<j<=n；求：用動態(tài)規(guī)劃法求解時,計算最優(yōu)值（最少租金）的遞歸公式？設(shè)計計算最優(yōu)值（最少租金）的算法？并分析其時間復(fù)雜度？解：計算最優(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個站 for (int r = 2; r <= n; r+) for (int i = 1; i <= n - r+1

18、; i+) int j=i+r-1; m i j = mii + mi+1 j; s i j = i; /斷點位置在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 +“，”

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

20、j +A ; /S j存放對應(yīng)j幣種總張數(shù) GZ= GZ-A*B j ; for(i=1;i<=7;i+) print( B i , “-”, S i ); /輸出幣種和對應(yīng)張數(shù) 2、貪心算法的兩個基本要素是（貪心選擇性 ）和（ 最優(yōu)子結(jié)構(gòu) ）。 3、給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為M，應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大。貪心算法如下：float greedy_knapsack ( float M, float w , float p , float x ) / x 背包問題最優(yōu)解, w 物品重量， P 物品價值 int n=w

21、.length;float pp=0;float mmM; /pp計算當(dāng)前總價值，mm背包剩余載重for( int i=1;i<=n; i+ ) float ww i= p i / w i ； /計算物品單位價值ww x i=0; /初始化Mergesort ( w , n ); /按單位價值將物品排序， 便于貪心選擇for( int i=1; i<=n; i+ ) /貪心選擇，總是選擇價值最大放入背包 if ( w i<=mm ) /當(dāng)前物品小于背包剩余載重 x i=1; mm= mm - w i ; pp= pp + p i ; else x i=mm/w i; pp=

22、pp + x i*p i ; break; /i部分放入背包return pp;二、判斷題：1、滿足貪心選擇性質(zhì)必滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。 （ X ）三、簡答題： 1、貪心算法的基本思想？2、貪心算法的基本要素？3、貪心算法與動態(tài)規(guī)劃算法的異同?四、算法設(shè)計題：1、假設(shè)有7個物品，它們的重量和價值如下表所示。若這些物品均可以被分割，且背包容量M150，如果使用貪心方法求解此背包問題（背包不超載的前提下，裝載的物品價值達(dá)到最大）。物品ABCDEFG重量35306050401025價值10403050354030利用貪心算法求解該問題時，為了進(jìn)行貪心選擇，首先應(yīng)該做什么？ 然后進(jìn)行貪心裝載，給出一種正

23、確的物品裝載順序？并給出其最優(yōu)裝載方案？ 利用貪心思想設(shè)計該普通背包問題的貪心算法？分析其時間復(fù)雜度？解： 1）依據(jù)不同的標(biāo)準(zhǔn)對這些物品進(jìn)行排序，標(biāo)準(zhǔn)有重量、價值、單位價值； 2）重量從小到大：FGBAEDC ,得到的貪心解為：FGBAE 全部放入,D放入20% ，得到價值為165； 價值從大到小 ：DFBEGCA ，得到的貪心解為：DFBE 全部放入,G放入80% ，得到價值為189； 單位價值從大到小 ：FBGDECA ，得到的貪心解為：FBGD 全部放入,E放入87.5% ，得到價值為190.625； 3)顯然使用單位價值得出最佳轉(zhuǎn)載方案。 、2、設(shè)有n個活動集合，其中每個活動都要求使用

24、同一資源，如足球場，而在同一時間只能有一個活動使用該資源。每個活動i都有一個要求使用該資源起始時間si和結(jié)束時間fi，且si < fi；如果選擇了活動i，則它在半開區(qū)間si ， fi) 占用資源。若兩個活動si ， fi)與sj ， fj)不相交，則稱活動i與活動j是相容的；活動安排問題：就是在所給的活動集合中選出最大相容活動子集合；求：利用貪心算法求解該問題的基本思想？設(shè)計該活動安排問題的貪心算法？并分析其時間復(fù)雜度？3、給定下圖G(V, E)是一個無向連通圖，對每一條邊(v, w),其權(quán)值為c( v, w)；求：利用prim算法構(gòu)造其最小生成樹，畫出其選邊的過程？并構(gòu)造其算法？并分析

25、其時間復(fù)雜度？利用kruskal算法構(gòu)造其最小生成樹，畫出其選邊的過程？并構(gòu)造其算法？并分析其時間復(fù)雜度？4、對下圖中的有向圖，應(yīng)用Dijkstra算法計算從源(頂點1)到其它頂點間最短路徑的過程.要求：給出Dijkstra算法的迭代過程，計算源到給個頂點的最短路徑？（用表表示）解：見課本123頁表4-2解：迭代過程：第章 回溯算法一、填空題1、回溯法與分支限界法搜索方式不同，回溯法按 深度優(yōu)先 搜索解空間，分支限界法按 廣度優(yōu)先或最小耗費優(yōu)先 搜索解空間。二、判斷題1、回溯法中限界函數(shù)的目的是剪去得不到最優(yōu)解的子樹。 （ ）2、分支限界法類似于回溯法，也是一種在問題的解空間樹T上搜索問題解的

26、算法，兩者的搜索方式是相同的。 （ X ）三、簡答題1、簡述回溯法和分支限界法的相同點和不同點？2、什么是子集樹？ 什么是排列樹？什么叫滿m叉樹？3、回溯算法的基本思想？回溯算法的解題步驟？四、算法設(shè)計題1、n皇后問題在4×4格的棋盤上放置彼此不受攻擊的4個皇后。按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。用回溯算法解決4皇后問題： 構(gòu)造求解該問題的解空間樹？ 設(shè)計該4皇后問題的回溯算法？ 解：解空間樹 回溯算法2、01背包問題：假設(shè)有3個物品，它們的重量和價值如下表所示。若這些物品均不可以被分割，且背包容量M10，問應(yīng)該如何裝入使背包中物品的總價值最大

27、？物品ABC重量655價值422530用回溯算法求解該01背包問題： 構(gòu)造求解該問題的解空間樹？ 設(shè)計該01背包問題的回溯算法？ 解：1）解空間樹; 2)3、圖的著色問題：如下圖給定無向連通圖G和m種不同的顏色；用這m種顏色為圖G的各個頂點著色，是否有一種方法使得圖G中每一條邊的兩個頂點著不同顏色；求：構(gòu)造求解該問題的解空間樹？ 設(shè)計該圖的著色問題回溯算法？ 12345解：1）解空間樹： 2）算法:double mcoloring(int mm)int m=mm; /m可用顏色數(shù)double sum=0; /sum當(dāng)前著色方案數(shù) backtrack( 1 ); /深度優(yōu)先搜索解空間 retur

28、n sum;void backtrack( int t) if ( t>n ) / 搜索到葉子節(jié)點 sum+; /著色方案數(shù)加1 for (int i=1; i<=n; i+) system.out.print( x i ); /輸出解,頂點i著顏色x i else / 搜索到中間節(jié)點 for(int i=1; i<=m; i+) x t=i; /頂點t著顏色i=1m if( ok( t ) ) backtrack(t+1); boolean ok( int k) /當(dāng)前著色頂點與以前相鄰頂點是否同色 for(int j=1; j<=n; j+) if( a k j&a

29、mp;&( x j=x k ) ) /數(shù)組a是圖的鄰接矩陣 /當(dāng)前頂點k到j(luò)有邊：a k j，且色同：x j=x k return false; else return true;算法分析（m種顏色，n個節(jié)點） 計算限界函數(shù)，一重for循環(huán)時間復(fù)雜度：O(n); 在最壞的情況下每一個內(nèi)節(jié)點都需要判斷約束，內(nèi)節(jié)點個數(shù)：1+m+m2+ m3+mn-1=(mn-1)/(m-1)個；故圖的m著色問題的回溯算法，時間復(fù)雜度為：O(n*mn)。第六章 分支限界算法一、填空題1、按照活結(jié)點表的組織方式的不同，分支限界法包括 隊列式分支限界算法 和 優(yōu)先隊列式分支限界算法 兩種形式。2、回溯法與分支限

30、界法搜索方式不同，回溯法按 深度優(yōu)先 搜索解空間，分支限界法按 廣度優(yōu)先或最小耗費優(yōu)先 搜索解空間。3、隊列分支限界算法中，通常用隊列 實現(xiàn)，體現(xiàn)先進(jìn)先出原則 的原則。4、優(yōu)先隊列式分支限界算法，通常采用堆實現(xiàn)。6、回溯法與分支限界算法求解問題時，需要構(gòu)造對該問題的解空間結(jié)構(gòu),其解空間結(jié)構(gòu)通常有3種形式，分別是 子集樹 、排列樹、 滿m叉樹 。二、判斷題1、分支限界法類似于回溯法，也是一種在問題的解空間樹T上搜索問題解的算法，兩者的搜索方式是相同的。（X）三、簡答題1、簡述分支限界法的基本思想與解題步驟？2、分支限界算法與回溯算法異同點？四、算法設(shè)計題1、01背包問題：假設(shè)有3個物品，它們的重

31、量和價值如下表所示。若這些物品均不可以被分割，且背包容量M10，問應(yīng)該如何裝入使背包中物品的總價值最大？物品ABC重量655價值422530用分支限界算法求解該01背包問題： 構(gòu)造求解該問題的解空間樹？ 給出隊列式分支限界算法的求解過程？如設(shè)計該01背包問題的分支限界算法？并分析其時間復(fù)雜度？（隊列式分支限界，帶上界函數(shù)）、多段圖最短路徑問題求：構(gòu)造求解該問題的解空間樹？ 給出隊列式分支限界算法的求解過程？設(shè)計該問題的分支限界算法？并分析其時間復(fù)雜度？（隊列式分支限界，帶上界函數(shù)）解：2）求解過程：）算法描述： 法:隊列式分支限界法double shortest( int i) while (

32、true) /隊列不空， 搜索問題的解空間 for ( int j=1; j<=n;j+)/兒子結(jié)點入隊 if (a i j < Float.MAX_VALUE) / 頂點i到頂點j可達(dá) dist j= dist i +a i j; / dist i記錄源到頂點的距離 p j=enode.i; / p j記錄頂點j的前驅(qū) enQueue(v j, j); / 結(jié)點j加入隊列 ew = (Integer) queue.remove().intValue();/ 取隊首下一擴(kuò)展結(jié)點 if (ew = -1) / 同一層尾部標(biāo)記ew = -1：同一層結(jié)點處理結(jié)束 if (queue.is

33、Empty() return dist i;/判斷隊列是否為空 else queue.put(new Integer(-1); / 同層結(jié)點尾部標(biāo)志 ew = (Integer) queue.remove().intValue(); / 取下一擴(kuò)展結(jié)點 i+; / 進(jìn)入下一層 時間復(fù)雜度：第七章 概率算法1、什么叫概率算法？答：概率算法允許算法在執(zhí)行的過程中隨機(jī)選擇下一個計算步驟。2、概率算法有一個基本特征？答：基本特征是對所求解問題的同一實例用同一概率算法求解兩次可能得到完全不同的效果。3、概率算法可以分為哪4類？答：1)數(shù)值概率算法 2)蒙特卡羅算法 3)拉斯維加斯算法 4)舍伍德算法4、

34、在概率算法中使用的隨機(jī)數(shù)都是一定程度上隨機(jī)的，即偽隨機(jī)數(shù)；一般隨機(jī)數(shù)通過線性同余法方法產(chǎn)生。第八章 NP完全性理論1、什么是易解問題？什么是難解問題？難解問題分為哪兩類？答：1）易解問題：人們將存在多項式時間 算法的問題稱為易解問題;2）難解問題：將需要在指數(shù)時間內(nèi)解決的問題稱為難解問題；3）難解問題有兩類： 1）不可判定問題 2）非決定的難處理問題 。2、什么是不可判定問題？什么是非決定的難處理問題？答：1）不可判定問題 ：該類問題是不能解問題，它們太難了，以至于根本就不存在能求解它們的任何算法。2）非決定的難處理問題： 這類問題是可判定的（即可解的）。 但是，這類問題即使使用非決定的計算機(jī)

35、，也不能在多項式時間內(nèi)求解它們。3、什么是P類問題？什么是NP完全問題？答：1）P類問題：是一類能夠用確定性算法在多項式時間內(nèi)求解的判斷問題。事實上，所有易解問題都屬于P類問題。2）NP完全問題：對于某問題，很難找到其多項式時間的算法(或許根本不存在)，但是如果給了該問題的一個答案，則可以在多項式時間內(nèi)判定或驗證這個答案是否正確。 這種可以在多項式時間內(nèi)驗證一個解是否正確的問題稱為NP問題。4、列出幾個典型的NP完全問題？答：（1）圖著色問題COLORING（2）路徑問題LONG-PATH （3）頂點覆蓋問題VERTEX-COVER（4）子集和問題SUBSET-SUM（5）哈密爾頓回路問題HA

36、M-CYCLE（6）旅行商問題TSP（7）裝箱問題BIN-PACKING ， 能否用k個箱子來裝n個物品；第九章近似算法1、 所有NP完全問題都還沒有多項式時間的算法，然而許多NP完全問題都具有很重要的意義，對于這類問題通?？梢圆扇∫韵聨追N解題策略？答：）只對問題的特殊實例求解； ）用動態(tài)規(guī)劃或分支限界法求解。 ）啟發(fā)式方法求解 ）只求近似解2、 利用近似算法求解NP完全問題時，近似算法應(yīng)該滿足下面兩個基本的要求？答：1）算法的時間復(fù)雜性：要求算法能在n的多項式時間內(nèi)完成。2）解的近似程度：算法的近似解應(yīng)滿足一定的精度。通常，用來衡量精度的標(biāo)準(zhǔn)有近似比和相對誤差。1、二分搜索算法是利用（ A

37、）實現(xiàn)的算法。 A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 2、下列不是動態(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、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 4、最長公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 5. 回溯法解TSP問題時的解空間樹是（ A ）。 A、子集樹 B、排列樹 C、深度優(yōu)先生成樹 D、廣度優(yōu)先生成樹 6下列算法中通常以自底向上的方式求解最優(yōu)解的是（ B ）。 A、備忘錄法 B、動態(tài)規(guī)劃法

38、C、貪心法 D、回溯法 7、衡量一個算法好壞的標(biāo)準(zhǔn)是（C ）。 A 運行速度快 B 占用空間少 C 時間復(fù)雜度低 D 代碼短 8、以下不可以使用分治法求解的是（D ）。 A 棋盤覆蓋問題 B 選擇問題 C 歸并排序 D 0/1背包問題 9. 實現(xiàn)循環(huán)賽日程表利用的算法是（ A ）。 A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 10、實現(xiàn)最長公共子序列利用的算法是（ B ）。 A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 11下面不是分支界限法搜索方式的是（ D ）。 A、廣度優(yōu)先 B、最小耗費優(yōu)先 C、最大效益優(yōu)先 D、深度優(yōu)先 12下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解

39、的是（ D ）。 A、備忘錄法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 13. 一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的（ B ）。 A、重疊子問題 B、最優(yōu)子結(jié)構(gòu)性質(zhì) C、貪心選擇性質(zhì) D、定義最優(yōu)解 14廣度優(yōu)先是（ A ）的一搜索方式。 A、分支界限法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 15背包問題的貪心算法所需的計算時間為（ B ）。 A、O（n2） nB、O（nlogn） C、O（2） nD、O（n） 16實現(xiàn)最大子段和利用的算法是（ B ）。 A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 17實現(xiàn)棋盤覆蓋算法利用的算法是（ A ）。 A、分治法 B、動

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

41、最優(yōu)子結(jié)構(gòu) B、貪心選擇性質(zhì) C、構(gòu)造最優(yōu)解 D、定義最優(yōu)解 23. 采用最大效益優(yōu)先搜索方式的算法是（ A ）。 A、分支界限法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 24. （ D ）是貪心算法與動態(tài)規(guī)劃算法的共同點。 A、重疊子問題 B、構(gòu)造最優(yōu)解 C、貪心選擇性質(zhì) D、最優(yōu)子結(jié)構(gòu)性質(zhì) 25. 矩陣連乘問題的算法可由（ B）設(shè)計實現(xiàn)。 A、分支界限算法 B、動態(tài)規(guī)劃算法 C、貪心算法 D、回溯算法 26. 0-1背包問題的回溯算法所需的計算時間為（ A ） A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 27、背包問題的貪心算法所需的計算時間為（ B ） A、O（n2） B、O（nlogn） C、O（2） D、O（n） 29、使用分治法求解不需要滿足的條件是（A ）。 A 子問題必須是一樣的 B 子問題不能夠重復(fù)C 子問題的解可以合并 D 原問題和子問題使用相同的方法解 30、下面問題（B ）不能使用貪心法解決。 nnA 單源最短路徑問題 B N皇后問題 C 最小花費生成樹問題 D 背包問題 31、下列算法中不能解決0/1背包問題的是（A ） A 貪心法 B 動態(tài)規(guī)劃 C 回溯法 D 分支限界法 3