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

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

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

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

4、4分）分）1.參考答案：參考答案：滿二叉樹(shù)解題方案：解題方案：知識(shí)點(diǎn)記憶評(píng)分標(biāo)準(zhǔn)：評(píng)分標(biāo)準(zhǔn)：3分2.參考答案：參考答案：3分3.參考答案：參考答案：對(duì)解題方案：解題方案：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)。評(píng)分標(biāo)準(zhǔn)：評(píng)分標(biāo)準(zhǔn)：3分4.參考答案：參考答案：對(duì)解題方案：解題方案：貪心選擇目前最佳評(píng)分標(biāo)準(zhǔn)：評(píng)分標(biāo)準(zhǔn)：3分三、簡(jiǎn)答題（三、簡(jiǎn)答題（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解題方案：解題方案：評(píng)分標(biāo)準(zhǔn)：評(píng)分標(biāo)準(zhǔn)：152.參考答案：參考答案：按路徑長(zhǎng)度遞增次序產(chǎn)生算法：把頂點(diǎn)集合V分成兩組：（1）S：已求出的頂點(diǎn)的集合（初始時(shí)只含有源點(diǎn)V