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

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

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

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

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

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

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

8、式。(14 5/n 1/ n2) 14因為：lim ( 一)20;由漸近表達式的定義易知:n 14 5/n 1/ n214是14+5/n+1/ /的漸近表達式。4、找出最優解的性質，并刻劃其結構特征。遞歸地定義最優值。以自底向上的方式計算出最優值。根據計算最優值時得到的信息，構造最優解。四、算法設計題0X7f1、按照單位效益從大到小依次排列這7個物品為：FBGDECA。將它們的序號分別記為17。則可生產如下的狀態空間搜索樹。其 中各個節點處的限界函數值通過如下方式求得：【排序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運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處獲得該問題的最優解為（1,1,1,1,0,0,1）,背包效益為170。即在背包中裝入物品F、B、G、D、A時達到最大效益，為170,重量為150。【結論2分】2、初始單純型表如下：1） （5分）x2x3x5z0-13-2173-12412-240x610-4382）第一步入基變量x