.算法分析與設計2016年11月考試考前練習題一、簡答題1. 算法設計通常有哪些方法？（至少列出4種）并指出哪些算法具有的某個共有性質。解答:算法設計方法有分治算法，貪心算法，動態規劃算法，歸納算法，回溯算法，分支限界算法等。分治算法，貪心算法，動態規劃算法等算法都具有最優子結構性質。 2. Fibonacci數列如下定義：（1）請設計一個遞歸算法，計算F(n)。（2）分析算法的時間復雜性。解答:（1）int fibonacci(int n) If(n = 1)return 1; return fibonacci(n-1)+fibonacci(n-2); （2）T(n)=T(n-1)+T(n-2)。3. 動態規劃算法的兩大基本要素分別是？解答:最優子結構性質和子問題的重疊性質。4. 簡述設計動態規劃算法的主要步驟。解答:（1）找出最優解的性質，并刻劃其結構特征（2）遞歸地定義最優值（3）以自底向上的方式計算出最優值（4）根據計算最優值時得到的信息，構造最優解。5. 給定如下順序搜索算法： int seqSearch(Type *a, int n, Type k) for(int i=0;in;i+) if (ai=k) return i; return -1; 則最壞時間復雜性和最好時間復雜性分別是多少？解答:最壞時間復雜性是O(n)，最好時間復雜性是O(1)。6. 用回溯法解圖的m著色問題時，使用下面的函數OK檢查當前擴展結點的每一個兒子所相應的顏色的可用性，則需耗時（漸進時間上限）為多少？Bool Color:OK(int k)/ for(int j=1;j=n;j+)if(akj= =1)&(xj= =xk) return false;return true;解答:O(mn)7. 下面程序段的所需要的計算時間為（ ）。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;解答:O(n2)8. 簡述什么是穩定的排序算法？解答:如果一個排序算法保留了等值元素在輸入中的相對順序，它就被稱為是穩定的。9. 算法設計的質量指標。解答:正確性：算法應滿足具體問題的需求；可讀性：算法應該好讀，以有利于讀者對程序的理解；健壯性：算法應具有容錯處理，當輸入為非法數據時，算法應對其作出反應，而不是產生莫名其妙的輸出結果。效率與存儲量需求：效率指的是算法執行的時間；存儲量需求指算法執行過程中所需要的最大存儲空間。一般這兩者與問題的規模有關。10. 對下圖中的有向圖，應用Dijkstra算法計算從源頂點4到其它頂點間最短路徑的過程。解答:11. 為什么用分治法設計的算法一般有遞歸調用？解答:子問題的規模還很大時，必須繼續使用分治法，反復分治，必然要用到遞歸。12. 簡述動態規劃方法所運用的最優化原理。解答:最優化原理用數學化的語言來描述：假設為了解決某一優化問題，需要依次作出n個決策D1，D2，Dn，如若這個決策序列是最優的，對于任何一個整數k，1 k n，不論前面k個決策是怎樣的，以后的最優決策只取決于由前面決策所確定的當前狀態，即以后的決策Dk+1，Dk+2，Dn也是最優的。13. 簡述歸并排序算法的分治方法。解答:歸并排序的分治是將數組從中間分開，分別對前后來那個部分進行排序，將排序后的兩個數組合并成整個數組的排序。這樣分治為遞歸過程，直到一個元素時返回。14. 簡述回溯法與分支限界法的相同點。解答:分支限界法與回溯法的相同點是：都是一種在問題的解空間樹T中搜索問題解的算法。15. 什么是貪心選擇性質和最優子結構性質？解答:當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。二、算法分析解答題1. 設有n個活動的集合E=1,2,n，其中每個活動都要求使用同一資源，并且在同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間和一個結束時間,且。如果選擇了活動i，則它在半開時間區間，內占用資源。若區間，與區間，不相交，則稱活動i與活動j是相容的。a）給出活動i與活動j是相容的定義。b）描述求解活動安排問題的貪心算法，并分析算法的時間復雜性。解答:a）若區間，與區間，不相交，則稱活動i與活動j是相容的。b）void GreedySelector(int n, Type s, Type f, bool A) sort(s,f,n);/按照活動的結束時間的非降序排列。 A1=true; int j=1; for (int i=2;i=fj) Ai=true; j=i; else Ai=false; 算法中，如果活動按照其結束時間的非降序排列，則其時間復雜性是O(n)；如果沒有排序，則要考慮為n個活動排序所需要的時間，則其時間復雜性是O(nlogn)。2. O(1)空間子數組換位算法：設a0:n-1是一個n維數組，k(1 k n-1)是一個非負整數。試設計一個算法將子數組a0 : k-1與ak+1 : n-1換位。要求算法在最壞情況下耗時O(n)，且只用O(1)的輔助空間。解答:解： 3次反轉算法：將數組ai : j反轉的算法 void reverse(int a, int i, int j) while (im then output no solution; return /無解，返回end if end for k=1; xk=1 /在第1站加滿油。 s1=m /s1為用汽車的當前油量可行駛至的地點與A點的距離 i=2 while s1