算法設(shè)計(jì)分析參考資料重慶大學(xué)網(wǎng)絡(luò)教育.docx

1、算法設(shè)計(jì)分析參考資料一、單項(xiàng)選擇題（本大題共。分，共60小題，每小題0分）C1.算法的時(shí)間復(fù)雜度是指（）C.算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù)C2.衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（）。C. 時(shí)間復(fù)雜度低D3.在最長(zhǎng)公共子序列問(wèn)題中，如果定義ci,j為Xl.Xi和YL.Yj的最長(zhǎng)公共子序列的長(zhǎng) 度，則長(zhǎng)度為m的X序列與長(zhǎng)度為n的Y序列的最長(zhǎng)公共子序列的長(zhǎng)度為（）。D. cm,nD4.以下關(guān)于貪心算法，不正確的說(shuō)法是（）。D.所需求解的問(wèn)題可以不滿足最優(yōu)子結(jié)構(gòu)性質(zhì)C5.合并排序法的基本思想是：將待排序元素分成大小大致相同的（）個(gè)子集合，分別對(duì) 每個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好

2、序的集合。C. 2C6.對(duì)于n個(gè)元素的排序問(wèn)題，n = 2時(shí),只要作（）次比較即可排好序。C. 1A7.二分搜索算法的基本思想是將n個(gè)元素分成個(gè)數(shù)大致相同的兩半，取an/2與x進(jìn) 行比較：如果（），則只要在數(shù)組a的左半部繼續(xù)搜索X。A. x<an/2A8.備忘錄方法的遞歸方式是（）A.自頂向下C9.算法指的是（）。C. 解決問(wèn)題的方法和過(guò)程D10.應(yīng)用Johnson法則的流水作業(yè)調(diào)度采用的算法是（）D. 動(dòng)態(tài)規(guī)劃算法All,算法分析中，記號(hào)。表示（）A. 漸進(jìn)上界B12,在找零錢問(wèn)題中，收銀員算法中所應(yīng)用的貪心規(guī)則的最恰當(dāng)描述是（）。B. 總是選擇不超過(guò)剩余應(yīng)找錢數(shù)的最大面值的硬幣B13

3、.由邊界條件出發(fā),通過(guò)遞推式求f（n）的值，從邊界到求解的全過(guò)程十分清楚的是（）B.遞推D14.考慮最長(zhǎng)公共子序列問(wèn)題的下述遞歸表達(dá)式，如果全部子問(wèn)題組織在一個(gè)ci,j的二維 表格中，則ci,j不依賴于下述哪個(gè)子問(wèn)題：（）。0if / = 0 or j = 0、c/.y = - c/-Ly-l + lif >Oand.匕=yrmax(c/ - hy.7 H) if /<7 >0311(1. = i廠D.同一行的下一列A15.活動(dòng)選擇問(wèn)題就是在所給的活動(dòng)集合中，選出（）的相容活動(dòng)子集。A.當(dāng)前可選活動(dòng)中結(jié)束時(shí)間最早的活動(dòng)A16. 一個(gè)長(zhǎng)度為n英寸的鋼管的最優(yōu)切割問(wèn)題，總共有（）

4、個(gè)不同的子問(wèn)題。A. n+1對(duì)于 aeklu 五個(gè)字符,及其頻度數(shù)據(jù)：=0.32, =0.25, =0.20, =0.18, =0.05。請(qǐng)用 Huffmann 算法構(gòu)造其Huffmann樹(shù)。11.參考答案：對(duì)于aeklu五個(gè)字符，及其頻度數(shù)據(jù)：=0.32, =0.25, =0.20, =0.18, =0.05。請(qǐng) 用Huffmann算法構(gòu)造其Huffmann樹(shù)。由題可知字符a,e,k,l,u五個(gè)字符的權(quán)值分別為0.32,0.25,0.20,0.18,0.05。先由兩個(gè)權(quán)值最小的字符作為葉子節(jié)點(diǎn)構(gòu)造二叉樹(shù)，即l,u。則權(quán)值變?yōu)?0.32,0.25,0.20,0.23再選擇權(quán)值最小的節(jié)點(diǎn)構(gòu)造二叉

