算法設(shè)計與分析(試題A卷)

《算法設(shè)計與分析》課程試卷(A)答卷說明：1、考試方式閉卷2、滿分100分題號一二三四五六七總分總分人分?jǐn)?shù)得分評卷人一、單項選擇題（每小題3分，共30分）1、動態(tài)規(guī)劃算法的基本要素為（）。A、最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)B、重疊子問題性質(zhì)與貪心選擇性質(zhì)C、最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)D.、預(yù)排序與遞歸調(diào)用2、算法分析中，記號O表示（），記號表示（），記號表示（）。A、漸進(jìn)下界B、漸進(jìn)上界C、非緊上界D、緊漸進(jìn)界E、非緊下界3、以下關(guān)于漸進(jìn)記號的性質(zhì)是正確的有：（）A、B、C、O(f(n))+O(g(n))=O(min{f(n),g(n)})D、4、下列算法中通常以自底向上的方式求解最優(yōu)解的是（

）。A、備忘錄法B、動態(tài)規(guī)劃法C、貪心法D、回溯法5、衡量一個算法好壞的標(biāo)準(zhǔn)是（）。

A、運行速度快B、占用空間少C、時間復(fù)雜度低D、代碼段6、實現(xiàn)棋盤覆蓋算法利用的算法是（

）。A、分治法 B、動態(tài)規(guī)劃法C、貪心法D、回溯法7、下面關(guān)于NP問題說法正確的是（）。

A、NP問題都是不可能解決的問題

B、P類問題包含在NP類問題中

C、NP完全問題是P類問題的子集

D、NP類問題包含在P類問題中8、矩陣連乘問題的算法可由（

）設(shè)計實現(xiàn)。A、分支界限算法

B、動態(tài)規(guī)劃算法

C、貪心算法

9、（

）是貪心算法與動態(tài)規(guī)劃算法的共同點。A、重疊子問題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì) D、最優(yōu)子結(jié)構(gòu)性質(zhì)10、Hanoi塔問題如下圖所示?，F(xiàn)要求將塔座A上的的所有圓盤移到塔座B上，并仍按同樣順序疊置。移動圓盤時遵守Hanoi塔問題的移動規(guī)則。由此設(shè)計出解Hanoi塔問題的遞歸算法正確的為：（）A.A.voidhanoi(intn,intA,intC,intB){if(n>0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}B.B.voidhanoi(intn,intA,intB,intC){if(n>0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}C.C.voidhanoi(intn,intC,intB,intA){if(n>0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}D.D.voidhanoi(intn,intC,intA,intB){if(n>0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}得分評卷人二、填空題（每空2分，共18分）1、下面程序段的所需要的計算時間為。IntMaxSum(intn,int*a,int&besti,int&bestj){ intsum=0; for(inti=1;i<=n;i++){ intthissum=0; for(intj=i;j<=n;j++){ Thissum+=a[j]; if(thissum>sum) { sum=thissum; besti=i; bestj=j; } } } returnsum;}2、算法的復(fù)雜性有復(fù)雜性和復(fù)雜性之分。3、程序是

用某種程序設(shè)計語言的具體實現(xiàn)。4、算法是指解決問題的或。5、從分治法的一般設(shè)計模式可以看出，用它設(shè)計出的程序一般是。6、計算一個算法時間復(fù)雜度通?？梢杂嬎?、或計算步。得分評卷人三、證明題（每小題10分，共20分）1、舉反例證明0/1背包問題若使用的算法是按照pi/wi的非遞減次序考慮選擇的物品，即只要正在被考慮的物品裝得進(jìn)就裝入背包，則此方法不一定能得到最優(yōu)解（此題說明0/1背包問題與背包問題的不同）。2、求證：O(f(n))+O(g(n))=O(max{f(n),g(n)})得分評卷人四、算法設(shè)計題（1小題10分、2小題12分、3小題10分，共32分）1、老板有一袋金塊（共n塊，n是2的冪（n>=2）），最優(yōu)秀的雇員得到其中最重的一塊，最差的雇員得到其中最輕的一塊。假設(shè)有一臺比較重量的儀器，希望用最少的比較次數(shù)找出最重的金塊。（要求：用二分法解決問題。）部分背包問題：一個商人帶著一個能裝M千克的背包去鄉(xiāng)下收購貨物，準(zhǔn)備將這些貨物賣到城里獲利。現(xiàn)在已知有多種貨源，知道每一種貨物的重量