算法分析與設(shè)計(jì)復(fù)習(xí)題及參考答案模板

1、資料內(nèi)容僅供您學(xué)習(xí)參考，如有不當(dāng)或者侵權(quán)，請聯(lián)系改正或者刪除。網(wǎng)絡(luò)教育課程考試復(fù)習(xí)題及參考答案算法分析與設(shè)計(jì)一、名詞解釋：1.算法2.程序.遞歸函數(shù)4.子問題的重疊性質(zhì).隊(duì)列式分支限界法6.多機(jī)調(diào)度問題.最小生成樹二、簡答題：.備忘錄方法和動(dòng)態(tài)規(guī)劃算法相比有何異同？簡述之。.簡述回溯法解題的主要步驟。.簡述動(dòng)態(tài)規(guī)劃算法求解的基本要素。.簡述回溯法的基本思想。.簡要分析在遞歸算法中消除遞歸調(diào)用，將遞歸算法轉(zhuǎn)化為非遞歸算法的方法。.簡要分析分支限界法與回溯法的異同。.簡述算法復(fù)雜性的概念，算法復(fù)雜性度量主要指哪兩個(gè)方面？.貪心算法求解的問題主要具有哪些性質(zhì)？簡述之。.分治法的基本思想是什么 ？合并

2、排序的基本思想是什么？請分別簡述之。.簡述分析貪心算法與動(dòng)態(tài)規(guī)劃算法的異同。三、算法編寫及算法應(yīng)用分析題：.已知有 3 個(gè)物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容積M=20,根據(jù)0-1背包動(dòng)態(tài)規(guī)劃的遞推式求出最優(yōu)解。資料內(nèi)容僅供您學(xué)習(xí)參考，如有不當(dāng)或者侵權(quán)，請聯(lián)系改正或者刪除。.按要求完成以下關(guān)于排序和查找的問題。對數(shù)組A=15, 29, 135, 18, 32, 1, 27, 25, 5),用快速排序方法將其排成遞減 序。請描述遞減數(shù)組進(jìn)行二分搜索的基本思想，并給出非遞歸算法。給出上述算法的遞歸算法。使用上述算法對所得到的結(jié)果搜索如

3、下元素，并給出搜索過程:18, 31,135。(k).已知Ak(aij九*n 1, k=1,2, 3, 4, 5, 6, r1=5,r2=10,3=3,4=12,5=5,6=50,r7=6,求矩陣鏈積 A1XA2X A3X A4X A5X A6的最佳求積順序(要求給出計(jì) 算步驟)。.根據(jù)分枝限界算法基本過程，求解0-1背包問題。已知 n=3,M=20, (w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。.試用貪心算法求解汽車加油問題：已知一輛汽車加滿油后可行駛n公里，而旅途中有若干個(gè)加油站。試設(shè)計(jì)一個(gè)有效算法，指出應(yīng)在哪些加油站?？考佑?，使加油次數(shù)最少，請寫

4、出該算法。.試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)下列問題：設(shè)A和B是兩個(gè)字符串。我們要用最少的字符操作，將字符串A轉(zhuǎn)換為字符串B,這里所說的字符操作包括：刪除一個(gè)字符。插入一個(gè)字符。將一個(gè)字符改為另一個(gè)字符。請寫出該算法。.對于下圖使用Dijkstra算法求由頂點(diǎn)a到頂點(diǎn)h的最短路徑資料內(nèi)容僅供您學(xué)習(xí)參考，如有不當(dāng)或者侵權(quán)，請聯(lián)系改正或者刪除。.試寫出用分治法對數(shù)組 An實(shí)現(xiàn)快速排序的算法。.有n個(gè)活動(dòng)爭用一個(gè)活動(dòng)室。已知活動(dòng)i占用的時(shí)間區(qū)域?yàn)閟i, fi,活動(dòng)i,j相容的條件是：sj汽f問題的解表示為(xi|xi=1, 2，n,), x i表示順序?yàn)閕的活 動(dòng)編號(hào)活動(dòng)，求一個(gè)相容的活動(dòng)子集，且安排的活動(dòng)數(shù)目

