軟件設(shè)計(jì)師-常用算法設(shè)計(jì)方法

1、軟件設(shè)計(jì)師-常用算法設(shè)計(jì)方法(總分：29.00 ,做題時(shí)間：90分鐘)(總題數(shù)：20,分?jǐn)?shù)：29.00)利用貪心法求解0/1背包問題時(shí)，(26)能夠確保獲得最優(yōu)解。用動(dòng)態(tài)規(guī)劃方求解 O/1背包問題時(shí)，將“用前i個(gè)物品來(lái)裝容量是 x的背包”的0/1背包問題記為KNAP(1, i , X)設(shè)fi(X)是KNAP(1, i , X)最優(yōu)解的 效益值，第j個(gè)物品的重量和放入背包后取得效益值分別為WW p(j=1n),則依次求解f0(X) , fi(X),fn(X)的過程中使用的遞推關(guān)系式為(27) O(分?jǐn)?shù)：2.00)A.優(yōu)先選取重量最小的物品B.優(yōu)先選取效益最大的物品C.優(yōu)先選取單位重量效益最大的物

2、品VD.沒有任何準(zhǔn)則解析：A.f i (X)=minf i-1(X),f i-1(X)+P iB.f i(X)=maxf i-1(X),f i-1(X-Wi )+PiVC.f i(X)=minf i-1(X-Wi),f i-1(X-Wi)+pi)D.f i(X)=maxf i-1(x-Wi),f i-1(X)+P i解析：分析背包問題描述如下：有不同價(jià)值、不同重量的物品 n件，求從這n件物品中選取一部分物品 的選擇方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價(jià)值和最大。0/1背包：對(duì)于每一種物品I裝入背包只有一種選擇，即要么裝入要么不裝入，不能裝入多次或只裝入部分。部分背包則是

3、對(duì)于每一種物品I可以只裝入部分。貪心法就是不求最優(yōu)解，只求可行解的思想，只是局部最優(yōu)，不考慮整體最優(yōu)性。因此對(duì)于貪心法關(guān)鍵是貪心準(zhǔn)則。對(duì)于0/1背包，貪心法之所以不一定得到最優(yōu)解是因?yàn)樗鼰o(wú)法保證最終能將背包容量占滿，背 包空間的閑置使得背包所裝物品的總價(jià)值降低了。動(dòng)態(tài)規(guī)劃法是將一個(gè)不容易解決的較大問題劃分為若干個(gè)易于解決的小問題。1.拉斯維加斯(Las Vegas)算法是一種常用的(3)算法。(分?jǐn)?shù)：1.00)A.確定性B.近似C.概率 VD.加密解析：分析概率算法允許算法在執(zhí)行過程中可隨機(jī)地選擇下一個(gè)計(jì)算步驟。在許多情況下，當(dāng)算法在執(zhí) 行過程中面臨一個(gè)選擇時(shí)，隨機(jī)性選擇常比最優(yōu)選擇要省時(shí)，因

4、此概率算法可以在很大程度上降低算法的 復(fù)雜度。概率算法通常有兩個(gè)優(yōu)點(diǎn)。首先，較之那些我們所知的解決同一一問題最好的確定性算法，概率算法所需 的運(yùn)行時(shí)間或空間通常小一些；其次，迄今為止所發(fā)現(xiàn)的概率算法總是易于理解和實(shí)現(xiàn)的。概率算法可分為四類，分別是數(shù)值概率算法、蒙特卡羅算法(Monte Karlo)、拉斯維加斯算法(Las Vegas)和舍伍德算法(Sherwood)。2 .用遞歸算法實(shí)現(xiàn)n個(gè)相異元素構(gòu)成的有序序列的二分查找，采用一個(gè)遞歸工作棧時(shí)，該棧的最小容量應(yīng) 為(11)。(分?jǐn)?shù)：1.00)A.nB.n/2C.log 2nD.log 2(n+1)V解析：分析根據(jù)二分查找的過程，由于需要棧結(jié)構(gòu)

