算法分析与设计试题

1、选择题（20分）1 最长公共子序列算法利用的算法是（A、分支界限法 B动态规划法2 实现棋盘覆盖算法利用的算法是（A、分治法B动态规划法3. 下面是贪心算法的基本要素的是（A、重叠子问题B构造最优解4. 回溯法的效率不依赖于下列哪些因素（A.满足显约束的值的个数C.计算限界函数的时间B)0C贪心法D回溯法A)0C、贪心法D回溯法C)0C、贪心选择性质D定义最优解D ）B.计算约束函数的时间D.确定解空间的时间5. 下面哪种函数是回溯法中为避免无效搜索采取的策略（B）A.递归函数B.剪枝函数C。随机数函数D.搜索函数6. 米用最大效益优先搜索方式的算法是（A、分支界限法B、动态规划法7. 贪心算

2、法与动态规划算法的主要区别是（A、最优子结构B、贪心选择性质优解8. 实现最大子段和利用的算法是（A、分治策略B、动态规划法A）。C、贪心法D回溯法B）。C、构造最优解D、定义最B）。C、贪心法D回溯法9.优先队列式分支限界法选取扩展结点的原则是（C)。A、先进先出B、后进先出C、结点的优先级D随机10.下列算法中通常以广度优先方式系统搜索问题解的是（A ）A、分支限界法B动态规划法C贪心法D、回溯法二、填空题（22分每空2分）1、算法是由若干条指令组成的有穷序列，且要满足输入、输出确定性和有限性 四条性质。2、 大整数乘积算法是用分治法 来设计的。3、 以广度优先或以最小耗费方式搜索问题解的

3、算法称为分支限界法 。4、 舍伍德算法总能求得问题的一个解。5、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。6快速排序templatevclass Typevoid Quicksort (Type a, int p, int r)if (Pr) int q=Partiti on( a,p,r);Quicksort (a,p,q-1); /对左半段排序Quicksort (a,q+1,r); /对右半段排序7. 哈密顿环问题的算法可由回溯法设计实现。8. 贪心算法不一定产生最优解。9算法中通常以深度优先方式系统搜索问题解的是回溯法 o三、算法设计与分析(25

4、分)1. 用欧几里德迭代算法求两个数的最小公倍数(10分)#in cludeusing n amespace std;int Gcd(i nt m,i nt n)if(m=0)return n;if(n=0)return m;int t=mn?n:m;while(m%t| n%t)t-;return t;int main()int a,b;cout In put a & b (0=a ab;int m=a*b/Gcd(a,b);coutThe Least Com mon Multiple is:me ndl;return 0;2、 试用动态规划算法实现最大子矩阵和问题：求m n矩阵A的一个子矩

5、阵，使 其各元素之各为最大。(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+) bk=O; . (5 分)for(i nt j=i;j=m;j+)for(int k=1;ksum) sum=max;return sum; .(10 分)int MaxSum(int n,int *a)int sum=O,b=O;for(i nt i=1;i0) b+=ai;else b=ai;if(bsum) sum=b; Return su

6、m; . (15 分)四、简答题(33分)1、假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容 量M = 150,如果使用贪心方法求解此背包问题，使收益最大，请写出求解过程请写出求解 过程。(10分)物品ABCDEFG重量35306050401025价值10403050354030解:使用单位价值从大到小：FBGDECA ,得到贪心解为：FBGD全部放入，而E放入87.5% , 得到价值为190.625。2. 写出分治算法 MaxMin算法对下列实例中找最大数和最小数的过程。(10分)数组 A=(48,12,61,3,5,19,32,7)解：1、48,12,61,3

7、,5,19,32,7表中元素多于二，对半分割2、 48,12 61,3 5,19 32,7表中元素多于二，对半分割3、48 61, 12 3 19 32, 5 7求前半部分的最大最小和后半部分的最大最小，两个半部分的大者为最大，小者为最小4、613235 两个半部分的大者为最大，小者为最小5、 61 3(13 分)寻找结束3.写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。C(1,2)=3，C(1,3)=5，C(1,4)=2C(2,6)=8，C(2,7)=4，C(3,5)=5，C(3,6)=4， C(4,5)=2 ，C(4,6)=1C(5,8)=4， C(6,8)=5，C(7,8)=6解：Cost(4,8)=0Cost(3,7)= C(7,8)+0=6，Cost(3,6)= C(6，8)+0=5,Cost(3,5)= C(5，8)+0=4Cost(2,4)= minC(4，6)+ Cost(3,6), C(4，5)+ Cost(3,5)=mi n1+ 5, 2+4=6Cost(2,3)= minC(3，6)+ Cost(3,6) =mi n4+5=9Cost(2,2)= minC(2，6)+ Cost(3,6), C(2，7)+ Cost(3,7)=min