13計(jì)科算法設(shè)計(jì)匯總

1、題組選擇題1、二分搜索算法是利用（）實(shí)現(xiàn)的算法。A分治策略 B、動(dòng)態(tài)規(guī)劃法C、貪心法7、衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（C ）。A運(yùn)行速度快B占用空間少C時(shí)間復(fù)雜度高低8、以下不可以使用分治法求解的是（D ）。A棋盤覆蓋問題B選擇問題C歸并排序D 0/1D、回溯法D代碼短背包問題4.矩陣連乘問題的算法可由動(dòng)態(tài)規(guī)劃 設(shè)計(jì)實(shí)現(xiàn)。14.哈弗曼編碼的貪心算法所需的計(jì)算時(shí)間為（A、O (n2n)B O(nlogn )C、0(2n)D O (n)16最長公共子序列算法利用的算法是（）。A分支界限法B動(dòng)態(tài)規(guī)劃法C貪心法D回溯法17.實(shí)現(xiàn)棋盤覆蓋算法利用的算法是A、分治法B動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法18.下面是

2、貪心算法的基本要素的是（A、重疊子問題B構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)定義最優(yōu)解31、下列算法中不能解決0/1背包問題的是（A ）A貪心法B動(dòng)態(tài)規(guī)劃C回溯法D分支限界法 32、回溯法搜索狀態(tài)空間樹是按照（C ）的順序。A中序遍歷B廣度優(yōu)先遍歷C深度優(yōu)先遍歷D層次優(yōu)先遍歷34.實(shí)現(xiàn)合并排序利用的算法是）。A分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D回溯法40、背包問題的貪心算法所需的計(jì)算時(shí)間為A、0 (n2n)B、O (nlogn )C、0 (2n)D、O(n)填空題1.算法的復(fù)雜性有時(shí)間復(fù)雜性和空間復(fù)雜性之分。2、程序是算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。3、算法的“確定性”指的是組成算法的每條指令 是清晰