5、樹(shù)，即0.20,0.23則權(quán)值變?yōu)?.32,0.25, 0.43（3）同理選擇0.32和0.25對(duì)應(yīng)的節(jié)點(diǎn)作為葉子節(jié)點(diǎn),則權(quán)值變?yōu)?.57,0.43（4）只剩下兩個(gè)則繼續(xù)構(gòu)造，權(quán)值變?yōu)?,構(gòu)造結(jié)束。結(jié)構(gòu)為：12.有如下四個(gè)矩陣：=50 10 & = 1。. 40 C = 40 x 30 D = 30 x 5 請(qǐng)計(jì)算（雙乂。）所需要的總的數(shù)乘次數(shù)，并說(shuō)明計(jì)算方法。11. 參考答案： 由題中(A(B(CD)的計(jì)算順序可得: mA,D = mC,D + mB,CD + mA,B(CD) 首先計(jì)算CD：mC,D = 40 x 30 X 5 = 6000那么相乘后矩陣大后F： (CD)- 40X

6、5mB,CD = 10 x 40 x 5 = 2000相乘后矩陣f、(B(CD) 10X5mA,B(CD) - 50 X 10 X 5 = 2500因此總的相乘次數(shù)為：60。0 + 2000+ 2500 = 1050013.有5個(gè)關(guān)鍵字，其搜索概率如下：pl = 0.25, p2 = 0.2, p3 = 0.05, p4 = 0.2, p5 = 0.3. 請(qǐng)計(jì)算上述二又搜索樹(shù)的搜索代價(jià)的數(shù)學(xué)期望。13.參考答案：j度索次數(shù)d(i)受索概率Pi1Ip. 252°0.2320. 054I0.2520.3搜索期望£ = 1 + Sr=1d(i)-P1E=l+(l*0. 25+0*

7、0. 2+2*0. 05+1*0. 2+2*0. 3)14. 對(duì)于鋼管切割問(wèn)題的下述價(jià)格表：length/ |1234567891()priceyI_589K)1717202430請(qǐng)計(jì)算rl. r5o14. 參考答案：由算法自底向上版本BOTTOM-UP-CUT-ROD(p,n)1 let r0.nbe a new arrayr0=02 for j=l to nq=3 for i=l to j6q=max(q,pi+rj-l)7 rj=qreturn rn有以上算法可以解出rUJ(1)當(dāng) j=l 時(shí)，i=l,則 q=max;所以，rl=l.當(dāng)j=2時(shí)，當(dāng)i=l時(shí)，所以，r2=5.同理 j=3,

8、4,5 時(shí)，可計(jì)算出 r3=8;r4=10;r5=13.112345148 10 1315. Ford-Fulkerson算法的主要問(wèn)題是什么？15. 參考答案：當(dāng)最大流值較大時(shí)可能發(fā)生的情況是每次尋找出來(lái)的增廣路徑，都只能將流 網(wǎng)絡(luò)的流量增加很小的值，這樣的話，會(huì)大大增加循壞的次數(shù)。尤其是|f*|=2|E|dri=2! B 時(shí)，算法的時(shí)間復(fù)雜度變成流網(wǎng)絡(luò)規(guī)模O(|V| + |E|)的指數(shù)函數(shù)0(|E|2|E|)。16. 何謂P、NP、NPC問(wèn)題。16. 參考答案：P問(wèn)題也就是多項(xiàng)式復(fù)雜度的問(wèn)題；NP問(wèn)題就是多項(xiàng)式復(fù)雜度非確定性問(wèn) 題；NPC問(wèn)題是指只有把解域里面所有可能都窮舉了之后才能得到答

9、案，這樣的問(wèn)題是NP 里面最難的問(wèn)題，這類問(wèn)題就是NPC問(wèn)題。17. 有11個(gè)待安排的活動(dòng)，它們具有下表所示的開(kāi)始時(shí)間與結(jié)束時(shí)間，如果以貪心算法求解這些活動(dòng)的最優(yōu)安排(即為活動(dòng)安排問(wèn)題：在所給的活動(dòng)集合中選出最大的相容活動(dòng)了集 合)，得到的最大相容活動(dòng)子集合為活動(dòng)，I1234567891011Si456789101112131418, 描述分治法與動(dòng)態(tài)規(guī)劃法的的異同。18. 參考答案：分治法與動(dòng)態(tài)規(guī)劃法的相同點(diǎn)是：將待求解的問(wèn)題分解成若干個(gè)子問(wèn)題，先 求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解；兩者的不同點(diǎn)是：適合于用動(dòng)態(tài)規(guī)劃 法求解的問(wèn)題，經(jīng)分解得到的子問(wèn)題往往

10、不是互相獨(dú)立的。而用分治法求解的問(wèn)題，經(jīng)分解 得到的子問(wèn)題往往是互相獨(dú)立的。19. 設(shè)是一個(gè)流網(wǎng)絡(luò)，f為G的流，(S,T)為G的一個(gè)割，證明|f|=f(S,T)o參考答案：Ifl = f(s,V)= f(S,V)-f(S-s,V)= f(S,V) vt S - s = f(S,T) + f(S,S)=f(S,T)|f|=f (s,V) =f (S,V) -f (S-s,V) =f (S,V)tS-s=f (S,T) +f (S,S) =f (S,T)按增長(zhǎng)率由小至大的順序排列下列各函數(shù)：20.按增長(zhǎng)率由小至大的順序排列下列各函數(shù)：2、(3/2) (2/3) n* ,峪，n! , 2*, Ign

11、. n'J*'參考答案(2/3)B < 2*00 < lgn < n05 < n(a/2> < n,CB< (3/2)" < 2n< n! < nB五、問(wèn)答題(本大題共0分，共20小題，每小題0分)1. 什么是最優(yōu)子結(jié)構(gòu)性質(zhì)？五、問(wèn)答題(0分，共20題，每小題0分)參考答案：一個(gè)最優(yōu)化策略具有這樣的性質(zhì)，不論過(guò)去狀態(tài)和決策如何，對(duì)前面的決策 所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡(jiǎn)而言之，一個(gè)最優(yōu)化策略的子策略 總是最優(yōu)的。一個(gè)問(wèn)題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。1. 什么是算法的數(shù)據(jù)輸入、

12、輸出性？2. 參考答案：具有數(shù)據(jù)輸入：一個(gè)算法有零個(gè)或多個(gè)數(shù)據(jù)輸入，它們是在算法開(kāi)始之前對(duì) 算法最初賦予的量，這些輸入取自特定的對(duì)象集合。具有數(shù)據(jù)輸出：一個(gè)算法產(chǎn)生一個(gè)或多個(gè)輸出，它們是同輸入有某種特定關(guān)系的量。3. 試給出歸并排序的復(fù)雜度分析。2. 參考答案：合并兩個(gè)長(zhǎng)度為n/2的子序列的時(shí)間復(fù)雜度為O(n)o比較兩個(gè)元素大小的時(shí) 間為0(1),而每次比較都會(huì)從其中一個(gè)子序列中取出一個(gè)元素放到合并空間中，因此比較 的總次數(shù)不會(huì)超過(guò)n次，時(shí)間復(fù)雜度為O(n)o同時(shí)，其中一個(gè)子序列中的元素都被取出為 止，合并的過(guò)程不會(huì)停止，所以時(shí)間復(fù)雜度滿足O(n)。3. 試敘述流網(wǎng)絡(luò)的基本性質(zhì)。4. 參考答案

13、：(1)容量限制；(2)流量守恒闡述動(dòng)態(tài)規(guī)劃算法與分治法不同之處。4. 參考答案：與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題，經(jīng)分解得到的子問(wèn)題 往往不是互相獨(dú)立的。若用分治法解這類問(wèn)題，則分解得到的子問(wèn)題數(shù)目太多，以至于最后解決原問(wèn)題需要耗費(fèi)指 數(shù)時(shí)間。5. 己知變量x和y中分別存放了數(shù)據(jù)，交換其中的數(shù)據(jù)。請(qǐng)用自然語(yǔ)言描述算法。5. 參考答案：為了交換，需要引進(jìn)一個(gè)中間變量m,其算法如下： 將x中的數(shù)據(jù)送給 變量m,即x-m；將y中的數(shù)據(jù)送給變量x,即y-x；將m中的數(shù)據(jù)送給變量y, 即 m-*yo請(qǐng)概述最小代價(jià)生成樹(shù)的貪心選擇性質(zhì)，并證明。6. 參考答案：貪心選擇的性質(zhì)指的是局部最優(yōu)選

14、擇可以得到全局最優(yōu)解決方案，在最小代 價(jià)生成樹(shù)中，其表現(xiàn)為每次選擇的為當(dāng)前可選情況下權(quán)值最小的邊。證明：(1) 一定有一個(gè)最優(yōu)解包含了當(dāng)前權(quán)值最小的邊煩。假設(shè)最優(yōu)解不包含該邊，則將'e，nin加入其中，會(huì)形成一個(gè)環(huán)，任意去掉環(huán)里比'emin權(quán)值大的一條邊，則形成了一 個(gè)更優(yōu)的解，與假設(shè)矛盾。(2)選擇了Fmm后，子問(wèn)題為去掉了關(guān)聯(lián)的點(diǎn)的剩余的點(diǎn)為頂點(diǎn)集，剩余的邊為 邊集的圖的最小代價(jià)問(wèn)題，規(guī)模變小，性質(zhì)不變。通過(guò)歸納法，其可以通過(guò)貪心性質(zhì)得到最 優(yōu)解.7. 描述Ford-Fulkerson算法基本步驟。6. 參考答案：(1)開(kāi)始的時(shí)候，所有的節(jié)點(diǎn)u,vGV間的流值都為0,即f(

15、u,v)=0。(2)在每一次迭代中，我們將流網(wǎng)絡(luò)G的流量進(jìn)行增加，方法就是在一個(gè)關(guān)聯(lián)的“剩余網(wǎng)絡(luò)” Gf中尋找一條“增廣路徑”。一旦知道Gf中的-條增廣路徑的邊，就可以很容易辨別出G 中的對(duì)應(yīng)的邊，我們可以對(duì)這些邊上的流值進(jìn)行修改，從而增加流量(3)重復(fù)第2的操作， 直到剩余網(wǎng)絡(luò)中不再存在增廣路徑為止。7. 用偽代碼或程序語(yǔ)言寫(xiě)出二分搜索的算法，并分析其時(shí)間復(fù)雜度。8. 參考答案：int binary_search( int *a, int nz int key) (int mid, front=0, back=n-l;while (front<=back) (mid = (front+

16、back)/2;if (amid=key)return mid;if (amid<key)front = mid+1;elseback = mid-1;)return -1;)時(shí)間復(fù)雜度O(log(n)9. 簡(jiǎn)述分治法在每一層遞歸上的三個(gè)步驟的具體內(nèi)容。8. 參考答案：分解：將原問(wèn)題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同的子 問(wèn)題；解決：若子問(wèn)題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問(wèn)題；合并： 將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解。9. 簡(jiǎn)述快速排序的具體過(guò)程。10. 參考答案：通過(guò)i趟排序?qū)⒓o(jì)錄分割，其中一部分關(guān)鍵字均比另一部分?。喝缓笤俜謩e 對(duì)這兩部分進(jìn)行排序；通常

17、選取序列的第一個(gè)紀(jì)錄作為比較的參照（稱為支點(diǎn)Pivot）,然 后將關(guān)鍵字小的排在其前，大的排在其后，并以此時(shí)關(guān)鍵字的位置將序列分成兩部分，再對(duì) 兩部分進(jìn)行快速排序；因此快速排序是一個(gè)遞歸的算法。11. 有面值分別為1、5和11單位的硬幣，希望找回總額為15單位的硬幣，貪心算法的 思路和最優(yōu)解分別是什么？10. 參考答案：假設(shè)當(dāng)前的找回總額為a,貪心算法總是在可行的選擇中尋找小于等于a的 最大值b,然后改變找回額，即a=a-b,重新上面的過(guò)程直到不能繼續(xù)為止。按貪心算法, 應(yīng)找1個(gè)11單位面值的硬幣和4個(gè)1單位面值的硬幣，共找回5個(gè)硬幣。最優(yōu)的解應(yīng) 是3個(gè)5單位面值的硬幣。11. 簡(jiǎn)述貪心算法的

18、基本思想？12. 參考答案：貪心算法是通過(guò)做一系列的選擇來(lái)給出某一問(wèn)題的最優(yōu)解的對(duì)算法中的每一 決策點(diǎn)，做一個(gè)當(dāng)時(shí)（看起來(lái)像是）最佳的選擇。這種啟發(fā)式策略并不是總能產(chǎn)生出最優(yōu)解, 但正像我們?cè)诨顒?dòng)選擇問(wèn)題中看到的那樣，它常常能給出最優(yōu)解。13. 快速排序算法基本思想？12. 參考答案：快速排序算法是基于分治策略的一個(gè)算法。其基本思想是，對(duì)于輸入的子數(shù) 組ap:r,按以下3個(gè)步驟進(jìn)行排序：分解、遞歸求解、合并。13. 簡(jiǎn)述程序與算法的異同點(diǎn)。14. 參考答案：程序與算法不同。程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。程序可以不 滿足算法具有數(shù)據(jù)輸出的性質(zhì)。一個(gè)算法產(chǎn)生一個(gè)或多個(gè)輸出，它們是同輸入有

19、某種特定關(guān) 系的量）例如操作系統(tǒng)，它是一個(gè)在無(wú)限循環(huán)中執(zhí)行的程序，因而不是一個(gè)算法。然而我們 可把操作系統(tǒng)的各種任務(wù)看成是一些單獨(dú)的問(wèn)題，每一個(gè)問(wèn)題由操作系統(tǒng)中的一個(gè)子程序通 過(guò)特定的算法來(lái)實(shí)現(xiàn)。該子程序得到輸出結(jié)果后便終止。15. 簡(jiǎn)單區(qū)分語(yǔ)言、算法、程序的不同之處。14. 參考答案：語(yǔ)言：實(shí)現(xiàn)的工具；算法：解的描述；程序：算法+數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單闡述動(dòng)態(tài)規(guī)劃算法的基本思想。16. 參考答案：動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)問(wèn) 題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。18, 分治法基本步驟是什么？17. 參考答案：分治模式在每一層遞歸上都有三個(gè)步驟：1

