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

1、算法設(shè)計與分析試題對于下圖使用 Dijkstra算法求由頂點 a到頂點 h 的最短路徑解： 用 V1表示已經(jīng)找到最短路徑的頂點，V2 表示與 V1中某個頂點相鄰接且不在步驟V 1 V2E1E21.a bab2.a,bdabbd3.a,b,dc,f ab,bddc,df4.a,b,d,cfab,bddf5.a,b,c,d,f eab,bd,dc,dffe6.a,b,c,d,e,fgab,bd,dc,df,feeg7.a,b,c,d,e,f,gh ab,bd,dc,df,fe,eggh8.a,b,c,d,e,f,g,h ab,bd,de,df,fe,eg,gh 【以上每步 2 分】V1中的頂點；

2、E1 表示加入到最短路徑中的邊， 短的路徑。【 1分】E2為與 V1 中的頂點相鄰接且距離最結(jié)果：從 a 到 h 的最短路徑為 a b d f e g h ，權(quán)值為 18?！?1 分】求所有頂點對之間的最短路徑可以使用 Dijkstra 算法，使其起始節(jié)點從 a 循環(huán)到 h，每次求起始節(jié)點到其他節(jié)點的最短路徑，最終可以求得所有頂點 對之間的最短路徑。【2 分】二、 假設(shè)有 7 個物品，它們的重量和價值如下表所示。 若這些物品 均不能被分割，且背包容量 M150，使用回溯方法求解此背包問題。 請寫出狀態(tài)空間搜索樹。物品ABCDEFG重3365412量5000005價1435343值0000500

3、解：按照單位效益從大到小依次排列這 7個物品為： FBGDEC。A將它們的序號分別記為 17。則可生產(chǎn)如下的狀態(tài)空間搜索樹。其中各個節(jié)點處的限界函數(shù)值 通過如下方式求得：【排序 1 分】狀態(tài)空間搜索樹及其計算過程 17 分，每個節(jié)點1 分】ab.c40 40 30 50 10 170(1,1,1,1,0,0,1)40 40 30 50 35 115740 40 30 50 30 177.5 (1,1,1,1,0, 7 ,0)6012 115 190.625 (1,1,1,1,7,0,0)40 8d.40 40 30 35 30 150 105 167.5 (1,1,1,0,1, 3 ,0)60

4、 4e. 40 40 50 35 30 150 130 175 (1,1,0,1,1,1,0)f.60 3(1,1,0,1,1,0,47)150 13040 40 50 35 10 170.7135g. 40 40 50 30 160(1,1,0,1,0,1,0)(1,1,0,0,1,1, 27)h. 40 40 35 30 10 150 140 146.8535i. 40 30 50 35 30 150 125 167.5 (1,0,1,1,1, 5 ,0)60 12j. 40 30 50 35 30 150 145 157.5 (0,1,1,1,1,1 ,0)60 12在 Q1 處獲得該問

5、題的最優(yōu)解為 （1,1,1,1,0,0,1），背包效益為 170。即在背包中裝入 物品 F、B、G、D、A時達(dá)到最大效益，為 170，重量為 150?！窘Y(jié)論 2 分】三、 已知 Ak （aij（k）ri*ri 1，k=1，2，3，4，5，6，r1=5，r2=10，r3=3， r 4=12，r 5=5，r 6=50，r 7=6，求矩陣鏈積 A1× A2× A3×A4× A5× A6的最佳 求積順序。（要求：給出計算步驟）解：使用動態(tài)規(guī)劃算法進(jìn)行求解 求解矩陣為：【每個矩陣 18 分】12345610150330405165520102036033

6、024301950301809301770403000186050150060123456101224220222230344404450560因此，最佳乘積序列為（ A1A2）（A3A4）（A5A6），共執(zhí)行乘法 2010 次。【結(jié)論 2 分】四、回答如下問題：1）什么是算法？算法的特征有哪些？2）什么是 P 類問題？什么是 NP類問題？請描述集合覆蓋問題 的近似算法的基本思想。解：（1）算法是解決某類問題的一系列運算的集合【 2 分】。具有有窮行、可行性、確定性、 0個或者多個輸入、 1 個或者多個輸出【 8分】。 （2）用確定的圖靈機(jī)可以在多項式實踐內(nèi)可解的判定問題稱為P類問題【2 分】

