算法設(shè)計(jì)方案與分析測(cè)驗(yàn)題計(jì)本班

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

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

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

4、）算法框 架與（排列樹）算法框架。16. 用回溯法解0/1背包問題時(shí)，該問題的解空間結(jié)構(gòu)為（子集樹） 結(jié)構(gòu)。17用回溯法解批處理作業(yè)調(diào)度問題時(shí)，該問題的解空間結(jié)構(gòu)為（排 列樹）結(jié)構(gòu)。18用回溯法解0/1背包問題時(shí)，計(jì)算結(jié)點(diǎn)的上界的函數(shù)如下所示，請(qǐng)?jiān)诳崭裰刑钊牒线m的內(nèi)容：Typep Kn ap<Typew, Typep>:Boun d(i nt i)/計(jì)算上界Typew cleft = c - cw; /剩余容量Typep b = cp; /結(jié)點(diǎn)的上界/以物品單位重量價(jià)值遞減序裝入物品while (i <= n && wi <= cleft) cleft

5、-= wi;b += pi;i+;/ 裝滿背包if (i <= n)(b += pi/wi * cleft)return b;19. 用回溯法解布線問題時(shí)，求最優(yōu)解的主要程序段如下。如果布線 區(qū)域劃分為n m的方格陣列，擴(kuò)展每個(gè)結(jié)點(diǎn)需0(1)的時(shí)間，L為最短 布線路徑的長度，則算法共耗時(shí) (0(mn)，構(gòu)造相應(yīng)的最短距離 需要(O(L)時(shí)間。20. 用回溯法解圖的m著色問題時(shí)，使用下面的函數(shù)0K檢查當(dāng)前擴(kuò) 展結(jié)點(diǎn)的每一個(gè)兒子所相應(yīng)的顏色的可用性，則需耗時(shí)（漸進(jìn)時(shí)間上 限）（0 （mn）Bool Color:OK(i nt k)/for(i nt j=1;j<=n ;j+)if(ak

6、j= =1)&&(xj= =xk) return false; return true;21. 旅行售貨員問題的解空間樹是（排列樹）二、單選題1、模塊化程序設(shè)計(jì)方法主要通過（）來實(shí)現(xiàn)。A. 遞歸算法和遞歸程序B.過程和函數(shù)的定義和調(diào)用C.程序的循環(huán)結(jié)構(gòu)D.對(duì)象答案:B2、textl.text的含義正確的是（）。A. textl是控件名稱，text是控件屬性B.textl是窗體名稱，text是控件C. textl是控件名稱，text是方法 D.textl是控件屬性，text是控件 答案:A3、以下程序段運(yùn)行后S的值是（）。s = 0For i = 1 To 14x = 2 * i

7、 - 1If x Mod 3 = 0 The n s = s + 1Next iA. 0 B.4C.5D.14 答案:C4、數(shù)列1, 4, 7, 10, 13,的遞推公式為（）。A. f（1）=1;f（ n）二 n+3B. f(1)=1;f( n)二 n*2-1C. f(1)=1;f( n)二n *2+1D. f(1)=1;f( n)=f( n-1)+3答案:D5、對(duì)于對(duì)象及其特征的錯(cuò)誤理解是()。A. 對(duì)象都具有一個(gè)標(biāo)識(shí)自己以區(qū)別其他對(duì)象的名字。B. 對(duì)象都具有自身的屬性及其屬性值。C. 對(duì)象一般只用數(shù)據(jù)表示屬性，但不用代碼表示行為。D. 對(duì)象都具有自身的行為(操作)。答案:C6、VB函數(shù)L

8、eft ()從字串左端取部分字串，那么Left("Visual Basic 6.0",8)的值為()。A.Visual B B.Visual C.Visual Ba D.asic 6.0 答案:A7、程序段如下：c ="1234"For i = 1 To 4Print，Next如果要讓程序運(yùn)行后得到如下結(jié)果：1 12 123 1234 則在下劃線處應(yīng)填入的內(nèi)容為()。A.R ight(c,i) 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

9、 后 X 的結(jié)果為()。A.True B.編譯錯(cuò)誤C.1D.0答案:D9、若 x = False, y = True, 執(zhí)行If x And y The n x = 0Else x = 1后X的結(jié)果為()。A.False B.1 C編譯錯(cuò)誤 D.0 答案:B10、 以下程序段運(yùn)行時(shí)語句k=k+1執(zhí)行次數(shù)為()次。k= 20do while (k=0)k=k+1loopA.20 B.無數(shù)次C.1D.0答案:D11、如果A=30, B=40,執(zhí)行T=B:A=T:B=A語句后,A、B和T的值是 ()。A.30、40、30 B.40、40、40C.30、30、30D.40、30、40 答案:B12、用

10、選擇排序法對(duì)數(shù)據(jù)7, 6, 3, 9, 2從大到小排序，共需經(jīng)過（） 次數(shù)據(jù)對(duì)調(diào)。A.3B.4C.5D.10 答案:A13、采用模塊化方法得到的系統(tǒng)是由（）的模塊構(gòu)成的。A. 沒有連接 B.函數(shù) C.互相連接 D.過程 答案:C14、（1.5 分）下列程序段運(yùn)行后X的值是（）。x = 0For i = 1 To 5For j = i To 3x = x + 1Next jNext iA.0B.5C.6D.15 答案:C15、 要從n個(gè)數(shù)據(jù)元素中順序查找一個(gè)元素，最多查找次數(shù)是（）。A.1 B.n C. n/2 D.lg n 答案:B16、對(duì)半查找算法的前提是（）。A.被查找數(shù)據(jù)元素個(gè)數(shù)是奇數(shù)B

11、.被查找數(shù)據(jù)元素個(gè)數(shù)是偶數(shù)C.被查找數(shù)據(jù)元素是有序的D.被查找數(shù)據(jù)元素是無序的答案:C17、用折半查找法從數(shù)列3, 6, 7, 10, 12, 16, 25, 30, 75中找到 數(shù)據(jù)10的最少查找次數(shù)是（）。A.2B.3C.4D.7 答案:B18、對(duì)象的特征稱為（），我們可以把（）看作對(duì)象的響應(yīng)，把（）看作對(duì)象 的動(dòng)作。A.屬性，事件，方法B.屬性，方法，事件C.方法，事件，屬性D.方法，屬性，事件答案:A19、 設(shè)置一個(gè)控件在窗體上的位置可修改控件的（）屬性。A.Width、Height B.Visible、EnabledC.Top、Left D.Style 答案:C20、算法與程序的關(guān)系

12、（）。A.算法是對(duì)程序的描述B.算法決定程序，是程序設(shè)計(jì)的核心C.算法與程序之間無關(guān)系D.程序決定算法，是算法設(shè)計(jì)的核心答案:B21、當(dāng) a=5,b=7,c=-2,d=1 時(shí)，下列結(jié)果為 False的是（）。A.a + b > c + d And a > = 5 Or Not c > 0 Or d v 0B.c + d>a + b And a：=5 Or Not c>0 Or d >0C.a + b>c + d And av5 Or Not c>0 Or d v0D.a + dvb + c And a：=5 Or Not cv0 Or d v0答

13、案:D22、 在流程圖中表示算法中的條件判斷時(shí)使用（）圖形框。A.菱形框 B.矩形框 C.圓形框 D.平行四邊形框 答案:A23、VB語言中，下列各種基本數(shù)據(jù)類型說明符中表示單精度實(shí)型數(shù) 的是（）。A.I nteger B.Boolea n C.Si ngle D.Stri ng 答案:C24、 程序的基本結(jié)構(gòu)有順序結(jié)構(gòu)、（）和循環(huán)結(jié)構(gòu)。A.邏輯結(jié)構(gòu)B.選擇結(jié)構(gòu)C.模塊結(jié)構(gòu)D.層次結(jié)構(gòu)答案:B25、 一個(gè)算法應(yīng)該具備幾個(gè)方面的基本特征，下面不屬于算法基本特 征的是（）。A.輸入輸出B.有窮性C.確定性D.執(zhí)行性 答案:D26、 人們利用計(jì)算機(jī)解決問題的基本過程一般有如下四個(gè)步驟（-），請(qǐng)按各步

14、驟的先后順序在下列選項(xiàng)中選擇正確的答案（）。調(diào)試程序 分析問題 設(shè)計(jì)算法 編寫程序A.B.C.D.答案:B27、以下哪個(gè)是合法的變量名（）。A.sqr B.2pai C.cjlD.a+b 答案:C28、VB中保存工程文件的文件擴(kuò)展名為（）。A.vbp B.frm C.doc D.pas 答案:A29、VB表達(dá)式5 + 2 * 12 Mod 8的值是（）。A.13B.5C.28D.8 答案:B30、 由二進(jìn)制編碼指令組表示程序的程序設(shè)計(jì)語言是（）。A.自然語言 B.機(jī)器語言C.匯編語言D.高級(jí)語言 答案:B31. 應(yīng)用Johnson法則的流水作業(yè)調(diào)度采用的算法是（D）A.貪心算法 B.分支限界法

15、C.分治法D.動(dòng)態(tài)規(guī)劃算法32. Hanoi塔問題如下圖所示?，F(xiàn)要求將塔座A上的的所有圓盤移到塔座B上，并仍按同樣順序疊置。移動(dòng)圓盤時(shí)遵守Hanoi塔問題的移 動(dòng)規(guī)則。由此設(shè)計(jì)出解Hanoi塔問題的遞歸算法正確的為：（B）A. void hanoi(int n, int A, int C, int B) if (n > 0)han oi( n-1,A,C, B);move( n, a,b);hanoi(n-1, C, B, A);Hanoi 塔B. void hanoi(int n, int A, int B, int C) if (n > 0)hanoi(n-1, A, C, B

16、);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(n-1, A, C, B); move( n, a,b);hanoi(n-1, C, B, A);33. 動(dòng)態(tài)規(guī)劃算法的基本要素為(C)A.最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)B .重疊子問題性質(zhì)與

17、貪心選擇性質(zhì)C .最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)D. 預(yù)排序與遞歸調(diào)用記號(hào)表34. 算法分析中，記號(hào) O表示(B),記號(hào)。表示(A), 示(D )。A. 漸進(jìn)下界B. 漸進(jìn)上界C. 非緊上界D. 緊漸進(jìn)界E. 非緊下界35. 以下關(guān)于漸進(jìn)記號(hào)的性質(zhì)是正確的有：(A)A. f (n) =°(g(n),g(n) =°(h(n)二 f(n) =°(h(n)B. f(n) =O(g(n),g(n) =0(h(n)二 h(n) =O(f(n)C. O(f(n)+O(g(n) = O(minf(n),g(n)D. f(n) =O(g(n)二 g(n) =0(f (n)36.

18、能采用貪心算法求最優(yōu)解的問題，一般具有的重要性質(zhì)為：（A）A.最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)B .重疊子問題性質(zhì)與貪心選擇性質(zhì)C .最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)D.預(yù)排序與遞歸調(diào)用37. 回溯法在問題的解空間樹中，按（D）策略，從根結(jié)點(diǎn)出發(fā)搜索 解空間樹。A.廣度優(yōu)先B.活結(jié)點(diǎn)優(yōu)先 C.擴(kuò)展結(jié)點(diǎn)優(yōu)先D.深度優(yōu)先38. 分支限界法在問題的解空間樹中，按（A）策略，從根結(jié)點(diǎn)出發(fā) 搜索解空間樹。A .廣度優(yōu)先B.活結(jié)點(diǎn)優(yōu)先C.擴(kuò)展結(jié)點(diǎn)優(yōu)先D.深度優(yōu)先39. 程序塊（A）是回溯法中遍歷排列樹的算法框架程序void backtrack (int t)if (t>n) output(x);elsef

19、or (int i=t;i<=n ;i+) swap(xt, xi);if (legal(t) backtrack(t+1); swap(xt, xi);B.C.void backtrack (int t)if (t>n) output(x);elsefor (int i=0;i<=1;i+) xt=i;if (legal(t) backtrack(t+1);void backtrack (int t)if (t>n) output(x);elsefor (int i=0;i<=1;i+) xt=i;if (legal(t) backtrack(t-1);void

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

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

22、被一臺(tái)DTM所接受的語言；NP=L|L是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)被一臺(tái)NDTM所接受的語言；44. 記號(hào)0的定義正確的是(A)O(g(n) = f(n) |存在正常數(shù)c和n0使得對(duì)所有n-nO有：0乞f(n)- cg(n);O(g(n) = f(n) |存在正常數(shù)c和n0使得對(duì)所有n 一 nO有：0 一 cg(n)s f(n) ；O(g(n) = f(n) |對(duì)于任何正常數(shù)c>0,存在正數(shù)和nO >0使得對(duì)所有n - nO 有：0 乞f(n)<cg(n) ;O(g(n) = f(n) |對(duì)于任何正常數(shù)c>0,存在正數(shù)和n0 >0使得對(duì)所有n-n0 有：0 -cg(n)

23、 < f(n) ;45. 記號(hào)門的定義正確的是(B)。O(g(n) = f(n) |存在正常數(shù)c和n0使得對(duì)所有n-n0有：0乞f(n)咗 cg(n)；O(g(n) = f(n) |存在正常數(shù)c和n0使得對(duì)所有n-n0有：0空cg(n)"f(n) ；(g(n) = f(n) |對(duì)于任何正常數(shù)c>0，存在正數(shù)和n0 >0使得對(duì)所有n - n0 有：0 乞f(n)<cg(n) ；(g(n) = f(n) |對(duì)于任何正常數(shù)c>0，存在正數(shù)和n0 >0使得對(duì)所有n-n0 有：0 -cg(n) < f(n) ；三、判斷題1、 VB表達(dá)式(A &

24、 B & C )的值一定是字符型數(shù)據(jù)。對(duì)2、程序循環(huán)結(jié)構(gòu)中的循環(huán)體語句將根據(jù)實(shí)際情況(條件)確定執(zhí)行次數(shù)。對(duì)3、程序通過編譯可以有效發(fā)現(xiàn)程序的語法錯(cuò)誤。4、在VB中，Int(100 * Rnd + 1)的取值范圍是1100之間的所有整 數(shù)(包括1和100)對(duì)5、 運(yùn)行程序時(shí)，程序中的所有語句都要運(yùn)行一次或多次。錯(cuò)6、算法有五大特征，其中包括輸入和輸出這兩種，意思就是說一個(gè)算法必須要有輸入，也必須要有輸出。錯(cuò)7、在VB中，編寫程序代碼在代碼編輯窗口中進(jìn)行。代碼由語句、常數(shù)和聲明部分組成。對(duì)8 VB的所有控件在程序運(yùn)行以后都是可見的。錯(cuò)9、在VB程序設(shè)計(jì)中，方法表示了對(duì)象的行為，即對(duì)象所能

25、完成的 某種操作。對(duì)10、 控件是應(yīng)用程序的圖形界面中顯示可供用戶操縱，并可控制應(yīng)用程序的圖形界面元素，是 VB可視化編程的基本操作對(duì)象。對(duì)11、 如果知道一個(gè)三角形的兩個(gè)角和一條邊的值，可以用解析法設(shè)計(jì)程序求解該三角形的面積。對(duì)12、在面向?qū)ο蟪绦蛟O(shè)計(jì)中，類是對(duì)多個(gè)對(duì)象的抽象，因此，同一類的不同對(duì)象只能有不同的對(duì)象名，屬性值則相同。錯(cuò)13、列舉一切與命題相關(guān)的情況，然后根據(jù)問題設(shè)定的條件，逐個(gè)加以檢查，找到滿足條件的解答的方法稱為窮舉法。對(duì)14、 遞歸算法就是一種直接或間接地調(diào)用自身的算法。對(duì)15、對(duì)一個(gè)排好序的數(shù)組來說，要查找其中的一個(gè)元素，使用二分查 找法查找速度最快。錯(cuò)16、已知三角形

26、的兩邊分別為a、b,它們的夾角為0.6弧度，在VB中可用公式（a * b * Sin（0.6） / 2）求出該三角形的面積。對(duì)17、 條件語句在執(zhí)行過程中將由電腦隨機(jī)選擇執(zhí)行哪部分語句。錯(cuò)18、 匯編語言實(shí)際是一種符號(hào)化的機(jī)器語言，它采用英文助記符代替 機(jī)器指令，比機(jī)器語言容易識(shí)別和記憶，從而提高了程序的可讀性。對(duì)19、 在一個(gè)循環(huán)語句的循環(huán)體中含有另一個(gè)循環(huán)語句，肯定出現(xiàn)死循 環(huán)。錯(cuò)20、 算法就是用計(jì)算機(jī)語言編寫的程序。錯(cuò)21、 用計(jì)算機(jī)解決某個(gè)問題的算法只有一種。錯(cuò)22、VB中的算術(shù)運(yùn)算符*（乘）、/（除）、（整除）、Mod（取余數(shù)）的運(yùn)算 優(yōu)先級(jí)相同。錯(cuò)23、 用高級(jí)語言編寫的必須經(jīng)過

27、翻譯器將其翻譯成機(jī)器語言，才能在 計(jì)算機(jī)上執(zhí)行。對(duì)24、 所有的程序都是從程序中的第一條語句開始按順序執(zhí)行的。錯(cuò)25、 在VB程序設(shè)計(jì)中，對(duì)象的行為稱為方法。對(duì)26、 如果程序經(jīng)過編譯未發(fā)現(xiàn)錯(cuò)誤，那么程序的調(diào)試就完成了。錯(cuò)27、 算法是程序設(shè)計(jì)的核心，是程序設(shè)計(jì)的靈魂。對(duì)28、窗體是VB程序設(shè)計(jì)的基礎(chǔ)，各種控件對(duì)象必須建立在窗體上，一個(gè)窗體對(duì)應(yīng)一個(gè)窗體模塊。對(duì)29、在面向?qū)ο蟪绦蛟O(shè)計(jì)中，一個(gè)程序?qū)ο蟮膶傩杂米兞縼肀硎?，而?duì)象的行為用對(duì)象中的代碼段來實(shí)現(xiàn)。對(duì)30、程序循環(huán)結(jié)構(gòu)中的循環(huán)體語句至少會(huì)執(zhí)行一次31、在VB中，開發(fā)的每個(gè)應(yīng)用程序都被稱為工程，工程是組成一個(gè)應(yīng)用程序的文件集合。對(duì)32、 凡

28、是能夠用解析法求解的問題都可以通過定量分析，并能用解析 表達(dá)式來描述。對(duì)33、 VB中的事件只能由用戶引發(fā)。錯(cuò)34、已知三角形的兩邊分別為a、b,它們的夾角為60度，在VB中可用公式（a * b * Sin（60） / 2）求出該三角形的面積。錯(cuò)35、條件語句在執(zhí)行過程中會(huì)根據(jù)邏輯表達(dá)式的值選擇執(zhí)行哪部分語句。對(duì)36、 對(duì)半查找的實(shí)質(zhì)是在一個(gè)有限且有序的對(duì)象中，通過每次減縮一半查找范圍而達(dá)到迅速確定目標(biāo)的一個(gè)有效算法。對(duì)38、遞歸算法的實(shí)質(zhì)是把問題轉(zhuǎn)化為規(guī)?？s小了的同類問題的子問題，然后遞歸調(diào)用函數(shù)或過程來表示問題的解。對(duì)39、 在一個(gè)循環(huán)語句的循環(huán)體中含有另一個(gè)循環(huán)語句，就形成了嵌套 循環(huán)。

29、對(duì)40、列舉一切與命題相關(guān)的情況，然后根據(jù)問題設(shè)定的條件，逐個(gè)加以檢查，找到滿足條件的解答的方法稱為解析法。錯(cuò)四、綜合題（50分）1、當(dāng)（a1,a2,a3,a4,a5,a6 =（-2,11,-4,13,-5,-2）時(shí)，最大子段和為刀 ak（2<=k<=4）（ 5 分）2、 由流水作業(yè)調(diào)度問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，T (N , 0) =( 5 分)3、最大子段和問題的簡單算法(10分)int maxsum(i nt n ,i nt *a,i nt & bestj)in tsum=0;for (i nt i=1;i< 二n ;i+)for (i nt j二i;jv 二n

30、;j+)int thissum=0;for(i nt k=i;k<=j;k+);if(thissum>sum)sum二thissum;>bestj二j;return sum;設(shè)計(jì)最優(yōu)二叉搜索樹問題的動(dòng)態(tài)規(guī)劃算法OptimalBi narysearchTree?(15 分)Void OptimalB in arysearchTree(i nt a,i nt n ,i nt * * m, int * * w)for(i nt i=0;i<=n; i+)wi+1i=ai; mi+1i=;for(i nt r=0 丁<n; r+)for(i nt i=1;i< 二n

31、-r;i+)in t j=i+r;wij=wij-1+aj+bj;mij=;sij=i；for(i nt k=i+1;k<=j;k+)int t=mik-1+mk+1j;if()mij=t; sij=k;mij=t; sij=k;5、設(shè) n=4,(a1,a2,a3,a4)=(3,4,8,10), (b1,b2,b3,b4)=(6,2,9,15)用兩種方法求4個(gè)作業(yè)的最優(yōu)調(diào)度方案并計(jì)算其最優(yōu)值？ (15分)五、簡答題(30分)1、將所給定序列a1:n分為長度相等的兩段a1:n/2和an/2+1:n,分別求出這兩段的最大子段和，則a1: n的最大子段和有哪三種情形？(10 分)2、由0 1背

32、包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以對(duì) m (i,j)建立怎樣的遞歸式？ (10分)3、0 1背包求最優(yōu)值的步驟分為哪幾步？ (10分)七.證明題1. 一個(gè)分治法將規(guī)模為n的問題分成k個(gè)規(guī)模為n/m的子問題去 解。設(shè)分解閥值n0=1，且adhoc解規(guī)模為1的問題耗費(fèi)1個(gè)單位時(shí) 間。再設(shè)將原問題分解為k個(gè)子問題以及用merge將k個(gè)子問題的解合并為原問題的解需用f(n)個(gè)單位時(shí)間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計(jì)算時(shí)間，則有:T(n )=0(1) n = 1kT (n / m)f (n) n 1l°gmnT(n) = nlogmk + 送 kj f(n/mj) 通過迭代法

33、求得T (n)的顯式表達(dá)式為：j試證明T (n)的顯式表達(dá)式的正確性。2. 舉反例證明0/1背包問題若使用的算法是按照 pi/wi的非遞減次序 考慮選擇的物品，即只要正在被考慮的物品裝得進(jìn)就裝入背包，則此方法不一定能得到最優(yōu)解(此題說明0/1背包問題與背包問題的不同)。證明：舉例如：p=7,4,4,w=3,2,2,c=4時(shí)，由于7/3最大，若按題 目要求的方法，只能取第一個(gè)，收益是 7。而此實(shí)例的最大的收益應(yīng) 該是8,取第2, 3個(gè)。3. 求證：O(f(n)+O(g(n) = O(maxf(n),g(n)。證明：對(duì)于任意f1(n) O(f(n)，存在正常數(shù)cl和自然數(shù)n1,使得對(duì)所有 n_n1

34、,有 f1(n) c1f(n)。類似地，對(duì)于任意g1(n) O(g(n),存在正常數(shù)c2和自然數(shù)n2,使得對(duì)所有nn2,有g(shù)1(n) -c2g(n)。令 c3=maxc1, c2， n3 =maxn1, n2， h(n)= maxf(n),g(n)。則對(duì)所有的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)裝載問題具有貪心選擇性質(zhì)。(最優(yōu)裝載問題：有一批集裝箱要裝上一艘載重量為 c的輪船。其中

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

36、是指在分 配中沒有兩件重疊的任務(wù)分配給同一臺(tái)機(jī)器。因此，在可行的分配中每臺(tái)機(jī)器在任何時(shí)刻最多只處理一個(gè)任務(wù)。最優(yōu)分配是指使用的機(jī)器 最少的可行分配方案。問題實(shí)例：若任務(wù)占用的時(shí)間范圍是 1，4，2，5，4，5，2，6，4, 7，則按時(shí)完成所有任務(wù)最少需要幾臺(tái)機(jī)器？(提示：使用 貪心算法)畫出工作在對(duì)應(yīng)的機(jī)器上的分配情況。f(n) =bf(n-1) g(n)2.已知非齊次遞歸方程：f(°"c，其中，b、c是常數(shù),nf(n)=cbn+瓦 bn_kg(i) g(n)是n的某一個(gè)函數(shù)。則f(n)的非遞歸表達(dá)式為：心 。h(n) =2h(n -1) 1現(xiàn)有Hanoi塔問題的遞歸方程為

37、：h(11 ，求h(n)的非遞歸表達(dá)式。解：利用給出的關(guān)系式，此時(shí)有：b=2, c=1, g(n)=1,從n遞推到1,有：n Ah(n) =cbnJL -二 bn 1_Lg(i)i 4-2nl 2n2 . 22 2 1=2n -13.單源最短路徑的求解。問題的描述：給定帶權(quán)有向圖(如下圖所示)G =(V,E),其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定 V中的一個(gè)頂點(diǎn)，稱為源。現(xiàn)在要 計(jì)算從源到所有其它各頂點(diǎn)的最短路長度。 這里路的長度是指路上各 邊權(quán)之和。這個(gè)問題通常稱為單源最短路徑問題。解法：現(xiàn)采用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑。 請(qǐng)將此過程填入下表中。迭代Sudist

38、2dist3dist4dist5初始1-10maxi nt3010012344請(qǐng)寫出用回溯法解裝載問題的函數(shù)。裝載問題：有一批共n個(gè)集裝箱要裝上2艘載重量分別為cl和c2的nZ Wj 蘭 G + C2輪船，其中集裝箱i的重量為wi，且7。裝載問題要求確定是否有一個(gè)合理的裝載方案可將這 n個(gè)集裝箱裝上這2艘輪船。如果 有，找出一種裝載方案。解: void backtrack (int i)搜索第i層結(jié)點(diǎn)if (i > n) /到達(dá)葉結(jié)點(diǎn)更新最優(yōu)解 bestx,bestw;return;r -= wi;if (cw + wi <= c) /搜索左子樹xi = 1;cw += wi;backtrack© + 1);cw -= wi;if (cw + r > bestw) xi = 0;/搜索右子樹backtrack(i + 1);r += wi;5. 用分支限界法解裝載問題時(shí)，對(duì)算法進(jìn)行了一些改進(jìn)，下面的程 序段給出了改進(jìn)部分；試說明斜線部分完成什么功能，以及這樣做的 原因，即采用這樣的方式，算法在執(zhí)行上有什么不同/檢查左兒子結(jié)點(diǎn)Type wt = Ew + wi; /左兒子結(jié)點(diǎn)