1、 土 :號學(xué) ：名姓 ：級班 程課試考題號一二三四總分得分評閱人算法分析考試試卷（A卷）課程名稱算法分析編號一、填空題（每小題3分，共30分）1、一個算法的優(yōu)劣可以用空間復(fù)雜度與時間復(fù)雜度 來衡量。2、這種不斷回頭尋找目標(biāo)的方法稱為回溯法 。3、直接或間接地調(diào)用自身的算法稱為遞歸算法。4、 記號在算法復(fù)雜性的表示法中表示緊致界 。5、由分治法產(chǎn)生的子問題往往是原問題較小模式，這就為使用 遞歸技術(shù)提供了方便。6、建立計算模型的目的是為了使 問題的計算復(fù)雜性分析有一個共同的客觀尺度。7、下列各步驟的先后順序是。調(diào)試程序分析問題設(shè)計算法編寫程序。8、最優(yōu)子結(jié)構(gòu)性質(zhì)的含義是問題最優(yōu)解包含其子問題最優(yōu)解

2、。9、貪心算法從初始階段開始，每一個階段總是作一個使局部最優(yōu)的貪心選擇。10、拉斯維加斯算法找到的解一定是正確的 。二、選擇題（每小題2分，共20分）1、哈夫曼編碼可利用（C ）算法實現(xiàn)。A、分治策略B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法2、下列不是基本計算模型的是（B ）。A RAM B、ROM C RASP D TM3、下列算法中通常以自頂向下的方式求解最優(yōu)解的是（C）。A分治法B、動態(tài)規(guī)劃法C、貪心法D、回溯法4、在對問題的解空間樹進(jìn)行搜索的方法中，一個活結(jié)點有多次機(jī)會成為活結(jié)點的是（A）A、回溯法B、分支限界法 C、回溯法和分支限界法 D、動態(tài)規(guī)劃5、秦始皇吞并六國使用的遠(yuǎn)交近攻，逐個

3、擊破的連橫策略采用了以下哪種算法思想？BA、遞歸；日分治；G迭代；D模擬。6、FIFO是（A）的一搜索方式。A、分支界限法 B 、動態(tài)規(guī)劃法 C、貪心法 D、回溯法7、投點法是（B ）的一種。A、分支界限算法 B 、概率算法 C、貪心算法 D、回溯算法8、若線性規(guī)劃問題存在最優(yōu)解，它一定不在（C ）A.可行域的某個頂點上B.可行域的某條邊上 C.可行域內(nèi)部D.以上都不對9、在一般輸入數(shù)據(jù)的程序里，輸入多多少少會影響到算法的計算復(fù)雜度，為了消除這種影響可用（B ）對輸入進(jìn)行預(yù)處理。A、蒙特卡羅算法 B、拉斯維加斯算法 C、舍伍德算法 D、數(shù)值概率算法10、若L是一個NP完全問題，L經(jīng)過多項式時間

4、變換后得到問題1,則l是（A ）.A、P類問題B 、NP隹問題C 、NP完全問題D、P類語言三、簡答題（每小題5分，共20分）1、采用高級程序設(shè)計語言表達(dá)算法，主要好處是：高級語言更接近算法語言，易學(xué)、易掌握，一般工程技術(shù)人員只需要幾周時間的培訓(xùn)就可以勝任程 序員的工作；高級語言為程序員提供了結(jié)構(gòu)化程序設(shè)計的環(huán)境和工具，使得設(shè)計出來的程序可讀性好，可維護(hù)性 強(qiáng)，可靠性高；高級語言不依賴于機(jī)器語言，與具體的計算機(jī)硬件關(guān)系不大，因而所寫出來的程序可植性好、重用 率局；把繁雜瑣碎的事務(wù)交給編譯程序，所以自動化程度高，開發(fā)周期短，程序員可以集中時間和精力從 事更重要的創(chuàng)造性勞動，提高程序質(zhì)量。2、由于

