算法分析與設(shè)計部分含計算的復(fù)習題及參考答案

1、二、簡答題：二、簡答題：1.備忘錄方法和動態(tài)規(guī)劃算法相比有何異同？簡述之。2.簡述回溯法解題的主要步驟。3.簡述動態(tài)規(guī)劃算法求解的基本要素。4.簡述回溯法的基本思想。5.簡要分析在遞歸算法中消除遞歸調(diào)用，將遞歸算法轉(zhuǎn)化為非遞歸算法的方法。6.簡要分析分支限界法與回溯法的異同。7.簡述算法復(fù)雜性的概念，算法復(fù)雜性度量主要指哪兩個方面？8.貪心算法求解的問題主要具有哪些性質(zhì)？簡述之。9.分治法的基本思想是什么？合并排序的基本思想是什么？請分

2、別簡述之。10.簡述分析貪心算法與動態(tài)規(guī)劃算法的異同。三、算法編寫及算法應(yīng)用分析題：三、算法編寫及算法應(yīng)用分析題：1.已知有3個物品：(w1w2w3)=(12106)(p1p2p3)=(151310)背包的容積M=20，根據(jù)01背包動態(tài)規(guī)劃的遞推式求出最優(yōu)解。2.按要求完成以下關(guān)于排序和查找的問題。①對數(shù)組A=15，29，135，18，32，1，27，25，5，用快速排序方法將其排成遞減序。②請描述遞減數(shù)組進行二分搜索的基本思想，并給出

3、非遞歸算法。③給出上述算法的遞歸算法。④使用上述算法對①所得到的結(jié)果搜索如下元素，并給出搜索過程：18，31，135。3.已知，1()()iikkijrrAa??k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩陣鏈積A1A2A3A4A5A6的最佳求積順序（要求給出計算步驟）。4.根據(jù)分枝限界算法基本過程求解01背包問題。已知n=3M=20，(w1w2w3)=(12106)(p1

4、p2p3)=(151310)。5.試用貪心算法求解汽車加油問題：已知一輛汽車加滿油后可行駛n公里，而旅途中有若干個加油站。試設(shè)計一個有效算法，指出應(yīng)在哪些加油站停靠加油，使加油次數(shù)最少，請寫出該算法。6.試用動態(tài)規(guī)劃算法實現(xiàn)下列問題：設(shè)A和B是兩個字符串。我們要用最少的字符操作，將字符串A轉(zhuǎn)換為字符串B，這里所說的字符操作包括：①刪除一個字符。②插入一個字符。③將一個字符改為另一個字符。請寫出該算法。7.對于下圖使用Dijkstra算法

5、求由頂點a到頂點h的最短路徑。ahgfedcb121228232238.試寫出用分治法對數(shù)組A[n]實現(xiàn)快速排序的算法。9.有n個活動爭用一個活動室。已知活動i占用的時間區(qū)域為[si，fi]，活動ij相容的條件是：sj≥fi，問題的解表示為(xi|xi=1，2…，n)，xi表示順序為i的活動編號活動，求一個相容的活動子集，且安排的活動數(shù)目最多。10.設(shè)x1、x2、x3是一個三角形的三條邊，而且x1x2x3=14。請問有多少種不同的三角形