(完整word版)算法设计试题(word文档良心出品)

1、一、选择题（15*2分）1.算法分析是（C）A. 将算法用某种程序设计语言恰当地表示出来B. 在抽象数据集合上执行程序，以确定是否会产生错误的结果C. 对算法需要多少计算时间和存储空间作定量分析D. 证明算法对所有可能的合法输入都能算出正确的答案2.算法与程序的区别在于算法具有（C）A.能行性B.确定性C.有穷性D.输入和输出3.记号0的定义正确的是（B）A.O(g( n) = f(n) |存在正常数c和nO使得当n > no有f（n） < cg（n） B.O(g( n) = f(n) |存在正常数c和nO使得当n>no有cg（n） < f（n） C. (g( n) =

2、 f(n) | 有 f(n)vcg(n) D. (g( n) = f(n) | 有 cg(n) < f(n) 对于任何正常数c>0,存在正数和no >0使得对所有n>no对于任何正常数c>0,存在正数和no >0使得对所有n>no4.衡量一个算法好坏的标准是（C）A.运行速度快B.占用空间少C.时间复杂度低D.代码短5.二分搜索算法是利用（A）实现的算法。A.分治法B.动态规划法C.贪心法 D.回溯法6.下面问题（B ）不能使用贪心法解决。A.单源最短路径问题B. N皇后问题C.最小代价生成树问题D.背包问题7 .用贪心法设计算法的关键是（B ） 0A

3、. 将问题分解为多个子问题来分别处理B. 选好最优量度标准C. 获取各阶段间的递推关系式D. 满足最优性原理8.找最小生成树的算法Kruskal的时间复杂度为（D ）（其中n为无向图的结点 数，m为边数）A. O（n2） B . O（mlogn） C . O（nlogm） D . O（mlogm）9.回溯法搜索状态空间树是按照（C ）的顺序。A.中序遍历 B.广度优先遍历C.深度优先遍历D.层次优先遍历10. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（B ）A.重叠子问题B.最优子结构性质C.最优量度标准性质 D.定义最优解11.程序块(A)是回溯法中遍历排列树的算法框架程序。

4、A.void backtrack(i nt t)if(t >n )out put(x);elsefor(i nt i=t;i<=n ;i+)swa p(xt,xi);if(legal(t)backtrack(t+1);swa p(xt,xi);B. Void backtrack (i nt t)if(t> n)out pu t(x);elsefor( int i=0;i<=1;i+)xt=i;if(legal(t)backtrack(t+1);C.Void backtrack (i nt t)if(t> n)out pu t(x);elsefor(i nt i=0

5、;iv=1;i+)xt=i; if(legal(t)backtrack(t-1);D.Void backtrack (int t)if(t> n)o ut put(x);elsefor(i nt i=t;i<=n ;i+)Swa p( xt,xi);if(legal(t)backtrack(t+1);12.0-1背包问题的回溯算法所需的计算时间为(A.O(n2n) B.O (nlogn )C.O (2n)A )D.O (n)13.A.O哈弗曼编码的贪心算法所需的计算时间为(n2n) B.O (nlogn ) C.O (2n) D.O (n)14. 矩阵连乘问题的算法可由(B)设计实

6、现。A.分支界限算法B.动态规划算法C.贪心算法D.回溯算法15. 采用广度优先策略搜索的算法是(A )。A.分支界限法B.动态规划法C.贪心法D.回溯法1.算法的复杂性有之分，衡量一个算法好坏的标准是二、填空题(15*2分)2. 某一问题可用动态规划算法求解的显著特征是3. 若序列A=xzyzzyx , B=zxyyzxz,请给出序列A和B的一个最长公共子序列。先求解4. 动态规划算法的基本思想是将待求解问题分解成若干然后从这些勺解得到原问题的解。5.0-1背包问题的回溯算法所需的计算时间为 用动态规划算法所需的计算时间为6. 二分法搜索算法是利用7. 所谓最优化问题是指问题给定某些约束条件

7、，。8. 回溯法解决问题时，应明确定义问题的解空间，。9. 描述问题解空间的树形结构。10. 在分枝限界法中一个活结点只可能一次成为点可能成为E结点。实现的算法。满足这些约束条件的问题解称为问题的解空间至少应包含E结点，回溯法中任何一个或结答案：1.时间、空间 时间复杂度空间复杂度。2. 算法效率3. xyzz.4. 子问题 子问题 子问题5.0 (n*2n) o(minnc 2、)6.动态规划法7.可行解8.2n9. 状态空间树10. 多次三、算法设计题（每题10分、共20分）1、设计一个回溯算法，使用可变长度状态空间树求解子集和数问题。解、子集和数的回溯算法:void SumOfSub(f

8、loat s,i nt k,float r,i nt*x,float m,float*w) xk=1;if(s+wk=m) for(i nt j=0;j<=k;j+)cout<<xj<< coutvve ndl;else if(s+wk+wk+1v=m)SumOfSub(s+wk,k+1,r-wk,x,m,w);if(s+r-wk>=m)&&(s+wk+1v=m) xk=0;SumOfSub(s,k+1,r-wk,x,m,w);void SumSub(i nt*x,i nt n, float m,float*w)float r=0;for(i

9、 nt i=0;i vn ;i+)r=r+wi;if(r>=m&&w0v=m)SumOfSub(0,0,r,x,m,w);利用贪心算2、假设 n=8,w1,.,w8=100,200,50,90,150,50,20,80,c=400.法时，所考察货箱的顺序为7,3,6,8,4,1,52 货箱736,8,4,1的总重量为且刀Xi=6.390个单位且已被装载，剩下的装载能力为 10,小于剩下的任何一个货箱。根据贪心解决算法，得到x1,x8=1,0,1,1,0,1,1,1.解、货箱装船算法实现：void Contain erLoad in g(i nt X,T w,T c,i n

10、t n)/货箱装船问题的贪心算法 /xt=1 当且仅当货箱t被装载，1<=t<=n/c是船的容量，w是货箱的重量/t是间接寻址表 int *t=new in t n+1;In directSort(w,t, n);/ 此时，wtt<=wtt+1,1<=t<n/初始化x for(i nt t=1;t<=n; t+) xt=0;/按重量次序选择物品 for(t=1;t<=n&&wtt<=c;t+)/剩余容量想 xt=1;c-=wtt;deletet;（货箱装船问题。货箱可以分步装载，每步装一个货箱，且需要考虑装载哪一个货箱。根据这种思

11、想可利用如下贪心准则： 从剩下的货箱中，选择重量最小的货箱。这种选择次序可以保证所选的货箱总重量最小，从而可以装载更多的货箱。根据这种贪心策略，首先选择最轻的货箱，然后选择次轻的货箱，如此下去，直到所有货箱均装上船，或船上不能再容纳其他任何一个货箱。)四、应用题(30分)1 (5分)、设背包问题实例 n=7 , M=15,(w0,w1,w2,w6)=(2,3,5,7,1,4,1),物品装入背包的 收益为：(p0,p 1,p2,p6)=(10,5,15,7,6,18,3)0求这一实验的最优解和最大收益。答案：由定理：如果p0/w0>=- >=pn-1/w n-1,则用贪心法求得的背包

12、问题的解是最优解， 知按pi/wi的非增次序选取物品可求得最优解设背包问题的解为x=(x0,x1,x2,x3,x4,x5,x6),由已知条件知(p0/w0,p1/w1,p6/w6)=(5,1.67,3,1,6,4.5,3)使用这一标准得到的解即最优 解为，(x0,x1,x6)=(1,2/3,1,0,1,1,1)此时刀 WiXi=(1*2+2/3*3+1*5+0*7+1*1+1*4+1)=15 符 合题目要求最大收益为：maxX P ixi=5*2/3+15*1+6*1+18*1+3*1=55.332 (5)、写出对下图所示的多段图采用向后递推动态规划算法求解时的计算过程答案：Bcost(1,0)=0Bcost(2,1)=5Bcost(2,2)=2Bcost(3,3)=mi n3+Bcost(2,1),6+Bcost(2,2)=8Bcost(3,4)=7Bcost(3,5)=mi n3+Bcost(2,1),8+Bcost(2,2)=8Bcost(4,6)=mi n1+Bcost(3,3),6+Bcost(3,4),6+Bcost(3,5)=9Bcost(4,7)=mi n4+Bcost