3、的，無歧義的。6算法是指解決問題的一種方法或一個(gè)過程。7、從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的程序一般是 遞歸算法。8、問題的最優(yōu)子結(jié)構(gòu)性質(zhì) 是該問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。9、以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為回溯法10、數(shù)值概率算法常用于 數(shù)值問題的求解。問答題6考慮用哈夫曼算法來找字符a,b,c,d,e,f的最優(yōu)編碼。這些字符出現(xiàn)在文件中的頻數(shù)之比為 20:10:6:4:44:16。要求:(1)( 4分）簡述使用哈夫曼算法構(gòu)造最優(yōu)編碼的基本步驟;(2)(5分）構(gòu)造對(duì)應(yīng)的哈夫曼樹，并據(jù)此給出a,b,c,d,e,f的一種最優(yōu)編碼。解：1）、哈夫曼算法是構(gòu)造最優(yōu)編

4、碼樹的貪心算法。其基本思想是，首先所有字符對(duì)應(yīng)n棵樹構(gòu)成的森林，每棵樹只有一個(gè)結(jié)點(diǎn)，根權(quán)為對(duì)應(yīng)字符的頻率。然后，重復(fù)下列過程n-1次：將森林中的根權(quán)最小的兩棵樹進(jìn)行合并產(chǎn)生一個(gè)新樹，該新樹根的兩個(gè)子樹分別是參與合并的兩棵子樹，根權(quán)為兩個(gè)子樹根權(quán)之和。2）、根據(jù)題中數(shù)據(jù)構(gòu)造哈夫曼樹如下圖所示。10G由此可以得出a,b,c,d,e,f 的一組最優(yōu)的編碼：01,0000,00010,00011,1,001題組1. 一個(gè)算法就是一個(gè)有窮規(guī)則的集合，其中之規(guī)則規(guī)定了解決某一特殊類型問題的一系列運(yùn)算， 此外， 算法還應(yīng)具有以下五個(gè)重要特 性:,之分，衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是2. 算法的復(fù)雜性有O3. 某一

5、問題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征是 o4. 若序列X=B,C,A,D,B,C,D Y=A,C,B,A,B,D,C,D請(qǐng)給出序列 X和丫的一個(gè)最長公共子序列O5. 用回溯法解問題時(shí)，應(yīng)明確定義問題的解空間，問題的解空間至少應(yīng)包含_6. 動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干 ,先求解然后從這些的解得到原問題的解。o,用動(dòng)態(tài)規(guī)劃算法所需的計(jì)算時(shí)7. 以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為8.0-1背包問題的回溯算法所需的計(jì)算時(shí)間為 間為o禾n實(shí)現(xiàn)的算法。9. 動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素是 10. 二分搜索算法是利用 答案：一、填空一個(gè)或多個(gè)輸出1確定性 有窮性 可行性 0 個(gè)或多個(gè)輸入2

6、.時(shí)間復(fù)雜性 空間復(fù)雜性 時(shí)間復(fù)雜度高低3. 該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)4. BABCD或CABCD或CADCD5. 一個(gè)（最優(yōu)）解6. 子問題 子問題 子問題7. 回溯法8. o（n*2n） o（minnc,2n）9. 最優(yōu)子結(jié)構(gòu) 重疊子問題10. 動(dòng)態(tài)規(guī)劃法2、下列不是動(dòng)態(tài)規(guī)劃算法基本步驟的是（A ）。A、找出最優(yōu)解的性質(zhì)B、構(gòu)造最優(yōu)解C、5. 回溯法解旅行售貨員問題時(shí)的解空間樹是（ 子集樹算出最優(yōu)解 D定義最優(yōu)解A）。A、B、C、D、排列樹 深度優(yōu)先生成樹 廣度優(yōu)先生成樹6A、B、C、D、下列算法中通常以自底向上的方式求解最優(yōu)解的是（ 備忘錄法動(dòng)態(tài)規(guī)劃法貪心法回溯法B ）。7、衡量一個(gè)算法

7、好壞的標(biāo)準(zhǔn)是（C）。A運(yùn)行速度快 B占用空間少C時(shí)間復(fù)雜度低D代碼短9. 實(shí)現(xiàn)循環(huán)賽日程表利用的算法是（ A 分治策略）。A、B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法題組三1. 算法分析是（ C）A. 將算法用某種程序設(shè)計(jì)語言恰當(dāng)?shù)乇硎境鰜鞡. 在抽象數(shù)據(jù)集合上執(zhí)行程序，以確定是否會(huì)產(chǎn)生錯(cuò)誤的結(jié)果 存儲(chǔ)空間作定量分析D證明算法對(duì)所有可能的合法輸入都能算出正確的答案2. 算法與程序的區(qū)別在于算法具有（C）A.能行性B.確定性4. 衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（C）A.運(yùn)行速度快B.占用空間少C時(shí)間復(fù)雜度低D.代碼短5. 二分搜索算法是利用（A）實(shí)現(xiàn)的算法。A.分治法B.動(dòng)態(tài)規(guī)劃法C.貪心法D.回溯法6.

8、下面問題（B ）不能使用貪心法解決。A.單源最短路徑問題 B. N皇后問題 C.最小代價(jià)生成樹問題 7用貪心法設(shè)計(jì)算法的關(guān)鍵是（C對(duì)算法需要多少計(jì)算時(shí)間和C有窮性D輸入和輸出D. 背包問題B ）。A.將問題分解為多個(gè)子問題來分別處理B.選好最優(yōu)量度標(biāo)準(zhǔn)C獲取各階段間的遞推關(guān)系式D.滿足最優(yōu)性原理8. 找最小生成樹的算法 Kruskal的時(shí)間復(fù)雜度為（D）（其中n為無向圖的結(jié)點(diǎn)數(shù)，m為邊數(shù)） AO（n2）BO（mlogn）CO（nlogm） DO（mlogm）9. 回溯法搜索狀態(tài)空間樹是按照（C ）的順序。A.中序遍歷B.廣度優(yōu)先遍歷 C.深度優(yōu)先遍歷 D.層次優(yōu)先遍歷10. 一個(gè)問題可用動(dòng)態(tài)規(guī)

