北师18秋《算法分析与设计》作业（二）（资料）

同学情

《算法分析与设计》作业（二）
本课程作业由两部分组成。第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。第二部分为“主观题部分”，由谋学网（www.mouxue.com）和论述题组成，共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个算法的正确性。如果算法不正确，请说明产生错误的原因。如果算法正确，请给算法的正确性证明。
1 public static int binarySearch(int [] a, int x, int n)
    {
     int left = 0;  int right = n - 1;
     while (left+1!= right) {
        int middle = (left + right)/2;  
        if (x > =a[middle]) left = middle;      
        else right = middle;
     }
     if (x==a[left]) return left;
     return -1;   
   }

2 public static int binarySearch(int [] a, int x, int n)
{
If (n>0 && x>=a[0]) {
      int left = 0;  int right = n - 1;
      while (left < right) {
        int middle = (left + right)/2;  
        if (x < a[middle]) right = middle-1;      
        else left = middle;
      }
     if (x==a[left]) return left;
}
     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.txt                                        output.txt
3        12
5        15
7