《算法分析与设计》作业( 一)
本课程作业由两部分组成。第一部分为”客观题部分”, 由
15个选择题组成, 每题1分, 共15分。第二部分为”主观题部分”,
由简答题和论述题组成, 共15分。作业总分30分, 将作为平时成
绩记入课程总成绩。
客观题部分:
一、选择题( 每题1分, 共15题)
1、递归算法: ( C )
A、直接调用自身
B、间接调用自身
C、直接或间接
调用自身 D、不调用自身
2、分治法的基本思想是将一个规模为n的问题分解为k个规模
较小的字问题, 这些子问题: ( D )
A、相互独立
B、与原问题相同
C、相互依赖
D、相互独立且与原问题相同
3、备忘录方法的递归方式是:
( C )
A、自顶向下
B、自底向上
C、和动态规划算法相同
D、非递归的
4、回溯法的求解目标是找出解空间中满足约束条件的:
( A )
A、所有解
B、一些解
C、极大解
D、极小解
5、贪心算法和动态规划算法共有特点是: ( A )
A、最优子结构
B、重叠子问题
C、贪心选择
D、
形函数
6、哈夫曼编码是: ( B)
A、定长编码
B、变长编码
C、随机编码
D、定
长或变长编码
7、多机调度的贪心策略是: ( A)
A、最长处理时间作业优先
B、最短处理时间作业优
先
C、随机调度
D、最优调度
8、程序能够不满足如下性质: ( D )
A、零个或多个外部输入
B、至少一个输出
C、指令的确定性
D、指令的有限性
9、用分治法设计出的程序一般是: ( A )
A、递归算法
B、动态规划算法
C、贪心算法
D、回溯法
10、采用动态规划算法分解得到的子问题:
( C )
A、相互独立
B、与原问题相同
C、相互依赖
D、相互独立且与原问题相同
11、回溯法搜索解空间的方法是: ( A )
A、深度优先
B、广度优先
C、最小耗费优先
D、随机搜索
12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策
有可能导致算法: ( C )
A、所需时间变化
B、一定找到解
C、找不到所需的解
D、性能变差
13、贪心算法能得到: ( C )
A、全局最优解
B、 0-1背包问题的解
C、背包问题的
解 D、无解
14、能求解单源最短路径问题的算法是: ( A )
A、分支限界法
B、动态规划
C、线形规划
D、蒙特卡罗算法
15、快速排序算法和线性时间选择算法的随机化版本是:
( A )
A、舍伍德算法
B、蒙特卡罗算法
C、拉斯维加斯算法
D、数值随机化算法
主观题部分:
二、写出下列程序的答案( 每题2.5分, 共2题)
1、请写出批处理作业调度的回溯算法。
#include
#include
using namespace std;
class Flowing
{
friend int Flow(int ** ,int ,int []);
private:
//int Bound(int i);
void Backtrack(int t);
int **M;//
int *x;//当前解
int *bestx;//
int *f2;//
int f1;//
int f;//
int bestf;//
int n;//
};
void Flowing::Backtrack(int i)
{
if(i>n){
for(int j=1;j<=n;j++)
bestx[j]=x[j];
bestf=f;
}
else
for(int j=i;j<=n;j++){
f1+=M[x[j]][1];
f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];
f+=f2[i];
if(fswap(x[i],x[j]);
Backtrack(i+1);
swap(x[i],x[j]);
}
f1-=M[x[j]][1];
f-=f2[i];
}
}
int Flow(int ** M,int n,int bestx[]){ int ub=INT_MAX;
Flowing X;
X.x=new int[n+1];
X.f2=new int[n+1];
X.M=M;
X.n=n;
X.bestx=bestx;
X.bestf=ub;
X.f1=0;
X.f=0;
for(int i=0;i<=n;i++)
X.f2[i]=0,X.x[i]=i;
X.Backtrack(1);
delete[] X.x;
delete[] X.f2;
return X.bestf;
}
void main(){
int **M;
