算法分析與設(shè)計(jì)

1、一、填空題（5分，每小題1分）1. 用矩陣冪的方法求斐波那契數(shù)，其運(yùn)行時(shí)間為（ ）。O（logn）2. 對(duì)于一個(gè)可以用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題，要求問(wèn)題既要滿足（）的特性，又要具有大量的（。最優(yōu)子結(jié)構(gòu)，重疊子問(wèn)題3. 對(duì)于一個(gè)可以用貪心法求解的問(wèn)題，不僅要求問(wèn)題滿足（）的特性，還應(yīng)證明其貪心策略的（ 。最優(yōu)子結(jié)構(gòu)，貪心選擇性質(zhì)4. 設(shè)有n個(gè)棧操作（PUSH、POP、MULTIPOP）的序列，作用于初始為空的棧 S。不區(qū)分三種操作，則每個(gè)操作的最壞運(yùn)行時(shí)間為（）,平攤運(yùn)行時(shí)間為（）。0（n）, 0（1）5. 三種平攤分析的方法分別為（ ）、（）、（）。聚集分析，記帳方法，勢(shì)能方法6. 四后問(wèn)題的搜索

2、空間為（ ）樹(shù)；0-1背包問(wèn)題的搜索空間為（）樹(shù)；巡回售貨員問(wèn)題的搜索空間為（）樹(shù)。排列樹(shù)，子集樹(shù)，排列樹(shù)7. （）法的求解目標(biāo)是找出解空間樹(shù)中滿足約束條件的所有解，而（）法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解?；厮莘?，分支限界法8回溯法一般以（ ）優(yōu)先的方式搜索解空間樹(shù)，而分支限界法則一般以（）優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹(shù)。深度優(yōu)先，廣度優(yōu)先二、單項(xiàng)選擇題（5分，每小題1分）1. 下列關(guān)于排序算法的敘述，不正確的是？（）A）堆排序的最差情形運(yùn)行時(shí)間為 （n lg n）B）快速排序平均情形運(yùn)行時(shí)間為 （nlg n）C）任何排序算法的

3、最差情形運(yùn)行時(shí)間都不可能比Q（n lg n）更小D）插入排序在最好情形下的運(yùn)行時(shí)間為 （n）2. 對(duì)于線性時(shí)間找第i小的元素的算法，（）下列敘述中 不正確的是？A）算法第一步中可以按每五個(gè)元素一組找中位數(shù)；B）算法第一步中可以按每七個(gè)元素一組找中位數(shù)；B）算法第一步中不能按每三個(gè)元素一組找中位數(shù)；D）如果要求的n個(gè)元素的中位數(shù)，則中位數(shù)一定是第一步中找到的中位數(shù)中的某一個(gè)3. 主方法可以求解滿足形如下式的遞推方程，()丁 = (!) +%1)則下列關(guān)于方程中的約束中不準(zhǔn)確的是？A) 對(duì)于系數(shù)a,必須滿足a > 1B) 對(duì)于系數(shù)b,必須滿足b > 1C) 若對(duì)于常數(shù) £&g

4、t; 0 , f(n)=0(nlogba-J，則 T(n)= ®(nlogba)D) 若 f(n)=O(n"ba)，則 T(n)= (nlogbalogbn)4. 下列哪些問(wèn)題不能用貪心法求解?A) 霍夫曼編碼問(wèn)題B) 單源最短路徑問(wèn)題C) 0-1背包問(wèn)題D) 最小生成樹(shù)問(wèn)題5. 可合并堆上可以不包含下列哪個(gè)操作?A) DECREASE-KEYH, x, k)C) INSERTH, x)B) UNION(H1, H2)D) EXTRACT-MIN(H)6. 不同堆上插入操作最差情形下的開(kāi)銷(xiāo)或平攤開(kāi)銷(xiāo)，(對(duì)二叉堆、二項(xiàng)堆和斐波那契堆，下列選項(xiàng)中描述錯(cuò)誤的是?A)二叉堆為O(l

5、g n)C)斐波那契堆為0(1)7.關(guān)于網(wǎng)絡(luò)流的割，下列選項(xiàng)中B) 二項(xiàng)堆為O(lg n)D) 三種堆的開(kāi)銷(xiāo)都是 0(lg n) 錯(cuò)誤的是？()割(S,T)是流網(wǎng)絡(luò)G=(V,E)的一個(gè)劃分，其中s S, t T。如果f是G上的流，那么 流經(jīng)割的凈流量為f(S,T),割(S,T)上的容量定義為c(S,T)。A) | f | FS T)C) f(s, V-s) = | f |B) f(S, T) = | f |D) f(S-s, V) = | f |8下列隨機(jī)算法一定有解但解不一定正確的是？()A) SherwoodB) LasVegasC) MonteCarloD)三者都不是9.在快速排序算法中

