资源描述：
《算法设计与分析试卷》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、《2012学年一算法分析试卷》一、选择题（15*2分）1、最大效益优先是（A）的一搜索方式。A、分支界限法B、动态规划法C、贪心法D、回溯法2.下列算法中通常以自底向上的方式求解最优解的是（备忘录法B、动态规划法C、贪心法衡量一个算法好坏的标准是（C）OA运行速度快B占用空间少C时间复杂度低D代码短哈弗曼编码的贪心算法所需的计算时间为（BA、3、4.A、0(n2n)B、0(nlogn)C、0(2n)5.分支限界法解最人团问题时，活结点表的组织形式是I)、I)、冋溯法0(n)A、最小堆B、最大堆C、D、数组6.最长公共子序列算法利用的
2、算法是（A、分支界限法B、动态规划法C、贪心法D、回溯法7.回溯法的效率不依赖于下列哪些因素（I)A.满足显约束的值的个数B.计算约束函数的时间C.计算限界函数的时间D.确定解空间的时间矩阵连乘问题的算法可山（B）设计实现。A、分支界限算法B、动态规划算法C、贪心算法D、回溯算法9.分支限界法解旅行售货员问题时，活结点表的组织形式是（A）oA、最小堆B、最大堆C、栈D、数组10、使用分治法求解不需要满足的条件是（A）。A子问题必须是一样的B子问题不能够重复C子问题的解可以合并D原问题利子问题使用相同的方法解11、下面问题（B）不能使
3、用贪心法解决。A单源最短路径问题BN皇后问题C最小花费生成树问题D背包问题12.实现大整数的乘法是利用的算法（C）oA、贪心法B、动态规划法C、分治策略I）、回溯法13.贪心算法与动态规划算法的主要区别是（B)oA、最优子结构B、贪心选择性质C、构造最优解D、定义最优14.以深度优先方式系统搜索问题解的算法称为（D）oA、分支界限算法B、概率算法C、贪心算法I）、回溯算法15.实现最长公共子序列利用的算法是（B）。A、分治策略B、动态规划法C、贪心法D、回溯法二、填空题（15*2分）1、算法的复杂性有m复杂性和空间复杂性之分。2、程
4、序是算法用某种程序设计语言的具体实现。3、算法的“确定性”指的是组成算法的每条指令是清晰的,无歧义的。4、矩阵连乘问题的算法可由动态规划设计实现。5、拉斯维加斯算法找到的解一定是正确解。6、算法是指解决问题的一种方法或一个过程o7、从分治法的一-般设计模式可以看出，用它设计出的程序一般是递归算法。8、问题的最优了结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。9、以深度优先方式系统搜索问题解的算法称为回溯法。10、计算一个算法时间复杂度通常可以计算循环次数、基木操作的频率或计算步。11・快速排序算法是基于分治策略的一种排序
5、算法。12.动态规划算法的两个基本要素是.最优子结构性质和重叠子问题性质。三、算法设计题（27分）1、（7分）写出欧几里得迭代算法（注意是迭代算法）intGcd（intm,intn）{If（m==O）returnn;If（n==0）returnm;while（m>0）intc=n%m;n=m;m=c;}Returnn;}2.(9分)给定已按升序排好序的n个元素a[O:n-l],现要在这n个元素中找出一特定元素x,返回其在数组中的位置，如果未找到返回-1。写出二分搜索的算法，并分析其时间复杂度。templatei
6、ntBinarySearch(Typea[],constType&x,intn){//在中搜索x,找到x时返回其在数组中的位置，否则返回intleft=0;intright=n~l;While(left〈二right){intmiddle二(left+right)/2;if(x二二a[middle])returnmiddle;if(x>a[middle])left二middle+1;elseright=middle-l;}Return-1;}时间复杂性为O(logn)3、(11分)写出对下图所示的多段图采用向前递推动态规划算法求解的
7、计算过程。第一段第2段BCOST(1,1)=0BCOST(2,2)=9BCOST(2,3)=7BCOST(2,4)=3BCOST(2,5)=2BC0ST(3,6)=min{BCOST(2,2)+4,BCOST(2,3)+2}=9BCOST(3,7)=min{BCOST(2,2)+2,BCOST(2,3)+7,BCOST(2,5)+11}=11BCOST(3,8)=min{BCOST(2,4)+11,BCOST(2,5)+8}=10BCOST(4,9)=min{BCOST(3,6)+6,BCOST(3,7)+4}=15BCOST(4,
8、10)二min{BCOST(3,6)+5,BCOST(3,7)+3,BCOST(3,8)+5}=14BCOST(4,11)=min{BCOST(3,8)+6}=16BCOST(5,12)=min(BCOST(4,9)+4,BCOST(
