海大算法設計與分析考試復習題

1、計算機算法設計與分析復習題、填空題1、一個算法復雜性的圖低體現(xiàn)在計算機運行該算法所需的時間和存儲器資源上，因此算法的復雜性有一時間復雜性和空間復雜性之分。2、出自于“平衡子問題”的思想，通常分治法在分割原問題，形成若干子問題時，這些子問題的規(guī)模都大致相同。3、 使用二分搜索算法在n個有序元素表中搜索一個特定元素，在最佳情況下，搜索的時間復雜性為0(1),在最壞情況下，搜索的時間復雜性為O(_logn_)4、 已知一個分治算法耗費的計算時間T(n),T(n)滿足如下遞歸方程：T(n)*0( 1)2T(n/ 2)+0(n)n :二 2n 2解得此遞歸方可得T(n)=0(_nlogn)。5、動態(tài)規(guī)劃

2、算法有一個變形方法_備忘錄方法。這種方法不同于動態(tài)規(guī)劃算法“自底向上”的填充方向，而是“自頂向下”的遞歸方向，為每個解過的子問題建立了備忘錄以備需要時查看，同樣也可避免相同子問題的重復求解。6 .遞歸的二分查找算法在divide階段所花的時間是0(1),conquer階段所花的時間是T(n/2),算法的時間復雜度是0(logn)_。7 .Prim算法利用貪心策略求解最小牛成樹問題.其時間復雜度是0(n2)。8、背包問題可用貪心法:回溯法等策略求解。9、用動態(tài)規(guī)劃算法計算矩陣連乘問題的最優(yōu)值所花的時間是一0(n3一,子問題空間大小是0(n2)。10、圖的m著色問題可用回溯法求解，其解空間樹中葉子

3、結(jié)點個數(shù)是mn,解空間樹中每個內(nèi)結(jié)點的孩子數(shù)是一o11、單源最短路徑問題可用貪心法、分支限界等策略求解。12、一個算法的優(yōu)劣可以用(時間復雜度)與(空間復雜度)與來衡量。13、回溯法在問題的解空間中，按(深度優(yōu)先方式)從根結(jié)點出發(fā)搜索解空間樹。14、直接或間接地調(diào)用自身的算法稱為(遞歸算法)。15、二記號在算法復雜性的表示法中表示(漸進確界或緊致界)。16、在分治法中，使子問題規(guī)模大致相等的做法是出自一種(平衡(banlancing)子問題)的思想。17、動態(tài)規(guī)劃算法適用于解(具有某種最優(yōu)性質(zhì))問題。18、貪心算法做出的選擇只是(在某種意義上的局部)最優(yōu)選擇。19、最優(yōu)子結(jié)構(gòu)性質(zhì)的含義是(問題

4、的最優(yōu)解包含其子問題的最優(yōu)解)。20 、回溯法按（深度優(yōu)先）策略從根結(jié)點出發(fā)搜索解空間樹。21 、拉斯維加斯算法找到的解一定是（正確解）。22 、按照符號O的定義O（f）+O（g）等于O（maxf（n）,g（n）。23 、二分搜索技術(shù)是運用（分治）策略的典型例子。24 、動態(tài)規(guī)劃算法中，通常不同子問題的個數(shù)隨問題規(guī)模呈（多項式）級增長。25 、（最優(yōu)子結(jié)構(gòu)性質(zhì)）和（子問題重疊性質(zhì)）是采用動態(tài)規(guī)劃算法的兩個基本要素。26 、（最優(yōu)子結(jié)構(gòu)性質(zhì)）和（貪心選擇性質(zhì)）是貪心算法的基本要素。27 、（選擇能產(chǎn)生最優(yōu)解的貪心準則）是設計貪心算法的核心問題。28 、分支限界法常以（廣度優(yōu)先）或（以最小耗費（最

5、大效益）優(yōu)先）的方式搜索問題的解空間樹。29 、貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列（局部最優(yōu)）的選擇，即貪心選擇達到。30 、按照活結(jié)點表的組織方式的不同，分支限界法包括（隊列式（FIFO）分支限界法）和（優(yōu)先隊列式分支限界法）兩種形式。31 、如果對于同一實例，蒙特卡洛算法不會給出兩個不同的正確解答，則稱該蒙特卡洛算法是（一致的）。32 、哈夫曼編碼可利用（貪心法）算法實現(xiàn)。33 概率算法有數(shù)值概率算法，蒙特卡羅（MonteCarlo）算法，拉斯維加斯（LasVegas）算法和舍伍德（Sherwood）算法34 以自頂向下的方式求解最優(yōu)解的有（貪心算法）35 、下列算法中通常

6、以自頂向下的方式求解最優(yōu)解的是（貪心法）。36 、在對問題的解空間樹進行搜索的方法中,一個活結(jié)點有多次機會成為活結(jié)點的是（回溯法）37 、旅行售貨員問題不能用（）解決可以用回溯法解決，分支限界法，NP完全性理論與近似算法38 、貪心算法不能解決（0-1背包問題N皇后問題）?？梢越鉀Q背包問題39 、投點法是（概率算法）的一種。40 、若線性規(guī)劃問題存在最優(yōu)解，它一定不在（可行域內(nèi)部）:、簡答題1、（8分）寫出下列復雜性函數(shù)的偏序關(guān)系（即按照漸進階從低到高排序）2n3nlognn!nlognn2nn103參考解答：103YlognYnlognYn2Y2nY3n<n!<nn2、(8分)現(xiàn)

7、在有8位運動員要進行網(wǎng)球循環(huán)賽，要設計一個滿足以下要求的比賽日程表：每個選手必須與其他選手各賽一次;每個選手一天只能賽一次；循環(huán)賽一共進行n-1天。參考解答:3, (8分)某體育餌有一羽毛球場出租，現(xiàn)在總共有10位客戶申請租用此羽毛每個客戶所租用的時間單s(i)表示開始租用時刻,f(i) i12345678910s(i)03153511886f65498713121110球場，4單表示結(jié)束租用時刻，10個客戶的申請如下表所示：元如下表所示,同一時刻，該羽毛球場只能租借給一位客戶，請設計一個租用安排方案，在這10位客戶里面，使得體育館能盡可能滿足多位客戶的需求，并算出針對上表的10個客戶申請，最

8、多可以安排幾位客戶申請。參考解答：將這10位客戶的申請按照結(jié)束時間f(i)遞增排序，如下表：i12345678910s(i(i)45678910111213選擇申請1(1,4)依次檢查后續(xù)客戶申請，只要與已選擇的申請相容不沖突，則選擇該申請。直到所有申請檢查完畢。申請4(5,7)、申請8(8,11)、申請10(11,13)最后，可以滿足：申請1(1,4)、申請4(5,7)、申請8(8,11)、申請10(11,13)共4個客戶申請。這已經(jīng)是可以滿足的最大客戶人數(shù).I mi, j”4、（8分）對于矩陣連乘所需最少數(shù)乘次數(shù)問題，其遞歸關(guān)系式為i= ji : jPi-i為矩陣

9、Ai的行,0mkinmi,kmk1,jpAPkPj其中mi,j為計算矩陣連乘Ai,Aj所需的最少數(shù)乘次數(shù)p為矩陣Ai的列?，F(xiàn)有四個矩陣，其中各矩陣維數(shù)分別為A1A2AA50x1010漢4040x3030漢5P。漢P1P1匯P2P2漢P3P3代P4請根據(jù)以上的遞歸關(guān)系，計算出矩陣連乘積AAAA所需要的最少數(shù)乘次數(shù)參考解答：rm11+m24+PoPQq=0+8000+50x10-5=10500m14=minm12m34P。P2P4二20000600050405=36000m13m44+P。p3P4=27000+0十50匯30漢5=34500-105005 、（8分）有這樣一類特殊0-1背包問題：可

10、選物品重量越輕的物品價值越高。n=6,c=20,P=（4,8,15,1,6,3）,W=（5,3,2,10,4,8）。其中n為物品個數(shù)，c為背包載重量，P表示物品的價值，W表示物品的重量。請問對于此0-1背包問題，應如何選擇放進去的物品，才能使到放進背包的物品總價值最大，能獲得的最大總價值多少？參考解答：因為該0-1背包問題比較特殊，恰好重量越輕的物品價值越高，所以優(yōu)先取重量輕的物品放進背包。最終可以把重量分別為2,3,4,5的三個物品放進背包，得到的價值和為15+8+6+4=33,為最大值。6 .請用英文寫出三種以上能求解0-1背包問題的設計算法策略。參考解答：DynamicProgrammi

11、ngBacktrackBranch-and-Bound（每答對一條給一分）7 .請說明動態(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)8 .請說明：（1）優(yōu)先隊列可用什么數(shù)據(jù)結(jié)構(gòu)實現(xiàn)？（2）優(yōu)先隊列插入算法基本思想?（3）優(yōu)先隊列插入算法時間復雜度？參考解答：（1）堆。（1分）（2）在小根堆中，將元素x插入到堆的末尾，然后將元素x的關(guān)鍵字與其雙親的關(guān)鍵字比較，若元素x的關(guān)鍵字小于其雙親的關(guān)鍵字，則將元素x與其雙親

12、交換，然后再將元素x與其新雙親的關(guān)鍵字相比，直到元素x的關(guān)鍵字大于雙親的關(guān)鍵字，或元素x到根為止。（4分）（3）0（logn）（1分）1.1. 計動態(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)解。10 .分治法所能解決的問題一般具有哪幾個特征？請簡述。參考解答：（1）該問題的規(guī)模縮小到一定的程度就可以容易地解決；（6分）（2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；（3）禾U用該問題分解出的子問題的解可以

13、合并為該問題的解；（4）原問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。11 .分支限界法的搜索策略是什么？參考解答：在擴展結(jié)點處，先生成其所有的兒子結(jié)點（分支），然后再從當前的活結(jié)點表中選擇下一個擴展結(jié)點。為了有效地選擇下一擴展結(jié)點，加速搜索的進程，在每一個活結(jié)點處，計算一個函數(shù)值（限界），并根據(jù)函數(shù)值，從當前活結(jié)點表中選擇一個最有利的結(jié)點作為擴展結(jié)點，使搜索朝著解空間上有最優(yōu)解的分支推進，以便盡快地找出一個最優(yōu)解。（6分）12 算法的要特性是什么？參考解答：確定性、可實現(xiàn)性、輸入、輸出、有窮性13 算法分析的目的是什么？參考解答：分析算法占用計算機資源的情況，對算法

14、做出比較和評價，設計出額更好的算法。14 算法的時間復雜性與問題的什么因素相關(guān)？參考解答：算法的時間復雜性與問題的規(guī)模相關(guān)，是問題大小n的函數(shù)。15 算法的漸進時間復雜性的含義？參考解答：當問題的規(guī)模n趨向無窮大時，影響算法效率的重要因素是T（n）的數(shù)量級，而其他因素僅是使時間復雜度相差常數(shù)倍，因此可以用T（n）的數(shù)量級（階）評價算法。時間復雜度T（n）的數(shù)量級（階）稱為漸進時間復雜性。16 最壞情況下的時間復雜性和平均時間復雜性有什么不同？參考解答：最壞情況下的時間復雜性和平均時間復雜性考察的是n固定時，不同輸入實例下的算法所耗時間。最壞情況下的時間復雜性取的輸入實例中最大的時間復雜度：W(

15、n)=maxT(n,I),I?Dn平均時間復雜性是所有輸入實例的處理時間與各自概率的乘積和：人尸刀P(I)T(n,1)I?Dn17 簡述二分檢索(折半查找)算法的基本過程。參考解答：設輸入是一個按非降次序排列的元素表Ai:j和x，選取A(i+j)/2與x比較，如果A(i+j)/2=x，則返回(i+j)/2，如果A(i+j)/2<x，則Ai:(i+j)/2-1找x,否則在A(i+j)/2+1:j找x。上述過程被反復遞歸調(diào)用。18 背包問題的目標函數(shù)和貪心算法最優(yōu)化量度相同嗎？參考解答:不相同。目標函數(shù):獲得最大利潤。最優(yōu)量度:最大利潤/重量比。19 采用回溯法求解的問題，其解如何表示？有什

16、么規(guī)定？參考解答：問題的解可以表示為n元組：(xi,x2,xJ,Xi?S,S為有窮集合，Xi?S,(xi,x2,Xn)具備完備性，即(xi,x2,Xn)是合理的，貝(X/?,Xi)(i<n)一定合理。20 回溯法的搜索特點是什么？參考解答：在解空間樹上跳躍式地深度優(yōu)先搜索，即用判定函數(shù)考察xk的取值，如果xk是合理的就搜索xk為根節(jié)點的子樹，如果xk取完了所有的值，便回溯到xk-1。21n皇后問題回溯算法的判別函數(shù)place的基本流程是什么？參考解答：將第K行的皇后分別與前k-1行的皇后比較，看是否與它們相容，如果不相容就返回false，測試完畢則返回true。22為什么用分治法設計的算

17、法一般有遞歸調(diào)用？參考解答：子問題的規(guī)模還很大時，必須繼續(xù)使用分治法，反復分治，必然要用到遞歸.23為什么要分析最壞情況下的算法時間復雜性？參考解答：最壞情況下的時間復雜性決定算法的優(yōu)劣，并且最壞情況下的時間復雜性較平均時間復雜性游可操作性。24簡述漸進時間復雜性上界的定義。參考解答：T(n)是某算法的時間復雜性函數(shù)，f(n)是一簡單函數(shù)，存在正整數(shù)No和C,nNo,有T(n)vf(n),這種關(guān)系記作T(n)=O(f(n)。25二分檢索算法最多的比較次數(shù)？參考解答：二分檢索算法的最多的比較次數(shù)為logn。26快速排序算法最壞情況下需要多少次比較運算？參考解答：最壞情況下快速排序退化成冒泡排序，

18、需要比較n2次。27貪心算法的基本思想？參考解答：是一種依據(jù)最優(yōu)化量度依次選擇輸入的分級處理方法?；舅悸肥牵菏紫雀鶕?jù)題意，選取一種量度標準；然后按這種量度標準對這n個輸入排序，依次選擇輸入量加入部分解中。如果當前這個輸入量的加入，不滿足約束條件，則不把此輸入加到這部分解中28 回溯法的解(X1,X2,Xn)的隱約束一般指什么？參考解答：回溯法的解(X1,X2,Xn)的隱約束一般指個元素之間應滿足的某種關(guān)系。29 闡述歸并排序的分治思路。參考解答：講數(shù)組一分為二，分別對每個集合單獨排序，然后將已排序的兩個序列歸并成一個含n個元素的分好類的序列。如果分割后子問題還很大，則繼續(xù)分治，直到一個元素。

19、30 快速排序的基本思想是什么。參考解答：快速排序的基本思想是在待排序的N個記錄中任意取一個記錄，把該記錄放在最終位置后，數(shù)據(jù)序列被此記錄分成兩部分。所有關(guān)鍵字比該記錄關(guān)鍵字小的放在前一部分，所有比它大的放置在后一部分，并把該記錄排在這兩部分的中間，這個過程稱作一次快速排序。之后重復上述過程，直到每一部分內(nèi)只有一個記錄為止。31 什么是直接遞歸和間接遞歸？消除遞歸一般要用到什么數(shù)據(jù)結(jié)構(gòu)？參考解答：在定義一個過程或者函數(shù)的時候又出現(xiàn)了調(diào)用本過程或者函數(shù)的成分，既調(diào)用它自己本身，這稱為直接遞歸。如果過程或者函數(shù)P調(diào)用過程或者函數(shù)Q,Q又調(diào)用P,這個稱為間接遞歸。消除遞歸一般要用到棧這種數(shù)據(jù)結(jié)構(gòu)。3

20、2 什么是哈密頓環(huán)問題？參考解答：哈密頓環(huán)是指一條沿著圖G的N條邊環(huán)行的路徑，它的訪問每個節(jié)點一次并且返回它的開始位置。33 用回溯法求解哈密頓環(huán)，如何定義判定函數(shù)？參考解答：當前選擇的節(jié)點Xk是從未到過的節(jié)點，即Xk工Xi(i=1,2,k-1),且C(Xk-1,Xk)工人，如果k=-1,貝uc(xk,X1)34 請寫出prim算法的基本思想。參考解答：思路是：最初生成樹T為空，依次向內(nèi)加入與樹有最小鄰接邊的n-1條邊。處理過程：首先加入最小代價的一條邊到T，根據(jù)各節(jié)點到T的鄰接邊排序，選擇最小邊加入，新邊加入后，修改由于新邊所改變的鄰接邊排序，再選擇下一條邊加入，直至加入n-1條邊。三、算法

21、設計題1. 【最長上升子序列問題】(8分)一一提示：此題可采用動態(tài)規(guī)劃算法實現(xiàn)對于給定的一個序列，仁N叮000。我們可以得到一些遞增上升的子序列(不忌，川，無)，這里1<iAiA|<iANo比如，對于序列(1,7,3,5,9,4,8),有它的一些上升子序列，如(1,7),(3,4,8)等等。這些子序列中最長的長度是4,比如子序列(1,3,5,8)o你的任務：就是對于給定的序列，求出最長上升子序列的長度。要求寫出你設計的算法思想及遞推函數(shù)的公式表達。.參考解答：設f(i)表示：從左向右掃描過來直到以ai元素結(jié)尾的序列，獲得的最長上升子序列的長度，且子序列包含ai元素(1<n)。

22、r1i=1f二maxf(j)1:當ai?aj;1乞j:ii11i1；j(仁j:i),都有aiaj即，f(i)是從f(1),f(2),至Uf(i-1)中找最大的一個值,再加1?；蛘呔褪?。主要是看ai這個元素能否加入到之前已經(jīng)獲得的最長上升子序列，如果能加入，是之前已獲得的最長上升子序列長度加一；如果不能加入，就取這最后一個元素作為一個單獨子序列，長度為1。最后，所要求的整個序列的最長公共子序列長度為maxf(i):1<=i<=n例如，對于序列：4263152i1234567array4263152f(i)1122132評分準則：1)答到使用動態(tài)規(guī)劃算法，并且推導出動態(tài)規(guī)劃算法的遞推

23、函數(shù)公式表達，邊界設定清晰，本題即可得滿分；(閱卷時仔細看遞推公式表達，公式表達含義正確即可，因其表達形式可能不唯一)2)說明使用動態(tài)規(guī)劃算法，但對遞推函數(shù)表達錯誤或含糊，扣2分以上；3)其它情況酌情考慮。2. (10分)對下圖所示的連通網(wǎng)絡G用克魯斯卡爾(Kruskal)算法求G的最小生成樹T,請寫出在算法執(zhí)行過程中，依次加入T的邊集TE中的邊。說明該算法的貪心策略和算法的基本思想，并簡要分析算法的時間復雜度。參考解答TE=(3,4),(2,3),(1,5),(4,6)(4,5)(5分)貪心策略是每次都在連接兩個不同連通分量的邊中選權(quán)值最小的邊?；舅枷耄菏紫葘D中所有頂點都放到生成樹中，然

