算法分析與設(shè)計

一、填空題(5分，每小題1分)1．用矩陣冪的方法求斐波那契數(shù)，其運行時間為（O(logn)2．對于一個可以用動態(tài)規(guī)劃法求解的問題，要求問題既要滿足（）的特性，又要具有大量的（最優(yōu)子結(jié)構(gòu)，重疊子問題3．對于一個可以用貪心法求解的問題，不僅要求問題滿足（）的特性，還應(yīng)證明其貪心策略的（最優(yōu)子結(jié)構(gòu)，貪心選擇性質(zhì)4．設(shè)有n個棧操作（PUSH、POP、MULTIPOP）的序列，作用于初始為空的棧S。為（，O(1)5．三種平攤分析的方法分別為（（聚集分析，記帳方法，勢能方法6．四后問題的搜索空間為（）樹；0-1背包問題的搜索空間為（。排列樹，子集樹，排列樹7．（（約束條件的解中找出在某種意義下的最優(yōu)解?；厮莘?，分支限界法8．回溯法一般以（般以（）優(yōu)先的方式搜索解空間樹，而分支限界法則一）優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。深度優(yōu)先，廣度優(yōu)先二、單項選擇題(5分，每小題1)1．下列關(guān)于排序算法的敘述，不正確的是？（）A)堆排序的最差情形運行時間為Θ(n)B)快速排序平均情形運行時間為Θ(lgn)C)任何排序算法的最差情形運行時間都不可能比Ω(nn更小D)插入排序在最好情形下的運行時間為Θ()2．對于線性時間內(nèi)找第i小的元素的算法，（）下列敘述中不正確的是？．．．A)算法第一步中可以按每五個元素一組找中位數(shù)；B)算法第一步中可以按每七個元素一組找中位數(shù)；B)算法第一步中不能按每三個元素一組找中位數(shù)；D)如果要求的n個元素的中位數(shù)，則中位數(shù)一定是第一步中找到的中位數(shù)中的某一個。1/73．主方法可以求解滿足形如下式的遞推方程，loga-εC)若對于常數(shù)ε>0，bblogaD)若，則bbb4．下列哪些問題不能用貪心法求解？B)單源最短路徑問題D)最小生成樹問題5．可合并堆上可以不包含下列哪個操作？A)DECREASE-KEY(,x,k)B)UNION(H,H)12D)EXTRACT-MIN()．．．A)二叉堆為lgn)B)二項堆為O(lgn)C)斐波那契堆為Θ(1)D)三種堆的開銷都是(lgn)B)(S,T)=|f|D)(S-s,)=|f|8．下列隨機(jī)算法一定有解但解不一定正確的是？A)SherwoodB)LasVegasC)MonteCarloD)三者都不是9．在快速排序算法中引入隨機(jī)過程的主要目的是什么？（A)改善確定性算法的平均運行時間B)保證算法總能在O(n)時間內(nèi)結(jié)束C)避免了算法最壞情況下的發(fā)生D)改善了確定性算法最壞情形下的平均運行時間10．用MonteCarlo方法估計四后問題回溯算法的效率。（）五次實驗結(jié)果分別為<1,4,2><2,4,1,3><4,2><3,1,4,2><1,3>，則解空間中的結(jié)點數(shù)估計為？A)16B)16.2C)17D)16.5三、簡答題(15分，每小題5分，要求只給結(jié)果)．．．．1．最接近數(shù)問題（分治法）2．刪數(shù)問題（貪心法）給定一個n位正整數(shù)≤n成一個新的正整數(shù)。對于給定的n位正整數(shù)a和正整數(shù)，設(shè)計一個算法找出剩下的數(shù)字組成的新整數(shù)最小的刪數(shù)方案。例：a=178543，k=4輸出：13for(i=0；(i<a.size()-1)&&；；a.erase(i,1)；//i為最近下降點//沒有最近下降點時為表尾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)計刪除數(shù)字的個數(shù)i=-1;//從頭開始查遞減區(qū)間}if(i==l-x-2&&x<s)m=1;//已經(jīng)無遞減區(qū)間,m=1脫離循環(huán)3/7}}}3．輸油管道問題a某石油公司計劃建造一條由東向西的主輸油管道。該管道要穿過一個有n口油井的油田。從每口油井都要有一條輸油管道沿最短路經(jīng)（或南或北）與主管道相連。c給定n口油井的位置，編程計算各油井到主管道之間的輸油管道最小長度總和。算法實現(xiàn)一1.地板覆蓋問題intfn(intn){if(n%2==1)return0;i