《算法设计与分析试卷及答案》由会员分享，可在线阅读，更多相关《算法设计与分析试卷及答案（9页珍藏版）》请在金锄头文库上搜索。
1、湖南科技学院二O年学期期末考试信息与计算科学专业年级算法设计与分析试题考试类型：开卷试卷类型：C卷考试时量：120分钟题号-一一二三四五总分统分人得分阅卷人复查人一、填空题(每小题3分，共计30分)1. 用O、Q和e表示函数f与g之间的关系.f (n )= n log ng (n ) = log nI 1,n = 12. 算法的时间复杂性为f(n)=仁宀、c，则算法的时间复杂性的阶8 f (3n /7) + n,n 2为。3. 快速排序算法的性能取决于。4. 算法是。5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是。6. 在算法的三种情况下的复杂性中，可操作性最
2、好且最有实际价值的是情况下的时间复杂性。7. 大Q符号用来描述增长率的下限，这个下限的阶 ，结果就越有价值。8. 问题能用动态规划算法求解的前提。9. 贪心选择性质是扌旨10. 回溯法在问题的解空间树中，按略，从根结点出发搜索解空间树。二、简答题(每小题10分，共计30分)1.试述回溯法的基本思想及用回溯法解题的步骤。2.有8个作业1,2,-,8要在由2台机器Ml和M2组成的流水线上完成加工。每个作 业加工的顺序都是先在Ml上加工，然后在M2上加工。Ml和M2加工作业i所需的 时间分别为：Mll028l2694l4M257ll5l63lll3作业12345678给出一个最优调度方案，使得从第一
3、个作业在机器Ml上开始加工，到最后一个作业在 机器M2上加工完成所需的时间最少，并计算所需的最少时间。最优调度方案为所需的最少时间为：3. 根据优先队列式分支限界法，求下图中从vl点到v9点的单源最短路径，请画出求 得最优解的解空间树。要求中间被舍弃的结点用X标记，获得中间解的结点用单圆圈O 框起（如02 ），最优解用双圆圈框起。12v5662333v1v3io442210v2v4_丿三、算法填空(每空 2分，共计 10 分)设R=rr2, rn是要进行排列的n个元素，其中元素片,巧,rn可能相同，试设计一 个算法，列出 R 的所有不同排列，并给出不同排列的总数。算法如下，填写缺失的语 句。t
4、emplate void Swap(Type &a,Type &b)Type t=b; /1a=t;templatebool ok(Type R,int k,int i)if(ik)for(int t=k;ti;t+)if( ) /2return false;return true;templatevoid Perm(Type R,int k,int n,int &sum) n为元素个数，sum记录不同排列的总数 if(k=n); /3for(int i=1;i=n;i+)cout;/4coutendl;elsefor(int i=k;i0)unsigned int i=0; /从串首开始找 while(in.length()&(n.at(i)1&n.at(0)=0)n.erase(0,1); /删除串首可能产生的无用零 return n;
