《算法分析与设计》作业（二）
本课程作业由两部分组成。第一部分为“客观题部分”，由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?i?j?n。试设计一个算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。
编程任务：对于给定的游艇出租站i到游艇出租站j之间的租金为r(i, j)，1?i?j?n，编程计算从游艇出租站1到游艇出租站n所需的最少租金。
数据输入：由文件input.txt提供输入数据。文件的第1行中有1个正整数n (n<=200)，
表示有n个游艇出租站。接下来的n-1行是r(i, j)，1?i?j?n。
结果输出：程序运行结束时，将计算出的从游艇出租站1到游艇出租站n所需的最少租
输出文件示例 output.txt
12
金输出到文件output.txt中。 输入文件示例 input.txt
3
5 15 7
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法分析与设计作业(二)在线全文阅读。
相关推荐：