《算法設(shè)計(jì)與分析》考試題目及答案

1、《算法分析與設(shè)計(jì)》期末復(fù)習(xí)題《算法分析與設(shè)計(jì)》期末復(fù)習(xí)題一、選擇題1.應(yīng)用Johnson法則的流水作業(yè)調(diào)度采用的算法是（D）A.貪心算法B.分支限界法C.分治法D.動(dòng)態(tài)規(guī)劃算法2.Hanoi塔問題如下圖所示?，F(xiàn)要求將塔座A上的的所有圓盤移到塔座B上，并仍按同樣順序疊置。移動(dòng)圓盤時(shí)遵守Hanoi塔問題的移動(dòng)規(guī)則。由此設(shè)計(jì)出解Hanoi塔問題的遞歸算法正確的為：（B）Hanoi塔A.voidhanoi(intnintAintCintB)if

2、(n0)hanoi(n1ACB)move(nab)hanoi(n1CBA)B.voidhanoi(intnintAintBintC)if(n0)hanoi(n1ACB)move(nab)hanoi(n1CBA)C.voidhanoi(intnintCintBintA)if(n0)hanoi(n1ACB)move(nab)hanoi(n1CBA)C最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)D.預(yù)排序與遞歸調(diào)用7.回溯法在問題的解空間樹中，按（D）策略

3、，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。A廣度優(yōu)先B.活結(jié)點(diǎn)優(yōu)先C.擴(kuò)展結(jié)點(diǎn)優(yōu)先D.深度優(yōu)先8.分支限界法在問題的解空間樹中，按（A）策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。A廣度優(yōu)先B.活結(jié)點(diǎn)優(yōu)先C.擴(kuò)展結(jié)點(diǎn)優(yōu)先D.深度優(yōu)先9.程序塊（A）是回溯法中遍歷排列樹的算法框架程序。A.B.C.voidbacktrackbacktrack(intt)if(tn)output(x)elsef(inti=tin)output(x)elsef(inti=0in)out