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

1、網(wǎng)絡(luò)教育課程考試復(fù)習(xí)題及參考答案網(wǎng)絡(luò)教育課程考試復(fù)習(xí)題及參考答案算法分析與設(shè)計(jì)算法分析與設(shè)計(jì)一、名詞解釋：一、名詞解釋：1.算法2.程序3.遞歸函數(shù)4.子問(wèn)題的重疊性質(zhì)5.隊(duì)列式分支限界法6.多機(jī)調(diào)度問(wèn)題7.最小生成樹二、簡(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)化為非

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

3、據(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)行二分搜索的基本思想，并給出非遞歸算法。③給出上述算法的遞歸算法。④使用上述算法對(duì)①所得到的結(jié)果搜索如下元素，并給出搜索過(guò)程：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的最佳求積順序（要求給出計(jì)算步驟）。4.根據(jù)分枝限界算法基本過(guò)程求解01背包問(wèn)題。已知n=3M=20，(w1w2w3)=(12106)(p1p2p3)=(151310)。5.試用貪心算法求解汽車加油問(wèn)題：已知一輛汽車加滿油后可行駛n公里，而旅途中有若干個(gè)加油站。試設(shè)計(jì)一個(gè)有效算法，指出應(yīng)在哪些加油站?？考佑?，使加油次數(shù)最少，請(qǐng)寫出該算法。6.試用動(dòng)態(tài)規(guī)劃算法實(shí)

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