7、。用不確定的圖靈機(jī)在多項式實踐內(nèi)可解的判定問題稱為 P類問題?！? 分】 集合覆蓋問題的近似算法采用貪心思想：對于問題 <X,F>，每次選擇 F 中覆 蓋了盡可能多的未被覆蓋元素的子集 S，然后將 U中被 S 覆蓋的元素刪除，并將 S加入 C中，最后得到的 C就是近似最優(yōu)解?！? 分】五、排序和查找是常用的計算機(jī)算法。按照要求完成以下各題：1）對數(shù)組 A=15，9，115，118，3，90，27，25，5 ，使用合 并排序方法將其排成遞減序。2） 若改變二分搜索法為三分搜索法，即從一個遞減序列A 中尋找元素 Z，先與元素 An比較，若Z A n ，則在前面 n 個 3 3 3 元素

8、中尋找 Z；否則與 A 2n 比較，總之使余下的序列為 n 個 33 元素。給出該方法的偽代碼描述。3）使用上述算法對（ 1）所得到的結(jié)果搜索如下元素，并給出 搜索過程： 118， 31，25。解：（1）第一步： 15 9 115 118 3 90 27 25 5第二步： 15 9 118 115 90 3 27 25 5第三步： 118 115 15 9 90 27 25 3 5第四步： 118 115 90 27 25 15 9 3 5第五步： 118 115 90 27 25 15 9 5 3 【5 分，每步 1 分】 2）輸入：遞減數(shù)組 Aleft:right，待搜索元素 v?！? 分

9、】 輸出： v 在 A中的位置 pos，或者不在 A中的消息（ -1 ）?！?1 分】 步驟：【8 分】int BinarySearch(int A,int left,int right,int v)int mid;while (left<=right) first=left+(right-left+1)/3; second=left+(right-left+1)/3*2; if (v=Afirst) return first; else if (v>Afirst) right=first-1; else if (v=Asecond) return second; else if

10、(v>Asecond) left=first+1;right=second-1; else left=second+1;return -1;（ 3）搜索 118：118>27，所以 right 3；118>115，所以 right 1； 118118， 找到。【2 分】搜索 31：31>27，所以 right 3；31<90，所以 left=4 ，結(jié)束，未找到?！? 分】 搜索 25：9<25<27，所以 left=5 ，right=6 ；2525，找到?！? 分】六、假設(shè)有 7 個物品，它們的重量和價值如下表所示。 若這些物品 均可以被分割，且背包容

11、量 M150，如果使用貪心方法求解此背 包問題，請回答：（ 20 分）。（4）對各個物品進(jìn)行排序時，依據(jù)的標(biāo)準(zhǔn)都有哪些？（5）使用上述標(biāo)準(zhǔn)分別對 7 個物品進(jìn)行排序，并給出利用各個 順序進(jìn)行貪心求解時獲得解。（6）上述解中哪個是最優(yōu)的？物品ABCDEFG重336541220%，得到價值為 165?！? 分】使用價值從大到?。?DFBEGC，A得到貪心解為： DFBE全部放入，而 G放入 80%， 得到價值為： 189?！? 分】使用單位價值從大到?。?FBGDEC，A得到貪心解為：FBGD全部放入，而E放入 87.5%， 得到價值為 190.625 ?！?5 分】（3）顯然使用單位價值作為標(biāo)準(zhǔn)

12、得到的是最優(yōu)解。 【2 分】七、多段圖問題：設(shè) G（V ，E）是一個賦權(quán)有向圖，其頂點集 V 被 劃分成 k>2個不相交的子集 Vi：1 i k ，其中， V1和 Vk分別只有一 個頂點 s（稱為源）和一個頂點 t（稱為匯），圖中所有的邊 （u,v ），u Vi ， v Vi 1。求由 s 到 t 的最小成本路徑。（ 25 分）（7）給出使用動態(tài)規(guī)劃算法求解多段圖問題的基本思想V18）使用上述方法求解如下多段圖問題。V5V2V3V4241s1解：（1）基本思想：設(shè) P（i,j） 是從 Vi 中的節(jié)點 j 到匯點 t 的最小成本路徑，Cost（i,j） 是其成本。則 Cost（i,j）=m

13、inc（j,h）+Cost（i+1,h）|h Vi+1,（j,h） E 。邊界條件是（2）V19 16,2/3 1s6,21/3 71)若 h=t，則 Cost(h,t) 0；(2)Cost(k-1,j) c(j,t) ?！?0 分】 求解過程可以表示為： 【6分，每個節(jié)點 0.5 分】V5V2V3V47,7 27,104,129,6 2 4 2 6 6 99,6 237 7 73 148,8 11 57,104 1115,851,128 8 6 117,10/11其中每個節(jié)點標(biāo)示的序偶 （p,q） 中，p表示節(jié)點到 t 的成本，q 表示后繼 節(jié) 點 的 編 號 。 從 而 ， 最 優(yōu) 路 徑