9、劃算法或貪心算法求解的關(guān)鍵特征是問題的（B）A.重疊子問題B.最優(yōu)子結(jié)構(gòu)性質(zhì)C.最優(yōu)量度標(biāo)準(zhǔn)性質(zhì)D.定義最優(yōu)解1. 算法的復(fù)雜性有 和之分，衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是2. 某一問題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征是A=xzyzzyx, B=zxyyzxz,請(qǐng)給出序列A和B的一個(gè)最長公共子序列4.動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干 從這些 的解得到原問題的解。5.0-1 背包問題的回溯算法所需的計(jì)算時(shí)間為為先求解O。 3. 若序列。,然后,用動(dòng)態(tài)規(guī)劃算法所需的計(jì)算時(shí)間6. 二分法搜索算法是利用 實(shí)現(xiàn)的算法。答案 ：1.時(shí)間、空間 時(shí)間復(fù)雜度空間復(fù)雜度。2.算法效率 3.xyzz.4.子問

10、題 子問題 子問題 5.o（n*2n） 6.動(dòng)態(tài)規(guī)劃法2.算法的復(fù)雜性有和之分，衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是2.時(shí)間復(fù)雜性 /空間復(fù)雜性 /時(shí)間復(fù)雜度高低3. 若序列 X二B,C,A,D,B,C,D丫二A,C,B,A,B,D,C,D請(qǐng)給出序列 X和丫的一個(gè)最長公共子序列3.BABCD或CABCD或CADCD1.（ D ）是貪心算法與動(dòng)態(tài)規(guī)劃算法的共同點(diǎn)。A、重疊子問題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D、最優(yōu)子結(jié)構(gòu)性質(zhì)2.哈夫曼編碼可以利用（C ）算法實(shí)現(xiàn)。A、分治策略 B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回朔法題組四1、二分搜索算法是利用（）實(shí)現(xiàn)的算法。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D 、回溯法2、下

11、列不是動(dòng)態(tài)規(guī)劃算法基本步驟的是（）。A、找出最優(yōu)解的性質(zhì)B 、構(gòu)造最優(yōu)解C 、算出最優(yōu)解D、定義最優(yōu)解3. 回溯法的效率不依賴于下列哪些因素（A.滿足顯約束的值的個(gè)數(shù)D. 確定解空間的時(shí)間4. 矩陣連乘問題的算法可由（規(guī)劃算法C、貪心算法）B. 計(jì)算約束函數(shù)的時(shí)間C. 計(jì)算限界函數(shù)的時(shí)間B）D、回溯算法設(shè)計(jì)實(shí)現(xiàn)。A、分支界限算法B、動(dòng)態(tài)5、使用分治法求解不需要滿足的條件是（ A A 子問題必須是一樣的 B 子問題不能夠重復(fù) 使用相同的方法解 6貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是（A、最優(yōu)子結(jié)構(gòu) B、貪心選擇性質(zhì)C、構(gòu)造最優(yōu)解D、定義最優(yōu)7. 以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為A、分支界限算

12、法B、概率算法C、貪心算法D、回溯算法8. 實(shí)現(xiàn)最長公共子序列利用的算法是（A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法9. 衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（A 運(yùn)行速度快 B 占用空間少）。C 子問題的解可以合并 D 原問題和子問題C ）。）。）。)。 A、 O( n2n)B、 O( nlogn )C 時(shí)間復(fù)雜度低 D 代碼短10、哈弗曼編碼的貪心算法所需的計(jì)算時(shí)間為（ BC、O（2n）D、O（n）二填空題1算法的復(fù)雜性有2、程序是（算法）3、算法的“確定性”指的是組成算法的每條（指令）是清晰的，無歧義的。（時(shí)間）復(fù)雜性和（空間）復(fù)雜性之分。用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。4矩陣連乘問題的算法可由