6、引入隨機(jī)過(guò)程的主要目的是什么？()A) 改善確定性算法的平均運(yùn)行時(shí)間B) 保證算法總能在0( nlg n)時(shí)間結(jié)束C) 避免了算法最壞情況下的發(fā)生D) 改善了確定性算法最壞情形下的平均運(yùn)行時(shí)間10 用Monte Carlo方法估計(jì)四后問(wèn)題回溯算法的效率。()五次實(shí)驗(yàn)結(jié)果分別為 1,4,2、 2,4,1,3、4,2、 3,1,4,2、1,3，貝V解空間 中的結(jié)點(diǎn)數(shù)估計(jì)為？A) 16B) 16.2C) 17D) 16.5三、簡(jiǎn)答題(15分，每小題5分，要求只給結(jié)果)1 最接近數(shù)問(wèn)題(分治法)2. 刪數(shù)問(wèn)題(貪心法)給定一個(gè)n位正整數(shù)a，去掉其中任意kwn個(gè)數(shù)字后，剩下的數(shù)字按原次序排列 組成一個(gè)新

7、的正整數(shù)。對(duì)于給定的 n位正整數(shù)a和正整數(shù)k,設(shè)計(jì)一個(gè)算法找出剩下的 數(shù)字組成的新整數(shù)最小的刪數(shù)方案。例：a=178543 , k=4 輸出：13for(i=0 ； (iva.size()-1) && iv=ai+1)； +i)；a.erase(i,1) ；/i為最近下降點(diǎn)/沒(méi)有最近下降點(diǎn)時(shí)為表尾a=5934625578 , k=6 輸出：2557#in clude<iostream>#in cludevstri ng> using n amespace std; int mai n()stri ng n;while(c in»n> >s

8、)i=-1,m=0,x=0;l=ne ngth(); while(x<s&&m=0)出現(xiàn)遞減，刪除遞減的首數(shù)字i+；if(n i> n i+1)/ n=n. erase(i,1);x+;/ x統(tǒng)計(jì)刪除數(shù)字的個(gè)數(shù) i=-1;/從頭開(kāi)始查遞減區(qū)間if(i=l-x-2&&x<s)m=1;已經(jīng)無(wú)遞減區(qū)間,m=1脫離循環(huán)coutvvn.substr(O,l-s+x)«endl;只打印剩下的左邊 l-(s-x)個(gè)數(shù)字return 0;3. 輸油管道問(wèn)題a某石油公司計(jì)劃建造一條由東向西的主輸油管道。該管道要穿過(guò)一個(gè)有n 口油井的油田。從每口油井都要

