3算法设计与分析试卷

《2012学年--算法分析试卷》一、选择题（15*2分）1、最大效益优先是（A）的一搜索方式。A、分支界限法B、动态规划法C、贪心法D、回溯法2．下列算法中通常以自底向上的方式求解最优解的是（B）。A、备忘录法B、动态规划法C、贪心法D、回溯法3、衡量一个算法好坏的标准是（C）。A运行速度快B占用空间少C时间复杂度低D代码短4．哈弗曼编码的贪心算法所需的计算时间为（B）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）5．分支限界法解最大团问题时，活结点表的组织形式是（B）。A、最小堆B、最大堆C、栈D、数组6．最长公共子序列算法利用的算法是（B）。A、分支界限法B、动态规划法C、贪心法D、回溯法7.回溯法的效率不依赖于下列哪些因素（D）A.满足显约束的值的个数B.计算约束函数的时间C.计算限界函数的时间D.确定解空间的时间8.矩阵连乘问题的算法可由（B）设计实现。A、分支界限算法B、动态规划算法C、贪心算法D、回溯算法9.分支限界法解旅行售货员问题时，活结点表的组织形式是（A）。A、最小堆B、最大堆C、栈D、数组10、使用分治法求解不需要满足的条件是（A）。A子问题必须是一样的B子问题不能够重复C子问题的解可以合并D原问题和子问题使用相同的方法解11、下面问题（B）不能使用贪心法解决。A单源最短路径问题BN皇后问题C最小花费生成树问题D背包问题12．实现大整数的乘法是利用的算法（C）。A、贪心法B、动态规划法C、分治策略D、回溯法13．贪心算法与动态规划算法的主要区别是（B）。A、最优子结构B、贪心选择性质C、构造最优解D、定义最优解14.以深度优先方式系统搜索问题解的算法称为(D)。A、分支界限算法B、概率算法C、贪心算法D、回溯算法15.实现最长公共子序列利用的算法是（B）。A、分治策略B、动态规划法C、贪心法D、回溯法二、填空题（15*2分）1.算法的复杂性有时间复杂性和空间复杂性之分。2、程序是算法用某种程序设计语言的具体实现。3、算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。4.矩阵连乘问题的算法可由动态规划设计实现。5、拉斯维加斯算法找到的解一定是正确解。6、算法是指解决问题的一种方法或一个过程。7、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。8、问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。9、以深度优先方式系统搜索问题解的算法称为回溯法。10、计算一个算法时间复杂度通常可以计算循环次数、基本操作的频率或计算步。11.快速排序算法是基于分治策略的一种排序算法。12.动态规划算法的两个基本要素是.最优子结构性质和重叠子问题性质。三、算法设计题（27分）1、（7分）写出欧几里得迭代算法(注意是迭代算法)intGcd(intm,intn){If(m==0)returnn;If(n==0)returnm;while(m0){intc=n%m;n=m;m=c;}Returnn;}2.（9分）给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，返回其在数组中的位置，如果未找到返回-1。写出二分搜索的算法，并分析其时间复杂度。templateclassTypeintBinarySearch(Typea[],constType&x,intn){//在a[0:n]中搜索x，找到x时返回其在数组中的位置，否则返回-1intleft=0;intright=n-1;While(left=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(xa[middle])left=middle+1;elseright=middle-1;}Return-1;}时间复杂性为O(logn)3、（11分）写出对下图所示的多段图采用向前递推动态规划算法求解的计算过程。第一段BCOST(1,1)=0第2段BCOST(2,2)=9BCOST(2,3)=7BCOST(2,4)=3BCOST(2,5)=2第3段BCOST(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}=10第4段BCOST(4,9)=min{BCOST(3,6)+6,BCOST(3,7)+4}=15BCOST(4,10)=min{BCOST(3,6)+5,BCOST(3,7)+3,BCOST(3,8)+5}=14BCOST(4,11)=min{BCOST(3,8)+6}=16第5段BCOST(5,12)=min{BCOST(4,9)+4,BCOST(4,10)+2,BCOST(4,11)+5}=16S到t的最小成本路径的成本＝16最小成本路径的求取记BD(i,j)＝每一COST(i,j)的决策即，使COST(i-1,l)+c(l,j)取得最小值的l值。例：BD(3,6)=3,BD(3,7)=2,BD(3,8)=5BD(4,9)=6,BD(4,10)=7,BD(4,11)=8BD(5,12)=10根据D(5,12)的决策值向前递推求取最小成本路径：●v4=BD(5,12)=10●v3=BD(4,BD(5,12))=7●v2=BD(3,BD(4,BD(5,12)))=BD(3,7)=2故由s到t的最小成本路径是：1→2→7→10→12四、算法应用题（13分）如图所示的数字三角形，请编写一个程序计算从顶到底的一条路径（路径是指上一层的一个数字到下一层两个数字连线的任一条），并找出数字和最大的路径。输出该最大路径数字和。738810274445265输出：30#includeiostreamusingnamespacestd;constintM=100;intn;inta[M][M];intfunc(){inti,j;for(i=n-1;i=1;i--)for(j=1;j=i;j++){if(a[i+1][j]a[i+1][j+1])a[i][j]+=a[i+1][j];elsea[i][j]+=a[i+1][j+1];}returna[1][1];}intmain(){inti,j,max;cinn;for(i=1;i=n;i++)for(j=1;j=i;j++)cina[i][j];max=func();coutmaxendl;return0;}