资源描述：
《2011算法设计与分析试题b答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、山东理工大学《算法设计与分析》评分标准（B）卷10-11学年第二学期班级：姓名：学号：…………………………………装……………………………订…………………………线………….………………………………一．简答题（每题5分，共20分）1．程序的时间复杂性和空间复杂性算法的复杂性是算法运行所需要的计算机资源的量。需要时间资源的量称为时间复杂性。需要空间资源的量称为空间复杂性。2．回溯法与分支限界法的区别两者都是问题的解空间树上搜索问题解的算法。回溯法与分支限界法的的求解目标不同，回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法
2、的求解目标是找出解空间树中满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。3．写出3个NP完全问题团问题、子集和问题、旅行售货员问题。(任意3个即可)4．概率算法的分类数值概率算法、舍五德算法、拉斯维加斯算法、孟特卡罗算法。二．解下列递推方程（10分）：T(n)=1n=1T(n)=8T(n/2)+O(n2),n>1T(n)=8T(n/2)+O(n2)=8(8T(n/22)+O(n/2)2)+O(n2)=82T(n/22)+O(n2)=8k3T(n/2k)+O(n2)(n=2
3、k)（------6分）=8logn=O(n3)（-----4分）三．实例题（每题10分，共40分）1.451312169522最大总费用：每次合并最多的2组45+22+（67+16）+（83+13）+（96+12）+（108+9）+117+5=593（-----5分）最小总费用：每次合并最少的4组5+9+13+12+（39+16+22+45）=161（-----5分）2.给出一个赋权无向图如下,求最小生成树。2544653345每错一边扣2分。共3页第1页(1)3.123*789的计算过程如下:令X=123Y=789则把X,Y分为两
4、段得X=1*102+23Y=7*102+89记A=1B=23C=7D=89则由大整数乘法得公式得X*Y=AC104+((A-B)(D-C)+AC+BD)102+BD=1*7*104+(-22*82+1*7+23*89)*102+23*89=970474.n=4,w=[15,10,8，13],p=[20,15,13,18],c=30。M(I,j)为背包容量为j，可选择物品为I,I+1,…,n时0-1背包问题的最优值（-----2分）M(1,30)=max{m(2,30),20+m(2,15)}=33m(2,30)=max{m(3,30)
5、,15+m(3,20)}={31,33}=33（-----4分）m(2,15)=max{m(3,15),15+m(3,5)}={18,15}=18m(3,30)=max{m(4,30),13+m(4,22)}={18，31}=31m(3,20)=max{m(4,20),13+m(4,12)}={18,0}=18m(3,15)=max{m(4,15),13+m(4,7)}={18,0}=18m(3,5)=m(4,5)=0（-----4分）最优值为33，最优解为（1,0,1,0）四．编程题（每题15分，共30分）1：code:#inclu
6、de#include#defineN600 //N不能太大了intmax(inta,intb){ returna>b?a:b;}intmain(){ inti,j,k,n; intV,W,p; intc[10],w[10],pr[10],v[10]; intf[N][N]; while(scanf("%d",&n)!=EOF) { scanf("%d%d",&V,&W); for(i=1;i<=n;i++) scanf("%d%d%d%d",&v[i],&w[i],&c[i]
7、,&pr[i]); memset(f,0,sizeof(f)); for(i=1;i<=n;i++) //（二维）多重背包转化成01背包 { j=c[i]; for(k=W;k>=j*w[i];k--) { for(p=V;p>=j*v[i];p--) { f[k][p]=max(f[k][p],f[k-j*w[i]][p-j*v[i]]+j*pr[i]); } } } printf("%d",f[W]
8、[V]); }}共3页第2页 for(j=1;j<=c[i];j*=2) { for(k=W;k>=j*w[i];k--) //就是再加这一维就行了 { for(p=V;p>=j*v[i];p-