20、分解：將原問(wèn)題分解成一系列子問(wèn)題；2解決：遞歸地解各小問(wèn)題。若小問(wèn)題足夠小，則直接求解3合并：將子問(wèn)題的結(jié)果合并成原問(wèn)題的解。求解 T（n）= % 把 2） + T（2）+6（n）, n> 1參考答案:T() = 7(-2)+7(2)+5=T(n - 4) + 7(2)+c(n-2) + 7(2) +e=7*(-4)+c(刀-2)+c + 2T(2)=T(n-6)+c(，-4)+c(，-2)+e + 3T(2).=7(2) +c4+c6+c(« - 2) +e+(M -1)7(2)=c-2)(刀+4) + n42 I = ®(»2)”(2) = 0 20 .

21、簡(jiǎn)述動(dòng)態(tài)規(guī)劃法解最優(yōu)化問(wèn)題通常的幾個(gè)步驟。18. 參考答案：動(dòng)態(tài)規(guī)劃法解最優(yōu)化問(wèn)題通常按以下兒個(gè)步驟進(jìn)行：(1)找出最優(yōu)解的性 質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征；(2)遞規(guī)地定義最優(yōu)值；(3)以自底向下地方式計(jì)算出最優(yōu)值:(4)根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。三數(shù)取中劃分的快速排序算法是基于 策略的一個(gè)算法。分治一個(gè)人把一對(duì)兔子用圍墻圍住。如果最初的一對(duì)兔子(一雌一雄)是新生的，并且所有的兔 了在出生后的第一個(gè)月都不能繁殖，但是在之后的每個(gè)月末都能生出一對(duì)兔子(雌-雄)， 那么一年后圍墻里將會(huì)有多少對(duì)兔子？第一個(gè)月后：2+2=4第二個(gè)月后：(2+2)x2=8第三個(gè)月后：(2+2)x2x2=16因此

