算法設計與分析試卷A及答案

1、算法分析考試試卷（A卷）課程名稱 算法分析 編號 題號一二三四總分得分評閱人一、填空題（每小題3分，共30分）1、一個算法的優(yōu)劣可以用 空間復雜度 與 時間復雜度 來衡量。2、這種不斷回頭尋找目標的方法稱為 回溯法 。3、直接或間接地調(diào)用自身的算法稱為 遞歸算法 。4、q 記號在算法復雜性的表示法中表示 緊致界 。5、由分治法產(chǎn)生的子問題往往是 原問題較小模式 ，這就為使用 遞歸技術 提供了方便。6、建立計算模型的目的是為了使 問題的計算復雜性分析有一個共同的客觀尺度 。7、下列各步驟的先后順序是 。調(diào)試程序 分析問題 設計算法 編寫程序。8、最優(yō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、在對問題的解空間樹進行搜索的方法中,一個活結點有多次機會成為

3、活結點的是( A )A、回溯法 B、分支限界法 C、回溯法和分支限界法 D、動態(tài)規(guī)劃5、秦始皇吞并六國使用的遠交近攻，逐個擊破的連橫策略采用了以下哪種算法思想？ BA、 遞歸；B、分治；C、迭代；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ù)的程序里，輸入多多少少會影響到算法的計算復雜度，為了消除這種影響可用（ B ）

4、對輸入進行預處理。A、蒙特卡羅算法 B、拉斯維加斯算法 C、舍伍德算法 D、數(shù)值概率算法10、若L是一個NP完全問題，L經(jīng)過多項式時間變換后得到問題l，則l是( A ).A、P類問題 B、NP難問題 C、NP完全問題 D、P類語言三、簡答題（每小題5分，共20分）1、采用高級程序設計語言表達算法，主要好處是：高級語言更接近算法語言，易學、易掌握，一般工程技術人員只需要幾周時間的培訓就可以勝任程序員的工作；高級語言為程序員提供了結構化程序設計的環(huán)境和工具，使得設計出來的程序可讀性好，可維護性強，可靠性高；高級語言不依賴于機器語言，與具體的計算機硬件關系不大，因而所寫出來的程序可植性好、重用率高；

5、把繁雜瑣碎的事務交給編譯程序，所以自動化程度高，開發(fā)周期短，程序員可以集中時間和精力從事更重要的創(chuàng)造性勞動，提高程序質(zhì)量。2、由于貪心算法是一種只顧眼前的步驟，而難以顧及全局步驟的算法，所以它通常表現(xiàn)出哪些特點？不能保證最后求得的解是最佳的；即多半是近似解。（少數(shù)問題除外）策略容易發(fā)現(xiàn)（關鍵：提取清楚問題中的維度）， 而且運用簡單，被廣泛運用。 策略多樣，結果也多樣。 算法實現(xiàn)過程中，通常用到輔助算法：排序3、求下列函數(shù)的漸近表達式： ; 14+5/n+1/n2; 因為：由漸近表達式的定義易知： ;的漸近表達式。 因為：由漸近表達式的定義易知： 14是14+5/n+1/ n2的漸近表達式。4、

6、簡述動態(tài)規(guī)劃算法的基本步驟 考試課程： 班級： 姓名： 學號： - 密 - 封 - 線 - - 密 - 封 - 線 -四、算法設計題（每小題15分，共30分）1、假設有7個物品，它們的重量和價值如下表所示。若這些物品均不能被分割，且背包容量M150，使用回溯方法求解此背包問題。請寫出狀態(tài)空間搜索樹并計算各個節(jié)點處的限界函數(shù)值，最后給出裝載方案及背包中物品的重量和價值。物品ABCDEFG重量35306050401025價值104030503540302、用單純形法解下列線性規(guī)劃問題1） 填寫初始單純型表2）寫出每一步的入基變量和離基變量3）填寫最終單純型表并給出最優(yōu)解目標函數(shù)的最大值為：最優(yōu)解為

7、：參考答案一、填空1、空間復雜度 時間復雜度 2、回溯法 3、遞歸算法 4、漸進確界或緊致界 5、原問題的較小模式 遞歸技術6、問題的計算復雜性分析有一個共同的客觀尺度 7、 8、問題的最優(yōu)解包含其子問題的最優(yōu)解 9、局部最優(yōu) 10、正確的二、選擇12345678910CBCABABCBA三、簡答題1、n高級語言更接近算法語言，易學、易掌握，一般工程技術人員只需要幾周時間的培訓就可以勝任程序員的工作；高級語言為程序員提供了結構化程序設計的環(huán)境和工具，使得設計出來的程序可讀性好，可維護性強，可靠性高；高級語言不依賴于機器語言，與具體的計算機硬件關系不大，因而所寫出來的程序可植性好、重用率高；把繁

8、雜瑣碎的事務交給編譯程序，所以自動化程度高，開發(fā)周期短，程序員可以集中時間和精力從事更重要的創(chuàng)造性勞動，提高程序質(zhì)量。2、 不能保證最后求得的解是最佳的；即多半是近似解。（少數(shù)問題除外）策略容易發(fā)現(xiàn)（關鍵：提取清楚問題中的維度）， 而且運用簡單，被廣泛運用。 策略多樣，結果也多樣。 算法實現(xiàn)過程中，通常用到輔助算法：排序3、解： 因為：由漸近表達式的定義易知： ;的漸近表達式。 因為：由漸近表達式的定義易知： 14是14+5/n+1/ n2的漸近表達式。 4、 找出最優(yōu)解的性質(zhì)，并刻劃其結構特征。遞歸地定義最優(yōu)值。以自底向上的方式計算出最優(yōu)值。根據(jù)計算最優(yōu)值時得到的信息，構造最優(yōu)解。四、算法設計題 1、按照單位效益從大到小依次排列這7個物品為：FBGDECA。將它們的序號分別記為17。則可生產(chǎn)如下的狀態(tài)空間搜索樹。其中各個節(jié)點處的限界函數(shù)值通過如下方式求得：【排序1分】a b. c d. e. f. g. h. i.j. 在Q1處獲得該問題的最優(yōu)解為，背包效益為170。即在背包中裝入物品F、B、G、D、A時達到最大效益，為170，重量為150。【結論2分】2、初始單純型表如下：1）（5分）  x2x3x5z0-13-2x173-12x412-240x610-4382）第一步入基變量x3、離基變量x4第二步入基變量x2、離基變量x1 3