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

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