22、12個(gè)月后有兔 子：(2+2)x2All=4x2All=8192只兔子也就是4096對(duì)兔子。x(l)=0,當(dāng) n>l 時(shí) x(n)=2x(n-l)+l,則 x(n)等于()。B、2n-在活動(dòng)安排問(wèn)題中，下述哪項(xiàng)描述中的活動(dòng)A,B是相容的()？A、活動(dòng)A于活動(dòng)B結(jié)束前開(kāi)始舌動(dòng)A于活動(dòng)B開(kāi)始后開(kāi)始C、活動(dòng)A于活動(dòng)B開(kāi)始前開(kāi)始 D.ls 動(dòng)A于活動(dòng)B開(kāi)始前結(jié)束關(guān)于解決最小代價(jià)生成樹(shù)問(wèn)題的Prim算法的下述說(shuō)法，不正確的是()。-1D、2七1A、從Q南出一個(gè)頂點(diǎn)的賣質(zhì)是在應(yīng)用MST性質(zhì)選擇連接A與V-A的最小權(quán)邊B、算法以優(yōu)先隊(duì)列為空為結(jié)束條件C、優(yōu)先隊(duì)列Q中頂點(diǎn)的鍵值指這個(gè)頂點(diǎn)與A集合中點(diǎn)的最

