算法分析作業(yè)

算法分析練習題（一）一、選擇題1、二分搜索算法是利用（

A

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

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

C、貪心法

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

A

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

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

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

D、定義最優(yōu)解3．下列算法中通常以自底向上的方式求解最優(yōu)解的是（

B

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

A運行速度快B占用空間少C時間復雜度低D代碼短

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

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

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

A

）。A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法7.備忘錄方法是那種算法的變形。（B）A、分治法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法8．最長公共子序列算法利用的算法是（

B

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

A

）。A、分治法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法10.矩陣連乘問題的算法可由（

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

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

C、貪心算法

D、回溯算法11、Strassen矩陣乘法是利用（

A

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

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

C、貪心法

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

A子問題必須是一樣的

B子問題不能夠重復

C子問題的解可以合并

D原問題和子問題使用相同的方法解

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

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

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

A

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

D

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

B

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

A

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

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

C、貪心法

D、回溯法18．實現(xiàn)大整數(shù)的乘法是利用的算法（

C

）。A、貪心法 B、動態(tài)規(guī)劃法 C、分治策略 D、回溯法19.實現(xiàn)最大子段和利用的算法是（

B

）。A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法20.一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征是問題的（

B

）。A、重疊子問題 B、最優(yōu)子結構性質(zhì) C、貪心選擇性質(zhì) D、定義最優(yōu)解21.實現(xiàn)最長公共子序列利用的算法是（

B

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

算法

用某種程序設計語言的具體實現(xiàn)。3、算法的“確定性”指的是組成算法的每條指令是清晰的，無歧義的。4.矩陣連乘問題的算法可由動態(tài)規(guī)劃設計實現(xiàn)。5、算法是指解決問題的一種方法或一個過程。出這兩段的最大子段和，則a[1:n]的最大子段和有哪三種情形？3、請說明動態(tài)規(guī)劃方法為什么需要最優(yōu)子結構性質(zhì)。最優(yōu)子結構性質(zhì)是指大問題的最優(yōu)解包含子問題的最優(yōu)解。

動態(tài)規(guī)劃方法是自底向上計算各個子問題的最優(yōu)解，即先計算子問題的最優(yōu)解，然后再利用子問題的最優(yōu)解構造大問題的最優(yōu)解，因此需要最優(yōu)子結構4、設計動態(tài)規(guī)劃算法的主要步驟是怎么的？請簡述。參考解答：（1）找出最優(yōu)解的性質(zhì)，并刻劃其結構特征。(6分)

（2）遞歸地定義最優(yōu)值。

（3）以自底向上的方式計算出最優(yōu)值。

（4）根據(jù)計算最優(yōu)值時得到的信息，構造最優(yōu)解。5、分治法所能解決的問題一般具有哪幾個特征？請簡述。參考解答：（1）該問題的規(guī)?？s小到一定的程度就可以容易地解決；(6分)

（2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結構性質(zhì);

（3）

利用該問題分解出的子問題的解可以合并為該問題的解；

（4）原問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。6、算法的要特性是什么？參考解答：確定性、可實現(xiàn)性、輸入、輸出、有窮性算法分析的目的是什么？參考解答：分析算法占用計算機資源的情況，對算法做出比較和評價，設計出額更好的算法。8、算法的時間復雜性與問題的什么因素相關？參考解答：算法的時間復雜性與問題的規(guī)模相關，是問題大小n的函數(shù)。9、算法的漸進時間復雜性的含義？參考解答：當問題的規(guī)模n趨向無窮大時，影響算法效率的重要因素是T(n)的數(shù)量級，而其他因素僅是使時間復雜度相差常數(shù)倍，因此可以用T(n)的數(shù)量級(階)評價算法。時間復雜度T(n)的數(shù)量級(階)稱為漸進時間復雜性。10簡述漸進時間復雜性上界的定義。參考解答：T(n)是某算法的時間復雜性函數(shù)，f(n)是一簡單函數(shù)，存在正整數(shù)No和C，n〉No，有T(n)<f(n)，這種關系記作T(n)=O(f(n))。11快速排序算法最壞情況下需要多少次比較運算？參考解答：最壞情況下快速排序退化成冒泡排序，需要比較n2次。闡述歸并排序的分治思路。參考解答：講數(shù)組一分為二，分別對每個集合單獨排序，然后將已排序的兩個序列歸并成一個含n個元素的分好類的序列。如果分割后子問題還很大，則繼續(xù)分治，直到一個元素?？焖倥判虻幕舅枷胧鞘裁?。參考解答：快速排序的基本思想是在待排序的N個記錄中任意取一個記錄，把該記錄放在最終位置后，數(shù)據(jù)序列被此記錄分成兩部分。所有關鍵字比該記錄關鍵字小的放在前一部分，所有比它大的放置在后一部分，并把該記錄排在這兩部分的中間，這個過程稱作一次快速排序。之后重復上述過程，直到每一部分內(nèi)只有一個記錄為止。14分治法的基本思想是什么？將一個規(guī)模為N的問題分解為K個規(guī)模較小的子問題，這些子問題相互獨立且與原問題性質(zhì)相同。求出子問題的解，就可得到原問題的解。即一種分目標完成程序算法，簡單問題可用二分法完成。15設計動態(tài)規(guī)劃算法的主要步驟？參考解答：（1）找出最優(yōu)解的性質(zhì)，并刻劃其結構特征。(6分)

