《算法分析与设计》作业（三）
本课程作业由两部分组成。
第一部分为“客观题部分”，由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 <= right) {
int middle = (left + right)/2;
if (x == a[middle]) return middle;
if (x > a[middle]) 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 < a[middle]) right = middle;
else left = middle;
}
if (x==a[left]) return left;
else return -1;
}
三、写出下列题目的程序（每题5分，共2题）
1. 程序存储问题
问题描述：设有n个程序{1, 2, …, n}要存放在长度为L的磁带上。
程序i存放在磁带
上的长度是l i , n i ≤≤1。
程序存储问题要求确定这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 ，文件的第2行是字符串B 。
结果输出：程序运行结束时，将编辑距离d(A, B)输出到文件output.txt 的第1行中。
输入文件示例 输出文件示例
input.txt output.txt
fxpimu 5
xwrs。