算法分析模擬題合集

西安電子科技大學(xué)網(wǎng)絡(luò)教育2010學(xué)年上學(xué)期期末考試模擬試題一課程名稱(chēng)：__算法分析與設(shè)計(jì)考試形式：閉卷學(xué)習(xí)中心：_________考試時(shí)間：90分鐘姓名：_____________學(xué)號(hào)：填空題（每小題4分，共計(jì)40分）1.通常只考慮三種情況下的時(shí)間復(fù)雜度，即最壞情況、最好情況和平均情況下的時(shí)間復(fù)雜度，分別記為T(mén)max(N)、Tmin(N)和Tavg(N)，實(shí)踐表明可操作性最好且最有實(shí)際價(jià)值的是最壞情況下的時(shí)間復(fù)雜度。2.的漸近表達(dá)式是，的漸近表達(dá)式是。3.根據(jù)符號(hào)O的定義易知O(1)=O(2)，用O(1)和O(2)表示同一個(gè)方法時(shí)，差別僅在于其中的常數(shù)因子。4.遞歸算法是指直接或間接地調(diào)用自身的算法，遞歸函數(shù)是指用函數(shù)自身給出定義的函數(shù)。5.貪心算法總是做出在當(dāng)前看來(lái)___最好__的選擇，也就是說(shuō)，貪心算法并不從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的____局部最優(yōu)選擇_。6.如果某問(wèn)題具有__貪心選擇性質(zhì)__和__最優(yōu)子結(jié)構(gòu)性質(zhì)_兩個(gè)重要性質(zhì)，該問(wèn)題可以用貪心算法求解。7.單源最短路徑問(wèn)題適合用__貪心算法__算法來(lái)求解、0-1背包問(wèn)題適合用__動(dòng)態(tài)規(guī)劃算法__算法來(lái)求解。8.分治法是將一個(gè)規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模__較小_的子問(wèn)題，這些子問(wèn)題_互相獨(dú)立_且與原問(wèn)題_相同_。遞歸地求解這些子問(wèn)題，然后將各個(gè)子問(wèn)題的解_合并_得到原問(wèn)題的解。9.動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素是__最優(yōu)子結(jié)構(gòu)（性質(zhì)）_和__子問(wèn)題重疊（性質(zhì)）__。10.__動(dòng)態(tài)規(guī)劃算法算法可以有效地解凸多邊形最優(yōu)三角剖分問(wèn)題，而_貪心算法_算法是求解最優(yōu)裝載問(wèn)題的有效方法。1.算法是滿(mǎn)足輸入、輸出、確定性和有限性的指令序列。程序與算法不同，程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。程序不滿(mǎn)足算法的有限性性質(zhì)。2.實(shí)踐表明，可操作性最好且最有實(shí)際價(jià)值的是_最壞__情況下的時(shí)間復(fù)雜性。3.直接或間接調(diào)用自身的算法稱(chēng)為_(kāi)遞歸算法_，用函數(shù)自身給出定義的函數(shù)是__遞歸函數(shù)_。4.找硬幣問(wèn)題是用_貪心算法__求解的典型例子，而最長(zhǎng)公共子序列問(wèn)題則適合用_動(dòng)態(tài)規(guī)劃算法_求解。5.函數(shù)式An2+Bn+C的復(fù)雜度是___，函數(shù)式Cn復(fù)雜度是__O(Cn)__。6.對(duì)于表達(dá)式、、，,按照漸近階從低到高的順序排列,順序是____、___、____、___。7.二分搜索算法是應(yīng)用__分治策略__的典型例子。這個(gè)方法很好地利用n個(gè)元素__已排好序__這個(gè)條件。可在最壞情況下用__時(shí)間完成搜索,而順序搜索法在最壞情況下需要__時(shí)間完成搜索。8.如果某問(wèn)題具有__最優(yōu)子結(jié)構(gòu)（性質(zhì)）__和__子問(wèn)題重疊（性質(zhì)）___兩個(gè)重要性質(zhì)_，該問(wèn)題可以用動(dòng)態(tài)規(guī)劃算法求解。9.備忘錄方法是動(dòng)態(tài)規(guī)劃算法的變形。與動(dòng)態(tài)規(guī)劃算法不同的是，備忘錄方法的遞歸方式是自頂向下，而動(dòng)態(tài)規(guī)劃算法的遞歸方式則是自底向上。10.部分背包問(wèn)題適用于__貪心算法__算法求解、而0-1背包問(wèn)題適用于__動(dòng)態(tài)規(guī)劃算法___算法求解。1.算法是滿(mǎn)足輸入、輸出、確定性和有限性等四個(gè)性質(zhì)的指令序列。2.算法復(fù)雜性的高低體現(xiàn)在運(yùn)行該算法所需的計(jì)算機(jī)資源的多少上，計(jì)算機(jī)的資源最重要的是時(shí)間和空間（即存儲(chǔ)器），因此算法的復(fù)雜性有時(shí)間復(fù)雜性和空間復(fù)雜性之分。3.與分治法類(lèi)似，動(dòng)態(tài)規(guī)劃算法的基本思想是__將待求解問(wèn)題分解為若干個(gè)子問(wèn)題__，先求解__子問(wèn)題_，然后從這些解得到原問(wèn)題的解。與分治法不同的是，適合用動(dòng)態(tài)規(guī)劃算法求解的問(wèn)題，經(jīng)分解得到的子問(wèn)題往往不是__互相獨(dú)立__的。4.Java語(yǔ)言的類(lèi)(class)體現(xiàn)了抽象數(shù)據(jù)類(lèi)型(ADT)的思想，一般由4個(gè)部分組成：類(lèi)名、數(shù)據(jù)成員、方法和訪(fǎng)問(wèn)修飾。5.抽象數(shù)據(jù)類(lèi)型的英文簡(jiǎn)稱(chēng)是ADT，它是算法的一個(gè)__數(shù)據(jù)模型_連同定義在該模型上并作為算法構(gòu)件的一組__運(yùn)算__。6.O(f)+O(g)=O(f+g)__，O(f)O(g)=O(fg)。7.分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模__較小__的相同問(wèn)題,以便各個(gè)擊破，____分而治之___。8.動(dòng)態(tài)規(guī)劃算法的第一步通常是刻畫(huà)最優(yōu)解的結(jié)構(gòu)。當(dāng)問(wèn)題的最優(yōu)解包含了其___子問(wèn)題___的最優(yōu)解時(shí)，稱(chēng)該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。9.動(dòng)態(tài)規(guī)劃算法與貪心算法的主要區(qū)別是__貪心選擇性質(zhì)__性質(zhì)。10.表示最優(yōu)前綴碼的二叉樹(shù)總是一顆完全二叉樹(shù)，即樹(shù)中任一個(gè)結(jié)點(diǎn)都有兩個(gè)兒子結(jié)點(diǎn)。二、簡(jiǎn)答題（每小題10分，共計(jì)40分）1.如果只需要求解問(wèn)題的最優(yōu)值，動(dòng)態(tài)規(guī)劃算法步驟是什么？如果需要構(gòu)造最優(yōu)解，則還需要加上什么步驟？如果只需要求解問(wèn)題的最優(yōu)值，動(dòng)態(tài)規(guī)劃算法步驟如下：（1）找出最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征；（2）遞歸地定義最優(yōu)值；（3）以自底向上的方式計(jì)算出最優(yōu)值；如果需要構(gòu)造最優(yōu)解，則還需要加上如下步驟：（4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。2.請(qǐng)簡(jiǎn)述什么是貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指，所求問(wèn)題的全局最優(yōu)解可以通過(guò)一系列局部最優(yōu)選擇，即貪心選擇來(lái)達(dá)到。3.請(qǐng)簡(jiǎn)述什么是最小生成樹(shù)。如果G的子圖G’是一棵包含G的所有頂點(diǎn)的樹(shù)，則稱(chēng)G’為G的生成樹(shù)。生成樹(shù)上各邊權(quán)的總和稱(chēng)為該生成樹(shù)的耗費(fèi)。在G的所有生成樹(shù)中，耗費(fèi)最小的生成樹(shù)稱(chēng)為G的最小生成樹(shù)。4.請(qǐng)簡(jiǎn)述貪心算法比動(dòng)態(tài)規(guī)劃算法效率高的原因。動(dòng)態(tài)規(guī)劃算法需要知道所有子問(wèn)題的解，而貪心算法不需要知道所有子問(wèn)題的解，它只是在每一步迭代中選擇看起來(lái)最好的解，并不從整體進(jìn)行最優(yōu)考慮，因此效率較高。1.請(qǐng)簡(jiǎn)述為什么部分背包問(wèn)題可以用貪心算法求解，而0-1背包問(wèn)題卻不能用貪心算法求解。對(duì)于部分背包問(wèn)題，依照貪心選擇策略，可以得到最優(yōu)解。而0-1背包問(wèn)題，貪心選擇之所以不能得到最優(yōu)解，是因?yàn)樵谶@種情況下，它無(wú)法保證最終能將背包裝滿(mǎn)，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。因而我們選擇的判斷標(biāo)準(zhǔn)出現(xiàn)了誤差。2.請(qǐng)寫(xiě)出如圖語(yǔ)法樹(shù)所對(duì)應(yīng)的矩陣鏈相乘的最優(yōu)完全加括號(hào)方式。((A1(A2A3))(A4(A5A6)))3.按照下表中的字母出現(xiàn)頻率，請(qǐng)畫(huà)出哈夫曼樹(shù)，并設(shè)計(jì)相應(yīng)的哈夫曼編碼。字母abcdef頻率(千次)4513121695哈夫曼編碼哈夫曼編碼：字母abcdef頻率(千次)4513121695哈夫曼編碼0101100111110111004.請(qǐng)簡(jiǎn)述動(dòng)態(tài)規(guī)劃算法求解最優(yōu)化問(wèn)題的步驟。（1）找出最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征；（2）遞歸地定義最優(yōu)值；（3）以自底向上的方式計(jì)算出最優(yōu)值；（4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。1.分治算法由哪些基本步驟組成？分治算法的時(shí)間復(fù)雜性常滿(mǎn)足什么樣的遞歸方程，寫(xiě)出該方程的一般形式，并指出其中各參數(shù)的意義。分治算法的一般步驟：分解→直接或遞歸求解子問(wèn)題→組合遞歸方程分治算法的時(shí)間復(fù)雜性C(n)往往滿(mǎn)足如下的遞歸方程：其中，n:問(wèn)題的規(guī)模。n0:可直接解的問(wèn)題規(guī)模的閾值。a:分解出的需要求解的子問(wèn)題的個(gè)數(shù)。n/c:分解出的子問(wèn)題的規(guī)模。g(n):分解規(guī)模為n的問(wèn)題以及組合相應(yīng)子問(wèn)題的解所需的時(shí)間。d:直接解規(guī)模為n0的問(wèn)題所需的時(shí)間。2.0-1背包問(wèn)題的形式化描述是什么？3.請(qǐng)簡(jiǎn)述貪心算法的簡(jiǎn)要求解步驟。貪心算法的簡(jiǎn)要求解步驟如下：將優(yōu)化問(wèn)題轉(zhuǎn)化成這樣的一個(gè)問(wèn)題，即先做出選擇，再解決剩下的一個(gè)子問(wèn)題。證明原問(wèn)題總是有一個(gè)最優(yōu)解是做貪心選擇得到的，從而說(shuō)明貪心選擇的安全性。說(shuō)明在做出貪心選擇后，剩余的子問(wèn)題具有這樣的一個(gè)性質(zhì)，即如果將子問(wèn)題的最優(yōu)解和我們所做的貪心選擇聯(lián)合起來(lái)，可以得出原問(wèn)題的一個(gè)最優(yōu)解。4.請(qǐng)簡(jiǎn)述歸并排序的基本思想。將待排序的序列分成長(zhǎng)度大致相等的兩個(gè)子序列，分別對(duì)2個(gè)子序列進(jìn)行排序，最終將2個(gè)已排好序的子序列合并為有序的完整序列。三、算法分析和設(shè)計(jì)題（每小題10分，共計(jì)20分） 1.請(qǐng)寫(xiě)出漢諾塔問(wèn)題的簡(jiǎn)要遞歸算法。publicstaticvoidHanoi(intn,inta,intb,intc) { if(n>0){Hanoi(n-1,a,c,b);Move(a,b);Hanoi(n-1,c,b,a)； }}2.請(qǐng)?jiān)O(shè)計(jì)一個(gè)在有序數(shù)組a[1..n]中二分搜索元素x的遞歸算法，要求若x在數(shù)組中則返回其下標(biāo)否則返回0.輸入：正整數(shù)n和存儲(chǔ)n個(gè)元素的數(shù)組a[1..n],被搜索的元素x輸出：若x在數(shù)組中則返回其下標(biāo)否則返回0i=binarysearch(1,n,a,x);returnI;endBINARYSEARCH1過(guò)程binarysearch(low,high,a,x)//在數(shù)組a的下標(biāo)為low到high范圍內(nèi)尋找x,//若找到x則返回其下標(biāo)否則返回0iflow>highthenreturn0;elsemid=;ifa[mid]=xthenreturnmid;elseifa[mid]<xthenreturnbinarysearch(low,mid-1,a,x);elsereturnbinarysearch(mid+1,high,a,x);endifendif1.請(qǐng)寫(xiě)出Fibonacci數(shù)列的遞歸定義式及其簡(jiǎn)要遞歸算法。Fibonacci數(shù)列的遞歸定義式是： 第n個(gè)Fibonacci數(shù)可以遞歸計(jì)算如下: publicstaticintFibonacci(intn) { if(n<=1)return1; returnFibonacci(n-1)+Fibonacci(n-2);}2.請(qǐng)寫(xiě)出二分搜索算法的簡(jiǎn)單程序描述(用java或C++語(yǔ)言)。publicstaticintBinarySearch(int[]a,intx,intn){intleft=0;intright=n-1;while(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left=middle+1;elseright=middle-1;}return-1;}1.請(qǐng)寫(xiě)出階乘函數(shù)的遞歸定義式及其簡(jiǎn)要遞歸