2014年9月份考試算法設(shè)計分析第三次作業(yè)

1、20142014年9月份考試算法設(shè)計分析第三次作業(yè)月份考試算法設(shè)計分析第三次作業(yè)一、填空題（本大題共一、填空題（本大題共2020分，共分，共5小題，每小題小題，每小題4分）分）1.如果一棵二叉樹的任何結(jié)點或者是樹葉，或者有兩棵非空子樹，則此二叉樹稱作______。2.按照漸近階比較大小n23______4n23.二進(jìn)制大整數(shù)乘法應(yīng)用于十進(jìn)制大整數(shù)的乘法的優(yōu)點是：______4.如果存在兩個正常數(shù)c和n0對于所有的n≥n0有______則

2、稱g(n)是f(n)的一個上界函數(shù)5.O的定義為______二、改錯題（本大題共二、改錯題（本大題共4040分，共分，共4小題，每小題小題，每小題1010分）分）1.與分治法不同的是，適合于用動態(tài)規(guī)劃求解的問題經(jīng)分解得到子問題往往是互相獨立的()2.拉斯維加斯算法的一個顯著特征是它所作的隨機(jī)性決策有可能導(dǎo)致算法找不到所需的解。()3.適宜于用貪心策略來解的大多數(shù)問題都有兩個特點:貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)。()4.貪心算法所做的選擇都是目

3、前最佳的()三、簡答題（本大題共三、簡答題（本大題共2020分，共分，共2小題，每小題小題，每小題1010分）分）1.5輸入兩個正整數(shù)a和b（ab），求它們的最大公約數(shù)。2.描述Dijkstra算法的基本思想。四、問答題（本大題共四、問答題（本大題共2020分，共分，共2小題，每小題小題，每小題1010分）分）1.分治法的適用條件？2.描述分支限界法基本思想。答案：答案：一、填空題（一、填空題（2020分，共分，共5題，每小題題，每小題

4、4分）分）1.參考答案：參考答案：滿二叉樹解題方案：解題方案：知識點記憶評分標(biāo)準(zhǔn)：評分標(biāo)準(zhǔn)：3分2.參考答案：參考答案：3分3.參考答案：參考答案：對解題方案：解題方案：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)。評分標(biāo)準(zhǔn)：評分標(biāo)準(zhǔn)：3分4.參考答案：參考答案：對解題方案：解題方案：貪心選擇目前最佳評分標(biāo)準(zhǔn)：評分標(biāo)準(zhǔn)：3分三、簡答題（三、簡答題（2020分，共分，共2題，每小題題，每小題1010分）分）1.參考答案：參考答案：算法如下：輸入a，b（ab）

5、；②求ab的余數(shù)r；③如果r≠0，則將b→a，r→b，再次求ab的余數(shù)r，轉(zhuǎn)至③；④輸出最大公約數(shù)b。intgcd(intaintb)inttmpif(abtmp=aa=bb=tmpwhile(b1)tmp=a%bif(tmp==0)breaka=bb=tmpreturnb解題方案：解題方案：評分標(biāo)準(zhǔn)：評分標(biāo)準(zhǔn)：152.參考答案：參考答案：按路徑長度遞增次序產(chǎn)生算法：把頂點集合V分成兩組：（1）S：已求出的頂點的集合（初始時只含有源點V