算法设计试题

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

A.运行速度快B.占用空间少C.时间复杂度低D.代码短5.二分搜索算法是利用（A）实现的算法。A.分治法B.动态规划法

C.贪心法

D.回溯法下面问题（B）不能使用贪心法解决。

A.单源最短路径问题 B.N皇后问题

C.最小代价生成树问题 D.背包问题7．用贪心法设计算法的关键是（B）。A.将问题分解为多个子问题来分别处理B.选好最优量度标准C.获取各阶段间的递推关系式D.满足最优性原理8.找最小生成树的算法Kruskal的时间复杂度为（D）（其中n为无向图的结点数，m为边数）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）是回溯法中遍历排列树的算法框架程序。A.voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(legal(t))backtrack(t+1);swap(x[t],x[i]);}}B.Voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t+1);}}C.Voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t-1);}}D.Voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){Swap(x[t],x[i]);if(legal(t))backtrack(t+1);}}12.0-1背包问题的回溯算法所需的计算时间为（

A）A.O（n2n） B.O（nlogn） C.O（2n） D.O（n）13．哈弗曼编码的贪心算法所需的计算时间为（B）A.O（n2n） B.O（nlogn） C.O（2n）D.O（n）14.矩阵连乘问题的算法可由（B）设计实现。A.分支界限算法

B.动态规划算法

C.贪心算法

D.回溯算法15.采用广度优先策略搜索的算法是（A）。A.分支界限法 B.动态规划法 C.贪心法 D.回溯法二、填空题（15*2分）1.算法的复杂性有______和______之分,衡量一个算法好坏的标准是_____________。2.某一问题可用动态规划算法求解的显著特征是_________________________。3.若序列A={xzyzzyx}，B={zxyyzxz}，请给出序列A和B的一个最长公共子序列__________________。4.动态规划算法的基本思想是将待求解问题分解成若干___________先求解_________,然后从这些_____________的解得到原问题的解。5.0-1背包问题的回溯算法所需的计算时间为____________,用动态规划算法所需的计算时间为________________。6.二分法搜索算法是利用___________实现的算法。7.所谓最优化问题是指问题给定某些约束条件，满足这些约束条件的问题解称为___________。8.回溯法解决问题时，应明确定义问题的解空间，问题的解空间至少应包含________。9.__________是描述问题解空间的树形结构。10.在分枝限界法中一个活结点只可能一次成为E结点，回溯法中任何一个或结点可能____成为E结点。答案：1.时间、空间时间复杂度空间复杂度。2.算法效率3.xyzz.4.子问题子问题子问题5.o（n*2n）o(min{nc2n})6.动态规划法7.可行解8.2n9.状态空间树10.多次三、算法设计题（每题10分、共20分）1、设计一个回溯算法，使用可变长度状态空间树求解子集和数问题。解、子集和数的回溯算法：voidSumOfSub(floats,intk,floatr,int*x,floatm,float*w){x[k]=1;if(s+w[k]==m){for(intj=0;j<=k;j++)cout<<x[j]<<’’;cout<<endl;}elseif(s+w[k]+w[k+1]<=m)SumOfSub(s+w[k],k+1,r-w[k],x,m,w);if((s+r-w[k]>=m)&&(s+w[k+1]<=m)){x[k]=0;SumOfSub(s,k+1,r-w[k],x,m,w);}}voidSumSub(int*x,intn,floatm,float*w){floatr=0;for(inti=0;i<n;i++)r=r+w[i];if(r>=m&&w[0]<=m)SumOfSub(0,0,r,x,m,w);}假设n=8,[w1,….,w8]=[100,200,50,90,150,50,20,80],c=400.利用贪心算法时，所考察货箱的顺序为7,3,6,8,4,1,5,2.货箱7,3,6,8,4,1的总重量为390个单位且已被装载，剩下的装载能力为10，小于剩下的任何一个货箱。根据贪心解决算法，得到[x1,…,x8]=[1,0,1,1,0,1,1,1],且∑Xi=6.解、货箱装船算法实现：voidContainerLoading(intX[],Tw[],Tc,intn){//货箱装船问题的贪心算法//x[t]=1当且仅当货箱t被装载，1<=t<=n//c是船的容量，w是货箱的重量//t是间接寻址表int*t=newint[n+1];IndirectSort(w,t,n);//此时，w[t[t]]<=w[t[t+1]],1<=t<n//初始化xfor(intt=1;t<=n;t++)x[t]=0;//按重量次序选择物品for(t=1;t<=n&&w[t[t]]<=c;t++){//剩余容量想x[[t]]=1;c-=w[t[t]];}delete[]t;}（货箱装船问题。货箱可以分步装载，每步装一个货箱，且需要考虑装载哪一个货箱。根据这种思想可利用如下贪心准则：从剩下的货箱中，选择重量最小的货箱。这种选择次序可以保证所选的货箱总重量最小，从而可以装载更多的货箱。根据这种贪心策略，首先选择最轻的货箱，然后选择次轻的货箱，如此下去，直到所有货箱均装上船，或船上不能再容纳其他任何一个货箱。）四、应用题（30分）1（5分）、设背包问题实例n=7，M=15,(w0,w1,w2…,w6)=(2,3,5,7,1,4,1),物品装入背包的收益为：(p0,p1,p2,…,p6)=(10,5,15,7,6,18,3)。求这一实验的最优解和最大收益。答案：由定理：如果p0/w0>=…>=pn-1/wn-1,则用贪心法求得的背包问题的解是最优解，知按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符合题目要求最大收益为：max∑pixi=5*2/3+15*1+6*1+18*1+3*1=55.332（5）、写出对下图所示的多段图采用向后递推动态规划算法求解时的计算过程0010256478t856332542671632答案：Bcost(1,0)=0Bcost(2,1)=5Bcost(2,2)=2Bcost(3,3)=min{3+Bcost(2,1),6+Bcost(2,2)}=8Bcost(3,4)=7Bcost(3,5)=min{3+Bcost(2,1),8+Bcost(2,2)}=8Bcost(4,6)=min{1+Bcost(3,3),6+Bcost(3,4),6+Bcost(3,5)}=9Bcost(4,7)=min{4+Bcost(3,3),2+Bcost(3,4),3+Bcot(3,5)}=9Bcost(5,8)=min{7+Bcost(4,6),3+Bcost(4,7)}=123（10分）、设有带时限的作业排序实例：n=4,(p0,d0,t0)=(5,1,1),(p1,d1,t0)=(10,3,2),(p2,d2,t2)=(6,2,1)和(p3,d3,t3)=(3,1,1),求使得总收益最大的作业子集J。c=8u=241c=8u=24114351191015c=02