23、小權(quán)邊的權(quán)重行結(jié)束后，生成何有"n-1個(gè)頂點(diǎn)行結(jié)束后，生成何有"n-1個(gè)頂點(diǎn)以下關(guān)于Huffmann樹(shù)的描述，哪一項(xiàng)是錯(cuò)誤的（）。B、在樹(shù)的同一層，字符的出現(xiàn)順序會(huì)影響平均編碼長(zhǎng)度的數(shù)學(xué)期望階乘函數(shù)用遞歸定義 Public static int factorialfint n) (if(n=0) return 1; return ( ) ;A、n*factorial(n-l)關(guān)于二分檢索算法的一些描述，正確的是（）。A、二分檢索箕法適合于無(wú)序的數(shù)列的檢索B、二分檢索算法不適合于檢索數(shù)據(jù)不屬于數(shù)組的情況C、二分檢索算法的時(shí)間夏雜度是0 （ n ）D、二分檢索算法的效率和二叉樹(shù)

24、的深度有關(guān)當(dāng)問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解時(shí)，稱該問(wèn)題具有（）。D、最優(yōu)子結(jié)構(gòu)性質(zhì)考慮關(guān)于0-1背包問(wèn)題的如卜.遞歸表達(dá)式，如果物品i的重量小于背包的剩余容量，并且我 們選擇裝入了物品i,則OPT（i, w）的取值為（）。A、0PT（i-l,w）Java的類一般有4個(gè)部分組成：請(qǐng)選出不屬于的一個(gè)（）A、類名C、數(shù)據(jù)成員適用動(dòng)態(tài)規(guī)劃解決的問(wèn)題必須滿足最優(yōu)子結(jié)構(gòu)和（）性質(zhì)。I A、無(wú)后效性B、遞歸C、無(wú)前效性| D、重疊子問(wèn)題|x(l)=4,當(dāng) n>l 時(shí) x(n)=3x(n-l)o 則 x(n)等于()。A、4*3時(shí)當(dāng)n越來(lái)越大時(shí)，下列函數(shù)中，增長(zhǎng)速度最快的應(yīng)該是()oD、y=100n

25、二分搜索算法是基于()設(shè)計(jì)的算法。A、分治法D17.算法的每種運(yùn)算必須要有確切的定義,不能有二義性，以下符合算法確定性運(yùn)算的是f（n）=f（n-l）+2,f（l）=10,n 為自然數(shù)A18,實(shí)現(xiàn)快速排序算法如下：Quicksort （A, p, r）IF p < r THEN q *- Partition（Az p, r） （） QuickSort（A, q+1, r）A. QuickSort（A,q-l,ijA19.找零錢問(wèn)題中，定義Cj為兌換j所需要的硬幣的最少數(shù)量，如果找出的第一個(gè)硬幣 為5分，則下述公式哪個(gè)是對(duì)的（）。A. CO = 1 + Cj-5B20.最長(zhǎng)公共子序列算法利用

26、的算法是（）0B. 動(dòng)態(tài)規(guī)劃法B21. Huffman編碼的貪心算法所需的計(jì)算時(shí)間為（）°B. 0 （nlogn）A22.使用分治法求解不需要滿足的條件是（）。A. 子問(wèn)題必須是一樣的D23.下列關(guān)于算法速度的描述，正確的是（）D.對(duì)于問(wèn)題規(guī)模比較大的時(shí)候，對(duì)數(shù)時(shí)間算法比指數(shù)時(shí)間算法快非常多C24,在使用偽代碼進(jìn)行算法描述時(shí)，不可以實(shí)現(xiàn)循環(huán)的是（）。C. ifB25.大型程序設(shè)計(jì)一般用（）數(shù)據(jù)類型來(lái)描述算法。B. 抽象A26.與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題（）。A. 經(jīng)分解得到子問(wèn)題往往不是互相獨(dú)立.的D27.快速排序法的基本思想是對(duì)輸入的數(shù)組按以下三個(gè)步驟進(jìn)行排序（）

27、。D. 分解，遞歸求解，合并D28.在最優(yōu)二叉搜索樹(shù)問(wèn)題中，我們的優(yōu)化目標(biāo)是（）。D.元素搜索代價(jià)的數(shù)學(xué)期望為最小C29. T（n）=2n3+10n2log（n）+30n 的漸近時(shí)間復(fù)雜度為（）。C. 0（n3）B30. Edmonds-Karp算法中尋找增廣路徑的方法是（）。B. 廣度優(yōu)先算法B31.在矩陣連乘問(wèn)題的動(dòng)態(tài)規(guī)劃解決方案里，我們的所做的頂層決策是（）。B.最后一次矩陣乘法發(fā)生的位置A32.關(guān)于0-1背包問(wèn)題的下述形式化公式描述：下述說(shuō)法不正確的是（）。A. i表示物品的重量A33.在活動(dòng)安排問(wèn)題中，如果把全部活動(dòng)按照結(jié)束時(shí)間遞增序排序后，按貪心算法，我們 總是安排（）。A.當(dāng)前可

28、選活動(dòng)中結(jié)束時(shí)間最早的活動(dòng)A34.找零錢問(wèn)題中，定義Cj為兌換j所需要的硬幣的最少數(shù)量，考慮下述遞歸表達(dá)式,8if j V 0,0if j = 0.1+minifj>ll<9<k下列關(guān)于對(duì)i的尋優(yōu)的最恰當(dāng)描述是（）。 A.考慮找出的第一個(gè)硬幣面值的各種可能性A35. Huffman編碼問(wèn)題中，我們的優(yōu)化目標(biāo)是（）。A. 所有字符編碼長(zhǎng)度的數(shù)學(xué)期望為最小B36, 一個(gè)有n個(gè)結(jié)點(diǎn)的帶權(quán)無(wú)向圖，其生成樹(shù)應(yīng)有（）條邊。B. n-1B37.算法必須具備輸入、輸出和（）等5個(gè)特性。B.可行性、確定性和有窮性A38.當(dāng)問(wèn)題的規(guī)模n趨向無(wú)窮大時(shí)，（）的數(shù)量級(jí)（階）稱為算法的漸進(jìn)時(shí)間復(fù)雜度。A

29、. 時(shí)間復(fù)雜度B39.下列算法中通常以自底向上的方式求解最優(yōu)解的是（）。B. 動(dòng)態(tài)規(guī)劃法B40.貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是（）。B.貪心選擇性質(zhì)D41.最優(yōu)二叉搜索樹(shù)的時(shí)間復(fù)雜度為（）。D. O（nlogn）D42.對(duì)于三個(gè)物體的背包問(wèn)題，問(wèn)題相關(guān)的數(shù)據(jù)為n=3, M=20,P=（25,24,15）,W（18,15,10）。 下面給出的四個(gè)可行解中，最好的是（）D.（0, 1, 1/2）B43.遞歸函數(shù)f（n）=f（n-l）+n（n>l）的遞歸出口是（）。B. f（l）=lB44,下面關(guān)于快速排序的說(shuō)法，正確的是（）B.快速排序的速度在分解的均勻的時(shí)候效果最好，速度最快D45.下

30、面關(guān)于貨郎擔(dān)問(wèn)題的描述，正確的是（）D.貨郎擔(dān)問(wèn)題可以通過(guò)動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)B46.在最優(yōu)二叉搜索樹(shù)問(wèn)題中，定義ei,j為ki，,kj的最優(yōu)二叉查找樹(shù)的期望搜索成本，而我們確定根結(jié)點(diǎn)下標(biāo)為r,則其左子樹(shù)的下標(biāo)范圍是（）。B. i.r-lC47.貪心算法與動(dòng)態(tài)規(guī)劃類似，用于解決最優(yōu)化問(wèn)題，下面關(guān)于它們的敘述正確的是（）C. 貪心算法是期望通過(guò)所做的局部最優(yōu)選擇來(lái)產(chǎn)生全局最優(yōu)解決方案D48.關(guān)于幾種排序算法的速度描述，正確的是（）D. 快速排序速度快，適合大規(guī)模數(shù)據(jù)B49.下面關(guān)于網(wǎng)絡(luò)流的屬性的描述，正確的是（）B.對(duì)于所有；B50,算法 simpleMaxMin（Al.r）如下，Max=Min=A

