201401批次考試算法設計分析C卷

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

2、意）。（本題分數(shù)：3分。）3. 快速排序法的基本思想是對輸入的子數(shù)組按以下三個步驟進行排序（A、分解，合并，遞歸求解 廠 B、合并，遞歸求解，分解C、遞歸求解，分解，合并D分解，遞歸求解，合并4. 與分治法不同的是，適合于用動態(tài)規(guī)劃求解的問題（）（本題分數(shù)：3分。）A、經(jīng)分解得到子問題往往不是互相獨立的經(jīng)分解得到子問題往往是互相獨立的經(jīng)分解得到子問題往往是互相交叉的經(jīng)分解得到子問題往往是任意的3分。）回溯法分支限界法C、回溯法和分支限界法5. 在對問題的解空間樹進行搜索的方法中，一個活結點最多有一次機會成為活結點的是（）（本題分數(shù):D 回溯法求解子集樹問題本題分數(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)（）（本題分數(shù)：3分。）7. 一般地講，當一個問題的所有子問題都至少要解一次時，用動態(tài)規(guī)劃算法和備忘錄算法相比:A、效果一樣動態(tài)規(guī)劃效果好B、備忘錄方法效果好無法判斷哪個效果好（本題A、子問題的可求解性8. 能夠用動態(tài)規(guī)劃解決的問題還有一個顯著特征（）這個性質并不是動態(tài)規(guī)劃適用的必要條件，但是如果該性質無法滿足，動態(tài)規(guī)劃算法同其他算法相比就不

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

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

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

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

8、ijkstra算法的迭代過程迭代 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六、問答題 （共4題、總分20分）1. 試簡述合并排序算法的基本思想？（本題分數(shù)：5分。）答：合并排序算法是用分治策略實現(xiàn)對n個元素進行排序的算法，其基本思想是（1）將待排序的元素分成大小大致相同的2個子集合；（2）分別對2個子集合進行排序；（3 ）最終將排好序的子集合合并成為所要求的排

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