14、 為 ： 1 2 7 10 12 和1 3 6 10 12，成本為 16?！? 分】八、設(shè) x1、x2、x3 是一個三角形的三條邊，而且 x1+x2+x3=14。請問有 多少種不同的三角形？給出解答過程。解：由于 x1、x2、x3是三角形的三條邊， 從而 xi +xj >xk，|x i -x j|<x k，（i,j,k=1,2,3 ）， 【4分】根據(jù) x1+x2+x3=14 可知 1<xi<7（i=1,2,3 ）【4分】。利用回溯法求解得到：7分，每個節(jié)點 0.5 分】即有 4 個可行解：（6，6，2），（6，5，3），（6，4，4，）（5，5，4）?！? 分】九、15

15、 謎問題：在一個 4×4 的方格的棋盤上，將數(shù)字 1 到 15 代表的 15 個棋子以任意的順序置入各方格中，空出一格。要求通過有限 次的移動， 把一個給定的初始狀態(tài)變成目標(biāo)狀態(tài)。 移動的規(guī)則是： 每次只能把空格周圍的四格數(shù)字 (棋子) 中的任意一個移入空格， 從而 形成一個新的狀態(tài)。為了有效的移動，設(shè)計了估值函數(shù)C1(x) ，表示在結(jié)點 x 的狀態(tài)下，沒有到達(dá)目標(biāo)狀態(tài)下的正確位置的棋子的個數(shù)。解：【每個節(jié)點 1 分，注意限界值1245637910128131411157123456791012813141115612456379101281314111512345679101281

16、31411151234561279108131411151235674910128131411151234568910712131411512345678910111213141總共20 分】124563791012813141115712345679101281314111541234567891012131411151234567891011121314152112345678910121314111533123456789101213141115123456789101112131415123456789101215131411十、設(shè)數(shù)組 A有 n 個元素，需要找出其中的最大最小值。 (

17、20 分)(1)請給出一個解決方法，并分析其復(fù)雜性。(2) 把 n 個元素等分為兩組 A1和 A2，分別求這兩組的最大值和 最小值，然后分別將這兩組的最大值和最小值相比較， 求出全部元素 的最大值和最小值。 如果 A1和 A2 中的元素多于兩個， 則再用上述方 法各分為兩個子集。 直至子集中元素至多兩個元素為止。 這是什么方 法的思想？請給出該方法的算法描述，并分析其復(fù)雜性。 解：(1)基本思想：從頭到尾逐個掃描，紀(jì)錄最大和最小元素。 【2 分】 輸入：具有 n 個元素的數(shù)組【 1分】 輸出：最大值和最小值【 1 分】 步驟：【4 分】void FindMaxMin(int A, int n,

18、 int max, int min)max=min=A0;for (i=1;i<n;i+)if (Ai>max) max=Ai;if (Ai<min) min=Ai;復(fù)雜性分析：由于是從頭到尾掃描各個元素， 而每個元素都要與 max和 min比較 一遍，從而時間復(fù)雜性為： O(n) ?！?2 分】( 2)【10分】 void FindMaxMin(int left,int right, int max, int min) if (left=right) max=min=Aleft;else if (left=right-1) max=(Aleft<Aright?Arig

19、ht:Aleft);min=( Aleft<Aright?Aleft:Aright);elsemid=(left+right)/2;FindMaxMin(left,mid,gmax,gmin); FindMaxMin(mid+1,right,hmax,hmin); max=(gmax<hmax?hmax:gmax); min=(gmin<hmin?gmin:hmin);十一、用分支限界法解裝載問題時， 對算法進(jìn)行了一些改進(jìn)， 下面的 程序段給出了改進(jìn)部分； 試說明斜線部分完成什么功能， 以及這樣做 的原因，即采用這樣的方式，算法在執(zhí)行上有什么不同。/ 檢查左兒子結(jié)點Type

20、wt = Ew + wi; /左兒子結(jié)點的重量if (wt <= c) / 可行結(jié)點 if (wt > bestw) bestw = wt;/ 加入活結(jié)點隊列if (i < n) Q.Add(wt);/ 檢查右兒子結(jié)點if (Ew + r > bestw && i < n) Q.Add(Ew); / 可能含最優(yōu)解 Q.Delete(Ew); / 取下一擴(kuò)展結(jié)點解：斜線標(biāo)識的部分完成的功能為：提前更新 bestw 值； 這樣做可以盡早的進(jìn)行對右子樹的剪枝。具體為：算法 Maxloading 初始 時將 bestw 設(shè)置為 0，直到搜索到第一個葉結(jié)點時

