算法設(shè)計與分析試題

1、算法設(shè)計與分析期末考試試題( A 卷)、選擇題： 試題說明：本題包含 12 個小題，占 24 分； 請將正確答案填寫在題目左側(cè)的括號內(nèi)。分支限界法與回溯法都是在問題的解空間樹A. 求解目標(biāo)不同，B. 求解目標(biāo)不同，C. 求解目標(biāo)相同，D. 求解目標(biāo)相同，回溯法在解空間樹A.深度優(yōu)先C.最小耗費優(yōu)先1、2、3、4、5、6、7、8、9、10、11、12、T 上搜索問題的解，二者()。搜索方式相同 搜索方式也不同 搜索方式不同 搜索方式也相同T 上的搜索方式是(B.廣度優(yōu)先D.活結(jié)點優(yōu)先)。)。回溯算法和分支限界法的問題的解空間樹不會是(A.有序樹B.子集樹C.排列樹D.無序樹在對問題的解空間樹進(jìn)行

2、搜索的方法中， 一個活結(jié)點最多有一次機(jī)會成為活結(jié)點的是 ( )。A.回溯法B.分支限界法C.回溯法和分支限界法D.回溯法求解子集樹問題從活結(jié)點表中選擇下一個擴(kuò)展結(jié)點的不同方式將導(dǎo)致不同的分支限界法，以下除 ( )之外都是最常見的方式。A.隊列式分支限界法B.優(yōu)先隊列式分支限界法C.棧式分支限界法D. FIFO分支限界法概率算法是一種非確定性地選擇下一計算步驟的方法， 例間的關(guān)聯(lián)，以下算法暗中適合于求解問題近似解的是(A.C.(A.C.力圖消除問題復(fù)雜性與具體實)。數(shù)值概率算法B.蒙特卡羅算法拉斯維加斯算法D.舍伍得算法)能夠求得問題的解，但卻無法有效地判定解的正確性。數(shù)值概率算法B.蒙特卡羅算

3、法拉斯維加斯算法D.舍伍得算法下面算法實現(xiàn)的是素數(shù)測試，該方法使用的數(shù)學(xué)原理是(A.費爾馬小定理B.費爾馬定理C. Wilson定理D.二次探測定理以下關(guān)于判定問題難易處理的敘述中正確的是(A. 可以由多項式時間算法求解的問題是難處理的B. 需要超過多項式時間算法求解的問題是易處理的C. 可以由多項式時間算法求解的問題是易處理的D. 需要超過多項式時間算法求解的問題是不能處理的 設(shè)f ( N)、g ( N)是定義在正數(shù)集上的正函數(shù)，如果存在正的常數(shù))。)。C 和自然數(shù) N0 ，使得當(dāng)N No時有f( N) Cg( N)，則稱函數(shù)f( N)當(dāng)N充分大時有上界 g ( N), 記作 f( N)A.

4、不高于 C.等價于 對于含有 nA. n!C. 2n+1-1對于含有 nA. 2n+1-1Cn!=O (g ( N)，即卩 f ( N)的階(B.不低于D.逼近個元素的子集樹問題，最壞情況下其解空間的葉結(jié)點數(shù)目為(B. 2nnD.n!/i!i1個元素的排列樹問題，最壞情況下計算時間復(fù)雜性為(nn!/i!i1D. 2n)g (N)的階。)。)。B二、判斷題： 試題說明：本題包含 請將正確答案填寫在題目左側(cè)的括號內(nèi)8 個小題，占 16 分；()1、2、分支限界法類似于回溯法， 的求解目標(biāo)是相同的。進(jìn)行問題復(fù)雜性分析時， 個計算模型是隨機(jī)存取機(jī)也是一種在問題的解空間樹T上搜索問題解的算法，兩者必須首

5、先建立求解問題所用的數(shù)學(xué)模型，其中比較重要的三RAM、隨機(jī)存取存儲程序機(jī) RAPS和圖靈機(jī)TM，它們的計3、4、5、6、7、算能力是等價的，只是計算速度不同。判定樹是RAM的一種變形和簡化，運用于基于比較的排序算法的復(fù)雜性分析，其算 法時間復(fù)雜性可用判定樹的高度來衡量。已知含有n個元素的某集合 X=X1, X2,，xn，要判定其中元素的唯一性，可以用判 別函數(shù)（Xi Xj）是否為0進(jìn)行判定。i j一個直接或間接地調(diào)用自身的算法稱為遞歸算法，而一個使用函數(shù)自身給岀定義的函數(shù)稱為遞歸函數(shù)。定義第歸函數(shù)時可以沒有初始值。動態(tài)規(guī)劃算法與分治法類似，其基本思想是將待求解問題分解成若干個子問題，先求解子問

6、題，然后從這些子問題的解得到原問題的解，二者采用的都是自底向上的計算方式。利用貪心算法求解問題時，往往需要事先把問題集合按照一定原則進(jìn)行排序， 安排問題即按活動結(jié)束時間的非減序進(jìn)行排列的。餓活動使用回溯法搜索問題的解空間樹時，按照深度優(yōu)先方式進(jìn)行搜索，其間不受其他條件限制。三、填空題：試題說明：本題包含5個小題，占20分，每空1分； 請將正確答案填寫在題目要求的位置。1、以下是對x，y，z三個數(shù)進(jìn)行升序排序的一棵判定樹，請在方框中填寫相應(yīng)的結(jié)果。并且具有(）、2、算法是由若干條指令組成的有序序列，的性質(zhì)。3、 評價算法的標(biāo)準(zhǔn)包括（）、（4、下面是棋盤覆蓋的分治策略算法，請按該算法將左圖特殊棋盤

7、進(jìn)行 void ChessBoard（int tr, int tc, int dr, int de, int size） if （size = = 1） retur n;int t = titl +;）以及正確性簡單性等。L型骨牌填充。s = size / 2;if (dr tr + s & de tc + s)ChessBoard(tr, te, dr, de, s);else Boardt 葉s-1tc+s-1 = t;ChessBoard(tr, tc, tr+s-1, tc+s-1, s);if (dr = tc + s)ChessBoard(tr, tc+s, dr, dc, s);

8、else Boardtr+s-1tc+s = t;ChessBoard(tr, tc+s, tr+s-1, tc+s, s);if (dr = tr + s & dc = tr + s & dc = tc + s)ChessBoard(tr+s, tc+s, dr, dc, s);else Boardtr+stc+s = t;ChessBoard(tr+s, tc+s, tr+s, tc+s, s);其中，tile為全局變量，初始值為0。T (k)c，由此算法可知，覆蓋一個2kx 2k的特殊棋盤所需要的L型骨牌的個數(shù)為()，算法時間復(fù)雜性=( )。5、若一個最優(yōu)化問題的最優(yōu)值為c*，求解該問題

9、的一個近似算法所求的的近似最優(yōu)解相應(yīng)的目標(biāo)函數(shù)值為則將該近似算法的性能比定義為n=()。四、算法理解題(占 24分)：1、依據(jù)優(yōu)先隊列式分支限界法，求下圖中從s點到t點的單源最短路徑，請畫岀求得最優(yōu)解的解空間樹。要求中間被舍棄的結(jié)點用X標(biāo)記，獲得中間解的結(jié)點用單圓圈o框起，最優(yōu)解用雙圓圈框起。s2、已知在如下所示的電路板中，陰影部分是已作了封鎖標(biāo)記的方格，請按照隊列式分支限界法在圖中確定 到b的最短布線方案，要求布線時只能沿直線或直角進(jìn)行，在圖中標(biāo)岀求得最優(yōu)解時各方格情況。ba3、設(shè)有n=2k個運動員要進(jìn)行循環(huán)賽，現(xiàn)設(shè)計一個滿足以下要求的比賽日程表: 每個選手必須與其他n-1名選手比賽各一次； 每個選手一天至多只能賽一次； 循環(huán)賽要在最短時間內(nèi)完成。（1）如果n=2k，循環(huán)賽最少需要進(jìn)行（）天；如果n工2k,循環(huán)賽最少需要進(jìn)行（）天。（2）當(dāng)n=23=8時，請畫岀循環(huán)賽日程表：4、請分別說明分治策略、動態(tài)規(guī)劃、貪心選擇策略、回溯法和分支限界法在實際應(yīng)用中的適用條件。