算法分析作業(yè)

1、.算法分析練習題（一）一、選擇題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、衡量一個算法好壞的標準是（C ）。A 運行速度快 B 占用空間少 C 時間復(fù)雜度低 D 代碼短5、以下不可以使用分治法求解的是（D ）。A 棋盤覆蓋問題 B 選擇問題 C 歸并排序 D 0/1背包問題6.實現(xiàn)循環(huán)賽日程表利用的算法是（A）。A、分治策略B、動態(tài)規(guī)劃

2、法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 子問題的解

3、可以合并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、分治

4、策略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、從分治法的

5、一般設(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.任何可用計算機求解的問題所需的時間都與其規(guī)模有關(guān)。14.快速排序算法的性能取決于 劃分的對稱性。15、出自于“平衡子問題”的思想，通常分治法在分割原問題，形成若干子

6、問題時，這些子問題的規(guī)模都大致相同。16、使用二分搜索算法在n 個有序元素表中搜索一個特定元素，在最佳情況下，搜索的時間復(fù)雜性為 O（），在最壞情況下，搜索的時間復(fù)雜性為O（ logn）。17、已知一個分治算法耗費的計算時間T(n) ，T(n) 滿足如下遞歸方程：T ( n )O (1)n22T (n / 2 ) O ( n ) n 2解得此遞歸方可得 T(n)= O （nlogn）。18、動態(tài)規(guī)劃算法有一個變形方法備忘錄方法。這種方法不同于動態(tài)規(guī)劃算法“自底向上”的填充方向，而是“自頂向下”的遞歸方向，為每個解過的子問題建立了備忘錄以備需要時查看，同樣也可避免相同子問題的重復(fù)求解。19、 遞

7、歸的二分查找算法在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ù)雜性的表示法中表示（漸進確界或緊致界）。24、在分治法中，使子問題規(guī)模大致相等的做法是出自一種（平衡子問題）的思想。25、動態(tài)規(guī)劃算法適用于解（具有某種最優(yōu)性質(zhì)）問題。;.26、最優(yōu)子結(jié)構(gòu)性質(zhì)的含義是（問題的最優(yōu)解包含其子問題的

8、最優(yōu)解）。27、按照符號 O 的定義 O(f)+O(g) 等于 O(maxf(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ī)劃算法int MaxSum(int n, int a)int sum=0, b=0 ； /sum 存儲當前最大的 bj, b 存儲 bj for(int j=1 ； j<=n ； j+) if （ b>0 ）b+=aj；elseb=ai；/ 一旦某個區(qū)段和

9、為負，則從下一個位置累和if (b>sum)sum=b；return sum ；2. 快速排序template<class Type>void QuickSort (Type a, int p, int r)if (p<r) int q=Partition(a,p,r);QuickSort （ a， p ， q-1 ）; /對左半段排序QuickSort(a,q+1,r); / 對右半段排序四、簡答題1、寫出下列復(fù)雜性函數(shù)的偏序關(guān)系（即按照漸進階從低到高排序）：2n3nlog nn!n log nn2nn1032、將所給定序列a1:n 分為長度相等的兩段a1:n/2和

10、an/2+1:n，分別求;.出這兩段的最大子段和，則a1:n 的最大子段和有哪三種情形？3、請說明動態(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)4、設(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)解。5、分治法所能解決的問題一般具有哪幾個特征？請簡述。參

11、考解答： （ 1 ）該問題的規(guī)模縮小到一定的程度就可以容易地解決；(6分 )（ 2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì) ;（ 3）利用該問題分解出的子問題的解可以合并為該問題的解；（4）原問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。6、算法的要特性是什么？參考解答：確定性、可實現(xiàn)性、輸入、輸出、有窮性7、 算法分析的目的是什么？參考解答：分析算法占用計算機資源的情況， 對算法做出比較和評價， 設(shè)計出額更好的算法。8、算法的時間復(fù)雜性與問題的什么因素相關(guān)？參考解答：算法的時間復(fù)雜性與問題的規(guī)模相關(guān)，是問題大小n 的函數(shù)。9、算法的漸進時