5、實(shí)現(xiàn)遞歸算法，棧的容量應(yīng)該要保證能存放查找失敗 時(shí)所有未完成運(yùn)行的算法的活動(dòng)記錄。第一次調(diào)用該算法時(shí)，棧中加入了一條查找記錄，表示待查有序表中元素的個(gè)數(shù)為n：第二次調(diào)用時(shí)，無(wú)論是在前半?yún)^(qū)還是在后半?yún)^(qū)進(jìn)行查找，棧中又加入了一條查找記錄，所確定的查找區(qū)間中的元素最多為n/2 :第三次調(diào)用時(shí)，棧中又加入了一條查找記錄，所確定的查找區(qū)間中的元素最多為n/4。依次類推，當(dāng)所確定的查找區(qū)間中的元素為。時(shí)，遞歸調(diào)用該算法的次數(shù)為log 2(n+1)次，查找結(jié)束。3 .快速排序算法采用的設(shè)計(jì)方法是(23)。(分?jǐn)?shù)：1.00)A.動(dòng)態(tài)規(guī)劃法(Dynamic Programming)B.分治法(Divideand

6、 Conquer) VC.回溯法(Backtracking)D.分枝定界法(Branch and Bound)解析：分析快速排序算法采用的設(shè)計(jì)方法是分治法。4 .采用動(dòng)態(tài)規(guī)劃策略求解問題的顯著特征是滿足最優(yōu)性原理，其含義是 (29)。(分?jǐn)?shù)：1.00)A.當(dāng)前所作出的決策不會(huì)影響后面的決策B.原問題的最優(yōu)解包含其子問題的最優(yōu)解VC.問題可以找到最優(yōu)解，但利用貪心法不能找到最優(yōu)解D.每次決策必須是當(dāng)前看來(lái)最優(yōu)的決策才可以找到最優(yōu)解解析：分析動(dòng)態(tài)規(guī)劃策略設(shè)計(jì)算法的第一步通常是刻畫最優(yōu)解結(jié)構(gòu)。當(dāng)問題的最優(yōu)解包含了子問題的最 優(yōu)解時(shí)，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)提供了該問題可用動(dòng)態(tài)

7、規(guī)劃算法求解的重 要線索。動(dòng)態(tài)規(guī)劃策略設(shè)計(jì)算法利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造 出整個(gè)問題的最優(yōu)解。5 .在分支一限界算法設(shè)計(jì)策略中，通常采用 搜索問題的解空間。(分?jǐn)?shù)：1.00)A.深度優(yōu)先B.廣度優(yōu)先 VC.自底向上D.拓?fù)湫蛄薪馕觯悍治龇种?限界算法是在問題的解空間樹上搜索問題解的算法，它的求解目標(biāo)是找出滿足約束條 件的一個(gè)解，或是在滿足約束條件的解中找出一個(gè)目標(biāo)函數(shù)達(dá)到極大或極小的解，即在某種意義下的最優(yōu) 解。分支一限界算法以廣度優(yōu)先的方式搜索解空間，其搜索策略是在擴(kuò)展節(jié)點(diǎn)處先生成其所有的兒子節(jié)點(diǎn)，然 后再?gòu)漠?dāng)前節(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展節(jié)點(diǎn)。6.下

8、面的程序段違反了算法的 (2)原則。Void sam()int n=2; while(!odd(n) n+=2 printf(n);(分?jǐn)?shù)：1.00)A.有窮性 VB.確定性C.可行性D.健壯性解析：分析一個(gè)算法要求必須總是在執(zhí)行有窮步之后結(jié)束，并月-每一步都可在有窮時(shí)間內(nèi)完成。上述程序段違反了算法的有窮性性質(zhì)，理論上將導(dǎo)致過程不可終止。設(shè)求解某問題的遞歸算法如下：F(int n) if n=1Move(1) elseF(n-1)； Move(n)；F(n-1)；求解該算法的計(jì)算時(shí)間時(shí)，僅考慮算法 Move所做的計(jì)算為主要計(jì)算，且 Move為常數(shù)級(jí)算法。則算法 F的 計(jì)算時(shí)間T(n)的遞推關(guān)系

9、式為_(9)_;設(shè)算法Move的計(jì)算時(shí)間為k,當(dāng)n=4時(shí)，算法F的計(jì)算時(shí)間為(10)。(分?jǐn)?shù)：2.00)A.T(n)=T(n-1)+1B.T(n)=2T(n-1)C.T(n)=2T(n-1)+1 VD.T(n)=2T(n+1)+1解析：A.14kB.15k VC.16kD.17k解析：分析考慮遞推關(guān)系時(shí)，只要看 else部分，顯然有：T(n)=2T(n-1)+1 。T(1)=1 ,據(jù)上述遞推關(guān)系 可得 T(4)=15。7 .貪婪法是一種(20)的算法。(分?jǐn)?shù)：1.00)A.不求最優(yōu)，只求滿意VB.只求最優(yōu)C.求取全部可行解D.求取全部最優(yōu)解解析：分析貪心法是一種不追求最優(yōu)解，只希望得到較為滿意

