2010算法设计与分析试题A

1、 山东理工大学算法设计与分析试卷纸（a ）卷 10-11第 一学期 班级： 姓名： 学号： 装订线.适用专业07算机科学14考核性质考试开 卷命题教师石少俭考试时间100分钟题号一二三四五六七八九十十一总分得分评阅人复核人 一 简答题（每题5分，共20分）1 程序的时间复杂性和空间复杂性2 回溯法与分支限界法的区别3 写出3个np完全问题4 概率算法特征二解下列递推方程（10分）： t(n)=1 n=1t(n)=3t(n/3)+(n/3)log3(n/3) ,n>1三 实例题（每题10分，共40分）1. 货物装箱问题：设有一艘货船装物品。共有n=6件物品，它们的重量如下表示：w1,.,

2、w6 = 95, 200, 60, 90, 50, 20，船的限载重量是c=300。试用贪心算法装船，要求物品装得最多。贪心准则：从剩下的货箱中选择重量最小的货箱。2. 给出一个赋权无向图如下，求顶点s到t的最短路 66586 3775 s t368 649 共 3 页 第 1 页山东理工大学算法设计与分析试卷纸（a ）卷 10-11 学年第 一 学期 班级： 姓名： 学号： 装订线.3. 用分治算法计算123*789。4.0-1背包问题:n=4, w=2,4,6,7, p =6,10,12,13, c = 11。 共 3 页 第 2 页山东理工大学算法设计与分析试卷纸（a ）卷 10-11

3、学年第 一 学期 班级： 姓名： 学号： 装订线.四综合题（第一题5分，第二题10分，第三题15分，共30分）1.一个人有一捆草，一只羊，一头老虎。他想把草、羊、老虎运过河。但是老虎要吃羊，羊要吃草。他要羊不吃草，虎不羊。完整运过去。请问他应怎样运？2求矩阵连乘a1 a2 a3 a4 a5的最优计算次序：各矩阵阶数依次为：3035，355，510，1020，2030。3.二维0-1背包问题：n件物品装船，已知物品i的重量为wi，体积为hi,价值为vi。船舱的体积为h，限重w。试用动态规划编程，求选择那些物品装船，可使得装入物品的总价值最大。 山东理工大学算法设计与分析参考答案及评分标准（a ）

4、卷 10-11学年第 一学期 班级： 姓名： 学号： 装订线.适用专业07计算机科学14考核性质考试开 卷命题教师石少俭考试时间100分钟题号一二三四五六七八九十十一总分得分评阅人复核人 简答题（每题5分，共20分）程序的时间复杂性和空间复杂性算法的复杂性是算法运行所需要的计算机资源的量。需要时间资源的量称为时间复杂性。需要空间资源的量称为空间复杂性。回溯法与分支限界法的区别两者都是问题的解空间树上搜索问题解的算法。回溯法与分支限界法的的求解目标不同，回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标是找出解空间树中满足约束条件的一个解，或是在满足约束条件的解中找出使