12、間復(fù)雜性的含義？參考解答：當問題的規(guī)模n 趨向無窮大時，影響算法效率的重要因素是T(n)的數(shù)量級，而其他因素僅是使時間復(fù)雜度相差常數(shù)倍，因此可以用T(n) 的數(shù)量級 ( 階 ) 評價算法。時間復(fù)雜度T(n) 的數(shù)量級 ( 階) 稱為漸進時間復(fù)雜性。10 簡述漸進時間復(fù)雜性上界的定義。參考解答： T(n) 是某算法的時間復(fù)雜性函數(shù)， f(n) 是一簡單函數(shù)，存在正整數(shù)No和 C， n No，有 T(n)<f(n) ，這種關(guān)系記作 T(n)=O(f(n) 。;.11 快速排序算法最壞情況下需要多少次比較運算？參考解答：最壞情況下快速排序退化成冒泡排序，需要比較n2 次。12 闡述歸并排序的分

13、治思路。參考解答：講數(shù)組一分為二，分別對每個集合單獨排序，然后將已排序的兩個序列歸并成一個含 n 個元素的分好類的序列。如果分割后子問題還很大，則繼續(xù)分治，直到一個元素。13 快速排序的基本思想是什么。參考解答：快速排序的基本思想是在待排序的 N 個記錄中任意取一個記錄，把該記錄放在最終位置后，數(shù)據(jù)序列被此記錄分成兩部分。所有關(guān)鍵字比該記錄關(guān)鍵字小的放在前一部分，所有比它大的放置在后一部分，并把該記錄排在這兩部分的中間，這個過程稱作一次快速排序。之后重復(fù)上述過程，直到每一部分內(nèi)只有一個記錄為止。14 分治法的基本思想是什么？將一個規(guī)模為N 的問題分解為K 個規(guī)模較小的子問題，這些子問題相互獨立

14、且與原問題性質(zhì)相同。求出子問題的解，就可得到原問題的解。即一種分目標完成程序算法，簡單問題可用二分法完成。15 設(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)解。16 分治法與動態(tài)規(guī)劃法的異同共同點：將待求解的問題分解成若干子問題，先求解子問題， 然后再從這些子問題的解得到原問題的解。不同點：1 、適合于用 動態(tài)規(guī)劃法 求解的問題，分解得到的各子問題往往不是相互獨立 的；而分治法中子問題相互獨立 。2 、動態(tài)規(guī)劃法 用表保存已求解過的子問題的解，

15、再次碰到同樣的子問題時不必重新求解，而只需查詢答案，故可獲得多項式級時間復(fù)雜度，效率較高；而分治法中對于每次出現(xiàn)的子問題均求解，導(dǎo)致同樣的子問題被反復(fù)求解，故產(chǎn)生 指數(shù)增長的時間復(fù)雜度，效率較低。17 分治法所能解決的問題一般具有的幾個特征？參考解答： （ 1 ）該問題的規(guī)?？s小到一定的程度就可以容易地解決；(6分 )（ 2）該問題可以分解為若干個規(guī)模較小的相同問題，;.即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì) ;（ 3）利用該問題分解出的子問題的解可以合并為該問題的解；（4）原問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。五、算法設(shè)計題1. 【最長上升子序列問題】 提示：此題可采用

16、動態(tài)規(guī)劃算法實現(xiàn)對于給定的一個序列 (a1, a2 ,L ,aN ) ， 1 N 1000 。我們可以得到一些遞增上升的子序列 ( ai 1, ai 2,L , aiK ) ，這里 1 i1 i2 Li K N 。比如，對于序列 (1, 7,3, 5, 9, 4, 8)，有它的一些上升子序列，如 (1,7), (3, 4, 8)等等。這些子序列中最長的長度是 4，比如子序列 (1, 3, 5, 8)。你的任務(wù)：就是對于給定的序列，求出最長上升子序列的長度。 要求寫出你設(shè)計的算法思想及遞推函數(shù)的公式表達。 .;.2. 【Gray 碼構(gòu)造問題】 提示：此題可采用分治遞歸算法實現(xiàn)問題描述： “格雷碼

17、”是一個長度為2n 的序列，滿足：（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 位運動員要進行網(wǎng)球循環(huán)賽，要設(shè)計一個滿足以下要求的比賽日程表：（ 1） 每個選手必須與其他選手各賽一次；（ 2） 每個選手一天只能賽一次；（ 3） 循

18、環(huán)賽一共進行 n 1 天。請利用分治法的思想，給這 8 位運動員設(shè)計一個合理的比賽日程。4. 對于矩陣連乘所需最少數(shù)乘次數(shù)問題，其遞歸關(guān)系式為：;.m i, j 0ijmin m i, k mk 1, j pi 1 pk pj iji k j其中 mi ， j 為計算矩陣連乘 AiAj 所需的最少數(shù)乘次數(shù)， pi-1 為矩陣 Ai 的行，pi 為矩陣 Ai 的列。現(xiàn)有四個矩陣，其中各矩陣維數(shù)分別為：AAAA12345010104040 3030 5p 0p 1p 1p 2p 2 p 3p 3 p 4請根據(jù)以上的遞歸關(guān)系，計算出矩陣連乘積A1 A2A3 A4 所需要的最少數(shù)乘次數(shù)。5. 有這樣一類特殊 0-1 背包問題：可選物品 重量越輕的物品價值越高。n=6，c=20，P=（ 4， 8， 15，1，6，3），W=（ 5，3，2，10，4，8）。其中 n 為物品個數(shù)， c 為背包載重量， P