10、解的方法。貪心法(或稱貪婪法)一般可以快速得到滿意的解，因?yàn)樗∪チ藶槲易顑?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。在數(shù)據(jù)壓縮編碼的應(yīng)用中，哈夫曼 (Huffman)算法可以用來(lái)構(gòu)造具有 (18)的二叉樹，這是一種采用了 (19) 的算法。一(分?jǐn)?shù)：2.00)A.前綴碼8 .最優(yōu)前綴碼 VC.后綴碼D.最優(yōu)后綴碼解析：A.貪心 VB.分治C.遞推D.回溯解析：分析給定一個(gè)序列的集合，若不存在一個(gè)序列是另一個(gè)序列的前綴，則該序列集合稱為前綴碼。相反，給定一個(gè)序列的集合，若不存在一個(gè)序列是另一個(gè)序列的后綴，則該序列集合稱為后綴碼。平均碼長(zhǎng)或文件總長(zhǎng)最小的前綴編碼稱為最優(yōu)的前綴碼，最優(yōu)的前綴碼對(duì)文件的

11、壓縮效果亦最佳。利用哈夫曼樹很容易求出給定字符集及其概率分布的最優(yōu)前綴碼。哈夫曼編碼是一種應(yīng)用廣泛且非常有效 的數(shù)據(jù)壓縮技術(shù)，該技術(shù)一般可將數(shù)據(jù)文件壓縮掉20%- 90%其壓縮效率取決于被壓縮文件的特征。在構(gòu)造哈夫曼樹的過程中，每次都是選取兩棵最小權(quán)值的二叉樹進(jìn)行合并，因此使用的是貪心算法。以下不屬于算法的基本特征的是 。窮舉法的適用范圍是(8)。(分?jǐn)?shù)：2.00)A.有確切定義的B.可行的C.可描述的D.不能有二義性解析：暫缺答案A. 一切問題B.解的個(gè)數(shù)極多的問題C.解的個(gè)數(shù)不太多的問題D.不適合設(shè)計(jì)算法解析：暫缺答案分析此題是考查算法的基本特征以及窮舉法的適用范圍，這些都很好理解，相信大

12、家都能選擇正確。8 .利用動(dòng)態(tài)規(guī)劃法求解每對(duì)節(jié)點(diǎn)之間的最短路徑問題時(shí)，設(shè)有向圖Gn V, E共有n個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)編號(hào)1n,設(shè)C是G的成本鄰接矩陣，用 Q(i,j)表示從i至U j并且不經(jīng)過編號(hào)比k還大的節(jié)點(diǎn)的最短路徑的長(zhǎng)度 (Dn(i,j)即為圖G中節(jié)點(diǎn)i至打的最短路徑長(zhǎng)度)，則求解該問題的遞推關(guān)系式為 (28)。(分?jǐn)?shù)：1.00)A.Dk(i,j)=D k-1(i,j)+C(i,j)B.Dk(i,j戶minD k-1(i,j),Dk-1(i,j)+C(i,j)C.Dk(i,j)=Dk-1(i,k)+Dk-1(k,j)D.Dk(i,j)=minD k-1(i,j),Dk-1(i,k)+D k-1

13、(k,j)V解析：分析從“Dk(i,j)表示從i至Uj并且不經(jīng)過編號(hào)比k還大的節(jié)點(diǎn)的最短路徑的長(zhǎng)度”中，我們得 到一個(gè)提示，在求i,j之間最短路徑的時(shí)候，會(huì)考慮它經(jīng)過哪些節(jié)點(diǎn)能縮短原來(lái)的路徑。在Q(i,j)=minDk-1(i,j),Dk-1(i,k)+Dk-1(k,j)中，Q(i,j) 表示 i 至U j 不經(jīng)過 k 的路徑長(zhǎng)度，而Dk-1(I,k)+Dk-1(k,j) 表示i至U j經(jīng)過k的路徑長(zhǎng)度，且 min()函數(shù)用于找最小值，所以此式正確。9 .算法是對(duì)問題求解過程的一類精確描述，算法中描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本操作在限定時(shí) 間內(nèi)執(zhí)行有限次來(lái)實(shí)現(xiàn)的，這句話說明算法具有 特性

14、。(分?jǐn)?shù)：1.00)A.正確性B.確定性C.可行性 VD.健壯性解析：分析一個(gè)算法具有下列5個(gè)重要特性。有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時(shí)間內(nèi)完成。確定性：算法中的每一條指令必須有確切的含義，讀者理解時(shí)不會(huì)產(chǎn)生二義性，并且在任何條件下，算法只有惟一的一條執(zhí)行路徑，即對(duì)于相同的輸入只能得出相同的輸出?？尚行裕阂粋€(gè)算法是可行的，即算法中描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)的。輸入：一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定的對(duì)象的集合。輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸入有著某些特定關(guān)系的量。綜卜所述，算法中的操作都是可以通過已

