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

1、網(wǎng)絡(luò)教育課程考試復(fù)習(xí)題及參考答案網(wǎng)絡(luò)教育課程考試復(fù)習(xí)題及參考答案算法分析與設(shè)計算法分析與設(shè)計一、名詞解釋：一、名詞解釋：1.算法2.程序3.遞歸函數(shù)4.子問題的重疊性質(zhì)5.隊列式分支限界法6.多機調(diào)度問題7.最小生成樹二、簡答題：二、簡答題：1.備忘錄方法和動態(tài)規(guī)劃算法相比有何異同？簡述之。2.簡述回溯法解題的主要步驟。3.簡述動態(tài)規(guī)劃算法求解的基本要素。4.簡述回溯法的基本思想。5.簡要分析在遞歸算法中消除遞歸調(diào)用，將遞歸算法轉(zhuǎn)化為非

2、遞歸算法的方法。6.簡要分析分支限界法與回溯法的異同。7.簡述算法復(fù)雜性的概念，算法復(fù)雜性度量主要指哪兩個方面？8.貪心算法求解的問題主要具有哪些性質(zhì)？簡述之。9.分治法的基本思想是什么？合并排序的基本思想是什么？請分別簡述之。10.簡述分析貪心算法與動態(tài)規(guī)劃算法的異同。三、算法編寫及算法應(yīng)用分析題：三、算法編寫及算法應(yīng)用分析題：1.已知有3個物品：(w1w2w3)=(12106)(p1p2p3)=(151310)背包的容積M=20，根

3、據(jù)01背包動態(tài)規(guī)劃的遞推式求出最優(yōu)解。2.按要求完成以下關(guān)于排序和查找的問題。①對數(shù)組A=15，29，135，18，32，1，27，25，5，用快速排序方法將其排成遞減序。②請描述遞減數(shù)組進(jìn)行二分搜索的基本思想，并給出非遞歸算法。③給出上述算法的遞歸算法。④使用上述算法對①所得到的結(jié)果搜索如下元素，并給出搜索過程：18，31，135。3.已知，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，

4、1()()iikkijrrAa??r7=6，求矩陣鏈積A1A2A3A4A5A6的最佳求積順序（要求給出計算步驟）。4.根據(jù)分枝限界算法基本過程求解01背包問題。已知n=3M=20，(w1w2w3)=(12106)(p1p2p3)=(151310)。5.試用貪心算法求解汽車加油問題：已知一輛汽車加滿油后可行駛n公里，而旅途中有若干個加油站。試設(shè)計一個有效算法，指出應(yīng)在哪些加油站?？考佑?，使加油次數(shù)最少，請寫出該算法。6.試用動態(tài)規(guī)劃算法實

5、現(xiàn)下列問題：設(shè)A和B是兩個字符串。我們要用最少的字符操作，將字符串A轉(zhuǎn)換為字符串B，這里所說的字符操作包括：①刪除一個字符。②插入一個字符。③將一個字符改為另一個字符。請寫出該算法。7.對于下圖使用Dijkstra算法求由頂點a到頂點h的最短路徑。ahgfedcb12122823223每次只能把空格周圍的四格數(shù)字（棋子）中的任意一個移入空格，從而形成一個新的狀態(tài)。為了有效的移動，設(shè)計了估值函數(shù)C1(x)，表示在結(jié)點x的狀態(tài)下，沒有到達(dá)目