201401批次考試算法設(shè)計(jì)分析C卷

1、201401批次考試算法設(shè)計(jì)分析 C卷題號(hào)一二四五六合計(jì)已做/題量10 / 103 / 50 / 50 / 20 / 20 / 413 / 28得分/分值0 / 300 / 200 / 100 / 100 / 100 / 200 / 100考試批次：201302批次考試課程：算法設(shè)計(jì)分析一、單項(xiàng)選擇題（共10題、總分30分）1. 計(jì)算機(jī)算法指的是（）。（本題分?jǐn)?shù)：3分。）A、計(jì)算方法廠(chǎng) B、排序方法備C、解決問(wèn)題的方法和過(guò)程廠(chǎng) D 調(diào)度方法2. 多階段決策問(wèn)題，就是要在可以選擇的那些策略中間 ，選取一個(gè)（）策略，使在預(yù)定的標(biāo)準(zhǔn)下達(dá)到最好的效果。（本題分?jǐn)?shù)：3分。）A 最優(yōu)B、最差C、平衡D 任

2、意）。（本題分?jǐn)?shù)：3分。）3. 快速排序法的基本思想是對(duì)輸入的子數(shù)組按以下三個(gè)步驟進(jìn)行排序（A、分解，合并，遞歸求解 廠(chǎng) B、合并，遞歸求解，分解C、遞歸求解，分解，合并D分解，遞歸求解，合并4. 與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題（）（本題分?jǐn)?shù)：3分。）A、經(jīng)分解得到子問(wèn)題往往不是互相獨(dú)立的經(jīng)分解得到子問(wèn)題往往是互相獨(dú)立的經(jīng)分解得到子問(wèn)題往往是互相交叉的經(jīng)分解得到子問(wèn)題往往是任意的3分。）回溯法分支限界法C、回溯法和分支限界法5. 在對(duì)問(wèn)題的解空間樹(shù)進(jìn)行搜索的方法中，一個(gè)活結(jié)點(diǎn)最多有一次機(jī)會(huì)成為活結(jié)點(diǎn)的是（）（本題分?jǐn)?shù):D 回溯法求解子集樹(shù)問(wèn)題本題分?jǐn)?shù)：3分。）6. 階乘函數(shù)用遞歸

3、定義Public static int factorial(int n) if(n=O) return 1;return () ;(n*factorial(n)n*factorial(n-1)n*factorial(n-2)n*factorial(n+1)（）（本題分?jǐn)?shù)：3分。）7. 一般地講，當(dāng)一個(gè)問(wèn)題的所有子問(wèn)題都至少要解一次時(shí)，用動(dòng)態(tài)規(guī)劃算法和備忘錄算法相比:A、效果一樣動(dòng)態(tài)規(guī)劃效果好B、備忘錄方法效果好無(wú)法判斷哪個(gè)效果好（本題A、子問(wèn)題的可求解性8. 能夠用動(dòng)態(tài)規(guī)劃解決的問(wèn)題還有一個(gè)顯著特征（）這個(gè)性質(zhì)并不是動(dòng)態(tài)規(guī)劃適用的必要條件，但是如果該性質(zhì)無(wú)法滿(mǎn)足，動(dòng)態(tài)規(guī)劃算法同其他算法相比就不

4、具備優(yōu)勢(shì)。分?jǐn)?shù)：3分。）B、子問(wèn)題的獨(dú)立性C、子問(wèn)題的可合并性子問(wèn)題的重疊性9. 在任何一個(gè)2k X 2k的棋盤(pán)覆蓋中，用到的 L型骨牌個(gè)數(shù)恰為（）。（本題分?jǐn)?shù)：3分。）kA (4 -1)/3(4 k-1)/2c、(2 k-1)/3(2 k-1)/210.動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度為（）（本題分?jǐn)?shù)：3分。）O(n)0(n!)O(n2)3D O(n )Top（）。（本題分?jǐn)?shù)：4分。）二、判斷題 （共5題、總分20分）1. 對(duì)于難于找到從邊界到解的全過(guò)程的情況，如果把問(wèn)題推進(jìn)一步，其結(jié)果仍維持原問(wèn)題的關(guān)系，則采用遞歸算法編程比較合適A、正確B、錯(cuò)誤2. 要想在電腦上擴(kuò)大所處理問(wèn)題的規(guī)模，有效的途徑是降低

5、算法的計(jì)算復(fù)雜度（）（本題分?jǐn)?shù)：4分。）A、正確B、錯(cuò)誤3. 快速排序算法是基于貪心策略的一個(gè)算法（）。（本題分?jǐn)?shù)：4分。）A、正確.B、錯(cuò)誤4. 分治與遞歸經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。（）（ 本題分?jǐn)?shù)：4分。）A、正確B、錯(cuò)誤5. 問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即稱(chēng)該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)（）（ 本題分?jǐn)?shù)：4分。） A、正確B、錯(cuò)誤三、填空題（共5題、總分10分）1. 回溯法使用 1方法搜索樹(shù)結(jié)構(gòu)，而分支限界法一般用2 方法來(lái)搜索這些樹(shù)。（本題分?jǐn)?shù)：2分。）答：深度優(yōu)先廣度優(yōu)先2. 對(duì)每一個(gè)字符規(guī)定一個(gè) 0, 1串作為其代碼，并要求任一字符的代碼都不是其他字