31、l;for i=l+l to r doif Ai>Max MaxAi;else if Ai<Min MinAi;return Max,Min其時(shí)間復(fù)雜度是（）。B. 2（n-l）C51. b面是貪心算法的基本要素的是（）。C. 貪心選擇性質(zhì)C52.分治法所能解決的問(wèn)題應(yīng)具有的關(guān)鍵特征是（）。C. 利用該問(wèn)題分解出的了問(wèn)題的解可以合并為該問(wèn)題的解A53.在鋼管切割問(wèn)題里，如果用rn表示長(zhǎng)度為n英寸的鋼管的最優(yōu)切割方案所獲得的 最大收益,且己知rn所代表的最優(yōu)解里，第一刀切下了 3英寸，則下述公式正確的是()。A. rn = p3 + rn-3D54.()是貪心算法與動(dòng)態(tài)規(guī)劃算法的共同

32、點(diǎn)。D. 最優(yōu)子結(jié)構(gòu)性質(zhì)B55.下列關(guān)于選擇排序和冒泡排序的穩(wěn)定性的說(shuō)法，正確的是()。B. 選擇排序是不穩(wěn)定的，冒泡排序是不穩(wěn)定的。A56.使用分治法求解不需要滿足的條件是()。A.子問(wèn)題必須是一樣的C57.在流網(wǎng)絡(luò)中，對(duì)于源節(jié)點(diǎn)，從其它節(jié)點(diǎn)流進(jìn)去的流與從該節(jié)點(diǎn)流向其它節(jié)點(diǎn)的流是相 等的。C. 在流網(wǎng)絡(luò)中，對(duì)于非源和非匯的節(jié)點(diǎn)，從其它節(jié)點(diǎn)流進(jìn)去的流與從該節(jié)點(diǎn)流向其它節(jié)點(diǎn) 的流是相等的。D58.遞歸算法不能適用以下場(chǎng)合()。D. 概率問(wèn)題A59.在最優(yōu)二叉搜索樹(shù)問(wèn)題中，定義ei,j為ki，,kj的最優(yōu)二叉查找樹(shù)的期望搜索成本, 而我們需要通過(guò)尋優(yōu)來(lái)確定最優(yōu)二叉查找樹(shù)的根結(jié)點(diǎn)的下標(biāo)r，則r的取值

33、范圍為()。A. iWrWjD60.程序可以不滿足算法性質(zhì)的()。D. 有限性二、判斷題(本大題共0分，共60小題，每小題0分)XI.對(duì)于矩陣鏈連乘的子問(wèn)題當(dāng)i=j時(shí)表明該矩陣鏈有兩個(gè)矩陣。()X2.算法就是一組無(wú)窮的規(guī)則()J3.問(wèn)題的規(guī)模越小，解題所需的計(jì)算時(shí)間往往也越少，從而也較容易處理。()J4.動(dòng)態(tài)規(guī)劃和分治法在分解子問(wèn)題方面的不同點(diǎn)是前者分解出的子問(wèn)題有重疊的，而后 者分解出的子問(wèn)題是相互獨(dú)立(不重疊)的()。J5.每一個(gè)遞歸定義都有其邊界條件。()J6.貪心算法并不從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)選擇。()J7.用浮點(diǎn)數(shù)來(lái)表示大型整數(shù)，只能近似地表示它的大

34、小。()J8.多階段決策問(wèn)題，就是要在可以選擇的那些策略中間，選取一個(gè)最優(yōu)策略，使在預(yù)定 的標(biāo)準(zhǔn)卜達(dá)到最好的效果。()V9.子問(wèn)題之間不包含公共的子問(wèn)題，這個(gè)條件涉及到分治法的效率。()X10.裴波那契數(shù)列的定義：f(n)=f(n-l)+f(n-2),f(0)=l,f(l)=2,其數(shù)據(jù)的定義形式不是按遞歸 定義。()V11.程序性能是指運(yùn)行一個(gè)程序所需的內(nèi)存大小和時(shí)間多少。()X12. 一個(gè)操作所需的時(shí)間和操作數(shù)的類型無(wú)關(guān)()V13.要想在電腦上擴(kuò)大所處理問(wèn)題的規(guī)模，有效的途徑是降低算法的計(jì)算復(fù)雜度。()V14.在JAVA語(yǔ)言中，執(zhí)行特定認(rèn)為的任務(wù)的函數(shù)或過(guò)程統(tǒng)稱為方法。()V15.與分治法不

