算法設(shè)計復(fù)習(xí)題

1、1.2.3.4.5.6.7.9.、選擇題選出不是算法所必須具備的特征(A有窮性 B確切性 C高效性 D可行性 不屬于給合問題的是( C )°A Euler的36名軍官問題 B圖的Hamiliton 下列( C )不是衡量算法的標(biāo)準(zhǔn)。A時間效率 B空間效率 C問題的難度 下列函數(shù)關(guān)系隨著輸入量增大增加量最快的是(3nA lognBnC2如果某一算法的執(zhí)行時間不超過輸入規(guī)模的A O(2 n)B O( n)下列程序段的算法時間復(fù)雜度是( for (i=1;i<=n ;i+)for (j=1;i<=m;m+)S;2 2A O(n )B O(m )下列程序段S執(zhí)行次數(shù)為( for

2、(i=1;i<=n ;i+)for (j=1;i<=m;m+)S;C)。C求二項式展開系數(shù)D集合的幕集2倍,0(m+n)D適應(yīng)能力D )。D n!那么算法漸近時間復(fù)雜度為(D "(n)D O(mn)B )。2 2AnB n /2使用F(n)=n*f(n-1)遞歸求FA 3次B 4次遞推關(guān)系 M( n)=M( n-1)+1,M(0)=0A O( n!)B O(2n)n(n +1)(4),Dn(n+1)/2DC遞歸調(diào)用子函數(shù)的次數(shù)為(C 5次D的算法時間復(fù)雜度為(C 0(n)D10.與遞推關(guān)系x( n)=2x( n-1)+1,x(1)=1等價的通項公式為(A x( n)=2n

3、 Bx( n)=2n-1C x( n)=2 n+111三個盤子的漢諾塔，至少要執(zhí)行移動操作次數(shù)為(A1次B3次C6次12. Fibonacci 數(shù)列第 10 項為(D)。A 3B13C2113. 12個金幣中有一枚是假幣，至少需要稱量的次數(shù)是(A 0B 1C 38次C0(1)B)。D x( n)=n!)°7次34)。4查的點的個數(shù)是(B) °A 1個B 2個C 6個D 8個15.下列圖形不屬于凸集的是(D ) °A三角形B四邊形C五邊形D 五角星16.對于凸集下列說法正確的是(B) °A凸集中的所有點都屬于凸包；B凸集中任意兩點的連線都在凸中；C凸集中任

4、意兩14. 二維最近鄰點問題， 如果使用分治法，對于一個子集上的某一點，另一個子集上需要檢 查的點的個數(shù)是(C )°A 1個B 2個C 6個D 8個15. 一維最近鄰點問題， 如果使用分治法，對于一個子集上的某一點，另一個子集上需要檢點的連線都不在凸集中；D 一個點集如果不是凸集，則點集中任意兩點的連線都不在凸集中717. 下列是動態(tài)規(guī)劃算法基本要素的是(A )。A最優(yōu)子結(jié)構(gòu)B構(gòu)造最優(yōu)解C貪心選擇因子D界限函數(shù)18. 下列問題中具有多項式解法的是(C)。A背包問題B生成排列序列問題Cn個元素的排序問題D集合的幕集問題19. 如果背包的容量為100,而物體共有10件，則使用動態(tài)規(guī)劃求解

5、背包問題數(shù)組大小為(D )。A 10B100C1000D1000020.排列問題屬于(D )。A可解問題B不可解冋題C P問題D NP問題21. (A )算法應(yīng)用到廣度優(yōu)先遍歷策略。A分支界限法B動態(tài)規(guī)劃法C分治法D回溯法22. Dijstra算法屬于(A )。A貪心算法B概率算法C回溯法D分支限界法23.若 f(n)=2n +3n ,2g(n)=100n +2n+100 ,則 f=O(g)為(B )。A真B假C無法確定D均不是24.若 f(n)=50n+logn,g(n)=10n+loglogn，則 f=O(g)為(A)。A真B假C無法確定D均不是25. Prim算法求最小生成樹米用的是(A

6、 )算法思想。A貪心算法B動態(tài)規(guī)劃法C回溯法D蠻力法二、簡答題1給出遞推公式 x(n)=x(n-1)+n,x(0)=0對應(yīng)的通項公式計算過程? 解：X( n) -X( n-1)=nX( n-1)-X( n-2)=n-1X(1)-X(0)=1X(n )-X(0)=( n+1) n2X( n)= (n+1) n22'之間的區(qū)別與聯(lián)系是什么？答：0描述增長率的上限.用來表示算法的精確階I描述增長率的下限只要當(dāng)考察問題規(guī)模充分大時，算法中基本語句的執(zhí)行次數(shù)在漸近意義下的階,3種等漸近符號。3. 什么是數(shù)據(jù)結(jié)構(gòu)，什么是算法，兩者有什么關(guān)系？答：數(shù)據(jù)結(jié)構(gòu)：計算機(jī)存儲/族素質(zhì)數(shù)據(jù)的方式。算法：一系列

7、解決問題的指令。程序=算法+數(shù)據(jù)結(jié)構(gòu)4. 將4n2,logn,3n,20n,2,n2/3,n!按漸近階從低到高順序排序。答：2<n2/3 <log n<20n<4n2 <3n<n!5. 舉例說明分治法、動態(tài)規(guī)劃法和貪心法適用范圍，及三者之間的區(qū)別。答：分治法：適用于原問題可劃分為子問題時如漢諾塔問題（循環(huán)賽，最近對，棋盤覆蓋 等）動態(tài)規(guī)劃：當(dāng)原問題可分解為子問題茄子問題重疊并且具有最優(yōu)子結(jié)構(gòu)時可用動態(tài)規(guī) 劃法，如TSP問題（多端最短路徑問題，0/1背包問題等）貪心：當(dāng)一個問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)且具有貪心選擇性時可用貪心算法，如最小生 成樹問題（背包問題，活動

8、安排問題等）在分治法德基礎(chǔ)上，滿足最優(yōu)子結(jié)構(gòu)性質(zhì)才能用動態(tài)規(guī)劃，在動態(tài)規(guī)劃可行的基礎(chǔ)上 滿足貪心選擇性才能用貪心。6簡述分治法、貪心法、蠻力法、回溯法、減治法的設(shè)計思想。答：分治：建一個難以直接解決的大問題劃分成一些規(guī)模較小的子問題，以便各個擊破， 分而治之。貪心：指根據(jù)當(dāng)前已有信息做出選擇，不從整體最優(yōu)考慮，只選擇局部最優(yōu)。蠻力：采用一定的策略將待求解問題的所有元素依次處理一次，從而找出問題的解。 回溯：只構(gòu)造可能解的一部分，然后評估這個部分解，如果這個部分解有可能導(dǎo)致一 個完全解，則對其進(jìn)一步構(gòu)造，否則，就不必繼續(xù)構(gòu)造這個解了。減治：把一個大問題劃分為若干子問題，但些子問題不需要分別求解，

9、只需求解其中 那個一個子問題。7舉例說明分治法和減治法的在設(shè)計上區(qū)別與聯(lián)系。答：分治法是將一個大問題分解為若干子問題分別求解，而減治法是只求解部分子問題。8簡述什么是歐拉回路，TSP問題，哈密頓回路問題。答：歐拉回路：圖G的一個回路，若它恰它通過 G中每條邊一次，則稱該回路為歐拉回路。 TSP：從圖的一個頂點出發(fā)，每個定點只能訪問一次，最后回到原點且使路徑最短。哈密頓回路：從一個城市出發(fā)，緊鍋蓋每一個城市恰好一次，然后回到出發(fā)城市。9. Strassen矩陣乘法可以利用什么算法實現(xiàn).答：可用分治法實現(xiàn)。三應(yīng)用題1.給出應(yīng)用動態(tài)規(guī)劃法設(shè)計算法的一般步驟，并用動態(tài)規(guī)劃法求下面多段圖中從頂點0到解:

10、d(0,9)=minc 01 +d(1,9) , Co2+d(2,9), C03 +d(3,9) d(1,9)=mi nc 14 +d(4,9) , ci5+d(5,9) d(2,9)=minc 24 +d(4,9) , C25+d(5,9) , C26 +d(6,9)d(3,9)=minc 35 +d(5,9) , C36+d(6,9) d(4,9)=minc 47 +d(7,9) , C48+d(8,9) d(5,9)=minc 57 +d(7,9) , C58+d(8,9) d(0,9)=minc 67 +d(7,9) , C68+d(8,9) d(7,9)= C79 =7 (7 9)d

11、(8,9)= C89 =3(8 t 9)d(6,9)=min6+7,5+3=8( 6t 8)d(5,9)= min8+7,6+3=9( 5t 8)d(4,9)= min5+7,6+3=9( 4t 8)d(3,9)= min4+9,7+8=13( 3t5)d(2,9)= min6+9,7+9,8+8=15( 2t4)d(1,9)= min 9+9,8+9=17( 1 t 5)d(0,9)= min 4+17,2+15,3+13=16( 0 t 3)最后得最短路徑為0 t 3t 5t 8 t 9長度為16o2.有4個物品，其重量分別為(4, 7, 5, 3)，物品的價值分別為(40, 42, 25

12、, 12)，背包容量為10。試設(shè)計3種貪心策略，并給出在每種貪心策略下背包問題的解。解：按單位價值最大，裝入物品1、3總價值65按背包容量最大，裝入物品2，4總價值543.給出23 13 49 6 31 19 28采用快速排序思想進(jìn)行排序時一次劃分的過程示意圖。 解：4.畫出當(dāng)有4個頂點的貨郎擔(dān)問題， 其費用矩陣如圖所示,求從頂點1出發(fā)，最后回到頂點1的最短191349631232819132363149281913623314928路線。畫出解空間樹搜索過程。14 (42),65.畫出當(dāng)n =4時,ooco1 78co5 172co6253co(12), 8 (40), 10 (25)給定背包容量W=10，每件物體的重量以及價值為 ，畫出解空間樹搜索過程。四、算法設(shè)計題1給定數(shù)組An，存儲n個實數(shù)，試設(shè)計一個算法，在最壞情況下用最少比較次數(shù)找出該 數(shù)組中元素的最大值和最小值，并說明采用了何種算法設(shè)計思想，其最壞比較多少次。2描述貪心法的求解過程，給出基于最近鄰點策略采用貪心法求解TSP問題偽代碼，并分析該算法的時間性能。3設(shè)計算法實現(xiàn)求數(shù)組中相差最小的兩個元素（稱為最接近數(shù)）的差。4有n枚硬幣，其中有一枚硬幣是假幣，且假幣的重量較輕，通過一架天平找出假幣，設(shè) 計找出假幣的方案，要求在最壞情況下用天平的比較次數(shù)最少。5. 個農(nóng)夫帶著一條狼、一只羊和一筐菜，想從河一邊（左