算法分析作業(yè)

算法分析作業(yè)算法分析作業(yè)算法分析作業(yè)xxx公司算法分析作業(yè)文件編號：文件日期：修訂次數(shù)：第1.0次更改批準(zhǔn)審核制定方案設(shè)計，管理制度算法分析練習(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)解的是（

B

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

A運行速度快B占用空間少C時間復(fù)雜度低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）設(shè)計實現(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子問題不能夠重復(fù)

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、構(gòu)造最優(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ī)劃算法或貪心算法求解的關(guān)鍵特征是問題的（

B

）。A、重疊子問題 B、最優(yōu)子結(jié)構(gòu)性質(zhì) C、貪心選擇性質(zhì) D、定義最優(yōu)解21.實現(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、從分治法的一般設(shè)計模式可以看出，用它設(shè)計出的程序一般是遞歸算法。7、矩陣連乘問題的算法可由動態(tài)規(guī)劃設(shè)計實現(xiàn)。8.動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干子問題，先求解子問題，然后從這些子問題的解得到原問題的解。9.算法是由若干條指令組成的有窮序列，且要滿足輸入、輸出、確定性和有限性四條性質(zhì)。10、大整數(shù)乘積算法是用分治法來設(shè)計的。11.快速排序算法是基于分治策略的一種排序算法。12.動態(tài)規(guī)劃算法的兩個基本要素是.性質(zhì)和性質(zhì)。13.任何可用計算機(jī)求解的問題所需的時間都與其規(guī)模有關(guān)。14.快速排序算法的性能取決于劃分的對稱性。15、出自于“平衡子問題”的思想，通常分治法在分割原問題，形成若干子問題時，這些子問題的規(guī)模都大致相同。16、使用二分搜索算法在n個有序元素表中搜索一個特定元素，在最佳情況下，搜索的時間復(fù)雜性為O（），在最壞情況下，搜索的時間復(fù)雜性為O（logn）。17、已知一個分治算法耗費的計算時間T(n)，T(n)滿足如下遞歸方程：解得此遞歸方可得T(n)=O（

nlogn）。18、動態(tài)規(guī)劃算法有一個變形方法備忘錄方法。這種方法不同于動態(tài)規(guī)劃算法“自底向上”的填充方向，而是“自頂向下”的遞歸方向，為每個解過的子問題建立了備忘錄以備需要時查看，同樣也可避免相同子問題的重復(fù)求解。19、遞歸的二分查找算法在divide階段所花的時間是O(1)，conquer階段所花的時間是

T(n/2)

，算法的時間復(fù)雜度是O(

log

n)。20、用動態(tài)規(guī)劃算法計算矩陣連乘問題的最優(yōu)值所花的時間是O(n3)，子問題空間大小是

O(n2)

。21、一個算法的優(yōu)劣可以用（時間復(fù)雜度）與（空間復(fù)雜度）與來衡量。22、直接或間接地調(diào)用自身的算法稱為（遞歸算法）。23、記號在算法復(fù)雜性的表示法中表示（漸進(jìn)確界或緊致界）。24、在分治法中，使子問題規(guī)模大致相等的做法是出自一種（平衡子問題）的思想。25、動態(tài)規(guī)劃算法適用于解（具有某種最優(yōu)性質(zhì)）問題。26、最優(yōu)子結(jié)構(gòu)性質(zhì)的含義是（問題的最優(yōu)解包含其子問題的最優(yōu)解）。27、按照符號O的定義O(f)+O(g)等于O(max{f(n),g(n)})。28、二分搜索技術(shù)是運用（分治）策略的典型例子。29、動態(tài)規(guī)劃算法中，通常不同子問題的個數(shù)隨問題規(guī)模呈（多項式）級增長。30、（最優(yōu)子結(jié)構(gòu)性質(zhì)）和（子問題重疊性質(zhì)）是采用動態(tài)規(guī)劃算法的兩個基本要素。三、算法填空1.最大子段和:動態(tài)規(guī)劃算法intMaxSum(intn,inta[]){intsum=0,b=0；速排序template<classType>voidQuickSort(Typea[],intp,intr){if(p<r){intq=Partition(a,p,r);QuickSort（a，p，q-1）;最長上升子序列問題】——提示：此題可采用動態(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á)。.2.【Gray碼構(gòu)造問題】——提示：此題可采用分治遞歸算法實現(xiàn)問題描述：“格雷碼”是一個長度為的序列，滿足：（a）每個元素都是長度為n比特的串（b）序列中無相同元素（c）連續(xù)的兩個元素恰好只有1個比特不同例如：n=2時，格雷碼為{00，01，11，10}。Gray碼是一種編碼，這種編碼可以避免在讀取時，因各數(shù)據(jù)位時序上的差異造成的誤讀。格雷碼在工程上有廣泛應(yīng)用。但格雷碼不便于運算，請你設(shè)計一種構(gòu)造方法，輸入長度序列n，輸出格雷碼（你只要做出一種構(gòu)造方案即可，格雷碼并不唯一）。3.現(xiàn)在有8位運動員要進(jìn)行網(wǎng)球循環(huán)賽，要設(shè)計一個滿足以下要求的比賽日程表：每個選手必須與其他選手各賽一次；每個選手一天只能賽一次；循環(huán)賽一共進(jìn)行n–1天。請利用分治法的思想，給這8位運動員設(shè)計一個合理的比賽日程。4.對于矩陣連乘所需最少數(shù)乘次數(shù)問題，其遞歸關(guān)系式為：其中m[i，j]為計算矩陣連乘Ai…Aj所需的最少數(shù)乘次數(shù)，pi-1為矩陣Ai的行，為矩陣Ai的列?，F(xiàn)有四個矩陣，其中各矩陣維數(shù)分別為：A1A2A3A4501010404030305p0p1p1p2p2p3p3p4請根據(jù)以上的遞歸關(guān)系，計算出矩陣連乘積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背包問題，應(yīng)如何選擇放進(jìn)去的物品，才能使到放進(jìn)背包的物品總價值最大，能獲得的最大總價值多少6.歸