35、同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題經(jīng)分解得到子問(wèn)題往往是互相不獨(dú) 立的()。V16.歸并排序是指將數(shù)組一分為二，分別對(duì)每個(gè)集合單獨(dú)排序，然后將己排序的兩個(gè)序列 歸并成個(gè)含n個(gè)元素的分好類的序列。如果分割后子問(wèn)題還很大，則繼續(xù)分治，直到- 個(gè)元素。()X17.與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題經(jīng)分解得到子問(wèn)題往往是互相獨(dú)立 的()。V18.對(duì)所有問(wèn)題，貪心算法不能都得到整體最優(yōu)解()。J19.算法重要特性是確定性、可實(shí)現(xiàn)性、輸入、輸出、有窮性()。V 20. 0-1背包問(wèn)題，無(wú)論物件的順序如何排列，動(dòng)態(tài)規(guī)劃總能獲得最優(yōu)解。()V21.指數(shù)時(shí)間算法只有在n取值非常小時(shí)才實(shí)用。()J22.

36、動(dòng)態(tài)規(guī)劃法其具體形式是多種多樣的，但都具有相同的填表格式。()J23. 一般來(lái)說(shuō)，對(duì)一個(gè)有序序列二分法(即把任意大小的問(wèn)題盡可能地等分為兩個(gè)子問(wèn)題) 較為有效。()X24.如果各子問(wèn)題是不獨(dú)立的，一般用動(dòng)態(tài)規(guī)劃法比分治法較差。()J25.動(dòng)態(tài)規(guī)劃對(duì)每-個(gè)子問(wèn)題只解次，并將結(jié)果保存起來(lái)，避免每次碰到時(shí)都要重復(fù)計(jì) 算。0X26.當(dāng)一個(gè)問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)只能用動(dòng)態(tài)規(guī)劃方法求解。()X27. Huffmann編碼樹(shù)所對(duì)應(yīng)的編碼并不一定是前綴碼。()V 28.通常，在分析一個(gè)算法的計(jì)算復(fù)雜性時(shí)，都將加法和乘法運(yùn)算當(dāng)作是基本運(yùn)算來(lái)處理。X29.問(wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增加而減小。()J3

37、0.子問(wèn)題之間不包含公共的子問(wèn)題，這個(gè)條件涉及到分治法的效率。()X31. Prim算法是一種動(dòng)態(tài)規(guī)劃算法。()J 32.標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃是在研究多階段決策問(wèn)題時(shí)推導(dǎo)出來(lái)的，具有嚴(yán)格的數(shù)學(xué)形式，適合用 于理論上的分析。()J33.問(wèn)題解法按遞歸算法實(shí)現(xiàn)的問(wèn)題適用于遞歸求解.()J34. 一般認(rèn)為，執(zhí)行一次加法或乘法運(yùn)算所需的計(jì)算時(shí)間當(dāng)作-個(gè)僅取決于計(jì)算機(jī)硬件處 理速度的常數(shù)。()J35.如果一類活動(dòng)過(guò)程一個(gè)階段的決策確定以后，常影響到下一個(gè)階段的決策，則稱它為 多階段決策問(wèn)題。()J36.對(duì)于矩陣鏈連乘的子問(wèn)題mi,j,其對(duì)應(yīng)的si,j用于記錄該矩陣鏈最后一次乘法發(fā)生 的位置。()J37.分治法的

38、一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的程序一般是一個(gè)遞歸過(guò)程。因此，分 治法的計(jì)算效率通常可以用遞歸方程來(lái)進(jìn)行分析。()X38.如果兩個(gè)序列的最后一個(gè)字符相同，則其最長(zhǎng)公共子序列必以那個(gè)相同的字符結(jié)尾。J39.反復(fù)應(yīng)用分治手段,不能使子問(wèn)題與原問(wèn)題類型一致而其規(guī)模卻不斷縮小。()J40.分治法在每一層遞歸上有三個(gè)步驟：分解、解決、合并。()J41.遞歸是從函數(shù)本身出發(fā)來(lái)達(dá)到邊界條件。()J42.遞歸的長(zhǎng)處是能使一個(gè)蘊(yùn)含遞歸關(guān)系且結(jié)構(gòu)復(fù)雜的程序簡(jiǎn)潔精煉，增加可讀性。()J43.數(shù)據(jù)之間的關(guān)系(即數(shù)據(jù)結(jié)構(gòu))按遞歸定義，如樹(shù)的遍歷，圖的搜索等，這類問(wèn)題適用 遞歸算法。()J44.貪心算法和動(dòng)態(tài)規(guī)劃算法都

39、要求問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。()J45.備忘錄方法可以看作是動(dòng)態(tài)規(guī)劃算法的變形。()J46.適宜于用貪心策略來(lái)解的問(wèn)題都有兩個(gè)特點(diǎn):貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)。()V 47. Huffmann編碼樹(shù)一定是滿樹(shù)。()J48.歸并排序算法是漸進(jìn)最優(yōu)算法。()J49.動(dòng)態(tài)規(guī)劃將原來(lái)具有指數(shù)級(jí)復(fù)雜度的搜索算法改進(jìn)成了具有多項(xiàng)式時(shí)間的算法。()J50.數(shù)量級(jí)反映了算法時(shí)間復(fù)雜度的最本質(zhì)的特征。()X51.對(duì)于0-1背包問(wèn)題的解向量X, Xi = l表明選擇物品l.io ()X52. Ford-Fulkerson算法規(guī)定了增廣路徑的搜索算法。()J53.f(n)=6X2n+n2, f(n)的漸進(jìn)性態(tài) f(n

40、)=0(2n)。()J54.如果頂點(diǎn)的總數(shù)為n,則Prim算法總共要選擇n-1條邊來(lái)構(gòu)成生成樹(shù)。()J55.二分搜索法的二分查找只適用于順序存儲(chǔ)結(jié)構(gòu)。()X56.不同的矩陣鏈加括號(hào)形式會(huì)導(dǎo)致矩陣鏈相乘的不同結(jié)果。()V57.算法分析的目的是分析算法占用計(jì)算機(jī)資源的情況，對(duì)算法做出比較和評(píng)價(jià)，設(shè)計(jì)出 更好的算法。()J58.算法的漸進(jìn)時(shí)間復(fù)雜性是指當(dāng)問(wèn)題的規(guī)模n趨向無(wú)窮大時(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ù)雜性。()J 59.快速排序是一個(gè)遞歸的算法。()J