24、后每次都在連接兩個不同連通分量的邊中選權(quán)值最小的邊，將其放入生成樹中，直到生成樹中有n-1條邊。(4分)時間復雜度為：O(eloge)(1分)3. (15分)考慮n=3的批處理作業(yè)調(diào)度實例：tji機器1機器2作業(yè)1110作業(yè)231作業(yè)321其中血是作業(yè)Ji需要在機器j上處理的時間。對于給定的3個作業(yè)，制定一個最佳作業(yè)調(diào)度方案，使其完成時間和達到最小。要求：(1)畫出該問題的解空間樹；(5分)(2)寫出該問題的剪枝策略(即限界條件)，要求只保留第一個最優(yōu)解；(2分)(3) 按優(yōu)先隊列式分支限界法搜索解空間樹，并用剪枝策略對解空間樹中該剪枝的位置打；(5分)(4)給出最優(yōu)解及最優(yōu)值。(3分)參考解

25、答(1)5分X23121(2)若當前代價f>=當前最優(yōu)解代價bestf,則剪枝。2分(3) 見(1)中所畫的圖。5分(4) 最優(yōu)解為3,1,2,最優(yōu)值為25。3分4.【Gray碼構(gòu)造問題】(8分)一一提示：此題可采用分治遞歸算法實現(xiàn)問題描述：“格雷碼”是一個長度為2。的序列，滿足：(a)每個元素都是長度為n比特的串(b)序列中無相同元素(c)連續(xù)的兩個元素恰好只有1個比特不同例如：n=2時，格雷碼為00,01,11,10oGray碼是一種編碼，這種編碼可以避免在讀取時，因各數(shù)據(jù)位時序上的差異造成的誤讀。格雷碼在工程上有廣泛應用。但格雷碼不便于運算，請你設計種構(gòu)造方法，輸入長度序列n,輸出

