文档介绍：该【算法设计与分析试卷及答案 】是由【1781111****】上传分享，文档一共【4】页，该文档可以免费在线阅读，需要了解更多关于【算法设计与分析试卷及答案 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..湖南科技学院二○年学期期末考试信息与计算科学专业年级《算法设计与分析》试题考试类型:开卷试卷类型:C卷考试时量:120分钟题号一二三四五总分统分人得分阅卷人复查人一、填空题(每小题3分,共计30分)、Ω和θ表示函数f与g之间的关系______________________________。?1,n?(n)??,则算法的时间复杂性的阶为?8f(3n/7)?n,n?2__________________________。。。,一个活结点最多有一次机会成为活结点的是_________________________。,可操作性最好且最有实际价值的是_____情况下的时间复杂性。,这个下限的阶越___________,结果就越有价值。。。。,按______________策略,从根结点出发搜索解空间树。二、简答题(每小题10分,共计30分)。{1,2,…,8}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工,然后在M2上加工。M1和M2加工作业i所需的时间分别为:M1**********M2571151631113作业12345678给出一个最优调度方案,使得从第一个作业在机器M1上开始加工,到最后一个作业在机器M2上加工完成所需的时间最少,并计算所需的最少时间。答:最优调度方案为:..所需的最少时间为:,求下图中从v1点到v9点的单源最短路径,请画出求得最优解的解空间树。要求中间被舍弃的结点用×标记,获得中间解的结点用单圆圈○框起(如),最优解用双圆圈◎框起。三、算法填空(每空2分,共计10分)设R={r,r,...,r}是要进行排列的n个元素,其中元素r,r,...,r可能相同,试设计一个算法,列12n12n出R的所有不同排列,并给出不同排列的总数。算法如下,填写缺失的语句。template<typenameType>voidSwap(Type&a,Type&b){Typet=b;________________;//1a=t;}template<typenameType>boolok(TypeR[],intk,inti){if(i>k)for(intt=k;t<i;t++)if(__________________)//2returnfalse;returntrue;}template<typenameType>voidPerm(TypeR[],intk,intn,int&sum){//n为元素个数,sum记录不同排列的总数if(k==n){______________________;//3for(inti=1;i<=n;i++)cout<<___________________;//4cout<<endl;}else{for(inti=k;i<=n;i++)if(ok(R,k,i)){Swap(R[k],R[i]);Perm(_________________________);//5Swap(R[k],R[i]);}}}四、算法设计(共计15分)设有n个程序{1,2,3...,n}要存放在长度为L的磁带上。程序i存放在磁带上的长度是Li,1≤i≤n。程序存储问题要求确定这n个程序在磁带上的一个存储方案,使得能够在磁带上存储尽可能多的程序,在保证存储最多程序的前提下还要求磁带的利用率达到最大。(1)给出求解存储最多程序的算法,并证明算法的正确性;(2)给出求解使磁带的利用率达到最大的方案的算法思路。。五、算法设计(共计15分):..通过键盘输入一个高精度的正整数n(n的有效位数≤240),去掉其中任意s个数字后,剩下的数字按原左右次序将组成一个新的正整数。对给定的n和s,寻找一种方案,使得剩下的数字组成的新最小。如输入n为178543,s为4,结果为13⑴简述你的算法思路;⑵给出算法(用C++描述)。注:正整数n存于字符串中,例:(0)//(2,3)//删除n中索引为2开始的3个字符解:⑴算法思路⑵算法stringMinNum(stringn,ints){湖南科技学院二○年学期期末考试《算法设计与分析》试题C答案一、填空题(每小题3分,共计30分)(n)=Ω(g(n))(解决问题的一种方法或一个过程),即贪心选择来达到。、简答题(每小题10分,共计30分),按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。5分基本步骤:5分①针对拨给问题,定义问题的解空间;②确定易于搜索的解空间结构;③以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。(6分)27548163所需的最少时间为:73(4分在前一问正确的前提下方可得分)、算法填空(每空2分,共计10分)=[t]==R[i]++[i]:..,k+1,n,sum四、算法设计(共计15分)贪心策略:最短程序优先。将程序从小到大排序,依次选取尽可能多的程序,但总长度不超过磁盘容量,则可求得最多可以存储的程序个数m。采用回溯法,从n个程序中选取总长度最大的m个,算法同装载问题。五、算法设计(共计15分),选取的贪心策略为:每一步总是选择一个使剩下的数最小的数字删去,即按高位到低位的顺序搜索,若各位数字递增,则删除最后一个数字,否则删除第一个递减区间的首字母。然后回到串首,按上述规则再删除下一个数字。重复以上过程s次,剩下的数字串便是总是的解。(stringn,ints){while(s>0){unsignedinti=0;//从串首开始找while(i<()&&((i)<(i+1)))i++;(i,1);//删除字符串n中索引为i的字符s--;}while(()>1&&(0)=='0')(0,1);//删除串首可能产生的无用零returnn;}