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

算法分析与设计作业（三）本课程作业由两部分组成。第一部分为“客观题部分”，由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、子集树 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、在用贪心法解多机调度时的贪心选择策略是： （ ） 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、以上都不对主观题部分：二、 改错题（每题2.5分，共2题） 下面有两个二分搜索算法，请判断它们的正确性。如果算法不正确，请说明产生错误的原因；如果算法正确，请给出算法的正确性证明。1 public static int binarySearch(int a, int x, int n) int left = 0; int right = n - 1; while (left amiddle) left = middle; else right = middle; return -1; 2 public static int binarySearch(int a, int x, int n) int left = 0; int right = n - 1; while (left = right-1) int middle = (left + right)/2; if (x amiddle) right = middle; else left = middle; if (x=aleft) return left; else return -1; 三、写出下列题目的程序（每题5分，共2题）1. 程序存储问题 问题描述：设有n个程序 1, 2, , n要存放在长度为L的磁带上。程序i存放在磁带上的长度是li, 。程序存储问题要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。编程任务：对于给定的n个程序存放在磁带上的长度，编程计算磁带上最多可以存储的程序数。数据输入：由文件input.txt给出输入数据。第1行是2个正整数，分别表示文件个数n和磁带的长度L。接下来的1行中，有n个正整数，表示程序存放在磁带上的长度。结果输出：将编程计算出的最多可以存储的程序数输出到文件output.txt。 输入文件示例输出文件示例 input.txt output.txt 6 50 5 2 3 13 8 80 20 2. 编辑距离问题问题描述：设A和B是2个字符串。要用最少的字符操作将字符串A转化为字符串B.这里所说的字符操作包括：（1） 删除一个字符；（2） 插入一个字符；（3） 将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A, B)。试设计一个有效算法，对任给的2个字符串A和B，计算出它们的编辑距离d(A, B)。编程任务：对于给定的字符串A和字符串B，编程计算其编辑距离d(A, B)。数据输入：由文件input.txt提供输入数据。文件的第1行是字符串A