算法設計與分析試卷計本3班

1、文檔供參考，可復制、編制，期待您的好評與關注！ 算法設計與分析試卷填空題（20分，每空2分）1.算法的性質包括輸入、輸出、有限性。2.動態(tài)規(guī)劃算法的基本思想就將待求問題、先求解子問題，然后從這些子問題的解得到原問題的解。3.設計動態(tài)規(guī)劃算法的4個步驟：4.找出，并刻畫其結構特征。5.根據(jù)計算最優(yōu)值得到的信息，。6.流水作業(yè)調度問題的johnson算法：令N1=,N2=i|ai>=bj;將N1中作業(yè)依ai的。7.對于流水作業(yè)高度問題，必存在一個最優(yōu)調度，使得作業(yè)（i）和（i+1）滿足Johnson不等式。8.最優(yōu)二叉搜索樹即是的二叉搜索樹。9.下面程序段的所需要的計算時間為（ ）。int

2、MaxSum(int n, int *a, int &besti, int &bestj)int sum=0;for(int i=1;i<=n;i+) int thissum=0;for(int j=i;j<=n;j+) thissum+=aj;if(thissum>sum)sum=thissum;besti=i;bestj=j;return sum;10,有11個待安排的活動，它們具有下表所示的開始時間與結束時間，如果以貪心算法求解這些活動的最優(yōu)安排（即為活動安排問題：在所給的活動集合中選出最大的相容活動子集合），得到的最大相容活動子集合為活動（ 1，4，8

