算法分析与设计

1、一、填空题（5分，每小题1分）1. 用矩阵幂的方法求斐波那契数，其运行时间为（ ）。O（logn）2. 对于一个可以用动态规划法求解的问题，要求问题既要满足（）的特性，又要具有大量的（。最优子结构，重叠子问题3. 对于一个可以用贪心法求解的问题，不仅要求问题满足（）的特性，还应证明其贪心策略的（ 。最优子结构，贪心选择性质4. 设有n个栈操作（PUSH、POP、MULTIPOP）的序列，作用于初始为空的栈 S。不区分三种操作，则每个操作的最坏运行时间为（）,平摊运行时间为（）。0（n）, 0（1）5. 三种平摊分析的方法分别为（ ）、（）、（）。聚集分析，记帐方法，势能方法6. 四后问题的搜索

2、空间为（ ）树；0-1背包问题的搜索空间为（）树；巡回售货员问题的搜索空间为（）树。排列树，子集树，排列树7. （）法的求解目标是找出解空间树中满足约束条件的所有解，而（）法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。回溯法，分支限界法8回溯法一般以（ ）优先的方式搜索解空间树，而分支限界法则一般以（）优先或以最小耗费优先的方式搜索解空间树。深度优先，广度优先二、单项选择题（5分，每小题1分）1. 下列关于排序算法的叙述，不正确的是？（）A）堆排序的最差情形运行时间为 （n lg n）B）快速排序平均情形运行时间为 （nlg n）C）任何排序算法的

3、最差情形运行时间都不可能比Q（n lg n）更小D）插入排序在最好情形下的运行时间为 （n）2. 对于线性时间找第i小的元素的算法，（）下列叙述中 不正确的是？A）算法第一步中可以按每五个元素一组找中位数；B）算法第一步中可以按每七个元素一组找中位数；B）算法第一步中不能按每三个元素一组找中位数；D）如果要求的n个元素的中位数，则中位数一定是第一步中找到的中位数中的某一个3. 主方法可以求解满足形如下式的递推方程，()丁 = (!) +%1)则下列关于方程中的约束中不准确的是？A) 对于系数a,必须满足a > 1B) 对于系数b,必须满足b > 1C) 若对于常数 £&g

4、t; 0 , f(n)=0(nlogba-J，则 T(n)= ®(nlogba)D) 若 f(n)=O(n"ba)，则 T(n)= (nlogbalogbn)4. 下列哪些问题不能用贪心法求解?A) 霍夫曼编码问题B) 单源最短路径问题C) 0-1背包问题D) 最小生成树问题5. 可合并堆上可以不包含下列哪个操作?A) DECREASE-KEYH, x, k)C) INSERTH, x)B) UNION(H1, H2)D) EXTRACT-MIN(H)6. 不同堆上插入操作最差情形下的开销或平摊开销，(对二叉堆、二项堆和斐波那契堆，下列选项中描述错误的是?A)二叉堆为O(l

5、g n)C)斐波那契堆为0(1)7.关于网络流的割，下列选项中B) 二项堆为O(lg n)D) 三种堆的开销都是 0(lg n) 错误的是？()割(S,T)是流网络G=(V,E)的一个划分，其中s S, t T。如果f是G上的流，那么 流经割的净流量为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下列随机算法一定有解但解不一定正确的是？()A) SherwoodB) LasVegasC) MonteCarloD)三者都不是9.在快速排序算法中

6、引入随机过程的主要目的是什么？()A) 改善确定性算法的平均运行时间B) 保证算法总能在0( nlg n)时间结束C) 避免了算法最坏情况下的发生D) 改善了确定性算法最坏情形下的平均运行时间10 用Monte Carlo方法估计四后问题回溯算法的效率。()五次实验结果分别为 1,4,2、 2,4,1,3、4,2、 3,1,4,2、1,3，贝V解空间 中的结点数估计为？A) 16B) 16.2C) 17D) 16.5三、简答题(15分，每小题5分，要求只给结果)1 最接近数问题(分治法)2. 删数问题(贪心法)给定一个n位正整数a，去掉其中任意kwn个数字后，剩下的数字按原次序排列 组成一个新

7、的正整数。对于给定的 n位正整数a和正整数k,设计一个算法找出剩下的 数字组成的新整数最小的删数方案。例：a=178543 , k=4 输出：13for(i=0 ； (iva.size()-1) && iv=ai+1)； +i)；a.erase(i,1) ；/i为最近下降点/没有最近下降点时为表尾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)出现递减，删除递减的首数字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脱离循环coutvvn.substr(O,l-s+x)«endl;只打印剩下的左边 l-(s-x)个数字return 0;3. 输油管道问题a某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要

9、有一条输油管道沿最短路经(或南或北)与主管道相连。b如果给定n 口油井的位置，即它们的x坐标(东西向)和y坐标(南北向)，应如 何确定主管道的最优位置，即使各油井到主管道之间的输油管道长度总和最小的位 置？c给定n 口油井的位置，编程计算各油井到主管道之间的输油管道最小长度总和。算法实现一int n;/油井的数量int x;/x坐标，读取后丢弃int a1000;/y 坐标cin»n;for(int k=O;k<n;k+)cin> >x»ak;sort(a,a+n);/按升序排序/计算各油井到主管道之间的输油管道最小长度总和int min=0;for(i

10、nt i=0;i< n;i+)min += ( int )fabs (ai-a n/2 );cout<< min<<en dl;四、计算题(75分，每小题15分，要求给出计算过程)1. 地板覆盖问题用2*1的地板块覆盖3*n的地面有多少种方案？如下图是一个覆盖的例子，函数fn可用于求解这个问题，请说明 fn算法的正确性，并说明算法运行时间的上界和下界。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作业调度问题给出n项作业J, J2,.,丄，对应每项作业有一个运行时间t,在m个处理器上调度这些作业，使完成的时间最小。 完成的时间定义为在所有的处理器中运行时间最长的处理器运行的 时间。采用如下的近似算法：即，按照原始给定的作业顺序：J1, J2，.，Jn,把每一项作业分配给当前情况下最近可用的那个处理器，使该作业尽可能早被处理（其它没有任何约束）。1. 试证明该算法的近似度为 2 1/m。（10分）2. 构造边界情况，说明这个界是紧的。（10分）1（提示：OP

12、Tti,OPT max ti）m证 显然. OPT(J) & - Yr(o), (2jOPT(/)maxt(a)m粽心1<m1设机器Mj的负载最大，记作/ (M八又设片是最后被分配给 机器他的作业根据算法在考虑分配b时Mj的负载最小慕 故+t(b)|(1 A二一s)+ 1_t(b)m J1、<()PT(/)+ 1- OPT m丿OPT(/).加=5的紧实例21毘优解紧实例M台机器'm(m-l)+l项作业、前m(m-l)项作业的处理时间 都为1,最后一项作业的处理时间为皿算法把前砍加1)项作业平均地分配给台机器，每台加1项- 最后一项杆意地分配给一台机器.G-MPS(f)=2wi-l.量优分配方案是把前m(w-l)项作业平均地分配给 Z 台机 器”每台加项，最后一项分配给留下的机器.OPT(Z)=m.G-MPS是2 近似算法3. 背包问题()附件一4. 图着色问题(回溯法)给定无向连通图 G=(V, E)和正整数m，求最小的整数 m,使得用m种颜色对G中的 顶点着色，使得任意两个相邻顶点着色不同。核心代码：colork=colork+1 ；while(colork<=m) if(Ok(k) break ；else colork=colork+1 ； / 搜索下一个颜色/whi