算法分析与设计

一、填空题(5分，每小题1分)1．用矩阵幂的方法求斐波那契数，其运行时间为（O(logn)2．对于一个可以用动态规划法求解的问题，要求问题既要满足（）的特性，又要具有大量的（最优子结构，重叠子问题3．对于一个可以用贪心法求解的问题，不仅要求问题满足（）的特性，还应证明其贪心策略的（最优子结构，贪心选择性质4．设有n个栈操作（PUSH、POP、MULTIPOP）的序列，作用于初始为空的栈S。为（，O(1)5．三种平摊分析的方法分别为（（聚集分析，记帐方法，势能方法6．四后问题的搜索空间为（）树；0-1背包问题的搜索空间为（。排列树，子集树，排列树7．（（约束条件的解中找出在某种意义下的最优解。回溯法，分支限界法8．回溯法一般以（般以（）优先的方式搜索解空间树，而分支限界法则一）优先或以最小耗费优先的方式搜索解空间树。深度优先，广度优先二、单项选择题(5分，每小题1)1．下列关于排序算法的叙述，不正确的是？（）A)堆排序的最差情形运行时间为Θ(n)B)快速排序平均情形运行时间为Θ(lgn)C)任何排序算法的最差情形运行时间都不可能比Ω(nn更小D)插入排序在最好情形下的运行时间为Θ()2．对于线性时间内找第i小的元素的算法，（）下列叙述中不正确的是？．．．A)算法第一步中可以按每五个元素一组找中位数；B)算法第一步中可以按每七个元素一组找中位数；B)算法第一步中不能按每三个元素一组找中位数；D)如果要求的n个元素的中位数，则中位数一定是第一步中找到的中位数中的某一个。1/73．主方法可以求解满足形如下式的递推方程，loga-εC)若对于常数ε>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．下列随机算法一定有解但解不一定正确的是？A)SherwoodB)LasVegasC)MonteCarloD)三者都不是9．在快速排序算法中引入随机过程的主要目的是什么？（A)改善确定性算法的平均运行时间B)保证算法总能在O(n)时间内结束C)避免了算法最坏情况下的发生D)改善了确定性算法最坏情形下的平均运行时间10．用MonteCarlo方法估计四后问题回溯算法的效率。（）五次实验结果分别为<1,4,2><2,4,1,3><4,2><3,1,4,2><1,3>，则解空间中的结点数估计为？A)16B)16.2C)17D)16.5三、简答题(15分，每小题5分，要求只给结果)．．．．1．最接近数问题（分治法）2．删数问题（贪心法）给定一个n位正整数≤n成一个新的正整数。对于给定的n位正整数a和正整数，设计一个算法找出剩下的数字组成的新整数最小的删数方案。例：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])//出现递减删除递减的首数字{n=n.erase(i,1);x++;//x统计删除数字的个数i=-1;//从头开始查递减区间}if(i==l-x-2&&x<s)m=1;//已经无递减区间,m=1脱离循环3/7}}}3．输油管道问题a某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经（或南或北）与主管道相连。c给定n口油井的位置，编程计算各油井到主管道之间的输油管道最小长度总和。算法实现一1.地板覆盖问题intfn(intn){if(n%2==1)return0;i