《算法分析與設(shè)計》2016年11月考試人大網(wǎng)校考前練習(xí)題.doc

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