[北京师范大学]19春《算法分析与设计》离线作业123（答案）
《算法分析与设计》作业（一）本课程作业由两部分组成。第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。第二部分为“主观题部分”，由和论述题组成，共15分。作业总分30分，将作为平时成绩记入课程总成绩。
客观题部分：
一、 选择题（每题1分，共15题）
1、递归算法： （ ）
A、直接调用自身 B、间接调用自身C、直接或间接调用自身 D、不调用自身
2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题，这些子问题：
（ ）
A、相互独立 B、与原问题相同
C、相互依赖 D、相互独立且与原问题相同
3、备忘录方法的递归方式是： （ ）
A、自顶向下 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、采用动态规划算法分解得到的子问题： （ ）
A、相互独立 B、与原问题相同
C、相互依赖 D、相互独立且与原问题相同
11、回溯法搜索解空间的方法是： （ ）
A、深度优先 B、广度优先 C、最小耗费优先 D、随机搜索
12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法：（ ）
A、所需时间变化 B、一定找到解
C、找不到所需的解 D、性能变差
13、贪心算法能得到： （ ）
A、全局最优解 B、0-1背包问题的解 C、背包问题的解 D、无解
14、能求解单源最短路径问题的算法是： （ ）
A、分支限界法 B、动态规划 C、线形规划 D、蒙特卡罗算法
15、快速排序算法和线性时间选择算法的随机化版本是： （ ）
A、舍伍德算法B、蒙特卡罗算法 C、拉斯维加斯算法 D、数值随机化算法
主观题部分：
二、 写出下列程序的答案（每题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、动态规划算法解各个子问题的方法是： （ ）
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) left = middle;
else right = middle;
}
if (x==a) return left;
return -1;
}
2 public static int binarySearch(int [] a, int x, int n)
{
If (n>0 && x>=a) {
int left = 0;int right = n - 1;
while (left < right) {
int middle = (left + right)/2;
if (x < a) right = middle-1;
else left = middle;
}
if (x==a) 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
《算法分析与设计》作业（三）
本课程作业由两部分组成。第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。第二部分为“主观题部分”，由谋学网（www.mouxue.com）和论述题组成，共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) return middle;
if (x > a) 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) right = middle;
else left = middle;
}
if (x==a) 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
页:
[1]