1、第3次作業一、填空題(本大題共30分，共10小題，每小題3分)1.程序的性能一般指程序的空間復雜性和 復雜性。2.計算機算法指的是解決問題的 和。最優子結構性質的含義是。4.貪心算法與動態規劃算法的主要區別是。5.有如下遞歸過程：void print(int w)(int i;if(w!=0)(print(w-1);for(i=1;i=w;i+) printf(3d”，w);printf(n”)； 調用語句print(4)的結果是。6.Edmonds-Karp算法規定，在剩余網絡中采用 尋找 路徑作為增廣路徑7.問題能夠應用分治算法思想進行求解的前提是問題的 性和解的性。8.在快速排序、插入排

2、序和歸并排序算法中，算法不是分治算法9.將矩陣鏈AAAAA在入處斷開，則m3,7=。3 4 5 6 75計算一個算法時間復雜度通常可以計算、或二、簡答題(本大題共30分，共5小題，每小題6分)下面程序段的所需要的計算時間為int 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;jsum) (sum=thissum;besti=i;bestj=j;return sum;請簡單描述一下插入排序算法思想。3.設G=(V,E)為流網絡f為流。證明

3、對于所有工匚33項=,Ford-Fulkerson算法的主要問題是什么？在三數取中劃分法中，第k小的元素要成為中心數，必須與一個比它更小的 元素以及一個比它大的元素一起被取出來，其概率等于多少？三、問答題(本大題共40分，共5小題，每小題8分)1.輸入三個不相同的數，求出其中的最小數。用自然語言描述算法。請概述最小代價生成樹的貪心選擇性質，并證明。3.簡述分治法在每一層遞歸上的三個步驟的具體內容證明 O(f(n)+O(g(n) = O(maxf(n), g(n)5.分治策略一定導致遞歸嗎如果是，請解釋原因。如果不是，給出一個不包含遞 歸的分治例子，并闡述這種分治和包含遞歸的分治的主要不同。答案

4、:一、填空題(30分，共10題，每小題3分)1.參考答案：時間解題方案：評分標準：2.參考答案：方法過程解題方案：評分標準：3.參考答案：問題的最優解包含其子問題的最優解解題方案：評分標準：貪心選擇性質解題方案：評分標準：5.參考答案:1 TOC o 1-5 h z 23 34 4 4解題方案：評分標準：6.參考答案：廣度優先搜索法最短評分標準：7.參考答案：可分可歸并解題方案：評分標準：8.參考答案：插入排序解題方案：評分標準：9.參考答案：m3,5 + m6,7 + p2p5p7評分標準：10.參考答案：循環次數基本操作的頻率計算步解題方案：評分標準：二、簡答題(30分，共5題，每小題6分

5、)1.參考答案：O(n2)解題方案：評分標準：2.參考答案：將無序子序列中的一個或幾個記錄“插入”到有序序列中，從而增加記錄的有 序子序列的長度。評分標準：3.參考答案：對所有 x,yEX, f(x,y)+f(y,x)=0。所以 f(X,X)+f(X,X)=0解題方案：評分標準：4.參考答案：當最大流值較大時可能發生的情況是每次尋找出來的增廣路徑，都只能將流網 絡的流量增加很小的值，這樣的話，會大大增加循壞的次數。尤其是|f*|二2E 時，算法的時間復雜度變成流網絡規模O(|V| + |E|)的指數函數O(|E| 2iei)。解題方案：評分標準：參考答案：3-以 u-kn（u - L（11 -

6、 2）解題方案：評分標準：三、問答題（40分，共5題，每小題8分）1.參考答案：先設置一個變量min，用于存放最小數。當輸入a、b、c三個不相同的數后， 先將a與b進行比較，把小者送給變量min，再把c與min進行比較，若cV min，貝。min=c。解題方案：評分標準：2.參考答案：貪心選擇的性質指的是局部最優選擇可以得到全局最優解決方案，在最小代價 生成樹中，其表現為每次選擇的為當前可選情況下權值最小的邊。證明：(1) 一定有一個最優解包含了當前權值最小的邊3抵.。假設最優解不 包含該邊，則將;.加入其中，會形成一個環，任意去掉環里比孔3.權值大的 一條邊，則形成了一個更優的解，與假設矛盾

7、。(2)選擇了3.后，子問題為去掉了孔；.關聯的點的剩余的點為 頂點集，剩余的邊為邊集的圖的最小代價問題，規模變小，性質不變。通過歸 納法，其可以通過貪心性質得到最優解。解題方案：評分標準：3.參考答案：分解：將原問題分解為若十個規模較小，相互獨立，與原問題形式相同的子問 題；解決：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問 題；合并：將各個子問題的解合并為原問題的解。解題方案：評分標準：4.參考答案：t(n) = 0 ff n)0 t(n) 0? n nc.= Og(n) = 0 s(n) 0? n n1- 0 tfn) - s(n) max (n0J n1。 t(n.j sfiij max nCiJ n1)所以 O(f