算法分析作業(yè)

1、算法分析練習(xí)題（一）一、選擇題1、二分搜索算法是利用（   A      ）實(shí)現(xiàn)的算法。A、分治策略   B、動(dòng)態(tài)規(guī)劃法   C、貪心法    D、回溯法2、下列不是動(dòng)態(tài)規(guī)劃算法基本步驟的是（   A    ）。A、找出最優(yōu)解的性質(zhì)   B、構(gòu)造最優(yōu)解   C、算出最優(yōu)解   D、定義最優(yōu)解3下列算法中通常以自底向上的方式求解最

2、優(yōu)解的是（   B      ）。A、備忘錄法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法4、衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（C ）。A 運(yùn)行速度快 B 占用空間少 C 時(shí)間復(fù)雜度低 D 代碼短5、以下不可以使用分治法求解的是（D ）。A 棋盤覆蓋問題 B 選擇問題 C 歸并排序 D 0/1背包問題6. 實(shí)現(xiàn)循環(huán)賽日程表利用的算法是（    A      ）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法7.備忘錄方法是那種算法的變形。（ B

3、 ）A、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法8最長(zhǎng)公共子序列算法利用的算法是（    B       ）。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法9實(shí)現(xiàn)棋盤覆蓋算法利用的算法是（     A      ）。A、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法10. 矩陣連乘問題的算法可由（         

4、; B）設(shè)計(jì)實(shí)現(xiàn)。A、分支界限算法      B、動(dòng)態(tài)規(guī)劃算法    C、貪心算法    D、回溯算法11、Strassen矩陣乘法是利用（    A     ）實(shí)現(xiàn)的算法。A、分治策略   B、動(dòng)態(tài)規(guī)劃法   C、貪心法    D、回溯法12、使用分治法求解不需要滿足的條件是（A ）。A 子問題必須是一樣的B 子問題不能夠重復(fù)

5、C 子問題的解可以合并D 原問題和子問題使用相同的方法解13、下列算法中不能解決0/1背包問題的是（A ）A 貪心法 B 動(dòng)態(tài)規(guī)劃 C 回溯法 D 分支限界法14實(shí)現(xiàn)合并排序利用的算法是（     A    ）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法15下列是動(dòng)態(tài)規(guī)劃算法基本要素的是（  D     ）。A、定義最優(yōu)解B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、子問題重疊性質(zhì)16下列算法中通常以自底向下的方式求解最優(yōu)解的是（   

6、 B     ）。A、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法17、合并排序算法是利用（   A      ）實(shí)現(xiàn)的算法。A、分治策略   B、動(dòng)態(tài)規(guī)劃法   C、貪心法    D、回溯法18實(shí)現(xiàn)大整數(shù)的乘法是利用的算法（      C   ）。A、貪心法B、動(dòng)態(tài)規(guī)劃法C、分治策略D、回溯法19. 實(shí)現(xiàn)最大子段和利用的

7、算法是（     B      ）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法20. 一個(gè)問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的（   B          ）。A、重疊子問題B、最優(yōu)子結(jié)構(gòu)性質(zhì)C、貪心選擇性質(zhì)D、定義最優(yōu)解21. 實(shí)現(xiàn)最長(zhǎng)公共子序列利用的算法是（     B   

8、   ）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法二、填空題1.算法的復(fù)雜性有 時(shí)間 復(fù)雜性和 空間 復(fù)雜性之分。2、程序是  算法   用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。3、算法的“確定性”指的是組成算法的每條 指令 是清晰的，無歧義的。4.矩陣連乘問題的算法可由 動(dòng)態(tài)規(guī)劃 設(shè)計(jì)實(shí)現(xiàn)。5、算法是指解決問題的 一種方法 或 一個(gè)過程 。6、從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的程序一般是 遞歸算法 。7、矩陣連乘問題的算法可由 動(dòng)態(tài)規(guī)劃 設(shè)計(jì)實(shí)現(xiàn)。8. 動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干 子問題 ，先求解 子問題

9、，然后從這些 子問題 的解得到原問題的解。9.算法是由若干條指令組成的有窮序列，且要滿足輸入、 輸出 、確定性和 有限性 四條性質(zhì)。10、大整數(shù)乘積算法是用 分治法 來設(shè)計(jì)的。11.快速排序算法是基于 分治策略 的一種排序算法。12.動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素是. 性質(zhì)和 性質(zhì) 。13.任何可用計(jì)算機(jī)求解的問題所需的時(shí)間都與其 規(guī)模 有關(guān)。14.快速排序算法的性能取決于 劃分的對(duì)稱性 。15、出自于“平衡子問題”的思想，通常分治法在分割原問題，形成若干子問題時(shí)，這些子問題的規(guī)模都大致 相同 。16、使用二分搜索算法在n個(gè)有序元素表中搜索一個(gè)特定元素，在最佳情況下，搜索的時(shí)間復(fù)雜性為O（），在最