3、，11 ）。1413121110987654fi122886535031Si1110987654321i11,所謂貪心選擇性質是指（所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到）。12,所謂最優(yōu)子結構性質是指（問題的最優(yōu)解包含了其子問題的最優(yōu)解）。13,回溯法是回溯法是指（具有限界函數(shù)的深度優(yōu)先生成法）。14. 用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產生問題的解空間。在任何時刻，算法只保存從根結點到當前擴展結點的路徑。如果解空間樹 中從根結點到葉結點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為（O(h(n)）。15. 回溯法的算法框架按照問題的解空間一般

4、分為（子集樹）算法框架與（排列樹）算法框架。16. 用回溯法解0/1背包問題時，該問題的解空間結構為（子集樹）結構。17.用回溯法解批處理作業(yè)調度問題時，該問題的解空間結構為（排列樹）結構。18.用回溯法解0/1背包問題時，計算結點的上界的函數(shù)如下所示，請在空格中填入合適的內容：Typep Knap<Typew, Typep>:Bound(int i)/ 計算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 結點的上界 / 以物品單位重量價值遞減序裝入物品 while (i <= n && wi <= cle

5、ft) cleft -= wi; b += pi; i+; / 裝滿背包 if (i <= n) （b += pi/wi * cleft）; return b;19. 用回溯法解布線問題時，求最優(yōu)解的主要程序段如下。如果布線區(qū)域劃分為的方格陣列，擴展每個結點需O(1)的時間，L為最短布線路徑的長度，則算法共耗時 ( O(mn) )，構造相應的最短距離需要（O(L)）時間。for (int i = 0; i < NumOfNbrs; i+) nbr.row = here.row + offseti.row; nbr.col = here.col + offseti.col; if (

6、gridnbr.rownbr.col = 0) / 該方格未標記 gridnbr.rownbr.col = gridhere.rowhere.col + 1; if (nbr.row = finish.row) && (nbr.col = finish.col) break; / 完成布線 Q.Add(nbr); 20. 用回溯法解圖的m著色問題時，使用下面的函數(shù)OK檢查當前擴展結點的每一個兒子所相應的顏色的可用性，則需耗時（漸進時間上限）（O（mn）。Bool Color:OK(int k)/ for(int j=1;j<=n;j+)if(akj= =1)&&a

7、mp;(xj= =xk) return false;return true;21. 旅行售貨員問題的解空間樹是（排列樹）。二、單選題1、模塊化程序設計方法主要通過()來實現(xiàn)。    A.遞歸算法和遞歸程序    B.過程和函數(shù)的定義和調用C.程序的循環(huán)結構    D.對象           答案:B 2、text1.text的含義正確的是()。  

8、;  A.text1是控件名稱，text是控件屬性    B.text1是窗體名稱，text是控件C.text1是控件名稱，text是方法    D.text1是控件屬性，text是控件    答案:A 3、以下程序段運行后S的值是()。s = 0For i = 1 To 14    x = 2 * i - 1    If x Mod 3 = 0 Then s = s + 1Next i

9、    A.0  B.4    C.5    D.14    答案:C    4、數(shù)列1，4，7，10，13，的遞推公式為()。    A.f(1)=1;f(n)=n+3    B.f(1)=1;f(n)=n*2-1    C.f(1)=1;f(n)=n*2+1

10、0;   D.f(1)=1;f(n)=f(n-1)+3    答案:D 5、對于對象及其特征的錯誤理解是()。    A.對象都具有一個標識自己以區(qū)別其他對象的名字。    B.對象都具有自身的屬性及其屬性值。    C.對象一般只用數(shù)據(jù)表示屬性，但不用代碼表示行為。    D.對象都具有自身的行為(操作)。    答

11、案:C 6、VB函數(shù)Left ()從字串左端取部分字串，那么Left("Visual Basic 6.0", 8)的值為()。    A.Visual B    B.Visual    C.Visual Ba    D.asic 6.0    答案:A 7、程序段如下：c ="1234"For i = 1 To 4  

12、  Print _，Next如果要讓程序運行后得到如下結果：1 12 123 1234則在下劃線處應填入的內容為()。    A.Right(c,i)    B.Left(c,i)    C.Mid(c,i,1)    D.Mid(c,i,i)    答案:B8、若X = True，執(zhí)行If X Then X = 0 Else X = 1后X的結果為()。A.True 

13、0;  B.編譯錯誤    C.1    D.0    答案:D 9、若x = False, y = True，執(zhí)行If x And y  Then x = 0Else x = 1后X的結果為()。    A.False    B.1    C.編譯錯誤    D.0 

14、   答案:B 10、以下程序段運行時語句k=k+1執(zhí)行次數(shù)為()次。k=20do while (k=0)    k=k+1loop    A.20    B.無數(shù)次    C.1    D.0    答案:D 11、如果A=30，B=40,執(zhí)行T=B:A=T:B=A語句后,A、B和T的值是()。  

15、;  A.30、40、30    B.40、40、40    C.30、30、30    D.40、30、40    答案:B 12、用選擇排序法對數(shù)據(jù)7，6，3，9，2從大到小排序，共需經(jīng)過()次數(shù)據(jù)對調。    A.3    B.4    C.5   &#

16、160;D.10    答案:A 13、采用模塊化方法得到的系統(tǒng)是由()的模塊構成的。    A.沒有連接    B.函數(shù)    C.互相連接    D.過程    答案:C    14、(1.5分)下列程序段運行后X的值是()。x = 0For i = 1 To 5    Fo

17、r j = i To 3        x = x + 1    Next jNext i    A.0    B.5    C.6    D.15    答案:C 15、要從n個數(shù)據(jù)元素中順序查找一個元素，最多查找次數(shù)是()。    A.1

18、0;   B.n    C.n/2    D.lgn    答案:B        16、對半查找算法的前提是()。    A.被查找數(shù)據(jù)元素個數(shù)是奇數(shù)    B.被查找數(shù)據(jù)元素個數(shù)是偶數(shù)    C.被查找數(shù)據(jù)元素是有序的  &#

19、160; D.被查找數(shù)據(jù)元素是無序的    答案:C 17、用折半查找法從數(shù)列3，6，7，10，12，16，25，30，75中找到數(shù)據(jù)10的最少查找次數(shù)是()。    A.2    B.3    C.4    D.7    答案:B 18、對象的特征稱為()，我們可以把()看作對象的響應，把()看作對象的動作。 

20、60;  A.屬性，事件，方法    B.屬性，方法，事件    C.方法，事件，屬性    D.方法，屬性，事件    答案:A    19、設置一個控件在窗體上的位置可修改控件的()屬性。    A.Width、Height    B.Visible、Enabled  

21、60; C.Top、Left    D.Style    答案:C    20、算法與程序的關系()。    A.算法是對程序的描述    B.算法決定程序，是程序設計的核心    C.算法與程序之間無關系    D.程序決定算法，是算法設計的核心    答案:B

22、60;   21、當a=5,b=7,c=-2,d=1時，下列結果為False的是()。    A.a + b c + d And a = 5 Or Not c 0 Or d 0    B.c + d a + b And a = 5 Or Not c 0 Or d 0    C.a + b c + d And a 5 Or Not c 0 Or d 0    D.a + d b + c And a = 5 O

23、r Not c 0 Or d 0    答案:D    22、在流程圖中表示算法中的條件判斷時使用()圖形框。    A.菱形框     B.矩形框    C.圓形框    D.平行四邊形框    答案:A    23、VB語言中，下列各種基本數(shù)據(jù)類型說明符中表示單精度

24、實型數(shù)的是()。    A.Integer    B.Boolean    C.Single    D.String    答案:C    24、程序的基本結構有順序結構、()和循環(huán)結構。    A.邏輯結構    B.選擇結構    C.

25、模塊結構    D.層次結構    答案:B   25、一個算法應該具備幾個方面的基本特征，下面不屬于算法基本特征的是()。    A.輸入輸出    B.有窮性    C.確定性    D.執(zhí)行性    答案:D 26、人們利用計算機解決問題的基本過程一般有如下四個步驟（），請

26、按各步驟的先后順序在下列選項中選擇正確的答案()。調試程序 分析問題 設計算法 編寫程序    A.    B.    C.    D.    答案:B    27、以下哪個是合法的變量名()。    A.sqr    B.2pai    

27、C.cj1    D.a+b    答案:C    28、VB中保存工程文件的文件擴展名為()。    A.vbp    B.frm    C.doc    D.pas    答案:A    29、VB表達式5 + 2 * 12 Mod 8

28、 的值是()。    A.13    B.5    C.28    D.8    答案:B    30、由二進制編碼指令組表示程序的程序設計語言是()。    A.自然語言    B.機器語言    C.匯編語言  &#

29、160; D.高級語言    答案:B31.應用Johnson法則的流水作業(yè)調度采用的算法是（D）A. 貪心算法 B. 分支限界法 C.分治法 D. 動態(tài)規(guī)劃算法32.Hanoi塔問題如下圖所示?，F(xiàn)要求將塔座A上的的所有圓盤移到塔座B上，并仍按同樣順序疊置。移動圓盤時遵守Hanoi塔問題的移動規(guī)則。由此設計出解Hanoi塔問題的遞歸算法正確的為：（B）A. void hanoi(int n, int A, int C, int B) if (n > 0) hanoi(n-1,A,C, B); move(n,a,b); hanoi(n-1,

30、 C, B, A); Hanoi塔B. void hanoi(int n, int A, int B, int C) if (n > 0) hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); C. void hanoi(int n, int C, int B, int A) if (n > 0) hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); D. void hanoi(int n, int C, int A, int B) if (n > 0) hanoi

