湖南工程學(xué)院 計算機(jī)算法設(shè)計與分析 期末考試復(fù)習(xí)題

1、二分搜索算法是利用（

A

）實現(xiàn)的算法。A、分治策略

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

C、貪心法

D、回溯法2、下列不是動態(tài)規(guī)劃算法基本步驟的是（

A

）。A、找出最優(yōu)解的性質(zhì)

B、構(gòu)造最優(yōu)解

C、算出最優(yōu)解

D、定義最優(yōu)解3、最大效益優(yōu)先是（

A

）的一搜索方式。A、分支界限法

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

C、貪心法

D、回溯法4、在下列算法中有時找不到問題解的是（

B

）。A、蒙特卡羅算法

B、拉斯維加斯算法

C、舍伍德算法

D、數(shù)值概率算法5.回溯法解旅行售貨員問題時的解空間樹是（

A

）。A、子集樹 B、排列樹 C、深度優(yōu)先生成樹 D、廣度優(yōu)先生成樹6．下列算法中通常以自底向上的方式求解最優(yōu)解的是（

B

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

A運(yùn)行速度快B占用空間少C時間復(fù)雜度低D代碼短

8、以下不可以使用分治法求解的是（D）。

A棋盤覆蓋問題B選擇問題C歸并排序D0/1背包問題

9.實現(xiàn)循環(huán)賽日程表利用的算法是（

A

）。A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法10、下列隨機(jī)算法中運(yùn)行時有時候成功有時候失敗的是（C）

A數(shù)值概率算法B舍伍德算法C拉斯維加斯算法D蒙特卡羅算法11．下面不是分支界限法搜索方式的是（

D

）。A、廣度優(yōu)先B、最小耗費優(yōu)先C、最大效益優(yōu)先D、深度優(yōu)先12．下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是（

D

）。A、備忘錄法B、動態(tài)規(guī)劃法C、貪心法D、回溯法13.備忘錄方法是那種算法的變形。（B）A、分治法 B、動態(tài)規(guī)劃法C、貪心法D、回溯法14．哈弗曼編碼的貪心算法所需的計算時間為（

B

）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）15．分支限界法解最大團(tuán)問題時，活結(jié)點表的組織形式是（

B

）。A、最小堆 B、最大堆 C、棧 D、數(shù)組16．最長公共子序列算法利用的算法是（

B

）。A、分支界限法B、動態(tài)規(guī)劃法C、貪心法D、回溯法17．實現(xiàn)棋盤覆蓋算法利用的算法是（

A

）。A、分治法 B、動態(tài)規(guī)劃法C、貪心法D、回溯法18.下面是貪心算法的基本要素的是（

C

）。A、重疊子問題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì) D、定義最優(yōu)解19.回溯法的效率不依賴于下列哪些因素（D）A.滿足顯約束的值的個數(shù) B.計算約束函數(shù)的時間C.計算限界函數(shù)的時間 D.確定解空間的時間20.下面哪種函數(shù)是回溯法中為避免無效搜索采取的策略（

B

）A．遞歸函數(shù) B.剪枝函數(shù) C。隨機(jī)數(shù)函數(shù) D.搜索函數(shù)21、下面關(guān)于NP問題說法正確的是（B）

ANP問題都是不可能解決的問題BP類問題包含在NP類問題中

CNP完全問題是P類問題的子集DNP類問題包含在P類問題中22、蒙特卡羅算法是（

B

）的一種。A、分支界限算法

B、概率算法

C、貪心算法

D、回溯算法23.下列哪一種算法不是隨機(jī)化算法（

C

）A.蒙特卡羅算法B.拉斯維加斯算法C.動態(tài)規(guī)劃算法D.舍伍德算法24.（

D

）是貪心算法與動態(tài)規(guī)劃算法的共同點。A、重疊子問題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì) D、最優(yōu)子結(jié)構(gòu)性質(zhì)25.矩陣連乘問題的算法可由（

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

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

C、貪心算法

D、回溯算法26.分支限界法解旅行售貨員問題時，活結(jié)點表的組織形式是（

A

）。A、最小堆 B、最大堆 C、棧 D、數(shù)組27、Strassen矩陣乘法是利用（

A

）實現(xiàn)的算法。A、分治策略

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

C、貪心法

D、回溯法29、使用分治法求解不需要滿足的條件是（A）。

A子問題必須是一樣的B子問題不能夠重復(fù)C子問題的解可以合并D原問題和子問題使用相同的方法解

30、下面問題（B）不能使用貪心法解決。

A單源最短路徑問題BN皇后問題C最小花費生成樹問題D背包問題

31、下列算法中不能解決0/1背包問題的是（A）

A貪心法B動態(tài)規(guī)劃C回溯法D分支限界法