26、格雷碼(你只要做出一種構(gòu)造方案即可，格雷碼并不唯一)。參考解答：此題可用分治法解決。當1時，輸出格雷碼0,1當n>1時，格雷碼的長度為2。，即共有2n個碼序列。止匕時，將問題一分為二，即上半部分和下半部分。上半部分最高位設為0,下半部分最高位設為1剩下n-1位的格雷碼的構(gòu)造采用遞歸的思路。評分準則：D答到使用分治算法，并且推導出分治算法的過程，邊界設定清晰(即當僅輸出1位的格雷碼如何處理)，本題即可得滿分；2)說明使用分治算法，但漏邊界條件，扣2分以上；10100其它情況酌情考慮5.(13分)給定帶權(quán)有向圖(如下圖所示)G = (V,E),其中每條邊的權(quán)是非負實數(shù)。另外，還給定V中的一個

27、頂點，稱為源?，F(xiàn)在要計算從源到所有其它各頂點的最短路長度。這里路的長度是指路上各邊權(quán)之和?，F(xiàn)采用Dijkstra算法計算從源頂點1到其它頂點間最短路徑。請將此過程填入下表中。迭代Sudist2dist3dist4dist5初始11234參考解答：(13分)迭代Sudist2dist3dist4dist5初始1-103010011,2210603010021,2,441050309031,2,4,331050306041,2,3,4,55105030606.(13分)有0-1背包問題如下：n=6,c=20,P=(4,8,15,1,6,3),W=(5,3,2,10,4,8)。其中n為物品個數(shù)，c為背包載重量，P表示物品的價值，W表示物品的重量。請問對于此0-1背包問題，應如何選擇放進去的物品，才能使到放進背包的物品總價值最大。P=(15,8,6,4,3,1)W=(2,3,4,5,8,10),單位重量物品價值(7.5,2.67,1.5,0.8,0.375,0.1)參考解答：(13分)可知隨著物品的重量增加