9、有一條輸油管道沿最短路經(jīng)(或南或北)與主管道相連。b如果給定n 口油井的位置，即它們的x坐標(biāo)(東西向)和y坐標(biāo)(南北向)，應(yīng)如 何確定主管道的最優(yōu)位置，即使各油井到主管道之間的輸油管道長(zhǎng)度總和最小的位 置？c給定n 口油井的位置，編程計(jì)算各油井到主管道之間的輸油管道最小長(zhǎng)度總和。算法實(shí)現(xiàn)一int n;/油井的數(shù)量int x;/x坐標(biāo)，讀取后丟棄int a1000;/y 坐標(biāo)cin»n;for(int k=O;k<n;k+)cin> >x»ak;sort(a,a+n);/按升序排序/計(jì)算各油井到主管道之間的輸油管道最小長(zhǎng)度總和int min=0;for(i

10、nt i=0;i< n;i+)min += ( int )fabs (ai-a n/2 );cout<< min<<en dl;四、計(jì)算題(75分，每小題15分，要求給出計(jì)算過(guò)程)1. 地板覆蓋問(wèn)題用2*1的地板塊覆蓋3*n的地面有多少種方案？如下圖是一個(gè)覆蓋的例子，函數(shù)fn可用于求解這個(gè)問(wèn)題，請(qǐng)說(shuō)明 fn算法的正確性，并說(shuō)明算法運(yùn)行時(shí)間的上界和下界。int fn (i nt n) if (n % 2 = 1) return 0;in t f = new intn+1;f0 = 1；for (i nt i = 2; i <= n; i += 2) fi =

11、fi-2*3;for (i nt j = i-4; j >= 0; j -= 2)fi += fj*2;return fn;2作業(yè)調(diào)度問(wèn)題給出n項(xiàng)作業(yè)J, J2,.,丄，對(duì)應(yīng)每項(xiàng)作業(yè)有一個(gè)運(yùn)行時(shí)間t,在m個(gè)處理器上調(diào)度這些作業(yè)，使完成的時(shí)間最小。 完成的時(shí)間定義為在所有的處理器中運(yùn)行時(shí)間最長(zhǎng)的處理器運(yùn)行的 時(shí)間。采用如下的近似算法：即，按照原始給定的作業(yè)順序：J1, J2，.，Jn,把每一項(xiàng)作業(yè)分配給當(dāng)前情況下最近可用的那個(gè)處理器，使該作業(yè)盡可能早被處理（其它沒(méi)有任何約束）。1. 試證明該算法的近似度為 2 1/m。（10分）2. 構(gòu)造邊界情況，說(shuō)明這個(gè)界是緊的。（10分）1（提示：OP

12、Tti,OPT max ti）m證 顯然. OPT(J) & - Yr(o), (2jOPT(/)maxt(a)m粽心1<m1設(shè)機(jī)器Mj的負(fù)載最大，記作/ (M八又設(shè)片是最后被分配給 機(jī)器他的作業(yè)根據(jù)算法在考慮分配b時(shí)Mj的負(fù)載最小慕 故+t(b)|(1 A二一s)+ 1_t(b)m J1、<()PT(/)+ 1- OPT m丿OPT(/).加=5的緊實(shí)例21毘優(yōu)解緊實(shí)例M臺(tái)機(jī)器'm(m-l)+l項(xiàng)作業(yè)、前m(m-l)項(xiàng)作業(yè)的處理時(shí)間 都為1,最后一項(xiàng)作業(yè)的處理時(shí)間為皿算法把前砍加1)項(xiàng)作業(yè)平均地分配給臺(tái)機(jī)器，每臺(tái)加1項(xiàng)- 最后一項(xiàng)桿意地分配給一臺(tái)機(jī)器.G-MPS(f)=2wi-l.量?jī)?yōu)分配方案是把前m(w-l)項(xiàng)作業(yè)平均地分配給 Z 臺(tái)機(jī) 器”每臺(tái)加項(xiàng)，最后一項(xiàng)分配給留下的機(jī)器.OPT(Z)=m.G-MPS是2 近似算法3. 背包問(wèn)題()附件一4. 圖著色問(wèn)題(回溯法)給定無(wú)向連通圖 G=(V, E)和正整數(shù)m，求最小的整數(shù) m,使得用m種顏色對(duì)G中的 頂點(diǎn)著色，使得任意兩個(gè)相鄰頂點(diǎn)著色不同。核心代碼：colork=colork+1 ；while(colork<=m) if(Ok(k) break ；else colork=colork+1 ； / 搜索下一個(gè)顏色/whi