5、最多。.設(shè)XI、X2、X3是一個(gè)三角形的三條邊，而且Xl+X2+X3=14。請問有多少種 不同的三角形？給出解答過程。.設(shè)數(shù)組A有n個(gè)元素，需要找出其中的最大最小值。請給出一個(gè)解決方法，并分析其復(fù)雜性。把n個(gè)元素等分為兩組 A1和A2,分別求這兩組的最大值和最小值，然后分別將這兩組的最大值和最小值相比較，求出全部元素的最大值和最小值。如果A1和A2中的元素多于兩個(gè)，則再用上述方法各分為兩個(gè)子集。直至子集中元素至多兩個(gè)元素為止。這是什么方法的思想？請給出該方法的算法描述，并分析其復(fù)雜性。n.有n個(gè)程序和長度為L的磁帶，程序i的長度為ai,已知 ai L,求最優(yōu)解 i 1(Xi, X2, ., X

6、i,Xn), Xi=0, 1,Xi = 1,表示程序i存入磁帶,Xi=0,表示程序i不n存入磁帶，滿足 Xiai L,且存放的程序數(shù)目最多。 i 1.試用分治法實(shí)現(xiàn)有重復(fù)元素的排列問題：設(shè)R r1,r2,.3)是要進(jìn)行排列的n資料內(nèi)容僅供您學(xué)習(xí)參考，如有不當(dāng)或者侵權(quán)，請聯(lián)系改正或者刪除。個(gè)元素，其中元素1/2,.,%可能相同，試設(shè)計(jì)計(jì)算R的所有不同排列的算 法。.試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn) 0-1閉包問題，請寫出該算法。.試用貪心算法求解下列問題：將正整數(shù)n分解為若干個(gè)互不相同的自然數(shù) 之和，使這些自然數(shù)的乘積最大，請寫出該算法。.試寫出用分治法對一個(gè)有序表實(shí)現(xiàn)二分搜索的算法。.試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)

7、最長公共子序列問題，請寫出該算法。.假設(shè)有7個(gè)物品，它們的重量和價(jià)值如下表所示。若這些物品均不能被分害L且背包容量 M =150,使用回溯方法求解此背包問題，請寫出狀態(tài)空間 搜索樹。物品ABCDEFG35306050401025價(jià)值10403050354030.求解子集和問題：對于集合S=1,2, 6, 8),求子集，要求該子集的元素之和d=9。畫出子集和問題的解空間樹；該樹運(yùn)用回溯算法，寫出依回溯算法遍歷節(jié)點(diǎn)的順序；如果S中有n個(gè)元素，指定d,用偽代碼描述求解子集和問題的回溯算法。.求解填字游戲問題：在3X 3個(gè)方格的方陣中要填入數(shù)字1到N( N 10)內(nèi)的某9個(gè)數(shù)字，每個(gè)方格填一個(gè)整數(shù)，似

8、的所有相鄰兩個(gè)方格內(nèi)的兩個(gè)整數(shù)之和為質(zhì)數(shù)。試采用回溯法寫出滿足這個(gè)要求的一種數(shù)字填法的算法和資料內(nèi)容僅供您學(xué)習(xí)參考，如有不當(dāng)或者侵權(quán)，請聯(lián)系改正或者刪除。滿足這個(gè)要求的全部數(shù)字填法的算法。.試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)最大子矩陣和問題：求m n矩陣A的一個(gè)子矩陣，使其各元素之和為最大。.試用回溯法解決下列整數(shù)變換問題：關(guān)于整數(shù)i的變換f和g定義如下：f (i) 3i;g(i) i/2。對于給定的兩個(gè)整數(shù)n和m,要求用最少的變換f和g變 換次數(shù)將n變?yōu)閙。.關(guān)于15謎問題。在一個(gè) 4X4的方格的棋盤上，將數(shù)字1到15代表的15 個(gè)棋子以任意的順序置入各方格中，空出一格。要求經(jīng)過有限次的移動(dòng)，把一個(gè)給定的初始狀態(tài)變成目標(biāo)狀態(tài)。移動(dòng)的規(guī)則是：每次只能把空格周圍的四格數(shù)字(棋子)中的任意一個(gè)移入空格，從而形成一個(gè)新的狀態(tài)。為 了有效的移動(dòng)，