资源描述：
《2006-2007(2)算法设计与分析试题答案(软件)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2006-2007学年第二学期《计算机算法设计与分析》试题院系：软件学院 专业：软件工程 年级：2004级 （参考答案）一．简答题（共10分）（5分）二．计算题（35分）１．(6分)对下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ(g(n))。(1)f(n)=3n，g(n)=2n(2)f(n)=logn+5，g(n)=logn2(3)f(n)=logn，g(n)=答：(1)f(n)=Ω(g(n))(2分)(2)f(n)=θ(g(n))(2分)(3)f(n)=O(g(n))(2分)2．（８分）采用动态规划策略，计算a=｛5
2、,-3,7,-4,-5,9,-2,10,-3,2｝的最大子段和，并给出这个最大子段和的起始下标和终止下标。［设数组a中的元素下标从１开始。］要求给出过程。答：b[1]=5；b[2]=max{b[1]+a[2]，a[2]}=max{2,-3}=2b[3]=max{b[2]+a[3]，a[3]}=max{9,7}=9b[4]=max{b[3]+a[4]，a[4]}=max{5,-4}=5b[5]=max{b[4]+a[5]，a[5]}=max{0,-5}=0b[6]=max{b[5]+a[6]，a[6]}=max{9,9}=9b[7]=max{b[6]+a[7]，a[7]}=max{7
3、,-2}=7b[8]=max{b[7]+a[8]，a[8]}=max{17,10}=17b[9]=max{b[8]+a[9]，a[9]}=max{14,-3}=14b[10]=max{b[9]+a[10]，a[10]}=max{16,2}=16(上述每两行１分，共５分)最大子段和为17（1分）（若数组下标从１开始）起始下标：６（１分），终止下标：８（１分）（若数组下标从０开始）起始下标：５（0.5分），终止下标：7（0.5分）３．（11分）设有３件工作分配给３个人，将工作i分配给第j个人所花的费用为Cij，现将为每一个人都分配１件不同的工作，并使总费用达到最小。设：5要求：（1）画
4、出该问题的解空间树；（６分）（2）写出该问题的剪枝策略(限界条件)；（1分）（3）按回溯法搜索解空间树，并利用剪枝策略对应该剪掉的子树打´；（２分）（4）最终给出该问题的最优值和最优解。（２分）答：（1）12323131211223332312116169999╳╳╳╳（每个分枝1分，或者是每层2分，共6分）（2）当耗费大于等于当前最优值时，剪枝。（1分）（3）见上图。（每2个╳1分，共2分）（4）最优值：9（1分）最优解：2，1，3４．（８分）给定两个序列X=，Y=，请采用动态规划策略求出其最长公共子序列。要求给出过程。答：j01234
5、5iyiBDCAB0xi00000051A0000112B0111123C0112224B0112235Ａ012223 （上述表内每一行一分，共６分） 最长公共子序列为 （２分） 5．（2分）考虑n=3时的0-1背包问题的实例：W={15,10,10}，P={50,30,30}，c=20。当x[1]=1，x[2]=0时，请计算Bound(2)。答：Bound(3)=50+5/10*20=65(2分)三、算法填空题（共10分，每空2分）给定n种物品和一个背包，物品i的重量是w[i],其价值是p[i],背包的容量为c。设物品已按单位重量价值递减的次序排序。每种物品
6、不可以装入背包多次，但可以装入部分的物品i。求解背包问题的贪心算法如下：floatKnapsack(floatx[],floatw[],floatp[],floatc,intn){floatmaxsum=;//maxsum表示装进包的物品价值总和for(inti=1;i<=n;i++)x[i]=0//x[i]=0表示第i个物品未装进包for()if(){x[i]=1;maxsum+=;c-=w[i];}elsebreak;if(c>0){x[i]=c/w[i];;}returnmaxsum;}答：(共５个空，每空2分，总计10分)０inti=1；i<=n；ｉ++5w[i]<=Cp[
7、i]maxsum+=p[i]*c/w[i]四、算法设计及分析题（共45分）1．（20分）请用分治策略设计递归的二分检索算法，并分析其时间复杂性（要求给出每个阶段所花的时间，在此基础上列出递归方程，并求出其解的渐进阶）。答：（此题解法不唯一）算法：intbsearch(A[],K,L,H)（1分）{if(H