5、貪心算法是一種只顧眼前的步驟，而難以顧及全局步驟的算法，所以它通常表現(xiàn)出哪些特點？不能保證最后求得的解是最佳的；即多半是近似解。（少數(shù)問題除外）策略容易發(fā)現(xiàn)（關(guān)鍵：提取清楚問題中的維度），而且運(yùn)用簡單，被廣泛運(yùn)用。策略多樣，結(jié)果也多樣。算法實現(xiàn)過程中，通常用到輔助算法：排序 3、求下列函數(shù)的漸近表達(dá)式：2n 10n-1; 14+5/n+1/r2;/ 22因為:lim (n 210n-1) n 0;由漸近表達(dá)式的定義易知:n n 10n -1n2是n2 10n-1;的漸近表達(dá)式。 因為：limn(14 5/n 1/ n2) 14214 5/n 1/ n20;由漸近表達(dá)式的定義易知：14是14+5

6、/n+1/ r2的漸近表達(dá)式。4、簡述動態(tài)規(guī)劃算法的基本步驟 線封密 :號學(xué) ：名姓 ：級班 程課試考3）填寫最終單純型表并給出最優(yōu)解目標(biāo)函數(shù)的最大值為:最優(yōu)解為：參考答案一、填空1、空間復(fù)雜度 時間復(fù)雜度 2、回溯法3、遞歸算法4、漸進(jìn)確界或緊致界5、原問題的較小模式遞歸技術(shù)6、問題的計算復(fù)雜性分析有一個共同的客觀尺度7、 8、問題的最優(yōu)解包含其子問題的最優(yōu)解9、局部最優(yōu)10、正確的二、選擇區(qū)2345678910CBCABABCBA三、簡答題1、 高級語言更接近算法語言，易學(xué)、易掌握，一般工程技術(shù)人員只需要幾周時間的培訓(xùn)就可以勝任程序員的工作；高級語言為程序員提供了結(jié)構(gòu)化程序設(shè)計的環(huán)境和工具

7、，使得設(shè)計出來的程序可讀性好，可維護(hù)性強(qiáng)，可靠性高；高級語言不依賴于機(jī)器語言，與具體的計算機(jī)硬件關(guān)系不大，因而所寫出來的程序可植性好、重用率高；把繁雜瑣碎的事務(wù)交給編譯程序，所以自動化程度高，開發(fā)周期短，程序員可以集中時間和精力從事更重要的創(chuàng)造性勞動，提高 程序質(zhì)量。2、 不能保證最后求得的解是最佳的；即多半是近似解。（少數(shù)問題除外）策略容易發(fā)現(xiàn)（關(guān)鍵：提取清楚問題中的維度），而且運(yùn)用簡單，被廣泛運(yùn)用。策略多樣，結(jié)果也多樣。算法實現(xiàn)過程中，通常用到輔助算法：排序223、解： 因為：lim （n 2 n- ） n 0;由漸近表達(dá)式的定義易知：n n 10n -122n是n 10n-1;的漸近表達(dá)

8、式。(14 5/n 1/ n2) 14因為：lim ( 一)20;由漸近表達(dá)式的定義易知:n 14 5/n 1/ n214是14+5/n+1/ /的漸近表達(dá)式。4、找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計算出最優(yōu)值。根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。四、算法設(shè)計題0X7f1、按照單位效益從大到小依次排列這7個物品為：FBGDECA。將它們的序號分別記為17。則可生產(chǎn)如下的狀態(tài)空間搜索樹。其 中各個節(jié)點處的限界函數(shù)值通過如下方式求得：【排序1分】Qic150 1157a- 40 40 30 50 35 190.625 (1,1,1,1廣，0,0)408150

9、 1157b. 40 40 30 50 30 177.5 (1,1,1,1,0，一,0)6012c. 40 40 30 50 10 170(1,1,1,1,0,0,1)d. 40 40e. 40 40f. 40 40g. 40h. 4030 35 3050 35 3050 35 1040 50 3040 35 30 10150 10560150 1306015014035167.5175170.71146.853 (1,1,1,0,1, ,0)41 (1,1,0,1七,0)34(1,1,0,1,1,0,7)(1,1,0,1,0,1,0)2(1,1,0,0,1,1,7)5 o。，1,1,1運(yùn)0).150 12560i.40 30 50 35 30 167.5150 145.j. 40 30 50 35 3060157.5(0,1,1,1,1.1,0)在Q1處獲得該問題的最優(yōu)解為（1,1,1,1,0,0,1）,背包效益為170。即在背包中裝入物品F、B、G、D、A時達(dá)到最大效益，為170,重量為150。【結(jié)論2分】2、初始單純型表如下：1） （5分）x2x3x5z0-13-2173-12412-240x610-4382）第一步入基變量x