奥鹏作业答案
《算法分析与设计》作业(一)
本课程作业由两部分组成。第一部分为“客观题部分”,由15个选择题组成,每题1分,共15分。第二部分为“主观题部分”,由()和论述题组成,共15分。作业总分30分,将作为平时成绩记入课程总成绩。
客观题部分:
一、 选择题(每题1分,共15题)
1、递归算法: ( )
①、直接调用自身 ②、间接调用自身③、直接或间接调用自身 ④、不调用自身
2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题,这些子问题: ( )
①、相互独立 ②、与原问题相同
③、相互依赖 ④、相互独立且与原问题相同
3、备忘录方法的递归方式是: ( )
①、自顶向下 ②、自底向上
③、和动态规划算法相同 ④、非递归的
4、回溯法的求解目标是找出解空间中满足约束条件的: ( )
①、所有解 ②、一些解 ③、极大解 ④、极小解
5、贪心算法和动态规划算法共有特点是: ( )
①、最优子结构 ②、重叠子问题 ③、贪心选择 ④、形函数
6、哈夫曼编码是: ( )
①、定长编码 ②、变长编码③、随机编码 ④、定长或变长编码
7、多机调度的贪心策略是: ( )
①、最长处理时间作业优先 ②、最短处理时间作业优先
③、随机调度 ④、最优调度
8、程序可以不满足如下性质: ( )
①、零个或多个外部输入 ②、至少一个输出
③、指令的确定性 ④、指令的有限性
9、用分治法设计出的程序一般是: ( )
①、递归算法 ②、动态规划算法
③、贪心算法 ④、回溯法
10、采用动态规划算法分解得到的子问题: ( )
①、相互独立 ②、与原问题相同
③、相互依赖 ④、相互独立且与原问题相同
11、回溯法搜索解空间的方法是: ( )
①、深度优先 ②、广度优先 ③、最小耗费优先 ④、随机搜索
12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法:( )
①、所需时间变化 ②、一定找到解
③、找不到所需的解 ④、性能变差
13、贪心算法能得到: ( )
①、全局最优解 ②、0-1背包问题的解 ③、背包问题的解 ④、无解
14、能求解单源最短路径问题的算法是: ( )
①、分支限界法 ②、动态规划 ③、线形规划 ④、蒙特卡罗算法
15、快速排序算法和线性时间选择算法的随机化版本是: ( )
①、舍伍德算法②、蒙特卡罗算法 ③、拉斯维加斯算法 ④、数值随机化算法
主观题部分:
二、 写出下列程序的答案(每题2.5分,共2题)
1、请写出批处理作业调度的回溯算法。
2、函数渐进阶
对于下列各组函数f(n)和g(n),确定f(n)=O(g(n))或f(n)=或f(n)= ,并简述理由。
(1) f(n)=logn2; g(n)=logn+5;
(2) f(n)=logn2; g(n)= ;
(3) f(n)=n; g(n)=log2n;
(4) f(n)=nlogn+n; g(n)=logn;
(5) f(n)=10; g(n)=log10;
(6) f(n)= log2n; g(n)=logn;
(7) f(n)=2n; g(n)=100n2;
(8) f(n) =2n; g(n)=3n;
三、写出下列题目的程序(每题5分,共2题)
1、请写出背包问题的贪心算法。
2、字符串比较问题
问题描述:对于长度相同的2个字符串A和B,其距离定义为相应位置字符距离之和。2个非空格字符的距离是它们的ASCII码之差的绝对值。空格与空格的距离为0,空格与其它字符的距离为一定值k。
在一般情况下,字符串A和B的长度不一定相同。字符串A的扩展是在A中插入若干空格字符所产生的字符串。在字符串A和B的所有长度相同的扩展中,有一对距离最小的扩展,该距离称为字符串A和B的扩展距离。
对于给定的字符串A和B,试设计一个算法,计算其扩展距离。
编程任务:对于给定的字符串A和B,编程计算其扩展距离。
数据输入:由文件input.txt给出输入数据。第1行是字符串A,第2行是字符串B,第3行是空格与其它字符的距离定值k。
结果输出:将计算出的字符串A和B的扩展距离输出到文件output.txt。
输入文件示例 输出文件示例
input.txt output.txt
cmc 10
snmn
2
《算法分析与设计》作业(二)
本课程作业由两部分组成。第一部分为“客观题部分”,由15个选择题组成,每题1分,共15分。第二部分为“主观题部分”,由()和论述题组成,共15分。作业总分30分,将作为平时成绩记入课程总成绩。
客观题部分:
一、 选择题(每题1分,共15题)
1、动态规划算法解各个子问题的方法是: ( )
①、自底向上 ②、自顶向下③、随机选择 ④、自底向上或自顶向下
2、回溯法解园排列问题的解空间树是: ( )
①、子集树 ②、排列树 ③、二叉树 ④、多叉树
3、用分治法求平面最接近点对问题时采用的著名原理是: ( )
①、Johnson法则 ②、鸽舍原理 ③、牛顿原理 ④、线性规划原理
4、分支限界法搜索解空间的方式是: ( )
①、广度优先 ②、深度优先 ③、随机 ④、以上都不是
5、采用如下随机方法计算 值: ( )
①、随机投点法 ②、舍伍德法 ③、拉斯维加斯法 ④、单纯形法
6、下面是描述算法复杂度的有: ( )
①、时间复杂度 ②、鸽舍原理 ③、二分法 ④、随机化算法
7、下面不属于单纯形法步骤是: ( )
①、选入基变量 ②、选离基变量 ③、做转轴变化 ④、动态规划
8、快速排序和线性时间选择的随机化版本是: ( )
①、舍伍德算法 ②、拉斯维加斯算法③、蒙特卡罗 ④、单纯形法
9、用回溯法解旅行售货员问题时生成的解空间树是: ( )
①、子集树 ②、排列树 ③、二叉树 ④、多叉树
10、用回溯法解0-1背包问题时生成的解空间树是: ( )
①、子集树 ②、排列树 ③、二叉树 ④、多叉树
11、用分支限界法解布线问题时的解空间是: ( )
①、子集树 ②、排列树 ③、图 ④、二叉树
12、跳跃表是采用哪种随机化算法设计的: ( )
①、舍伍德算法 ②、拉斯维加斯算法③、蒙特卡罗 ④、单纯形法
13、合并排序和快速排序都采用的策略是: ( )
①、分治 ②、Johnson法则 ③、鸽舍原理 ④、单纯形法
14、下面不属于单纯形法的步骤的是: ( )
①、选入基变量 ②、选离基变量③、作转轴变化 ④、找最优子结构
15、Kruskal算法能解以下问题: ( )
①、单源最短路径 ②、n后问题 ③、最小生成树 ④、装载问题
主观题部分:
二、 改错题(每题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 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转化为字符串②. 这里所说的字符操作包括:
(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 |