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

一、填空題(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。為（，O(1)5．三種平攤分析的方法分別為（（聚集分析，記帳方法，勢(shì)能方法6．四后問(wèn)題的搜索空間為（）樹(shù)；0-1背包問(wèn)題的搜索空間為（。排列樹(shù)，子集樹(shù)，排列樹(shù)7．（（約束條件的解中找出在某種意義下的最優(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)B)快速排序平均情形運(yùn)行時(shí)間為Θ(lgn)C)任何排序算法的最差情形運(yùn)行時(shí)間都不可能比Ω(nn更小D)插入排序在最好情形下的運(yùn)行時(shí)間為Θ()2．對(duì)于線性時(shí)間內(nèi)找第i小的元素的算法，（）下列敘述中不正確的是？．．．A)算法第一步中可以按每五個(gè)元素一組找中位數(shù)；B)算法第一步中可以按每七個(gè)元素一組找中位數(shù)；B)算法第一步中不能按每三個(gè)元素一組找中位數(shù)；D)如果要求的n個(gè)元素的中位數(shù)，則中位數(shù)一定是第一步中找到的中位數(shù)中的某一個(gè)。1/73．主方法可以求解滿足形如下式的遞推方程，loga-εC)若對(duì)于常數(shù)ε>0，bblogaD)若，則bbb4．下列哪些問(wèn)題不能用貪心法求解？B)單源最短路徑問(wèn)題D)最小生成樹(shù)問(wèn)題5．可合并堆上可以不包含下列哪個(gè)操作？A)DECREASE-KEY(,x,k)B)UNION(H,H)12D)EXTRACT-MIN()．．．A)二叉堆為lgn)B)二項(xiàng)堆為O(lgn)C)斐波那契堆為Θ(1)D)三種堆的開(kāi)銷都是(lgn)B)(S,T)=|f|D)(S-s,)=|f|8．下列隨機(jī)算法一定有解但解不一定正確的是？A)SherwoodB)LasVegasC)MonteCarloD)三者都不是9．在快速排序算法中引入隨機(jī)過(guò)程的主要目的是什么？（A)改善確定性算法的平均運(yùn)行時(shí)間B)保證算法總能在O(n)時(shí)間內(nèi)結(jié)束C)避免了算法最壞情況下的發(fā)生D)改善了確定性算法最壞情形下的平均運(yùn)行時(shí)間10．用MonteCarlo方法估計(jì)四后問(wèn)題回溯算法的效率。（）五次實(shí)驗(yàn)結(jié)果分別為<1,4,2><2,4,1,3><4,2><3,1,4,2><1,3>，則解空間中的結(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ù)≤n成一個(gè)新的正整數(shù)。對(duì)于給定的n位正整數(shù)a和正整數(shù)，設(shè)計(jì)一個(gè)算法找出剩下的數(shù)字組成的新整數(shù)最小的刪數(shù)方案。例：a=178543，k=4輸出：13for(i=0；(i<a.size()-1)&&；；a.erase(i,1)；//i為最近下降點(diǎn)//沒(méi)有最近下降點(diǎn)時(shí)為表尾a=5934625578，k=6輸出：2557#include<iostream>#include<string>usingnamespacestd;intmain(){stringn;ints,i,x,l,m;while(cin>>n>>s){i=-1,m=0,x=0;l=n.length();while(x<s&&m==0){i++;if(n[i]>n[i+1])//出現(xiàn)遞減刪除遞減的首數(shù)字{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)3/7}}}3．輸油管道問(wèn)題a某石油公司計(jì)劃建造一條由東向西的主輸油管道。該管道要穿過(guò)一個(gè)有n口油井的油田。從每口油井都要有一條輸油管道沿最短路經(jīng)（或南或北）與主管道相連。c給定n口油井的位置，編程計(jì)算各油井到主管道之間的輸油管道最小長(zhǎng)度總和。算法實(shí)現(xiàn)一1.地板覆蓋問(wèn)題intfn(intn){if(n%2==1)return0;i