《算法分析与设计》作业（二）本课程作业由两部分组成。第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。第二部分为“主观题部分”，由简答题和论述题组成，共15分。作业总分30分，将作为平时成绩记入课程总成绩。客观题部分：选择题（每题1分，共15题）1、动态规划算法解各个子问题的方法是：（）A、自底向上B、自顶向下C、随机选择D、自底向上或自顶向下2、回溯法解园排列问题的解空间树是：（）A、子集树B、排列树C、二叉树D、多叉树3、用分治法求平面最接近点对问题时采用的著名原理是：（）A、Johnson法则B、鸽舍原理C、牛顿原理D、线性规划原理4、分支限界法搜索解空间的方式是：（）A、广度优先B、深度优先C、随机D、以上都不是5、采用如下随机方法计算值：（）A、随机投点法B、舍伍德法C、拉斯维加斯法D、单纯形法6、下面是描述算法复杂度的有：（）A、时间复杂度B、鸽舍原理C、二分法D、随机化算法7、下面不属于单纯形法步骤是：（）A、选入基变量B、选离基变量C、做转轴变化D、动态规划8、快速排序和线性时间选择的随机化版本是：（）A、舍伍德算法B、拉斯维加斯算法C、蒙特卡罗D、单纯形法9、用回溯法解旅行售货员问题时生成的解空间树是：（）A、子集树B、排列树C、二叉树D、多叉树10、用回溯法解0-1背包问题时生成的解空间树是：（）A、子集树B、排列树C、二叉树D、多叉树11、用分支限界法解布线问题时的解空间是：（）A、子集树B、排列树C、图D、二叉树12、跳跃表是采用哪种随机化算法设计的：（）A、舍伍德算法B、拉斯维加斯算法C、蒙特卡罗D、单纯形法13、合并排序和快速排序都采用的策略是：（）A、分治B、Johnson法则C、鸽舍原理D、单纯形法14、下面不属于单纯形法的步骤的是：（）A、选入基变量B、选离基变量C、作转轴变化D、找最优子结构15、Kruskal算法能解以下问题：（）A、单源最短路径B、n后问题C、最小生成树D、装载问题主观题部分：改错题（每题2.5分，共2题）下面的2个算法与本章中的二分搜索算法BinarySearch略有不同。请判断这2个算法的正确性。如果算法不正确，请说明产生错误的原因。如果算法正确，请给算法的正确性证明。1publicstaticintbinarySearch(int[]a,intx,intn){intleft=0;intright=n-1;while(left+1!=right){intmiddle=(left+right)/2;if(x>=a[middle])left=middle;elseright=middle;}if(x==a[left])returnleft;return-1;}2publicstaticintbinarySearch(int[]a,intx,intn){If(n>0&&x>=a[0]){intleft=0;intright=n-1;while(left<right){intmiddle=(left+right)/2;if(x<a[middle])right=middle-1;elseleft=middle;}if(x==a[left])returnleft;}return-1;}三、写出下列题目的程序（每题5分，共2题）1.考虑最大团问题的子集空间树中第i层的一个结点x，设MinDegree(x)是以结点x为根的子树中所有结点度数的最小值。（1）设x.u=min{x.cn+n-i+1,MinDegree(x)+1}，证明以结点x为根的子树中任一叶结点所相应的团的大小不超过x.u。（2）依此x.u的定义重写算法BBMaxClique.（3）比较新旧算法所需的计算时间和产生的排列树结点数。2.租用游艇问题问题描述：长江游艇俱乐部在长江上设置了n个游艇出租站1，2，…，n.游客可在这些游艇出租站租用游艇，游艇出租站i到游艇出租占j之间的租金为r(i,j)，。试设计一个算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。编程任务：对于给定的游艇出租站i到游艇出租站j之间的租金为r(i,j)，，编程计算从游艇出租站1到游艇出租站n所需的最少租金。数据输入：由文件input.txt提供输入数据。文件的第1行中有1个正整数n(n<=200)，表示有n个游艇出租站。接下来的n-1行是r(i,j)，。结果输出：程序运行结束时，将计算出的从游艇出租站1到游艇出租站n所需的最少租金输出到文件output.txt中。输入文件示例输出文件示例input.txtoutput.txt12157