32、回溯法搜索狀態(tài)空間樹是按照（C）的順序。

A中序遍歷B廣度優(yōu)先遍歷C深度優(yōu)先遍歷D層次優(yōu)先遍歷33、下列隨機(jī)算法中運(yùn)行時有時候成功有時候失敗的是（C）

A數(shù)值概率算法B舍伍德算法C拉斯維加斯算法D蒙特卡羅算法

34．實現(xiàn)合并排序利用的算法是（

A

）。A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法35．下列是動態(tài)規(guī)劃算法基本要素的是（

D

）。A、定義最優(yōu)解B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、子問題重疊性質(zhì)36．下列算法中通常以自底向下的方式求解最優(yōu)解的是（

B

）。A、分治法B、動態(tài)規(guī)劃法C、貪心法D、回溯法37．采用廣度優(yōu)先策略搜索的算法是（

A

）。A、分支界限法B、動態(tài)規(guī)劃法C、貪心法D、回溯法38、合并排序算法是利用（

A

）實現(xiàn)的算法。A、分治策略

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

C、貪心法

D、回溯法39、在下列算法中得到的解未必正確的是（

B

）。A、蒙特卡羅算法

B、拉斯維加斯算法

C、舍伍德算法

D、數(shù)值概率算法40、背包問題的貪心算法所需的計算時間為（

B

）A、O（n2n）

B、O（nlogn）

C、O（2n）

D、O（n）41．實現(xiàn)大整數(shù)的乘法是利用的算法（

C

）。A、貪心法B、動態(tài)規(guī)劃法C、分治策略D、回溯法42．0-1背包問題的回溯算法所需的計算時間為（

A

）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）43．采用最大效益優(yōu)先搜索方式的算法是（

A

）。A、分支界限法B、動態(tài)規(guī)劃法C、貪心法D、回溯法44．貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別是（

B

）。A、最優(yōu)子結(jié)構(gòu)B、貪心選擇性質(zhì) C、構(gòu)造最優(yōu)解D、定義最優(yōu)解45.實現(xiàn)最大子段和利用的算法是（

B

）。A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法46.優(yōu)先隊列式分支限界法選取擴(kuò)展結(jié)點的原則是（

C

）。A、先進(jìn)先出 B、后進(jìn)先出C、結(jié)點的優(yōu)先級 D、隨機(jī)47.背包問題的貪心算法所需的計算時間為（

B

）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）48、廣度優(yōu)先是（

A

）的一搜索方式。A、分支界限法

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

C、貪心法

D、回溯法49、舍伍德算法是（

B

）的一種。A、分支界限算法

B、概率算法

C、貪心算法

D、回溯算法50、在下列算法中有時找不到問題解的是（

B

）。A、蒙特卡羅算法

B、拉斯維加斯算法

C、舍伍德算法

D、數(shù)值概率算法51下列哪一種算法是隨機(jī)化算法（

D

）A.貪心算法B.回溯法C.動態(tài)規(guī)劃算法D.舍伍德算法52.一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的（

B

）。A、重疊子問題B、最優(yōu)子結(jié)構(gòu)性質(zhì) C、貪心選擇性質(zhì) D、定義最優(yōu)解53．采用貪心算法的最優(yōu)裝載問題的主要計算量在于將集裝箱依其重量從小到大排序，故算法的時間復(fù)雜度為(B)。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）54.以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為(D)。A、分支界限算法

B、概率算法

C、貪心算法

D、回溯算法55.實現(xiàn)最長公共子序列利用的算法是（

B

）。A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法1.算法的復(fù)雜性有時間復(fù)雜性和空間復(fù)雜性之分。2、程序是算法

用某種程序設(shè)計語言的具體實現(xiàn)。3、算法的“確定性”指的是組成算法的每條指令是清晰的，無歧義的。4.矩陣連乘問題的算法可由動態(tài)規(guī)劃設(shè)計實現(xiàn)。5、拉斯維加斯算法找到的解一定是正確解。6、算法是指解決問題的一種方法或一個過程。7、從分治法的一般設(shè)計模式可以看出，用它設(shè)計出的程序一般是遞歸算法。8、問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。9、以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為回溯法。10、數(shù)值概率算法常用于數(shù)值問題的求解。11、計算一個算法時間復(fù)雜度通?？梢杂嬎阊h(huán)次數(shù)、基本操作的頻率或計算步。12、利用概率的性質(zhì)計算近似值的隨機(jī)算法是數(shù)值概率算法，運(yùn)行時以一定的概率得到正確解的隨機(jī)算法是__蒙特卡羅算法_____________________。14、解決0/1背包問題可以使用動態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是動態(tài)規(guī)劃，需要排序的是回溯法，分支限界法。