41、60.通常用T(n)來(lái)表示某一算法的“時(shí)間復(fù)雜性”，當(dāng)輸入量n逐漸增大時(shí)，時(shí)間復(fù)雜性的極限稱為算法的“漸近時(shí)間復(fù)雜性”。()三、填空題(本大題共。分，共40小題，每小題0分)1. 算法是這樣一種算法，它期望通過(guò)所做的局部最優(yōu)選擇產(chǎn)生出一個(gè)全局最優(yōu)解。1. 參考答案：貪心2.0-1背包問(wèn)題中，對(duì)于物品能否裝入背包，我們只考慮其重量和價(jià)值，而不考慮其o2. 參考答案：形狀和體積算法的實(shí)現(xiàn)工具是 。3. 參考答案：程序語(yǔ)言由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的 ,這就為使用遞歸技術(shù)提供了方便。3. 參考答案：較小模式動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素是和。4. 參考答案：最優(yōu)子結(jié)構(gòu)性質(zhì)重疊子問(wèn)題性質(zhì)歸并排序算法

42、是用 策略實(shí)現(xiàn)對(duì)n個(gè)元素進(jìn)行排序的算法。4. 參考答案：分治矩陣連乘問(wèn)題的算法可由實(shí)現(xiàn)。5. 參考答案：動(dòng)態(tài)規(guī)劃在JAVA語(yǔ)言中，執(zhí)行特定認(rèn)為的任務(wù)的函數(shù)或過(guò)程統(tǒng)稱為 。8. 參考答案：方法快速排序算法是基于的一種排序算法。6. 參考答案：分治法T為時(shí)間復(fù)雜性，對(duì)于給定的算法A,設(shè)使用A的次數(shù)為E且每執(zhí)行一次算法的時(shí)間為t,因此T= o參考答案：tE7. 有如下遞歸過(guò)程：void reverse (int n) printf( "%d” ,n%10);if(n/10!=0) reverse(n/10);調(diào)用語(yǔ)句 reverse(582)的結(jié)果是 。11. 參考答案：285貪心算法通過(guò)

43、達(dá)成全局最優(yōu)。8. 參考答案：局部最優(yōu)遞歸按其調(diào)用方式分：。12. 參考答案：直接遞歸間接遞歸貪心法和動(dòng)態(tài)規(guī)劃設(shè)計(jì)方法都利用了 性質(zhì)。9. 參考答案：最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)性質(zhì)的含義是。13. 參考答案：?jiǎn)栴}的最優(yōu)解包含其子問(wèn)題的最優(yōu)解對(duì)于有n種可選擇物品的0-1背包問(wèn)題，其解空間由長(zhǎng)度為n的0-1向量組成。該解空間包含對(duì)變量的所有0-1賦值。當(dāng)n=3時(shí)，其解空間是：。10. 參考答案： (0, 0, 0) , (0, 1, 0) , (0, 0, 1) , (1, 0, 0) , (0, 1, 1), (1, 0, 1) , (1, 1, 0) (1, 1. 1) 最優(yōu)二叉搜索樹(shù)是指為最小的二

44、叉搜索樹(shù)。14. 參考答案：搜索代價(jià)的數(shù)學(xué)期望貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是。18, 參考答案：貪心選擇性質(zhì)數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式稱為。15. 參考答案：數(shù)據(jù)結(jié)構(gòu)算法中最基本的數(shù)據(jù)類型有、o20. 參考答案：布爾值數(shù)據(jù)、字符數(shù)據(jù)、整數(shù)和實(shí)數(shù)等21.S(n)=O(f(n),其中n為, S(n)表示空間復(fù)雜度。21. 參考答案：?jiǎn)栴}的規(guī)模直接或間接地調(diào)用自身的算法稱為算法。22. 參考答案：遞歸動(dòng)態(tài)規(guī)劃法求解多階段決策問(wèn)題，用一個(gè)表來(lái)記錄 o22. 參考答案：所有己解決的子問(wèn)題的答案找零錢問(wèn)題中，我們應(yīng)用的貪心規(guī)則是，23. 參考答案：總是找不超過(guò)當(dāng)前剩余應(yīng)找錢數(shù)的最大面值硬幣一

45、個(gè)30行20列的矩陣可與一個(gè)行75列的矩陣相乘。25, 參考答案：20在n加倍的情況下，一個(gè)O(n2)的算法計(jì)算時(shí)間增長(zhǎng) 倍。26. 參考答案：4用函數(shù)自身給出定義的函數(shù)稱為 。27. 參考答案：遞歸函數(shù)算法的指的是組成算法的每條指令是清晰的，無(wú)歧義的。28. 參考答案：確定性由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，這就為使用 技術(shù)提供了方便。28. 參考答案：遞歸快速排序算法的空間復(fù)雜度平均情況下為,最壞的情況下為29. 參考答案：O(log(n), O(n)二又搜索樹(shù)中，搜索一個(gè)節(jié)點(diǎn)所需的比較次數(shù)=該節(jié)點(diǎn)在樹(shù)中的深度+。29. 參考答案：1一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時(shí)間復(fù)雜度為O參考答案：O(n)33.0記號(hào)在算法復(fù)雜性的表示法中表示。30. 參考答案：漸進(jìn)確界或緊致界按照漸近階比較大小1000nlog(n)0.1n2?34. 參考答案：從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的程序一般是一個(gè)過(guò)程。35, 參考答案：遞歸偽代碼是一種語(yǔ)言。36. 參考答案：算法描述對(duì)于有n種可選擇物品的0-1背包問(wèn)題，其解空間由