A卷
一、选择题
1.二分搜索算法是利用（A ）实现的算法。
A、分治策略
B、动态规划法
C、贪心法
D、回溯法
2. 回溯法解旅行售货员问题时的解空间树是（ A  ）。
A、子集树
B、排列树
C、深度优先生成树
D、广度优先生成树
3.下列算法中通常以自底向上的方式求解最优解的是（B    ）。
A、备忘录法
B、动态规划法
C、贪心法
D、回溯法
4．下面不是分支界限法搜索方式的是（  D  ）。
A、广度优先
B、最小耗费优先
C、最大效益优先
D、深度优先
5．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为    (    B          ) 。
A、O（n2n）
B、O（nlogn）
C、O（2n）
D、O（n）
6．分支限界法解最大团问题时，活结点表的组织形式是（ B）。
A、最小堆
B、最大堆
C、栈
D、数组
7、下面问题（B ）不能使用贪心法解决。
A 单源最短路径问题
B N皇后问题
C 最小花费生成树问题
D 背包问题
8.下列算法中不能解决0/1背包问题的是（A ）
A 贪心法
B 动态规划
C 回溯法
D 分支限界法
9.背包问题的贪心算法所需的计算时间为（  B  ）
A、O（n2n）
B、O（nlogn）
C、O（2n）
D、O（n）
10.背包问题的贪心算法所需的计算时间为（B  ）。
A、O（n2n）
B、O（nlogn）
C、O（2n）
D、O（n）
二、填空题
1.算法的复杂性有复杂性和复杂性之分。
2.算法是由若干条指令组成的有穷序列，且要满足输入、、确定性和四条性质。其中算法的“确定性”指的是组成算法的每条是清晰的，无歧义的。
3.解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是，需要排序的是，。
4.动态规划算法的两个基本要素是.            性质和性质。
5.回溯法是一种既带有又带有的搜索算法；分支限界法是一种既带有又带有的搜索算法。
6. 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为。
7.用回溯法解图的m着问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜的可用性，则需耗时（渐进时间上限）。
Bool Color::OK(int k)
{//
for(int j=1;j<=n;j++)
if((a[k][j]= =1)&&(x[j]= =x[k])) return false;
return true;
}
8.用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为n m
⨯的方格阵列，扩展每个结点需O(1)的时间，L为最短布线路径的长度，则算法共耗时，构造相应的最短距离需要时间。
for (int i = 0; i < NumOfNbrs; i++) {
if (w][l] == 0) {
// 该方格未标记
w][l]
= w][l] + 1;
if ((w == w) &&
(l == l)) break; // 完成布线
Q.Add(nbr);}
}
9.快速排序算法是基于的一种排序算法。
10.            是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别
三．简答题
1.设计动态规划算法的主要步骤是怎么的？请简述。
2.分治法所能解决的问题一般具有哪几个特征？请简述。
3.分支限界法的搜索策略是什么？
四．计算题
1.已知非齐次递归方程：
f(n)bf(n1)g(n)
f(0)c
=-+
⎧
⎨
=
⎩
，其中，b、c是常数，g(n)是n的某一个函数。则f(n)
的非递归表达式为：
n
n n i
i1
f(n)cb b g(i)
-
=
=+∑。
现有Hanoi塔问题的递归方程为：
h(n)2h(n1)1
h(1)1
=-+
⎧
⎨
=
⎩
，求h(n)的非递归表达式。
2.给定带权有向图（如下图所示）G =(V,E)，其中每条边的权是非负实数。另外，还给定V 中的一个
顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。现采用Dijkstra 算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。
五．程序题
1.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n 公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。
2.试用动态规划算法实现下列问题：设A 和B 是两个字符串。我们要用最少的字符操作，将字符串A 转换为字符串B ，这里所说的字符操作包括：    （1）删除一个字符。 （2）插入一个字符。
（3）将一个字符改为另一个字符。  请写出该算法。
答案：
一、AABDB  BBABB 二、
1. 时间    空间
4
3      2      1      {1} 初始 dist[5]
dist[4] dist[3] dist[2] u S 迭代
2. 输出    有限性    指令
3. 动态规划    回溯法    分支限界法
4. 最优子结构    重叠子问题
5. 系统性    跳跃性    系统性    跳跃性
6. （O(h(n))）
7. O （mn ）
8.  O(mn)    O(L)
9. 分治策略  10. 贪心选择性质 三、
1.（1）出最优解的性质，并刻划其结构特征。  （2）递归地定义最优值。
（3）以自底向上的方式计算出最优值。
（4）根据计算最优值时得到的信息，构造最优解。
2. （1）该问题的规模缩小到一定的程度就可以容易地解决；
（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质;  （3） 利用该问题分解出的子问题的解可以合并为该问题的解；
（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
3.  在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地出一个最优解。
四、 1.解：利用给出的关系式，此时有：b=2, c=1, g(n)=1, 从n 递推到1，有：
n 1
n 1
n 1i i 1
n 1n 22n h(n)cb
b g(i)
<22121----=--=+=+++++=-∑ 2.
60
30
50
10
5
{1，2，3，4，5}
4
60 30 50 10 3 {1，2，4，3} 3 90 30 50 10 4 {1，2，4} 2 100 30 60 10 2 {1，2} 1 100 30  10 - {1} 初始 dist[5] dist[4] dist[3]
dist[2] u S 迭代
五．程序题
1.解：int greedy(vecter<int>x,int n)
{
int sum=0,k=x.size();
for(int j=0;j<k;j++)
哈夫曼编码树的带权路径长度
if(x[j]>n){
cout<<”No solution”<<endl;
return -1;
}
For(int i=0,s=0;i<k;i++){
S+=x[i];
if(s>n){sum++;s=x[i];}
}
return sum;
}
2.解：此题用动态规划算法求解：
int dist()
{
int m=a.size();
int n=b.size();
vector<int>d(n+1，0);
for(int i=1;i<=n;i++)d[i]=i;
for(i=1;i<=m;i++){
int y=i-1;
for(int j=1;j<=n;j++){
int x-y;
y=d[j];
int z=j>1?d[j-1]:i;
int del=a[i-1]==b[j-1]?0:1;
d[j]=min(x+del,y+1,z+1);
}
}
return d[n];
}
一、填空题（每小题3分，共30分）
1、一个算法的优劣可以用与与来衡量。
2、这种不断回头寻目标的方法称为。
3、直接或间接地调用自身的算法称为。
4、 记号在算法复杂性的表示法中表示。
5、由分治法产生的子问题往往是，这就为使用提供了方便。
6、建立计算模型的目的是为了使。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。