10、壞情況下，搜索的時(shí)間復(fù)雜性為O（ logn ）。17、已知一個(gè)分治算法耗費(fèi)的計(jì)算時(shí)間T(n)，T(n)滿足如下遞歸方程：解得此遞歸方可得T(n)= O（  nlogn ）。18、動(dòng)態(tài)規(guī)劃算法有一個(gè)變形方法 備忘錄方法 。這種方法不同于動(dòng)態(tài)規(guī)劃算法“自底向上”的填充方向，而是“自頂向下”的遞歸方向，為每個(gè)解過的子問題建立了備忘錄以備需要時(shí)查看，同樣也可避免相同子問題的重復(fù)求解。19、遞歸的二分查找算法在divide階段所花的時(shí)間是 O(1) ，conquer階段所花的時(shí)間是  T(n/2)  ，算法的時(shí)間復(fù)雜度是 O( log n) 。 20、用

11、動(dòng)態(tài)規(guī)劃算法計(jì)算矩陣連乘問題的最優(yōu)值所花的時(shí)間是 O(n3) ， 子問題空間大小是  O(n2)  。21、一個(gè)算法的優(yōu)劣可以用（時(shí)間復(fù)雜度）與（空間復(fù)雜度）與來衡量。22、直接或間接地調(diào)用自身的算法稱為（遞歸算法）。23、q 記號(hào)在算法復(fù)雜性的表示法中表示（漸進(jìn)確界或緊致界）。24、在分治法中，使子問題規(guī)模大致相等的做法是出自一種（平衡子問題）的思想。25、動(dòng)態(tài)規(guī)劃算法適用于解（具有某種最優(yōu)性質(zhì)）問題。26、最優(yōu)子結(jié)構(gòu)性質(zhì)的含義是（問題的最優(yōu)解包含其子問題的最優(yōu)解）。27、按照符號(hào)O的定義O(f)+O(g)等于O(maxf(n),g(n)。28、二分搜索技術(shù)是運(yùn)用（分治）

12、策略的典型例子。29、動(dòng)態(tài)規(guī)劃算法中，通常不同子問題的個(gè)數(shù)隨問題規(guī)模呈（多項(xiàng)式）級(jí)增長(zhǎng)。30、（最優(yōu)子結(jié)構(gòu)性質(zhì)）和（子問題重疊性質(zhì)）是采用動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素。三、算法填空1.最大子段和: 動(dòng)態(tài)規(guī)劃算法int MaxSum(int n, int a) int sum=0, b=0； /sum存儲(chǔ)當(dāng)前最大的bj, b存儲(chǔ)bj for(int j=1； j<=n； j+) if（b>0） b+=aj ； else b=ai ； /一旦某個(gè)區(qū)段和為負(fù)，則從下一個(gè)位置累和 if (b>sum) sum=b ； return sum； 2.快速排序template<clas

13、s Type>void QuickSort (Type a, int p, int r) if (p<r) int q=Partition(a,p,r); QuickSort（a，p，q-1） ; /對(duì)左半段排序 QuickSort(a,q+1,r) ; /對(duì)右半段排序 四、簡(jiǎn)答題1、寫出下列復(fù)雜性函數(shù)的偏序關(guān)系（即按照漸進(jìn)階從低到高排序）：2、將所給定序列a1:n分為長(zhǎng)度相等的兩段a1:n/2和an/2+1:n，分別求出這兩段的最大子段和，則a1:n的最大子段和有哪三種情形？3、請(qǐng)說明動(dòng)態(tài)規(guī)劃方法為什么需要最優(yōu)子結(jié)構(gòu)性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì)是指大問題的最優(yōu)解包含子問題的最優(yōu)解。

14、60;動(dòng)態(tài)規(guī)劃方法是自底向上計(jì)算各個(gè)子問題的最優(yōu)解，即先計(jì)算子問題的最優(yōu)解，然后再利用子問題的最優(yōu)解構(gòu)造大問題的最優(yōu)解，因此需要最優(yōu)子結(jié)構(gòu)4、設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的主要步驟是怎么的？請(qǐng)簡(jiǎn)述。參考解答：（1）找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(6分)          （2）遞歸地定義最優(yōu)值。          （3）以自底向上的方式計(jì)算出最優(yōu)值。 （4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)

15、解。5、分治法所能解決的問題一般具有哪幾個(gè)特征？請(qǐng)簡(jiǎn)述。參考解答：（1）該問題的規(guī)模縮小到一定的程度就可以容易地解決；(6分)          （2）該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì); （3） 利用該問題分解出的子問題的解可以合并為該問題的解；           （4）原問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公

16、共的子問題。6、算法的要特性是什么？ 參考解答：確定性、可實(shí)現(xiàn)性、輸入、輸出、有窮性7、 算法分析的目的是什么？參考解答：分析算法占用計(jì)算機(jī)資源的情況，對(duì)算法做出比較和評(píng)價(jià)，設(shè)計(jì)出額更好的算法。8、算法的時(shí)間復(fù)雜性與問題的什么因素相關(guān)？ 參考解答：算法的時(shí)間復(fù)雜性與問題的規(guī)模相關(guān)，是問題大小n的函數(shù)。9、算法的漸進(jìn)時(shí)間復(fù)雜性的含義？ 參考解答：當(dāng)問題的規(guī)模n趨向無窮大時(shí)，影響算法效率的重要因素是T(n)的數(shù)量級(jí)，而其他因素僅是使時(shí)間復(fù)雜度相差常數(shù)倍，因此可以用T(n)的數(shù)量級(jí)(階)評(píng)價(jià)算法。時(shí)間復(fù)雜度T(n)的數(shù)量級(jí)(階)稱為漸進(jìn)時(shí)間復(fù)雜性。10簡(jiǎn)述漸進(jìn)時(shí)間復(fù)雜性上界的定義。參考解答：T(n)