6、符代碼的前綴，這種編碼稱(chēng)為1（本題分?jǐn)?shù)：2分。）答：前綴碼3. 下面程序段的時(shí)間復(fù)雜度是：1 for （i=0; in; i+） for （j=0; jm; j+） Aij=0;（本題分?jǐn)?shù)：2分。）答：4. 數(shù)據(jù)的基本單位稱(chēng)為1（本題分?jǐn)?shù)：2分。）答：數(shù)據(jù)元素5. 上界函數(shù) bound計(jì)算結(jié)點(diǎn)所相應(yīng)價(jià)值的上界。private static double bound （int i） /計(jì)算結(jié)點(diǎn)所相應(yīng)價(jià)值的上界double cleft = c-cw;/剩余容量double b = cp;/價(jià)值上界/以物品單位重量?jī)r(jià)值遞減序裝填剩余容量while （i=n & wiv=cleft）cleft -=

7、wi; b += pi;i+; /裝填剩余容量裝滿(mǎn)背包if （i=n）1;return b; （本題分?jǐn)?shù)：2分。）答：b += pi/wi*cleft四、改錯(cuò)題（共2題、總分10分）1. 在一個(gè)貪心算法中，我們所做的總是當(dāng)前最佳的選擇（）。（本題分?jǐn)?shù)：5分。）答：對(duì)2. 拉斯維加斯算法可以得到求解問(wèn)題的正確解，但可能找不到解（）（本題分?jǐn)?shù)：5分。）答：對(duì)Top五、簡(jiǎn)答題 （共2題、總分10分）1. 設(shè)有兩個(gè)算法在同一機(jī)器上運(yùn)行，其執(zhí)行時(shí)間分別為100n2和2n,要使前者快于后者，n至少要多大？（本題分?jǐn)?shù)：5分。）答：n=152. 描述Dijkstra 算法的基本思想。（本題分?jǐn)?shù)：5分。）答：D

8、ijkstra算法的迭代過(guò)程迭代 S u dist1 dist2 dist3 dist4 初始0 - 10 30 100 1 0，1 1 10 60 30 100 2 0，1，3 3 10 50 30 90 3 0，1，3，2 2 10 50 30 60 4 0，1，3, 2，4 4 10Top50 30 60六、問(wèn)答題 （共4題、總分20分）1. 試簡(jiǎn)述合并排序算法的基本思想？（本題分?jǐn)?shù)：5分。）答：合并排序算法是用分治策略實(shí)現(xiàn)對(duì)n個(gè)元素進(jìn)行排序的算法，其基本思想是（1）將待排序的元素分成大小大致相同的2個(gè)子集合；（2）分別對(duì)2個(gè)子集合進(jìn)行排序；（3 ）最終將排好序的子集合合并成為所要求的排

9、好序的集合。2. 用貪心算法思想求解如下連續(xù)背包問(wèn)題：給定一個(gè)承載量為 20的背包和3個(gè)物品，3個(gè)物品重量分別為 w1=18, w2=15, w3=10其價(jià)值分別為v1=25，v2=24，v3=15。每件物品可取數(shù)量為 xi （0xi 1），求背包裝滿(mǎn) 情況下物品的最大價(jià)值。（本題分?jǐn)?shù)：5分。）解：3種物品單價(jià)分別為：25/18、24/15、 15/10即第二種物品單價(jià)最高，且w2=15 V20,應(yīng)先取它完全放入背包，可取數(shù)量為x2=1;單價(jià)次高的為第三種物品，由于背包余下載重為：20- w2=20 15=5，可取第三種物品數(shù)量為 x3=5/10=0.5 ;此時(shí)背包已經(jīng)裝滿(mǎn)，因此第一種物品可取數(shù)量為x仁0。得到最優(yōu)解：(xl, x2, x3) = ( 0, 1, 0.5);此時(shí)，背包內(nèi)物品總價(jià)值最大，為 wmax = 0X 25+1X 24+0.5 X 15=31.53. 簡(jiǎn)述分支限界法在問(wèn)題的解空間樹(shù)搜索策略？ ( 本題分?jǐn)?shù)： 5 分。 )答： 分支限界法采用寬度優(yōu)先的方式搜索解空間樹(shù)，它將活結(jié)點(diǎn)存放在一個(gè)特殊的表中。其策略是：在擴(kuò)展結(jié)點(diǎn)處，先生成其所有的兒子結(jié)點(diǎn),將那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子舍棄，其余兒子加入活結(jié)點(diǎn)表中。此后，從活結(jié)點(diǎn)表中按照一定的規(guī)則取出一個(gè)結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。并