2011.2算法设计与分析试题A答案

山东理工大学《算法设计与分析》参考答案及评分标准（A）卷10-11学年第一学期班级：姓名：学号：…………………………………装……………………………订…………………………线………….………………………………适用专业07计算机科学1—4考核性质考试开卷命题教师石少俭考试时间100分钟题号一二三四五六七八九十十一总分得分评阅人复核人一．简答题（每题5分，共20分）1．程序的时间复杂性和空间复杂性算法的复杂性是算法运行所需要的计算机资源的量。需要时间资源的量称为时间复杂性。需要空间资源的量称为空间复杂性。2．回溯法与分支限界法的区别两者都是问题的解空间树上搜索问题解的算法。回溯法与分支限界法的的求解目标不同，回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标是找出解空间树中满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。3．写出3个NP完全问题团问题、子集和问题、旅行售货员问题。4．概率算法特征对所求问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。二．解下列递推方程（10分）：T(n)=1n=1T(n)=3T(n/3)+(n/3)log3(n/3),n1T(n)=3T(n/3)+(n/3)log3(n/3)=3(3T(n/32)+(n/3)log3(n/3))+(n/3)log3(n/32=32T(n/32)+(n/3)(log3(n/3)+log3(n/32))=3kT(n/3k)+(n/3)(log3(n/3)+log3(n/32)+……+log3(n/3k))=3kT(n/3k)+(n/3)(log3(nk/3k(k+1)/2)(n=3k)=n+(n/3)(k-1)/2(log3n)=O(nlog23n)三．实例题（每题10分，共40分）1.货物装箱问题：设有一艘货船装物品。共有n=6件物品，它们的重量如下表示：[w1,...,w6]=[100,200,50,90,50,20]，船的限载重量是c=300。试用贪心算法装船，要求物品装得最多。贪心准则：从剩下的货箱中选择重量最小的货箱。设xi=1表示第i件物品装船，xi=0表示第i件物品不装船，则贪心算法如下：1）x6=1，船的限载重量c=300-20=2802）x3=1，船的限载重量c=280-50=2303）x5=1，船的限载重量c=230-50=1804）x4=1，船的限载重量c=180-90=90解为（0，0，1，1，1，1）2.给出一个赋权无向图如下，求顶点S到T的最短路665863775ST368649共4页第1页山东理工大学《算法设计与分析》答案…………………………………装……………………………订…………………………线………….………………………………3.用分治算法计算123*789。令X=123Y=789则把X,Y分为两段得X=1*102+23Y=7*102+89记A=1B=23C=7,D=89则由大整数乘法得公式得X*Y=AC104+((A-B)(D-C)+AC+BD)102+BD=1*23*104+(-22*82+1*23+23*89)*102+23*89=970474.0-1背包问题:n=4,w=[2,4,6,7],p=[6,10,12,13],c=11。使用回溯法的求解过程为：由以上解空间树得知：当X=(1,1,1,1)时，w=1911因此X=(1,1,1,1)不是一个可行解当X=(1,1,1,0)时，w=1211因此X=(1,1,1,0)不是一个可行解当X=(1,1,0,1)时，w=1311因此X=(1,1,0,1)不是一个可行解当X=(1,1,0,0)时，w=611因此X=(1,1,0,0)是一个可行解,P=16当X=(1,0,1,1)时，w=1511因此X=(1,0,1,1)不是一个可行解当X=(1,0,1,0)时，w=811因此X=(1,0,1,0)是一个可行解,P=18当X=(1,0,0,1)时，w=911因此X=(1,0,0,1)是一个可行解,P=19当X=(1,0,0,0)时，w=211因此X=(1,0,0,0)是一个可行解,P=6当X=(0,1,1,1)时，w=1711因此X=(0,1,1,1)不是一个可行解当X=(0,1,1,0)时，w=1011因此X=(0,1,1,0)是一个可行解,P=22当X=(0,1,0,1)时，w=11=11因此X=(0,1,0,1)是一个可行解,P=23当X=(0,1,0,0)时，w=411因此X=(0,1,0,0)是一个可行解,P=10当X=(0,0,1,1)时，w=1311因此X=(0,0,1,1)不是一个可行解当X=(0,0,1,0)时，w=611因此X=(0,0,1,0)是一个可行解,P=12当X=(0,0,0,1)时，w=711因此X=(0,0,0,1)是一个可行解,P=13当X=(0,0,0,0)时，w=011因此X=(0,0,0,0)是一个可行解,P=0因此X=(0,1,0,1)问题的一个最优解,即不装入物品1,装入物品2,不装入物品3,装入物品4;其最优值为23共4页第2页山东理工大学《算法设计与分析》答案…………………………………装……………………………订…………………………线………….………………………………共4页第3页山东理工大学《算法设计与分析》试卷纸四．编程题（每题15分，共30分）1.一个人有一捆草，一只羊，一头老虎。他想把草、羊、老虎运过河。但是老虎要吃羊，羊要吃草。他要羊不吃草，虎不羊。完整运过去。请问他应怎样运？人、羊；人回来，人、草；人、羊；人、虎；人；人、羊3.求矩阵连乘A1A2A3A4A5的最优计算次序：各矩阵阶数依次为：30╳35，35╳5，5╳10，10╳20，20╳30。M[1][2]=30*35*5=5250;m[2][3]=10*20*30=6000M[3][4]=5*10*20=1000;m[4][5]=10*20*30=6000M[1][5]=min{m[1][k]+m[k+1][5]+P1PkP5}=13750K=1:m[1][1]+m[2][5]+30*35*30=9250+31500K=2:m[1][2]+m[3][5]+30*5*30=5250+4000+4500=13750K=3:m[1][3]+m[4][5]+30*10*30=21750K=4:m[1][4]+m[5][5]+30*20*30=27250M[2][5]=min{m[2][k]+m[k+1][5]+P2PkP5}=9250K=2:m[2][2]+m[3][5]+35*5*30=9250K=3:m[2][3]+m[4][5]+35*10*30=1750+6000+10500K=4:m[2][4]+m[5][5]+35*20*30=4500+21000M[3][5]=min{m[3][k]+m[k+1][5]+P3PkP5}=4000K=3:m[3][3]+m[4][5]+5*10*30=6000+1500=7500K=4:m[3][4]+m[5][5]+5*20*30=4000M[1][4]=min{m[1][k]+m[k+1][4]+P1PkP4}=9250K=1:m[1][1]+m[2][4]+30*35*20=4500+21000K=2:m[1][2]+m[3][4]+30*5*20=9250K=3:m[1][3]+m[4][4]+30*10*20=12750M[1][3]=min{m[1][k]+m[k+1][3]+P1PkP3}=6750K=1:m[1][1]+m[2][3]+30*35*10=12500K=2:m[1][2]+m[3][3]+30*5*10=6750M[2][4]=min{m[2][k]+m[k+1][4]+P2PkP4}=4500K=2:m[2][2]+m[3][4]+35*5*20=4500K=3:m[2][3]+m[4][4]+35*10*20=8750最优解为（12）（（34）5）最优值为13750。…………………………………装……………………………订…………………………线………….………………………………3.二维0-1背包问题：n件物品装船，已知物品i的重量为wi，体积为hi,价值为vi。船舱的体积为H，限重W。试用动态规划编程，求选择那些物品装船，可使得装入物品的总价值最大。1.templateclassType2.Typeknapsack_dynamic(intw[],Typep[],intn,intm,BOOLx[])3.{inti,j,k;5.Typev,(*optp)[m+1]=newType[n+1][m+1];/*分配工作单元*/6.for(i=0;i=n;i++){/*初始化第0列*/7.optp[i][0]=0;x[i]=FALSE;/*解向量初始化为FALSE*/8.}9.for(i=0;i=m;i++)/*初始化第0行*/10.optp[0][i]=0;11.for(i=1;i=n;i++){/*计算optp[i][j]*/12.for(j=1;j=m;j++){13.optp[i][j]=optp[i-1][j];14.if((j=w[i])&&(optp[i-1,j-w[i]]+p[i]optp[i-1][j])optp[i][j]=optp[i-1,j-w[i]]+p[i];16.}17.}18.j=m;/*递推装入背包的物体*/19.for(i=n;i0;i--){20.if(optp[i][j]optp[i-1][j]){x[i]=TRUE;j=j–w[i];22.}23.}24.v=optp[n][m];25.deleteoptp;/*释放工作单元*/26.returnv;/*返回最大价值*/27.}共4页第4页