17、是某算法的時(shí)間復(fù)雜性函數(shù)，f(n)是一簡(jiǎn)單函數(shù)，存在正整數(shù)No和C，nNo，有T(n)<f(n)，這種關(guān)系記作T(n)=O(f(n)。11快速排序算法最壞情況下需要多少次比較運(yùn)算？參考解答：最壞情況下快速排序退化成冒泡排序，需要比較n2次。12 闡述歸并排序的分治思路。參考解答：講數(shù)組一分為二，分別對(duì)每個(gè)集合單獨(dú)排序，然后將已排序的兩個(gè)序列歸并成一個(gè)含n個(gè)元素的分好類的序列。如果分割后子問題還很大，則繼續(xù)分治，直到一個(gè)元素。13 快速排序的基本思想是什么。 參考解答：快速排序的基本思想是在待排序的N個(gè)記錄中任意取一個(gè)記錄，把該記錄放在最終位置后，數(shù)據(jù)序列被此記錄分成兩部分。所有關(guān)鍵字比該

18、記錄關(guān)鍵字小的放在前一部分，所有比它大的放置在后一部分，并把該記錄排在這兩部分的中間，這個(gè)過程稱作一次快速排序。之后重復(fù)上述過程，直到每一部分內(nèi)只有一個(gè)記錄為止。 14分治法的基本思想是什么？將一個(gè)規(guī)模為N的問題分解為K個(gè)規(guī)模較小的子問題，這些子問題相互獨(dú)立且與原問題性質(zhì)相同。求出子問題的解，就可得到原問題的解。即一種分目標(biāo)完成程序算法，簡(jiǎn)單問題可用二分法完成。15設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的主要步驟？參考解答：（1）找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(6分)          （2）遞歸地定義最優(yōu)值。

19、          （3）以自底向上的方式計(jì)算出最優(yōu)值。 （4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。16分治法與動(dòng)態(tài)規(guī)劃法的異同共同點(diǎn)：將待求解的問題分解成若干子問題，先求解子問題，然后再從這些子問題的解得到原問題的解。不同點(diǎn)：1、適合于用動(dòng)態(tài)規(guī)劃法求解的問題，分解得到的各子問題往往不是相互獨(dú)立的；而分治法中子問題相互獨(dú)立。2、動(dòng)態(tài)規(guī)劃法用表保存已求解過的子問題的解，再次碰到同樣的子問題時(shí)不必重新求解，而只需查詢答案，故可獲得多項(xiàng)式級(jí)時(shí)間復(fù)雜度，效率較高；而分治法中對(duì)于每次出現(xiàn)的子

20、問題均求解，導(dǎo)致同樣的子問題被反復(fù)求解，故產(chǎn)生指數(shù)增長(zhǎng)的時(shí)間復(fù)雜度，效率較低。17分治法所能解決的問題一般具有的幾個(gè)特征？參考解答：（1）該問題的規(guī)模縮小到一定的程度就可以容易地解決；(6分)          （2）該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì); （3） 利用該問題分解出的子問題的解可以合并為該問題的解；           

21、（4）原問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。五、算法設(shè)計(jì)題1.【最長(zhǎng)上升子序列問題】 提示：此題可采用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)對(duì)于給定的一個(gè)序列，。我們可以得到一些遞增上升的子序列，這里。比如，對(duì)于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。這些子序列中最長(zhǎng)的長(zhǎng)度是4，比如子序列(1, 3, 5, 8)。你的任務(wù)：就是對(duì)于給定的序列，求出最長(zhǎng)上升子序列的長(zhǎng)度。要求寫出你設(shè)計(jì)的算法思想及遞推函數(shù)的公式表達(dá)。.2.【Gray碼構(gòu)造問題】 提示：此題可采用分治遞歸算法實(shí)現(xiàn)問題描述：“格雷碼”是一個(gè)長(zhǎng)度為的序列，滿足：（a）每個(gè)元素都是長(zhǎng)度為n比特的串（b）序列中無相同元素（c）連續(xù)的兩個(gè)元素恰好只有1個(gè)比特不同例如：n=2時(shí)，格雷碼為00，01，11，10。Gray碼是一種編碼，這種編碼可以避免在讀取時(shí)，因各數(shù)據(jù)位時(shí)序上的差異造成的誤讀。格雷碼在工程上有廣泛應(yīng)用。但格雷碼不便于運(yùn)算，請(qǐng)你設(shè)計(jì)一種構(gòu)造方法，輸入長(zhǎng)度序列n，輸出格雷碼（你只要做出一種構(gòu)造方案即可，格