15、使用回溯法進(jìn)行狀態(tài)空間樹裁剪分支時一般有兩個標(biāo)準(zhǔn)：約束條件和目標(biāo)函數(shù)的界，N皇后問題和0/1背包問題正好是兩種不同的類型，其中同時使用約束條件和目標(biāo)函數(shù)的界進(jìn)行裁剪的是0/1背包問題，只使用約束條件進(jìn)行裁剪的是N皇后問題。17、矩陣連乘問題的算法可由動態(tài)規(guī)劃設(shè)計實現(xiàn)。18、拉斯維加斯算法找到的解一定是正確解。19.貪心算法的基本要素是貪心選擇質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。21.動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干子問題，先求解子問題，然后從這些子問題的解得到原問題的解。算法是由若干條指令組成的有窮序列，且要滿足輸入，輸出、確定性和有限性四條性質(zhì)。23、大整數(shù)乘積算法是用分治法來設(shè)計的。24、以廣度優(yōu)先或以最小耗費方式搜索問題解的算法稱為分支限界法。25、舍伍德算法總能求得問題的一個解。貪心選擇性質(zhì)是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法主要區(qū)別。27.快速排序算法是基于分治策略的一種排序算法。28.動態(tài)規(guī)劃算法的兩個基本要素是.最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問題性質(zhì)。30.回溯法是一種既帶有系統(tǒng)性又帶有跳躍性的搜索算法。31.分支限界法主要有隊列式（FIFO）分支限界法和優(yōu)先隊列式分支限界法。32．分支限界法是一種既帶有系統(tǒng)性又帶有跳躍性的搜索算法。33．回溯法搜索解空間樹時，常用的兩種剪枝函數(shù)為約束函數(shù)和限界函數(shù)。34.任何可用計算機(jī)求解的問題所需的時間都與其規(guī)模有關(guān)。35.快速排序算法的性能取決于劃分的對稱性。1分治法的基本思想時將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解。2設(shè)計動態(tài)規(guī)劃算法的主要步驟為：（1）找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征（2）遞歸地定義最優(yōu)值（3）以自底向上的方式計算出最優(yōu)值（4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。3.分治法與動態(tài)規(guī)劃法的相同點是：將待求解的問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。兩者的不同點是：適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨立的。而用分治法求解的問題，經(jīng)分解得到的子問題往往是互相獨立的。4.分支限界法與回溯法的相同點是：都是一種在問題的解空間樹T中搜索問題解的算法。不同點：（1）求解目標(biāo)不同；（2）搜索方式不同；（3）對擴(kuò)展結(jié)點的擴(kuò)展方式不同；（4）存儲空間的要求不同。5用回溯法搜索子集樹的算法為：6.分治法所能解決的問題一般具有的幾個特征是：（1）該問題的規(guī)?？s小到一定的程度就可以容易地解決；（2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì);（3）利用該問題分解出的子問題的解可以合并為該問題的解；（4）原問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。7.用分支限界法設(shè)計算法的步驟是：(1)針對所給問題，定義問題的解空間（對解進(jìn)行編碼）；分(2)確定易于搜索的解空間結(jié)構(gòu)（按樹或圖組織解）；(3)以廣度優(yōu)先或以最小耗費（最大收益）優(yōu)先的方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。8.常見的兩種分支限界法的算法框架（1）隊列式(FIFO)分支限界法：按照隊列先進(jìn)先出（FIFO）原則選取下一個節(jié)點為擴(kuò)展節(jié)點。（2）優(yōu)先隊列式分支限界法：按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當(dāng)前擴(kuò)展節(jié)點。9.回溯法中常見的兩類典型的解空間樹是子集樹和排列樹。當(dāng)所給的問題是從n個元素的集合S中找出滿足某種性質(zhì)的子集時，相應(yīng)的解空間樹稱為子集樹。這類子集樹通常有2n個葉結(jié)點，遍歷子集樹需O(2n)計算時間。當(dāng)所給的問題是確定n個元素滿足某種性質(zhì)的排列時，相應(yīng)的解空間樹稱為排列樹。這類排列樹通常有n!個葉結(jié)點。遍歷排列樹需要O(n!)計算時間。10.分支限界法的搜索策略是：在擴(kuò)展結(jié)點處，先生成其所有的兒子結(jié)點（分支），然后再從當(dāng)前的活結(jié)點表中選擇下一個擴(kuò)展結(jié)點。為了有效地選擇下一擴(kuò)展結(jié)點，加速搜索的進(jìn)程，在每一個活結(jié)點處，計算一個函數(shù)值（限界），并根據(jù)函數(shù)值，從當(dāng)前活結(jié)點表中選擇一個最有利的結(jié)點作為擴(kuò)展結(jié)點，使搜索朝著解空間上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個最優(yōu)解。計算機(jī)算法設(shè)計與分析復(fù)習(xí)題一、填空題1、一個算法復(fù)雜性的高低體現(xiàn)在計算機(jī)運(yùn)行該算法所需的時間和存儲器資源上，因此算法的復(fù)雜性有時間復(fù)雜性和空間復(fù)雜性之分。2、出自于“平衡子問題”的思想，通常分治法在分割原問題，形成若干子問題時，這些子問題的規(guī)模都大致相同。3、使用二分搜索算法在n個有序元素表中搜索一個特定元素，在最佳情況下，搜索的時間復(fù)雜性為O（1），在最壞情況下，搜索的時間復(fù)雜性為O（logn）。4、已知一個分治算法耗費的計算時間T(n)，T(n)滿足如下遞歸方程：解得此遞歸方可得T(n)=O（）。5、動態(tài)規(guī)劃算法有一個變形方法備忘錄方法。這種方法不同于動態(tài)規(guī)劃算法“自底向上”的填充方向，而是“自頂向下”的遞歸方向，為每個解過的子問題建立了備忘錄以備需要時查看，同樣也可避免相同子問題的重復(fù)求解。6．遞歸的二分查找算法在divide階段所花的時間是O(1)，conquer階段所花的時間是T(n/2)，算法的時間復(fù)雜度是O(logn)。7．Prim算法利用貪心策略求解最小生成樹問題，其時間復(fù)雜度是O(n2)。8．背包問題可用貪心法，回溯法等策略求解。9．用動態(tài)規(guī)劃算法計算矩陣連乘問題的最優(yōu)值所花的時間是O(n3)，子問題空間大小是O(n2)。10．圖的m著色問題可用回溯法求解，其解空間樹中葉子結(jié)點個數(shù)是mn，解空間樹中每個內(nèi)結(jié)點的孩子數(shù)是m。11．單源最短路徑問題可用貪心法、分支限界等策略求解。12、一個算法的優(yōu)劣可以用（時間復(fù)雜度）與（空間復(fù)雜度）與來衡量。13、回溯法在問題的解空間中，按（深度優(yōu)先方式）從根結(jié)點出發(fā)搜索解空間樹。14、直接或間接地調(diào)用自身的算法稱為（遞歸算法）。15、q記號在算法復(fù)雜性的表示法中表示（漸進(jìn)確界或緊致界）。16、在分治法中，使子問題規(guī)模大致相等的做法是出自一種（平衡(banlancing)子問題）的思想。17、動態(tài)規(guī)劃算法適用于解（具有某種最優(yōu)性質(zhì)）問題。18、貪心算法做出的選擇只是（在某種意義上的局部）最優(yōu)選擇。19、最優(yōu)子結(jié)構(gòu)性質(zhì)的含義是（問題的最優(yōu)解包含其子問題的最優(yōu)解）。20、回溯法按（深度優(yōu)先）策略從根結(jié)點出發(fā)搜索解空間樹。21、拉斯維加斯算法找到的解一定是（正確解）。22、按照符號O的定義O(f)+O(g)等于O(max{f(n),g(n)})。23、二分搜索技術(shù)是運(yùn)用（分治）策略的典型例子。24、動態(tài)規(guī)劃算法中，通常不同子問題的個數(shù)隨問題規(guī)模呈（多項式）級增長。25、（最優(yōu)子結(jié)構(gòu)性質(zhì)）和（子問題重疊性質(zhì)）是采用動態(tài)規(guī)劃算法的兩個基本要素。26、（最優(yōu)子結(jié)構(gòu)性質(zhì)）和（貪心選擇性質(zhì)）是貪心算法的基本要素。27、（選擇能產(chǎn)生最優(yōu)解的貪心準(zhǔn)則）是設(shè)計貪心算法的核心問題。28、分支限界法常以（廣度優(yōu)先）或（以最小耗費(最大效益)優(yōu)先）的方式搜索問題的解空間樹。29、貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列（局部最優(yōu)）的選擇，即貪心選擇達(dá)到。30、按照活結(jié)點表的組織方式的不同，分支限界法包括（隊列式(FIFO)分支限界法）和（優(yōu)先隊列式分支限界法）兩種形式。31、如果對于同一實例，蒙特卡洛算法不會給出兩個不同的正確解答，則稱該蒙特卡洛算法是（一致的）。32、哈夫曼編碼可利用（貪心法）算法實現(xiàn)。33概率算法有數(shù)值概率算法，蒙特卡羅（MonteCarlo）算法，拉斯維加斯（LasVegas）算法和舍伍德（Sherwood）算法34以自頂向下的方式求解最優(yōu)解的有（貪心算法）35、下列算法中通常以自頂向下的方式求解最優(yōu)解的是（貪心法）。36、在對問題的解空間樹進(jìn)行搜索的方法中,一個活結(jié)點有多次機(jī)會成為活結(jié)點的是（回溯法）37、旅行售貨員問題不能用（）解決可以用回溯法解決，分支限界法，NP完全性理論與近似算法38、貪心算法不能解決（0-1背包問題N皇后問題）?？梢越鉀Q背包問題39、投點法是（概率算法）的一種。40、若線性規(guī)劃問題存在最優(yōu)解，它一定不在（可行域內(nèi)部）二、簡答題1、（8分）寫出下列復(fù)雜性函數(shù)的偏序關(guān)系（即按照漸進(jìn)階從低到高排序）：參考解答：2、（8分）現(xiàn)在有8位運(yùn)動員要進(jìn)行網(wǎng)球循環(huán)賽，要設(shè)計一個滿足以下要求的比賽日程表：每個選手必須與其他選手各賽一次；每個選手一天只能賽一次；循環(huán)賽一共進(jìn)行n–1天。請利用分治法的思想，給這8位運(yùn)動員設(shè)計一個合理的比賽日程。參考解答：12345678214365873412785643218765567812346587214378563412876543213、（8分）某體育館有一羽毛球場出租，現(xiàn)在總共有10位客戶申請租用此羽毛球場，每個客戶所租用的時間單元如下表所示，s(i)表示開始租用時刻，f(i)表示結(jié)束租用時刻，10個客戶的申請如下表所示：i12345678910s(i)03153511886f(i)65498713121110同一時刻，該羽毛球場只能租借給一位客戶，請設(shè)計一個租用安排方案，在這10位客戶里面，使得體育館能盡可能滿足多位客戶的需求，并算出針對上表的10個客戶申請，最多可以安排幾位客戶申請。參考解答：將這10位客戶的申請按照結(jié)束時間f(i)遞增排序，如下表：i12345678910s(i(i)45678910111213=1\*GB2⑴選擇申請1（1,4）=2\*GB2⑵依次檢查后續(xù)客戶申請，只要與已選擇的申請相容不沖突，則選擇該申請。直到所有申請檢查完畢。申請4（5,7）、申請8（8,11）、申請10（11,13）=3\*GB2⑶最后，可以滿足：申請1（1,4）、申請4（5,7）、申請8（8,11）、申請10（11,13）共4個客戶申請。這已經(jīng)是可以滿足的最大客戶人數(shù)。4、（8分）對于矩陣連乘所需最少數(shù)乘次數(shù)問題，其遞歸關(guān)系式為：其中m[i，j]為計算矩陣連乘Ai…Aj所需的最少數(shù)乘次數(shù)，pi-1為矩陣Ai的行，為矩陣Ai的列?，F(xiàn)有四個矩陣，其中各矩陣維數(shù)分別為：A1A2A3A450′1010′4040′3030′5p0′p1p1′p2p2′p3p3′p4請根據(jù)以上的遞歸關(guān)系，計算出矩陣連乘積A1A2參考解答：5、（8分）有這樣一類特殊0-1背包問題：可選物品重量越輕的物品價值越高。n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。其中n為物品個數(shù)，c為背包載重量，P表示物品的價值，W表示物品的重量。請問對于此0-1背包問題，應(yīng)如何選擇放進(jìn)去的物品，才能使到放進(jìn)背包的物品總價值最大，能獲得的最大總價值多少？參考解答：因為該0－1背包問題比較特殊，恰好重量越輕的物品價值越高，所以優(yōu)先取重量輕的物品放進(jìn)背包。最終可以把重量分別為2，3，4，5的三個物品放進(jìn)背包，得到的價值和為15+8+6+4=33，為最大值。6.請用英文寫出三種以上能求解0-1背包問題的設(shè)計算法策略。參考解答：DynamicProgrammingBacktrackBranch-and-Bound（每答對一條給一分）7.請說明動態(tài)規(guī)劃方法為什么需要最優(yōu)子結(jié)構(gòu)性質(zhì)。參考解答：最優(yōu)子結(jié)構(gòu)性質(zhì)是指大問題的最優(yōu)解包含子問題的最優(yōu)解。動態(tài)規(guī)劃方法是自底向上計算各個子問題的最優(yōu)解，即先計算子問題的最優(yōu)解，然后再利用子問題的最優(yōu)解構(gòu)造大問題的最優(yōu)解，因此需要最優(yōu)子結(jié)構(gòu).請說明：(1)優(yōu)先隊列可用什么數(shù)據(jù)結(jié)構(gòu)實現(xiàn)？(2)優(yōu)先隊列插入算法基本思想？(3)優(yōu)先隊列插入算法時間復(fù)雜度？參考解答：（1）堆。(1分)（2）在小根堆中，將元素x插入到堆的末尾，然后將元素x的關(guān)鍵字與其雙親的關(guān)鍵字比較，若元素x的關(guān)鍵字小于其雙親的關(guān)鍵字，則將元素x與其雙親交換，然后再將元素x與其新雙親的關(guān)鍵字相比，直到元素x的關(guān)鍵字大于雙親的關(guān)鍵字，或元素x到根為止。(4分)（3）O(logn)（1分）9..設(shè)計動態(tài)規(guī)劃算法的主要步驟是怎么的？請簡述。參考解答：（1）找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(6分)（2）遞歸地定義最優(yōu)值。（3）以自底向上的方式計算出最優(yōu)值。（4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。10.分治法所能解決的問題一般具有哪幾個特征？請簡述。參考解答：（1）該問題的規(guī)?？s小到一定的程度就可以容易地解決；(6分)（2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì);（3）利用該問題分解出的子問題的解可以合并為該問題的解；（4）原問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。11.分支限界法的搜索策略是什么？參考解答：在擴(kuò)展結(jié)點處，先生成其所有的兒子結(jié)點（分支），然后再從當(dāng)前的活結(jié)點表中選擇下一個擴(kuò)展結(jié)點。為了有效地選擇下一擴(kuò)展結(jié)點，加速搜索的進(jìn)程，在每一個活結(jié)點處，計算一個函數(shù)值（限界），并根據(jù)函數(shù)值，從當(dāng)前活結(jié)點表中選擇一個最有利的結(jié)點作為擴(kuò)展結(jié)點，使搜索朝著解空間上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個最優(yōu)解。(6分)算法的要特性是什么？參考解答：確定性、可實現(xiàn)性、輸入、輸出、有窮性算法分析的目的是什么？參考解答：分析算法占用計算機(jī)資源的情況，對算法做出比較和評價，設(shè)計出額更好的算法。算法的時間復(fù)雜性與問題的什么因素相關(guān)？參考解答：算法的時間復(fù)雜性與問題的規(guī)模相關(guān)，是問題大小n的函數(shù)。算法的漸進(jìn)時間復(fù)雜性的含義？參考解答：當(dāng)問題的規(guī)模n趨向無窮大時，影響算法效率的重要因素是T(n)的數(shù)量級，而其他因素僅是使時間復(fù)雜度相差常數(shù)倍，因此可以用T(n)的數(shù)量級(階)評價算法。時間復(fù)雜度T(n)的數(shù)量級(階)稱為漸進(jìn)時間復(fù)雜性。最壞情況下的時間復(fù)雜性和平均時間復(fù)雜性有什么不同？參考解答：最壞情況下的時間復(fù)雜性和平均時間復(fù)雜性考察的是n固定時，不同輸入實例下的算法所耗時間。最壞情況下的時間復(fù)雜性取的輸入實例中最大的時間復(fù)雜度：W(n)=max{T(n，I)},I∈Dn平均時間復(fù)雜性是所有輸入實例的處理時間與各自概率的乘積和：A(n)=∑P(I)T(n，I)I∈Dn簡述二分檢索（折半查找）算法的基本過程。參考解答：設(shè)輸入是一個按非降次序排列的元素表A[i：j]和x，選取A[(i+j)/2]與x比較，如果A[(i+j)/2]=x，則返回(i+j)/2，如果A[(i+j)/2]<x，則A[i：(i+j)/2-1]找x，否則在A[(i+j)/2+1：j]找x。上述過程被反復(fù)遞歸調(diào)用。背包問題的目標(biāo)函數(shù)和貪心算法最優(yōu)化量度相同嗎？參考解答：不相同。目標(biāo)函數(shù)：獲得最大利潤。最優(yōu)量度：最大利潤/重量比。采用回溯法求解的問題，其解如何表示？有什么規(guī)定？參考解答：問題的解可以表示為n元組：（x1,x2,……xn），xi∈Si,Si為有窮集合，xi∈Si,（x1,x2,……xn）具備完備性，即（x1,x2,……xn）是合理的，則（x1,x2,……xi）(i<n)一定合理?；厮莘ǖ乃阉魈攸c是什么？參考解答：在解空間樹上跳躍式地深度優(yōu)先搜索，即用判定函數(shù)考察x[k]的取值，如果x[k]是合理的就搜索x[k]為根節(jié)點的子樹，如果x[k]取完了所有的值，便回溯到x[k-1]。n皇后問題回溯算法的判別函數(shù)place的基本流程是什么？參考解答：將第K行的皇后分別與前k-1行的皇后比較，看是否與它們相容，如果不相容就返回false，測試完畢則返回true。為什么用分治法設(shè)計的算法一般有遞歸調(diào)用？參考解答：子問題的規(guī)模還很大時，必須繼續(xù)使用分治法，反復(fù)分治，必然要用到遞歸.為什么要分析最壞情況下的算法時間復(fù)雜性？參考解答：最壞情況下的時間復(fù)雜性決定算法的優(yōu)劣，并且最壞情況下的時間復(fù)雜性較平均時間復(fù)雜性游可操作性。簡述漸進(jìn)時間復(fù)雜性上界的定義。參考解答：T(n)是某算法的時間復(fù)雜性函數(shù)，f(n)是一簡單函數(shù)，存在正整數(shù)No和C，n〉No，有T(n)<f(n)，這種關(guān)系記作T(n)=O(f(n))。二分檢索算法最多的比較次數(shù)？參考解答：二分檢索算法的最多的比較次數(shù)為logn。快速排序算法最壞情況下需要多少次比較運(yùn)算？參考解答：最壞情況下快速排序退化成冒泡排序，需要比較n2次。貪心算法的基本思想？參考解答：是一種依據(jù)最優(yōu)化量度依次選擇輸入的分級處理方法?；舅悸肥牵菏紫雀鶕?jù)題意，選取一種量度標(biāo)準(zhǔn)；然后按這種量度標(biāo)準(zhǔn)對這n個輸入排序，依次選擇輸入量加入部分解中。如果當(dāng)前這個輸入量的加入，不滿足約束條件，則不把此輸入加到這部分解中回溯法的解（x1,x2,……xn）的隱約束一般指什么？參考解答：回溯法的解（x1,x2,……xn）的隱約束一般指個元素之間應(yīng)滿足的某種關(guān)系。闡述歸并排序的分治思路。參考解答：講數(shù)組一分為二，分別對每個集合單獨排序，然后將已排序的兩個序列歸并成一個含n個元素的分好類的序列。如果分割后子問題還很大，則繼續(xù)分治，直到一個元素。快速排序的基本思想是什么。參考解答：快速排序的基本思想是在待排序的N個記錄中任意取一個記錄，把該記錄放在最終位置后，數(shù)據(jù)序列被此記錄分成兩部分。所有關(guān)鍵字比該記錄關(guān)鍵字小的放在前一部分，所有比它大的放置在后一部分，并把該記錄排在這兩部分的中間，這個過程稱作一次快速排序。之后重復(fù)上述過程，直到每一部分內(nèi)只有一個記錄為止。什么是直接遞歸和間接遞歸？消除遞歸一般要用到什么數(shù)據(jù)結(jié)構(gòu)？參考解答：在定義一個過程或者函數(shù)的時候又出現(xiàn)了調(diào)用本過程或者函數(shù)的成分，既調(diào)用它自己本身，這稱為直接遞歸。如果過程或者函數(shù)P調(diào)用過程或者函數(shù)Q，Q又調(diào)用P，這個稱為間接遞歸。消除遞歸一般要用到棧這種數(shù)據(jù)結(jié)構(gòu)。什么是哈密頓環(huán)問題？參考解答：哈密頓環(huán)是指一條沿著圖G的N條邊環(huán)行的路徑，它的訪問每個節(jié)點一次并且返回它的開始位置。用回溯法求解哈密頓環(huán)，如何定義判定函數(shù)？參考解答：當(dāng)前選擇的節(jié)點X[k]是從未到過的節(jié)點,即X[k]≠X[i](i=1,2,…,k-1)，且C(X[k-1],X[k])≠∞，如果k=-1，則C(X[k],X[1])≠∞。請寫出prim算法的基本思想。參考解答：思路是：最初生成樹T為空，依次向內(nèi)加入與樹有最小鄰接邊的n-1條邊。處理過程：首先加入最小代價的一條邊到T，根據(jù)各節(jié)點到T的鄰接邊排序，選擇最小邊加入，新邊加入后，修改由于新邊所改變的鄰接邊排序，再選擇下一條邊加入，直至加入n-1條邊。三、算法設(shè)計題1.【最長上升子序列問題】（8分）——提示：此題可采用動態(tài)規(guī)劃算法實現(xiàn)對于給定的一個序列，。我們可以得到一些遞增上升的子序列，這里。比如，對于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。這些子序列中最長的長度是4，比如子序列(1,3,5,8)。你的任務(wù)：就是對于給定的序列，求出最長上升子序列的長度。要求寫出你設(shè)計的算法思想及遞推函數(shù)的公式表達(dá)。.參考解答：設(shè)表示：從左向右掃描過來直到以元素結(jié)尾的序列，獲得的最長上升子序列的長度，且子序列包含元素（）。即，是從，……到中找最大的一個值，再加1?；蛘呔褪?。主要是看a[i]這個元素能否加入到之前已經(jīng)獲得的最長上升子序列，如果能加入，是之前已獲得的最長上升子序列長度加一；如果不能加入，就取這最后一個元素作為一個單獨子序列，長度為1。最后，所要求的整個序列的最長公共子序列長度為max{f(i):1<=i<=n}例如，對于序列：4263152i1234567array4263152f(i)1122132評分準(zhǔn)則：答到使用動態(tài)規(guī)劃算法，并且推導(dǎo)出動態(tài)規(guī)劃算法的遞推函數(shù)公式表達(dá)，邊界設(shè)定清晰，本題即可得滿分；（閱卷時仔細(xì)看遞推公式表達(dá)，公式表達(dá)含義正確即可，因其表達(dá)形式可能不唯一）說明使用動態(tài)規(guī)劃算法，但對遞推函數(shù)表達(dá)錯誤或含糊，扣2分以上；其它情況酌情考慮。2．對下圖所示的連通網(wǎng)絡(luò)G，用克魯斯卡爾(Kruskal)算法求G的最小生成樹T,請寫出在算法執(zhí)行過程中，依次加入T的邊集TE中的邊。說明該算法的貪心策略和算法的基本思想，并簡要分析算法的時間復(fù)雜度。112345618111715192126679參考解答TE={(3,4),(2,3),(1,5),（4,6）（4,5）}（5分）貪心策略是每次都在連接兩個不同連通分量的邊中選權(quán)值最小的邊?；舅枷耄菏紫葘D中所有頂點都放到生成樹中，然后每次都在連接兩個不同連通分量的邊中選權(quán)值最小的邊，將其放入生成樹中，直到生成樹中有n-1條邊。（4分）時間復(fù)雜度為：O(eloge)（1分）3.（15分）考慮n=3的批處理作業(yè)調(diào)度實例：tji機(jī)器1機(jī)器2作業(yè)1110作業(yè)231作業(yè)321其中tji是作業(yè)Ji需要在機(jī)器j上處理的時間。對于給定的3個作業(yè)，制定一個最佳作業(yè)調(diào)度方案，使其完成時間和達(dá)到最小。要求：（1）畫出該問題的解空間樹；（5分）（2）寫出該問題的剪枝策略(即限界條件),要求只保留第一個最優(yōu)解;(2分)（3）按優(yōu)先隊列式分支限界法搜索解空間樹，并用剪枝策略對解空間樹中該剪枝的位置打；（5分）（4）給出最優(yōu)解及最優(yōu)值。（3分）參考解答（1）5分2113232113231231323V021113491618232325303336361026※（2）若當(dāng)前代價f>=當(dāng)前最優(yōu)解代價bestf，則剪枝。2分（3）見（1）中所畫的圖。5分（4）最優(yōu)解為{3，1，2}，最優(yōu)值為25。3分4.【Gray碼構(gòu)造問題】（8分）——提示：此題可采用分治遞歸算法實現(xiàn)問題描述：“格雷碼”是一個長度為的序列，滿足：（a）每個元素都是長度為n比特的串（b）序列中無相同元素（c）連續(xù)的兩個元素恰好只有1個比特不同例如：n=2時，格雷碼為{00，01，11，10}。Gray碼是一種編碼，這種編碼可以避免在讀取時，因各數(shù)據(jù)位時序上的差異造成的誤讀。格雷碼在工程上有廣泛應(yīng)用。但格雷碼不便于運(yùn)算，請你設(shè)計一種構(gòu)造方法，輸入長度序列n，輸出格雷碼（你只要做出一種構(gòu)造方案即可，格雷碼并不唯一）。參考解答：此題可用分治法解決。當(dāng)n＝1時，輸出格雷碼{0,1}當(dāng)n>1時，格雷碼的長度為，即共有個碼序列。此時，將問題一分為二，即上半部分和下半部分。上半部分最高位設(shè)為0，下半部分最高位設(shè)為1。剩下n-1位的格雷碼的構(gòu)造采用遞歸的思路。評分準(zhǔn)則：答到使用分治算法，并且推導(dǎo)出分治算法的過程，邊界設(shè)定清晰（即當(dāng)僅輸出1位的格雷碼如何處理），本題即可得滿分；說明使用分治算法，但漏邊界條件，扣2分以上；其它情況酌情考慮。5.（13分）給定帶權(quán)有向圖（如下圖所示）G=(V,E)，其中每條邊的權(quán)是非負(fù)實數(shù)。另外，還給定V中的一個頂點，稱為源?，F(xiàn)在要計算從源到所有其它各頂點的最短路長度。這里路的長度是指路上各邊權(quán)之和。現(xiàn)采用Dijkstra算法計算從源頂點1到其它頂點間最短路徑。請將此過程填入下表中。44321{1}初始dist[5]dist[4]dist[3]dist[2]uS迭代參考解答：（13分）60603050105{1，2，3，4，5}4603050103{1，2，4，3}3903050104{1，2，4}21003060102{1，2}11003010-{1}初始dist[5]dist[4]dist[3]di