（2）遞歸地定義最優(yōu)值。

（3）以自底向上的方式計算出最優(yōu)值。

（4）根據(jù)計算最優(yōu)值時得到的信息，構造最優(yōu)解。16分治法與動態(tài)規(guī)劃法的異同共同點：

將待求解的問題分解成若干子問題，先求解子問題，然后再從這些子問題的解得到原問題的解。

不同點：

1、適合于用動態(tài)規(guī)劃法求解的問題，分解得到的各子問題往往不是相互獨立的；

而分治法中子問題相互獨立。

2、動態(tài)規(guī)劃法用表保存已求解過的子問題的解，再次碰到同樣的子問題時不必重新求解，而只需查詢答案，故可獲得多項式級時間復雜度，效率較高；

而分治法中對于每次出現(xiàn)的子問題均求解，導致同樣的子問題被反復求解，故產(chǎn)生指數(shù)增長的時間復雜度，效率較低。17分治法所能解決的問題一般具有的幾個特征？參考解答：（1）該問題的規(guī)?？s小到一定的程度就可以容易地解決；(6分)

（2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結構性質(zhì);

（3）

利用該問題分解出的子問題的解可以合并為該問題的解；

（4）原問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。五、算法設計題1.【最長上升子序列問題】——提示：此題可采用動態(tài)規(guī)劃算法實現(xiàn)對于給定的一個序列，。我們可以得到一些遞增上升的子序列，這里。比如，對于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。這些子序列中最長的長度是4，比如子序列(1,3,5,8)。你的任務：就是對于給定的序列，求出最長上升子序列的長度。要求寫出你設計的算法思想及遞推函數(shù)的公式表達。.2.【Gray碼構造問題】——提示：此題可采用分治遞歸算法實現(xiàn)問題描述：“格雷碼”是一個長度為的序列，滿足：（a）每個元素都是長度為n比特的串（b）序列中無相同元素（c）連續(xù)的兩個元素恰好只有1個比特不同例如：n=2時，格雷碼為{00，01，11，10}。Gray碼是一種編碼，這種編碼可以避免在讀取時，因各數(shù)據(jù)位時序上的差異造成的誤讀。格雷碼在工程上有廣泛應用。但格雷碼不便于運算，請你設計一種構造方法，輸入長度序列n，輸出格雷碼（你只要做出一種構造方案即可，格雷碼并不唯一）。3.現(xiàn)在有8位運動員要進行網(wǎng)球循環(huán)賽，要設計一個滿足以下要求的比賽日程表：每個選手必須與其他選手各賽一次；每個選手一天只能賽一次；循環(huán)賽一共進行n–1天。請利用分治法的思想，給這8位運動員設計一個合理的比賽日程。4.對于矩陣連乘所需最少數(shù)乘次數(shù)問題，其遞歸關系式為：其中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ù)以上的遞歸關系，計算出矩陣連乘積A1A25.有這樣一類特殊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背包問題，應如何選擇放進去的物品，才能使到放進背包的物品總價值最大，能獲