21、才更新 bestw 。因此在算法搜 索到第一個葉子結(jié)點之前，總有 bestw=0，r>0 故 Ew+r>bestw 總是成立。也就 是說，此時右子樹測試不起作用。為了使上述右子樹測試盡早生效，應(yīng)提早更新 bestw 。又知算法最終找到的 最優(yōu)值是所求問題的子集樹中所有可行結(jié)點相應(yīng)重量的最大值。 而結(jié)點所相應(yīng)得 重量僅在搜索進(jìn)入左子樹是增加，因此，可以在算法每一次進(jìn)入左子樹時更新 bestw 的值。十二、簡要回答下列問題：1. 算法重要特性是什么？ 算法分析的目的是什么？算法的時間復(fù)雜 性與問題的什么因素相關(guān)？2. 什么是哈密頓環(huán)問題？用回溯法求解哈密頓環(huán)，如何定義判定函 數(shù)？ 答：

22、1. （1）確定性、可實現(xiàn)性、輸入、輸出、有窮性， （2）分析算法占用計算 機(jī)資源的情況，對算法做出比較和評價，設(shè)計出額更好的算法， （3）算法的時間 復(fù)雜性與問題的規(guī)模相關(guān)，是問題大小 n 的函數(shù)；2. （1）哈密頓環(huán)是指一條沿著圖 G的 N 條邊環(huán)行的路徑，它的訪問每 個節(jié)點一次并且返回它的開始位置， （2）當(dāng)前選擇的節(jié)點 Xk 是從未到過的節(jié) 點,即 Xk Xi（i=1,2, ,k-1） ，且 C（Xk-1, Xk） ，如果 k=-1 ，則 C（Xk, X1） 。十三、簡要回答下列問題：1. 快速排序的基本思想是什么。2. 什么是直接遞歸和間接遞歸？消除遞歸一般要用到什么數(shù)據(jù)結(jié)構(gòu)？答：1

23、. 快速排序的基本思想是在待排序的 N個記錄中任意取一個記錄，把 該記錄放在最終位置后， 數(shù)據(jù)序列被此記錄分成兩部分。 所有關(guān)鍵字比該記錄關(guān) 鍵字小的放在前一部分， 所有比它大的放置在后一部分， 并把該記錄排在這兩部 分的中間， 這個過程稱作一次快速排序。 之后重復(fù)上述過程， 直到每一部分內(nèi)只 有一個記錄為止。2. 在定義一個過程或者函數(shù)的時候又出現(xiàn)了調(diào)用本過程或者函數(shù)的成分，既 調(diào)用它自己本身，這稱為直接遞歸。如果過程或者函數(shù) P 調(diào)用過程或者函數(shù) Q，Q又調(diào)用 P，這個稱為間接遞歸。消除遞歸一般要用到棧這種數(shù)據(jù)結(jié)構(gòu)十四、寫出多段圖最短路經(jīng)動態(tài)規(guī)劃算法求解下列實例的過程， 并求出最優(yōu)值。各邊

24、的代價如下：C(1,2)=3 ， C(1,3)=5 ，C(1,4)=2C(2,6)=8 ， C(2,7)=4 ，C(3,5)=5 ，C(3,6)=4 ， C(4,5)=2 ，C(4,6)=1C(5,8)=4 ， C(6,8)=5 ，C(7,8)=6解： Cost(4,8)=0Cost(3,7)= C(7,8)+0=6 ，D5=8Cost(3,6)= C(6 ，8)+0=5, D6=8Cost(3,5)= C(5 ， 8)+0=4 D7=8Cost(2,4)= minC(4 ，6)+ Cost(3,6), C(4 ，5)+ Cost(3,5)= min1+ 5, 2+4=6 D4=6Cost(2

25、,3)= minC(3 ，6)+ Cost(3,6) = min4+5=9 D3=5Cost(2,2)= minC(2 ，6)+ Cost(3,6), C(2 ，7)+ Cost(3,7)= min8+5, 4+6=10 D2=7Cost(1,1)= minC(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+Cost(2,4)= min3+10, 5+9,2+6= 8D1=41468十五、寫出 maxmin算法對下列實例中找最大數(shù)和最小數(shù)的過程。數(shù)組 A=(48,12,61,3,5,19,32,7)解： 寫出 maxmin算法對下列實例中找最大數(shù)和最小數(shù)的過程。數(shù)組 A=()1、 48,12,61,3, 5,19,32,72、48,12 61,3 5,19 32,73、48 61, 12 3 19 32，574、61 32 3 55、61 3十六、快速排序算法對下列實例排序，算法執(zhí)行過程中，寫出數(shù) 組 A 第一次被分割的過程。A=(65,70,75,80,85,55,50,2)解： 第一個分割元素為 65(1) (2) (3)