资源描述：
《2011.2算法设计与分析试题A答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、山东理工大学《算法设计与分析》参考答案及评分标准（A）卷10-11学年第一学期班级：姓名：学号：…………………………………装……………………………订…………………………线………….………………………………适用专业07计算机科学1—4考核性质考试开卷命题教师石少俭考试时间100分钟题号一二三四五六七八九十十一总分得分评阅人复核人一．简答题（每题5分，共20分）1．程序的时间复杂性和空间复杂性算法的复杂性是算法运行所需要的计算机资源的量。需要时间资源的量称为时间复杂性。需要空间资源的量称为空间复杂性。2．回溯法与分支限界法的
2、区别两者都是问题的解空间树上搜索问题解的算法。回溯法与分支限界法的的求解目标不同，回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标是找出解空间树中满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。3．写出3个NP完全问题团问题、子集和问题、旅行售货员问题。4．概率算法特征对所求问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。二．解下列递推方程（10分）：T(n)=1n=1T(n)=3T(n/3)+(n/3)log3(n/3
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(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.货物装箱问题
4、：设有一艘货船装物品。共有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，
5、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*
6、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=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=
7、(1,0,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,
8、0,1)时，w=11=11因此X=(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)是一个可
