算法分析与设计作业(三)

《算法分析与设计作业(三)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法分析与设计》作业（三）本课程作业由两部分组成。第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。第二部分为“主观题部分”，由简答题和论述题组成，共15分。作业总分30分，将作为平时成绩记入课程总成绩。客观题部分：一、选择题（每题1分，共15题）1、贪心算法解各个子问题的方法是：（）A、自底向上B、自顶向下C、随机选择D、自底向上或自顶向下2、用回溯法解旅行售货员问题时生成的树是：（）A、子集树B、排列树C、二叉树D、多叉树3、在n后问题中任意两个皇后能放在：（）A、同一行B、同一列C、同一斜线D、以上都不行4、用回溯法解0-1背包问题时生成的解空间树是：（）A、

2、子集树B、排列树C、二叉树D、多叉树5、用贪心算法解单源最短路径问题时采用的算法是：（）A、Dijkstra算法B、Prime算法C、Kruskal算法D、蒙特卡罗算法6、在用动态规划解流水作业调度时的最优调度法则是：（）A、最优子结构B、重叠子问题C、Johnson法则D、最长处理时间作业优先7、算法与程序的区别在于：（）A、输入B、输出C、指令的确定性D、指令的有限性8、从分治法的一般设计模式可以看出，用它设计的程序一般是：（）A、顺序B、选择C、循环D、递归9、回溯法的解空间是在搜索过程中：（）A、动态产生B、静态产生C、无解空间D、动态或者静态产生10、在用贪心法解多机调度时

3、的贪心选择策略是：（）A、最优子结构B、重叠子问题C、Johnson法则D、最长处理时间作业优先11、合并排序和快速排序采用的共同策略是：（）A、分治法B、蒙特卡罗法C、拉斯维加斯法D、单纯形法12、用回溯法解最大团问题时生成的解空间树是：（）A、子集树B、排列树C、二叉树D、多叉树13、用分支限界法解装载问题的解空间是：（）A、子集树B、排列树C、单向链表D、多向链表14、计算定积分的算法：（）A、随机投点法B、舍伍德法C、分治法D、回溯法15、用随机化算法解同一实例两次得到：（）A、结果和时间都相同B、结果相同时间不相同C、结果和时间都不相同D、以上都不对主观题部分：二、改错题（

4、每题2.5分，共2题）下面有两个二分搜索算法，请判断它们的正确性。如果算法不正确，请说明产生错误的原因；如果算法正确，请给出算法的正确性证明。1publicstaticintbinarySearch(int[]a,intx,intn){intleft=0;intright=n-1;while(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left=middle;elseright=middle;}return-1;}2publicstaticintbinarySear

5、ch(int[]a,intx,intn){intleft=0;intright=n-1;while(left<=right-1){intmiddle=(left+right)/2;if(x

6、程序。编程任务：对于给定的n个程序存放在磁带上的长度，编程计算磁带上最多可以存储的程序数。数据输入：由文件input.txt给出输入数据。第1行是2个正整数，分别表示文件个数n和磁带的长度L。接下来的1行中，有n个正整数，表示程序存放在磁带上的长度。结果输出：将编程计算出的最多可以存储的程序数输出到文件output.txt。输入文件示例输出文件示例input.txtoutput.txt65052313880202.编辑距离问题问题描述：设A和B是2个字符串。要用最少的字符操作将字符串A转化为字符串B.这里所说的字符操作包括：（1）删除一个字符；（2）插入一个字符；（3）将一个字符改为

7、另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的2个字符串A和B，计算出它们的编辑距离d(A,B)。编程任务：对于给定的字符串A和字符串B，编程计算其编辑距离d(A,B)。数据输入：由文件input.txt提供输入数据。文件的第1行是字符串A，文件的第2行是字符串B。结果输出：程序运行结束时，将编辑距离d(A,B)输出到文件output.txt的第1行中。输入文件示例输出文件