北师17秋《算法分析与设计》作业(二)答案

[复制链接]
发表于 2017-8-18 09:37:05 | 显示全部楼层 |阅读模式
《算法分析与设计》作业(二)
本课程作业由两部分组成。第一部分为“客观题部分”,由15个选择题组成,每题1分,共15分。第二部分为“主观题部分”,由简答题和论述题组成,共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



算法分析与设计作业2-答案.rar

4.49 KB, 下载次数: 11, 下载积分: 贡献 1

售价: 10 金币  [记录]

答案

快速回复 返回顶部 返回列表