15、經(jīng)實(shí)現(xiàn)的基本操作在限定時(shí)間內(nèi)執(zhí)行有限次來(lái)實(shí)現(xiàn)的，這句話說 明了算法的可行性特點(diǎn)。在下列算法設(shè)af方法中，(16)在求解問題的過程中并不從整體最優(yōu)上加以考慮，而是作出在當(dāng)前看來(lái)是最好的選擇。利用該設(shè)計(jì)方法可以解決(17)問題。(分?jǐn)?shù)：2.00)A.分治法B.貪心法 VC.動(dòng)態(tài)規(guī)劃法D.回溯法解析：A.排序B.檢索C.背包 VD.0/1背包解析：分析貪心法是這樣的一種解題方法：逐步給出解的各部分，在每一步“貪婪地”選擇最好的部分解，但不顧及這樣選擇對(duì)整體的影響，因此一般得到的不是最好的解。解決背包問題：有不同價(jià)值、不同重量的物品n件，求從這n件物品中選取一部分物品的選擇方案，使選中物品的總重量不超

16、過指定的限制重量，但選中物品的價(jià)值之和最大。較高效率地解決背包問題一般用遞歸和貪心算法，而背包問題規(guī)模不是很大的時(shí)候，也可以采用窮舉法。對(duì)于求取兩個(gè)長(zhǎng)度為n的字符串的最長(zhǎng)公共子序列(LCS)問題，利用(24)策略可以有效地避免子串最長(zhǎng)公 共子序列的重復(fù)計(jì)算，得到時(shí)間復(fù)雜度為O(n2)的正確算法。串1, 0, 0, 1, O, 1, 0, 1和 0, 1, 0,1, 1,0,1 , 1的最長(zhǎng)公共子序列的長(zhǎng)度為(25) o(分?jǐn)?shù)：2.00)A.分治B.貪心C.動(dòng)態(tài)規(guī)劃D.分支一限界解析：暫缺答案A.3B.4C.5D.6解析：暫缺答案分析經(jīng)常會(huì)遇到復(fù)雜問題不能簡(jiǎn)單地分解成幾個(gè)子問題，而會(huì)分解出一系列

17、子問題的情況。簡(jiǎn)單地采用 把大問題分解成子問題，并綜合子問題的解導(dǎo)出大問題解的方法，則問題求解的時(shí)間會(huì)按問題規(guī)模呈嘉級(jí) 數(shù)增加。為了節(jié)約重復(fù)求相同子問題的時(shí)間，引入一個(gè)數(shù)組，不管它們是否對(duì)最終解有用，把所有子問題的解存于 該數(shù)組中，這就是動(dòng)態(tài)規(guī)劃法所采用的基本方法。10.設(shè)某算法的計(jì)算時(shí)間可用遞推關(guān)系式T(n)=2T(n/2)+n 表示，則該算法的時(shí)間復(fù)雜度為 。(分?jǐn)?shù)：1.00)A.O(lgn)B.O(nlgn) 7C.O(n)D.O(n2)解析：分析運(yùn)用數(shù)學(xué)遞推公式，可以推算出數(shù)量級(jí)O(nlgn)。11.用迭代法求解方程x5-x-1=0 ,下列迭代公式不可能正確的是(6)。(分?jǐn)?shù)：1.00

18、)A.B.C.D. V解析：分析迭代法中要求迭代公式與原方程有共同的不同點(diǎn)。其中顯然選項(xiàng)D不符合。遞歸算法的執(zhí)行過程，一般來(lái)說，可先后分成 (12)和(13)兩個(gè)階段。(分?jǐn)?shù)：2.00)A.試探B.遞推 VC.枚舉D.分析解析：A.回溯B.回歸 7C.返回D.合成解析：分析遞歸算法的執(zhí)行過程分遞推和回歸兩個(gè)階段。在遞推階段，由較復(fù)雜的問題的求解推到比原 問題簡(jiǎn)單一些的問題的求解。在回歸階段，當(dāng)獲得最簡(jiǎn)單情況的解后，逐級(jí)返回，依次獲得稍復(fù)雜問題的 解。以關(guān)鍵字比較為基礎(chǔ)的排序算法在最壞情況下的計(jì)算時(shí)間下界為O(nlogn)。下面的排序算法中，最壞情況下計(jì)算時(shí)間可以達(dá)到 O(nlogn)的是(21),該算法采用的設(shè)計(jì)方法是(22)。(分?jǐn)?shù)：2.00)A.歸并排序 VB.插入排序C.選擇排序D.冒泡排序解析：A.分治法 VB.貪心法C.動(dòng)態(tài)規(guī)劃方法D.回溯法解析：分析直接插入排序、簡(jiǎn)單選擇排序和冒泡排序最壞情況下的計(jì)算時(shí)間可以達(dá)到O(n*n),而歸并排序的時(shí)間在最壞情況下可達(dá)到O(nlog