31、(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); 33. 動態(tài)規(guī)劃算法的基本要素為（C）A. 最優(yōu)子結構性質與貪心選擇性質B重疊子問題性質與貪心選擇性質C最優(yōu)子結構性質與重疊子問題性質D. 預排序與遞歸調用34. 算法分析中，記號O表示（B）， 記號表示（A）， 記號表示（D）。A.漸進下界B.漸進上界C.非緊上界D.緊漸進界E.非緊下界 35. 以下關于漸進記號的性質是正確的有：（A）A.B. C. O(f(n)+O(g(n) = O(minf(n),g(n) D. 36. 能采用貪心算法求最優(yōu)解的問題，一般具有的重要性質為：（A）A. 最優(yōu)

32、子結構性質與貪心選擇性質B重疊子問題性質與貪心選擇性質C最優(yōu)子結構性質與重疊子問題性質D. 預排序與遞歸調用37. 回溯法在問題的解空間樹中，按（D）策略，從根結點出發(fā)搜索解空間樹。A.廣度優(yōu)先 B. 活結點優(yōu)先 C.擴展結點優(yōu)先 D. 深度優(yōu)先38. 分支限界法在問題的解空間樹中，按（A）策略，從根結點出發(fā)搜索解空間樹。 A 廣度優(yōu)先 B. 活結點優(yōu)先 C.擴展結點優(yōu)先 D. 深度優(yōu)先39. 程序塊（A）是回溯法中遍歷排列樹的算法框架程序。void backtrack (int t) if (t>n) output(x); else for (int i=t;i<=n;i+) s

33、wap(xt, xi); if (legal(t) backtrack(t+1); swap(xt, xi); A.void backtrack (int t) if (t>n) output(x); else for (int i=0;i<=1;i+) xt=i; if (legal(t) backtrack(t+1); B. void backtrack (int t) if (t>n) output(x); else for (int i=0;i<=1;i+) xt=i; if (legal(t) backtrack(t-1); C.void backtrack

34、(int t) if (t>n) output(x); else for (int i=t;i<=n;i+) swap(xt, xi); if (legal(t) backtrack(t+1); D.40. 回溯法的效率不依賴于以下哪一個因素？（C ）產生xk的時間；滿足顯約束的xk值的個數(shù)；問題的解空間的形式； 計算上界函數(shù)bound的時間；滿足約束函數(shù)和上界函數(shù)約束的所有xk的個數(shù)。計算約束函數(shù)constraint的時間；41. 常見的兩種分支限界法為（D）A. 廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法；B. 隊列式（FIFO）分支限界法與堆棧式分支限界法；C. 排列樹法與子集樹

35、法；D. 隊列式（FIFO）分支限界法與優(yōu)先隊列式分支限界法；42. k帶圖靈機的空間復雜性S(n)是指（B）k帶圖靈機處理所有長度為n的輸入時，在某條帶上所使用過的最大方格數(shù)。k帶圖靈機處理所有長度為n的輸入時，在k條帶上所使用過的方格數(shù)的總和。k帶圖靈機處理所有長度為n的輸入時，在k條帶上所使用過的平均方格數(shù)。k帶圖靈機處理所有長度為n的輸入時，在某條帶上所使用過的最小方格數(shù)。43. NP類語言在圖靈機下的定義為（D）NP=L|L是一個能在非多項式時間內被一臺NDTM所接受的語言；NP=L|L是一個能在多項式時間內被一臺NDTM所接受的語言；NP=L|L是一個能在多項式時間內被一臺DTM所

36、接受的語言；NP=L|L是一個能在多項式時間內被一臺NDTM所接受的語言；44. 記號O的定義正確的是（A）。O(g(n) = f(n) | 存在正常數(shù)c和n0使得對所有nn0有：0 f(n) cg(n) ；O(g(n) = f(n) | 存在正常數(shù)c和n0使得對所有nn0有：0 cg(n) f(n) ；O(g(n) = f(n) | 對于任何正常數(shù)c>0，存在正數(shù)和n0 >0使得對所有nn0有：0 f(n)<cg(n) ；O(g(n) = f(n) | 對于任何正常數(shù)c>0，存在正數(shù)和n0 >0使得對所有nn0有：0 cg(n) < f(n) ；45. 記

37、號的定義正確的是（B）。O(g(n) = f(n) | 存在正常數(shù)c和n0使得對所有nn0有：0 f(n) cg(n) ；O(g(n) = f(n) | 存在正常數(shù)c和n0使得對所有nn0有：0 cg(n) f(n) ；(g(n) = f(n) | 對于任何正常數(shù)c>0，存在正數(shù)和n0 >0使得對所有nn0有：0 f(n)<cg(n) ；(g(n) = f(n) | 對于任何正常數(shù)c>0，存在正數(shù)和n0 >0使得對所有nn0有：0 cg(n) < f(n) ；三、判斷題1、VB表達式（A & B & C）的值一定是字符型數(shù)據(jù)。 &#

38、160;  對2、程序循環(huán)結構中的循環(huán)體語句將根據(jù)實際情況（條件）確定執(zhí)行次數(shù)。    對3、程序通過編譯可以有效發(fā)現(xiàn)程序的語法錯誤。    對4、在VB中，Int(100 * Rnd + 1)的取值范圍是1100之間的所有整數(shù)（包括1和100）對5、運行程序時，程序中的所有語句都要運行一次或多次。    錯6、算法有五大特征，其中包括輸入和輸出這兩種，意思就是說一個算法必須要有輸入，也必須要有輸出。    錯7、在

39、VB中，編寫程序代碼在代碼編輯窗口中進行。代碼由語句、常數(shù)和聲明部分組成。    對8、VB的所有控件在程序運行以后都是可見的。    錯9、在VB程序設計中，方法表示了對象的行為，即對象所能完成的某種操作。  對10、控件是應用程序的圖形界面中顯示可供用戶操縱，并可控制應用程序的圖形界面元素，是VB可視化編程的基本操作對象。   對11、如果知道一個三角形的兩個角和一條邊的值，可以用解析法設計程序求解該三角形的面積。   對12、在面

40、向對象程序設計中，類是對多個對象的抽象，因此，同一類的不同對象只能有不同的對象名，屬性值則相同。    錯13、列舉一切與命題相關的情況，然后根據(jù)問題設定的條件，逐個加以檢查，找到滿足條件的解答的方法稱為窮舉法。    對14、遞歸算法就是一種直接或間接地調用自身的算法。    對15、對一個排好序的數(shù)組來說，要查找其中的一個元素，使用二分查找法查找速度最快。  錯16、已知三角形的兩邊分別為a、b，它們的夾角為0.6弧度，在VB中可用公式(a * b *

41、 Sin(0.6) / 2)求出該三角形的面積。   對17、條件語句在執(zhí)行過程中將由電腦隨機選擇執(zhí)行哪部分語句。    錯18、匯編語言實際是一種符號化的機器語言，它采用英文助記符代替機器指令，比機器語言容易識別和記憶，從而提高了程序的可讀性。    對19、在一個循環(huán)語句的循環(huán)體中含有另一個循環(huán)語句，肯定出現(xiàn)死循環(huán)。    錯20、算法就是用計算機語言編寫的程序。    錯21、用計算機解決某個問題的算法只有一種

42、。    錯22、VB中的算術運算符*(乘)、/(除)、(整除)、Mod(取余數(shù))的運算優(yōu)先級相同。   錯23、用高級語言編寫的必須經(jīng)過翻譯器將其翻譯成機器語言，才能在計算機上執(zhí)行。  對24、所有的程序都是從程序中的第一條語句開始按順序執(zhí)行的。    錯25、在VB程序設計中，對象的行為稱為方法。    對26、如果程序經(jīng)過編譯未發(fā)現(xiàn)錯誤，那么程序的調試就完成了。    錯27、算法是程序設計的核心，是

43、程序設計的靈魂。    對28、窗體是VB程序設計的基礎，各種控件對象必須建立在窗體上，一個窗體對應一個窗體模塊。    對29、在面向對象程序設計中，一個程序對象的屬性用變量來表示，而對象的行為用對象中的代碼段來實現(xiàn)。    對30、程序循環(huán)結構中的循環(huán)體語句至少會執(zhí)行一次。    錯31、在VB中，開發(fā)的每個應用程序都被稱為工程，工程是組成一個應用程序的文件集合。    對32、凡是能夠用解析

44、法求解的問題都可以通過定量分析，并能用解析表達式來描述。  對33、VB中的事件只能由用戶引發(fā)。    錯34、已知三角形的兩邊分別為a、b，它們的夾角為60度，在VB中可用公式(a * b * Sin(60) / 2)求出該三角形的面積。    錯35、條件語句在執(zhí)行過程中會根據(jù)邏輯表達式的值選擇執(zhí)行哪部分語句。    對36、對半查找的實質是在一個有限且有序的對象中，通過每次減縮一半查找范圍而達到迅速確定目標的一個有效算法。   &

45、#160;對38、遞歸算法的實質是把問題轉化為規(guī)?？s小了的同類問題的子問題，然后遞歸調用函數(shù)或過程來表示問題的解。   對39、在一個循環(huán)語句的循環(huán)體中含有另一個循環(huán)語句，就形成了嵌套循環(huán)。   對40、列舉一切與命題相關的情況，然后根據(jù)問題設定的條件，逐個加以檢查，找到滿足條件的解答的方法稱為解析法。   錯四、綜合題（50分）1、當（a1,a2,a3,a4,a5,a6）=(-2,11,-4,13,-5,-2)時，最大子段和為ak(2<=k<=4)（5分）2、由流水作業(yè)調度問題的最優(yōu)子結構性

46、質可知，T（N，0）=（5分）3、最大子段和問題的簡單算法(10分)int maxsum(int n,int *a,int & bestj)intsum=0;for (int i=1;i<=n;i+)for (int j=i;j<=n;j+)int thissum=0;for(int k=i;k<=j;k+);if(thissum>sum)sum=thissum;；bestj=j; return sum;設計最優(yōu)二叉搜索樹問題的動態(tài)規(guī)劃算法OptimalBinarysearchTree? (15分)Void OptimalBinarysearchTree(int

47、 a,int n,int * * m, int * * w)for(int i=0;i<=n;i+) wi+1i=ai; mi+1i=;for(int r=0;r<n;r+)for(int i=1;i<=n-r;i+)int j=i+r;wij=wij-1+aj+bj;mij=;sij=i;for(int k=i+1;k<=j;k+)int t=mik-1+mk+1j;if() mij=t; sij=k;mij=t; sij=k;5、設n=4, (a1,a2,a3,a4)=(3,4,8,10), (b1,b2,b3,b4)=(6,2,9,15) 用兩種方法求4個作業(yè)的最

48、優(yōu)調度方案并計算其最優(yōu)值？（15分）五、簡答題（30分）1、將所給定序列a1:n分為長度相等的兩段a1:n/2和an/2+1:n，分別求出這兩段的最大子段和，則a1:n的最大子段和有哪三種情形？(10分)答： 2、由01背包問題的最優(yōu)子結構性質，可以對m（i,j）建立怎樣的遞歸式? (10分)3、01背包求最優(yōu)值的步驟分為哪幾步？（10分）七證明題1. 一個分治法將規(guī)模為n的問題分成k個規(guī)模為nm的子問題去解。設分解閥值n0=1，且adhoc解規(guī)模為1的問題耗費1個單位時間。再設將原問題分解為k個子問題以及用merge將k個子問題的解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治

49、法解規(guī)模為|P|=n的問題所需的計算時間，則有：通過迭代法求得T（n）的顯式表達式為：試證明T（n）的顯式表達式的正確性。2. 舉反例證明0/1背包問題若使用的算法是按照pi/wi的非遞減次序考慮選擇的物品，即只要正在被考慮的物品裝得進就裝入背包，則此方法不一定能得到最優(yōu)解（此題說明0/1背包問題與背包問題的不同）。證明：舉例如：p=7,4,4,w=3,2,2,c=4時，由于7/3最大，若按題目要求的方法，只能取第一個，收益是7。而此實例的最大的收益應該是8，取第2，3 個。3. 求證：O(f(n)+O(g(n) = O(maxf(n),g(n) 。證明：對于任意f1(n) O(f(n) ，存

50、在正常數(shù)c1和自然數(shù)n1，使得對所有nn1，有f1(n) c1f(n) 。類似地，對于任意g1(n) O(g(n) ，存在正常數(shù)c2和自然數(shù)n2，使得對所有nn2，有g1(n) c2g(n) 。令c3=maxc1, c2， n3 =maxn1, n2，h(n)= maxf(n),g(n) 。則對所有的 n n3，有f1(n) +g1(n) c1f(n) + c2g(n) c3f(n) + c3g(n)= c3(f(n) + g(n) c32 maxf(n),g(n) = 2c3h(n) = O(maxf(n),g(n) .4. 求證最優(yōu)裝載問題具有貪心選擇性質。（最優(yōu)裝載問題：有一批集裝箱要裝

51、上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。設集裝箱已依其重量從小到大排序，(x1,x2,xn)是最優(yōu)裝載問題的一個最優(yōu)解。又設 。如果給定的最優(yōu)裝載問題有解，則有。） 證明：六解答題機器調度問題。問題描述：現(xiàn)在有n件任務和無限多臺的機器，任務可以在機器上得到處理。每件任務的開始時間為si，完成時間為fi，si<fi 。si，fi為處理任務i的時間范圍。兩個任務i，j重疊指兩個任務的時間范圍區(qū)間有重疊，而并非指i，j的起點或終點重合。例如：區(qū)間1，4與區(qū)間2，4重疊，而與4，7不重疊。一個可行的任務分配是指

52、在分配中沒有兩件重疊的任務分配給同一臺機器。因此，在可行的分配中每臺機器在任何時刻最多只處理一個任務。最優(yōu)分配是指使用的機器最少的可行分配方案。問題實例：若任務占用的時間范圍是1，4，2，5，4，5，2，6，4，7，則按時完成所有任務最少需要幾臺機器？（提示：使用貪心算法）畫出工作在對應的機器上的分配情況。2. 已知非齊次遞歸方程： ，其中，b、c是常數(shù)，g(n)是n的某一個函數(shù)。則f(n)的非遞歸表達式為：?，F(xiàn)有Hanoi塔問題的遞歸方程為： ，求h(n)的非遞歸表達式。解：利用給出的關系式，此時有：b=2, c=1, g(n)=1, 從n遞推到1，有：3. 單源最短路徑的求解。問題的描述：給定帶權有向圖（如下圖所示）G =(V,E)，其中每條邊的權是非負實數(shù)。另外，還給定V中的一個頂點，稱為源?，F(xiàn)在要計算從源到所有其它各頂點的最短路長度。這里路的長度是指路上各邊權之和。這個問題通常稱為單源最短路徑問題。解法：現(xiàn)采用Dijkstra算法計算從源頂點1到其它頂點間最短路徑。請將此過程填入下表中。432110030maxint10-1初始dist5dist4dist3dist2uS迭代4. 請寫出用回溯法解裝載問題的函數(shù)。裝載問題：有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且。裝載問題要求確定是否有一個合理的裝載