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

1、1.2.3.4.5.6.7.9.、選擇題選出不是算法所必須具備的特征(A有窮性 B確切性 C高效性 D可行性 不屬于給合問(wèn)題的是( C )°A Euler的36名軍官問(wèn)題 B圖的Hamiliton 下列( C )不是衡量算法的標(biāo)準(zhǔn)。A時(shí)間效率 B空間效率 C問(wèn)題的難度 下列函數(shù)關(guān)系隨著輸入量增大增加量最快的是(3nA lognBnC2如果某一算法的執(zhí)行時(shí)間不超過(guò)輸入規(guī)模的A O(2 n)B O( n)下列程序段的算法時(shí)間復(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求二項(xiàng)式展開(kāi)系數(shù)D集合的幕集2倍,0(m+n)D適應(yīng)能力D )。D n!那么算法漸近時(shí)間復(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的算法時(shí)間復(fù)雜度為(C 0(n)D10.與遞推關(guān)系x( n)=2x( n-1)+1,x(1)=1等價(jià)的通項(xiàng)公式為(A x( n)=2n

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

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

5、背包問(wèn)題數(shù)組大小為(D )。A 10B100C1000D1000020.排列問(wèn)題屬于(D )。A可解問(wèn)題B不可解冋題C P問(wèn)題D NP問(wèn)題21. (A )算法應(yīng)用到廣度優(yōu)先遍歷策略。A分支界限法B動(dòng)態(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無(wú)法確定D均不是24.若 f(n)=50n+logn,g(n)=10n+loglogn，則 f=O(g)為(A)。A真B假C無(wú)法確定D均不是25. Prim算法求最小生成樹(shù)米用的是(A

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

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

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

9、只需求解其中 那個(gè)一個(gè)子問(wèn)題。7舉例說(shuō)明分治法和減治法的在設(shè)計(jì)上區(qū)別與聯(lián)系。答：分治法是將一個(gè)大問(wèn)題分解為若干子問(wèn)題分別求解，而減治法是只求解部分子問(wèn)題。8簡(jiǎn)述什么是歐拉回路，TSP問(wèn)題，哈密頓回路問(wèn)題。答：歐拉回路：圖G的一個(gè)回路，若它恰它通過(guò) G中每條邊一次，則稱該回路為歐拉回路。 TSP：從圖的一個(gè)頂點(diǎn)出發(fā)，每個(gè)定點(diǎn)只能訪問(wèn)一次，最后回到原點(diǎn)且使路徑最短。哈密頓回路：從一個(gè)城市出發(fā)，緊鍋蓋每一個(gè)城市恰好一次，然后回到出發(fā)城市。9. Strassen矩陣乘法可以利用什么算法實(shí)現(xiàn).答：可用分治法實(shí)現(xiàn)。三應(yīng)用題1.給出應(yīng)用動(dòng)態(tài)規(guī)劃法設(shè)計(jì)算法的一般步驟，并用動(dòng)態(tài)規(guī)劃法求下面多段圖中從頂點(diǎn)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長(zhǎng)度為16o2.有4個(gè)物品，其重量分別為(4, 7, 5, 3)，物品的價(jià)值分別為(40, 42, 25

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