5、某一目标函数值达到极大或极小的解，即在某种意义下的最优解。写出3个np完全问题团问题、子集和问题、旅行售货员问题。概率算法特征 对所求问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。二解下列递推方程（10分）： t(n)=1 n=1t(n)=3t(n/3)+(n/3)log3(n/3) ,n>1t(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(

6、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(n log23n)实例题（每题10分，共40分）货物装箱问题：设有一艘货船装物品。共有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）

7、x3=1，船的限载重量c=280-50=2303）x5=1，船的限载重量c=230-50=1804）x4=1，船的限载重量c=180-90=90解为（0，0，1，1，1，1）给出一个赋权无向图如下，求顶点s到t的最短路 66586 3775 s t368 649 共 4 页 第 1 页山东理工大学算法设计与分析答案 装订线.3. 用分治算法计算123*789。令 x=123 y=789 则把x,y分为两段得x=1*102+23 y=7*102+89记a=1 b=23 c=7,d=89则由大整数乘法得公式得x*y=ac104+( (a-b)(d-c) +ac+bd) 102+bd=1*23*10

8、4+(-22*82+1*23+23*89)*102+23*89 =97047 4.0-1背包问题:n=4, w=2,4,6,7, p =6,10,12,13, c = 11。使用回溯法的求解过程为：由以上解空间树得知：当x=(1,1,1,1)时，w=19>11 因此x=(1,1,1,1)不是一个可行解当x=(1,1,1,0)时，w=12>11 因此x=(1,1,1,0)不是一个可行解当x=(1,1,0,1)时，w=13>11 因此x=(1,1,0,1)不是一个可行解当x=(1,1,0,0)时，w=6<11 因此x=(1,1,0,0)是一个可行解,p=16当x=(1,0,

9、1,1)时，w=15>11 因此x=(1,0,1,1)不是一个可行解当x=(1,0,1,0)时，w=8<11 因此x=(1,0,1,0)是一个可行解,p=18当x=(1,0,0,1)时，w=9<11 因此x=(1,0,0,1)是一个可行解,p=19当x=(1,0,0,0)时，w=2<11 因此x=(1,0,0,0)是一个可行解,p=6当x=(0,1,1,1)时，w=17>11 因此x=(0,1,1,1)不是一个可行解当x=(0,1,1,0)时，w=10<11 因此x=(0,1,1,0)是一个可行解,p=22当x=(0,1,0,1)时，w=11=11 因此x=

10、(0,1,0,1)是一个可行解,p=23当x=(0,1,0,0)时，w=4<11 因此x=(0,1,0,0)是一个可行解,p=10当x=(0,0,1,1)时，w=13>11 因此x=(0,0,1,1)不是一个可行解当x=(0,0,1,0)时，w=6<11 因此x=(0,0,1,0)是一个可行解,p=12当x=(0,0,0,1)时，w=7<11 因此x=(0,0,0,1)是一个可行解,p=13当x=(0,0,0,0)时，w=0<11 因此x=(0,0,0,0)是一个可行解,p=0因此x=(0,1,0,1)问题的一个最优解,即不装入物品1, 装入物品2 ,不装入物品3

11、, 装入物品4;其最优值为23 共 4 页 第 2 页山东理工大学算法设计与分析答案 四编程题（每题15分，共30分）1.一个人有一捆草，一只羊，一头老虎。他想把草、羊、老虎运过河。但是老虎要吃羊，羊要吃草。他要羊不吃草，虎不羊。完整运过去。请问他应怎样运？人、羊；人回来，人、草；人、羊；人、虎；人；人、羊求矩阵连乘a1 a2 a3 a4 a5的最优计算次序：各矩阵阶数依次为：3035，355，510，1020，2030。m12=30*35*5=5250;m23=10*20*30=6000m34=5*10*20=1000;m45=10*20*30=6000m15=minm1k+mk+15+p1

12、pkp5=13750k=1:m11+m25+30*35*30=9250+31500k=2:m12+m35+30*5*30=5250+4000+4500=13750k=3:m13+m45+30*10*30=21750k=4:m14+m55+30*20*30=27250m25=minm2k+mk+15+p2pkp5=9250k=2:m22+m35+35*5*30=9250k=3:m23+m45+35*10*30=1750+6000+10500k=4:m24+m55+35*20*30=4500+21000m35=minm3k+mk+15+p3pkp5=4000k=3:m33+m45+5*10*30=

13、6000+1500=7500k=4:m34+m55+5*20*30=4000m14=minm1k+mk+14+p1pkp4=9250k=1:m11+m24+30*35*20=4500+21000k=2:m12+m34+30*5*20=9250k=3:m13+m44+30*10*20=12750m13=minm1k+mk+13+p1pkp3=6750k=1:m11+m23+30*35*10=12500k=2:m12+m33+30*5*10=6750m24=minm2k+mk+14+p2pkp4=4500k=2:m22+m34+35*5*20=4500k=3:m23+m44+35*10*20=87

14、50最优解为（12）（34）5）最优值为13750。 装订线. 共 4 页 第 3 页 山东理工大学算法设计与分析试卷纸 装订线.3.二维0-1背包问题：n件物品装船，已知物品i的重量为wi，体积为hi,价值为vi。船舱的体积为h，限重w。试用动态规划编程，求选择那些物品装船，可使得装入物品的总价值最大。1. template <class type> 2. type knapsack_dynamic(int w,type p,int n,int m,bool x) 3. int i,j,k; 5. type v,(*optp)m+1 = new typen+1m+1; /* 分配工作单元 */ 6. for (i=0;i<=n;i+)/* 初始化第0列 */ 7. optpi0 = 0; xi = false; /* 解向量初始化为false */ 8. 9. for (i=0;i<=m;i+)/* 初始化第0行 */10. optp0i = 0;11. for (i=1;i<=n;i+) /* 计算optpij */12. for (j=1;j<=m;j+) 13. optpij = optpi-1j;14. if (j>=wi)&&(optpi-1,j-wi+pi&g