13、（動(dòng)態(tài)規(guī)劃）設(shè)計(jì)實(shí)現(xiàn)。5、 拉斯維加斯算法找到的解一定是（正確解）。6、 算法是指解決問題的（一種方法）或（一個(gè)過程）。7、 從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的程序一般是（遞歸算法）。8、問題的（最優(yōu)子結(jié)構(gòu)性質(zhì)）是該問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。9、 計(jì)算一個(gè)算法時(shí)間復(fù)雜度通常可以計(jì)算（循環(huán)次數(shù)）、 （基本操作的頻率 ）或計(jì)算步。10、快速排序算法是基于（分治策略）的一種排序算法。三、算法設(shè)計(jì)題寫出歐幾里得迭代算法 (注意是迭代算法 ) int Gcd(int m,int n)If(m=0)return n;If(n=0)return m;while(m0)int c

14、=n%m;n=m;m=c; Return n;題組五1下列不屬于一個(gè)好的算法應(yīng)具有的特性的是（C）A.正確性B.簡明性 C無限性 D最優(yōu)性2矩陣連乘問題的算法可由（B）設(shè)計(jì)實(shí)現(xiàn)。A、分支界限算法B、動(dòng)態(tài)規(guī)劃算法C貪心算法D、回溯算法3廣度優(yōu)先是（A）的一搜索方式。A、分支界限法 B、動(dòng)態(tài)規(guī)劃法 C、貪心法 D、回溯法4學(xué)校要舉行運(yùn)動(dòng)會(huì)，請(qǐng)你設(shè)計(jì)一個(gè)能夠?qū)\(yùn)動(dòng)員分?jǐn)?shù)自動(dòng)排序的軟件, 以下最好的方法和步驟是（ C）如果要設(shè)計(jì)此軟件，A.分析問題，編寫程序，設(shè)計(jì)算法，調(diào)試程序 B設(shè)計(jì)算法，編寫程序，提出問題，調(diào)試程序 C提出問題，設(shè)計(jì)算法，編寫程序，調(diào)試程序 D .設(shè)計(jì)算法，提出問題，編寫程序，調(diào)試

15、程序A）C實(shí)際問題的描述 D、最終結(jié)果5. 用計(jì)算機(jī)程序解決實(shí)際問題的過程中，需要進(jìn)行算法設(shè)計(jì)，算法指的是（A、解決問題的方法和步驟B、數(shù)值計(jì)算的方法6. 算法分析是（ C）。B 在抽象數(shù)據(jù)集合上執(zhí)行程序，以確D. 證明算法對(duì)所有可能的合法輸A. 將算法用某種程序設(shè)計(jì)語言恰當(dāng)?shù)乇硎境鰜?定是否會(huì)產(chǎn)生錯(cuò)誤的結(jié)果C.對(duì)算法需要多少計(jì)算時(shí)間和存儲(chǔ)空間作定量分析B ）。入都能算出正確的答案7. 用貪心法設(shè)計(jì)算法的關(guān)鍵是（A.將問題分解為多個(gè)子問題來分別處理B.選好貪心準(zhǔn)則C.獲取各階段間的遞推關(guān)系式D 滿足最優(yōu)性原理8.考慮背包問題： n=6， M=10， V（1:6）=（15,59,21,30,60

16、,5） ， W（1:6）=（1,5,2,3,6,1 ）。該問題的 最大效益值為（ C ）。若把它看著是 0/1 背包問題，則最大效益值為（A. 101 B. 110 C. 115 D. 120 11.算法確認(rèn)是（ B ）。A.將算法用某種程序設(shè)計(jì)語言恰當(dāng)?shù)乇硎境鰜?算出正確的答案C.對(duì)算法需要多少計(jì)算時(shí)間和存儲(chǔ)空間作定量分析確定是否會(huì)產(chǎn)生錯(cuò)誤的結(jié)果B ）。B.證明算法對(duì)所有可能的合法輸入都能D.在抽象數(shù)據(jù)集合上執(zhí)行程序，以12.算法與程序的區(qū)別在于算法具有（A 能行性 B.確定性14.算法直接插入排序在 （ D）。A 14 B. 28 C. 7 D.15. 二分搜索算法是利用22（A）實(shí)現(xiàn)的算

