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

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

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

3、非遞歸算法。③給出上述算法的遞歸算法。④使用上述算法對(duì)①所得到的結(jié)果搜索如下元素，并給出搜索過(guò)程：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的最佳求積順序（要求給出計(jì)算步驟）。4.根據(jù)分枝限界算法基本過(guò)程求解01背包問(wèn)題。已知n=3M=20，(w1w2w3)=(12106)(p1

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

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