选择题（20分）
1 •最长公共子序列算法利用的算法是（ A、分支界限法 B动态规划法
B C贪心法
A
)
0
)0
D回溯法
2 •实现棋盘覆盖算法利用的算法是（ A、分治法
B动态规划法
C贪心法 、
D回溯法
C
)0
D定义最优解
3. 下面是贪心算法的基本要素的是（
C贪心选择性质 A、重叠子问题 B构造最优解 、
D ） 4. 回溯法的效率不依赖于下列哪些因素（ A.满足显约束的值的个数
B.计算约束函数的时间
D.确定解空间的时间 C.计算限界函数的时间
5.
数是回溯法中为避免无效搜索采取的策略（ A.递归函数
B.剪枝函数
C。随机数函数
A C、贪心法 B
C、构造最优解
下面哪种函
B ） D.搜索函数 ）。 D回溯法 ）。 D、定义最
6. 米用最大效益优先搜索方式的算法是（ A、分支界限法
B、动态规划法
7. 贪心算法与动态规划算法的主要区别是（ A、最优子结构 优解
8. 实现最大子段和利用的算法是（
A、分治策略
B、贪心选择性质
B ）。
D回溯法 C
)。
C、贪心法 B、动态规划法
9.优先队列式分支限界法选取扩展结点的原则是（
B、后进先出
A、先进先出
C、结点的优先级 D随机
A ）
D、回溯法
10.下列算法中通常以广度优先方式系统搜索问题解的是（
A、分支限界法
B动态规划法
C贪心法
二、填空题（22分每空2分） 1、
组成的有穷序列，且要满足输入、 确定性和
有限性 ______ 四条性质。
分治法 来设计的。
分支限界法 。 算法是由若干条指令
输出
2、 大整数乘积算法是用
3、 以广度优先或以最小耗费方式搜索问题解的算法称为 4、 舍伍德算法总能求得问题的
一个解。
5、 贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态 规划算法的主要区别。 6•快速排序
templatevclass Type>
void Quicksort (Type a[], int p, int r) {
if (Pint q=Partiti on( a,p,r); Quicksort (a,p,q-1); // Quicksort (a,q+1,r); // } } 7.哈密顿环问题的算法可由 回溯法 设计实现。
回溯法 o
8. 贪心算法不一定产生最优解。
9•算法中通常以深度优先方式系统搜索问题解的是
对左半段排序 对右半段排序
三、算法设计与分析(25分)
1.
用欧几里德迭代算法求两个数的最小公倍数(10分)
#in clude using n amespace std; int Gcd(i nt m,i nt n) {if(m==0)
return n; if(n==0)
return m; int t=m>n?n:m; while(m%t|| n%t) t--; return t; }
int main() {
int a,b;
cout«\" In put a & b (0<=a >a>>b;int m=a*b/Gcd(a,b);
cout<<\"The Least Com mon Multiple is:\"<return 0;2、 试用动态规划算法实现最大子矩阵和问题：求 m n矩阵A的一个子矩阵，使 其各元素之各为最大。(15分)
解：解答如下：
int MaxSum2(int m,int n,int **a) {
int sum=O;
int *b=new in t[ n+1]; for(int i=1;i<=m;i++){
for(int k=1;k<=n;k++) b[k]=O; for(i nt j=i;j<=m;j++){
for(int k=1;k<=n;k++) b[k]+=a[j][k]; int max=MaxSu m(n ,b); if(max>sum) sum=max;
} }
return sum; }
int MaxSum(int n,int *a)
{
int sum=O,b=O; for(i nt i=1;i<=n ;i++){ if(b>0) b+=a[i]; else b=a[i]; if(b>sum) sum=b;
} Return sum; ...................................... .. (15 分) }
四、简答题(33分)
1、假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容 量M = 150,如果使用贪心方法求解此背包问题，使收益最大，请写出求解过程请写出求解 过程。(10分)
物品 重量 价值 A B C D E F G 25 30 ....................................... ..
(10 分)
...................................... .. (5 分)
35 30 60 50 40 10 10 40 30 50 35 40 解:使用单位价值从大到小：FBGDECA ,得到贪心解为：FBGD全部放入，而E放入87.5% , 得到价值为190.625。 2.
算法对下列实例中找最大数和最小数的过程。
数组 A=(48,12,61,3,5,19,32,7) 解：1、48,12,61,3, 2、 48,12 61,3 5,19 32,7
3、 48 〜61, 12 〜3 19 〜32, 5 〜7
5,19,32,7
表中元素多于二， 对半分割 表中元素多于二， 对半分割
写出分治算法 MaxMin(10分)
求前半部分的最大最小和后半部分的最大最小，两个半部分的大者为最大，小者
为最小
4、61〜32
3〜5 两个半部分的大者为最大，小者为最小
5、 61 3 寻找结束 3. 写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。
(13 分)
C(1,2)=3，C(1,3)=5 ，C(1,4)=2
C(2,6)=8 ，C(2,7)=4 ，C(3,5)=5 ，C(3,6)=4， C(4,5)=2 ，C(4,6)=1 C(5,8)=4， C(6,8)=5 解：Cost(4,8)=0 Cost(3,7)= C(7,8)+0=6 Cost(3,6)= C(6 ，8)+0=5, Cost(3,5)= C(5 ，8)+0=4 Cost(2,4)= min{C(4 Cost(2,3)= min{C(3
=mi n{4+5}=9 Cost(2,2)= min{C(2
，6)+ Cost(3,6), C(2
，7)+ Cost(3,7)}
=min {8+5, 4+6}=10
Cost(1,1)= min {C(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+ Cost(2,4)}
=min {3+10, 5+9,2+6}= 8
按上所述，Cost(1,1)为所求最优值。
，6)+ Cost(3,6), C(4 ，6)+ Cost(3,6) }
，5)+ Cost(3,5)}
=mi n{1+ 5, 2+4}=6
， ，C(7,8)=6
