北师17秋《算法分析与设计》作业（三）答案

青青

《算法分析与设计》作业（三）
本课程作业由两部分组成。第一部分为“客观题部分”，由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存放在磁带上的长度是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，文件的第2行是字符串B。
结果输出：程序运行结束时，将编辑距离d(A, B)输出到文件output.txt的第1行中。
   输入文件示例                                输出文件示例
   input.txt                   output.txt
   fxpimu                     5
       xwrs