17、法。3.4.5.6. _【_貪心法】 _和_【 動(dòng)態(tài)規(guī)劃法】 _要求問題最優(yōu)解具有最優(yōu)子結(jié)構(gòu)特性。7. 使用剪枝函數(shù)的深度優(yōu)先生成狀態(tài)空間樹中結(jié)點(diǎn)的求解方法稱為_【回溯法】9.所謂最優(yōu)子結(jié)構(gòu)性質(zhì)是指【問題的最優(yōu)解包含了其子問題的最優(yōu)解】C ）。C.有窮性 D.輸入和輸出A1.8=45,33,24,45,12,12,24,12 上運(yùn)行時(shí)執(zhí)行的元素比較次數(shù)為A.分治法 B.動(dòng)態(tài)規(guī)劃法 C貪心法D.回溯法二、填空題（每空 2 分，共 15 個(gè)空）1 算法一般分為： _【精確】算法和【啟發(fā)式】 _算法。2. 一個(gè)合法的遞歸定義包括兩部分：_【基礎(chǔ)情況 】_和_【 遞歸部分】一個(gè)算法的 【時(shí)間復(fù)雜度】

18、是指算法運(yùn)行所需要的時(shí)間。如果無向連通圖G中不包含任何關(guān)節(jié)點(diǎn)，則稱該圖G為_【_雙連通圖。】_【合并排序 】_的基本運(yùn)算是把兩個(gè)或多個(gè)有序序列合并成一個(gè)有序序列。 _【_貪心法】 _和_【 動(dòng)態(tài)規(guī)劃法】子集樹】 _ 算法框架與 _【排列樹】10.回溯法的算法框架按照問題的解空間一般分為_算法框架11.若序列A=xzyzzyx, B=zxyyzxz,請(qǐng)給出序列 A和B的一個(gè)最長公共子序列 _【_XYZZJ簡答題1、分治法的基本思想？分治法的基本思想是將一個(gè)規(guī)模為 n 的問題分解為 k 個(gè)規(guī)模較小的子問題， 這些子問題 互相獨(dú)立且與原問題相同。 遞歸的解這些子問題， 然后將各子問題的解合并得到原問

19、題的解。2、簡述動(dòng)態(tài)規(guī)劃的算法步驟。找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征； 遞歸地定義最優(yōu)值； 以自底向上的方式計(jì)算出最優(yōu)值； 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解3、簡述貪心算法與動(dòng)態(tài)規(guī)劃法的基本要素。貪心算法的基本要素：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。 動(dòng)態(tài)規(guī)劃算法的基本要素是：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)。4、簡述回溯法的算法步驟。1.針對(duì)所給問題，定義問題的解空間；2.確定易于搜索的解空間結(jié)構(gòu)；3. 以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。算法設(shè)計(jì)大題1、求兩個(gè)數(shù)的最大公約數(shù) , 歐幾里德算法int gcd(int m, int n) int r;while (n!=0) r = m % n;m = n;n = r;return m;2、寫一函數(shù)，判斷某個(gè)數(shù)是否素?cái)?shù)，以及求1 1000 之內(nèi)的素?cái)?shù)3、選擇排序（冒泡排序）4、順序查找5、在 n 個(gè)元素中找最大值和最小值#includeusing namespace std;void maxmin(int a,int n,int &max,int &min)max = min = a0;for (int i = 1; i max) max = ai;if (ai min) min = ai;int main() int a = 4,7,2,5,9,6,8,3;int s, t;maxmin(a, 8,