北京航空航天大学算法设计与分析试题答案

1、2006-2007学年第二学期计算机算法设计与分析试题院系：软件学院专业：软件工程年级：2004级一简答题（共10分） 略二. 计算题(35分)1. (6分)对下列各组函数 f(n)和 g(n),确定 f(n)=O(g(n)或 f(n)= Q (g(n)或 f(n)= B (g(n)。(1) f(n)=3n, g(n)=2n2(2) f(n)=log n + 5, g(n)=log n（2分）（2分）（2分）(3) f(n)=log n, g(n)= n 答：(1) f(n) = Q (g(n) f(n) = 9 (g(n)(3) f(n) = O(g(n)2. （8分）采用动态规划策略，计算

2、a=5,-3,7,-4,-5,9,-2,10,-3,2的最大子段和, 并给出这个最大子段和的起始下标和终止下标。设数组a中的元素下标从1开 始。要求给出过程。答：b1=5 ；b2=maxb1+a2 , a2=max2,-3=2 b3=maxb2+a3 , a3=max9,7=9 b4=maxb3+a4 , a4=max5,-4=5 b5=maxb4+a5 , a5=max0,-5=0 b6=maxb5+a6 , a6=max9,9=9 b7=maxb6+a7 , a7=max7,-2=7 b8=maxb7+a8 , a8=max17,10=17 b9=maxb8+a9 , a9=max14,-

3、3=14 b10=maxb9+a10 , a10=max16,2=16 （上述每两行1分，共5分） 最大子段和为17 （1分）（若数组下标从1开始）起始下标：6（ 1分），终止下标：8（ 1分）（若数组下标从0开始）起始下标：5（0.5分），终止下标：7 （0.5分）3. （ 11分）设有3件工作分配给3个人，将工作 i分配给第j个人所花的费用 为Cij ,现将为每一个人都分配1件不同的工作，并使总费用达到最小。设：823C2343 45要求:（1）画出该问题的解空间树；（6分）（2）写出该问题的剪枝策略（限界条件）；（1分）（2分）（3）按回溯法搜索解空间树，并利用剪枝策略对应该剪掉的子树打

4、（4）最终给出该问题的最优值和最优解。（2分） 答:（1）122dbdddd16169999XXXX231 2 1（每个分枝1分，或者是每层2分，共6分） 当耗费大于等于当前最优值时，剪枝。（1分）（3）见上图。（每2个X 1分，共2分）（4）最优值：9（1分）最优解：2， 1，3001 电11*14.（8分）给定两个序列X=<A,B,C,B,A>，Y=vB,D,C,A,B，请采用动态规划策略求出其最长公共子序列。要求给出过程。答:j 012345iyiBDCAB0 0 0 00Xi4 B 0112235 A 012223（上述表内每一行一分，共6分） 最长公共子序列为<B

5、, C, B> （2分）5. （2 分）考虑 n=3 时的 0-1 背包问题的实例：W=15,10,10 , P=50,30,30,c=20。当 x1=1，x2=0 时，请计算 Bound（2）。答：Bound（3）=50+5/10 * 20 = 65（2 分）三、算法填空题（共10分，每空2分）给定n种物品和一个背包，物品i的重量是wi,其价值是pi,背包的容量为c。设物品已按单位重量价值递减的次序排序。每种物品不可以装入背包多次，但可以装入部分的物品i。求解背包问题的贪心算法如下：float Knapsack （float x , float w , float p ,float c

6、, int n） float maxsum= ;/ maxsum表示装进包的物品价值总和for （ int i=1;i<=n; i+）xi=0 / xi=0 表示第 i 个物品未装进包for （ ）if（） xi =1;maxsum+= ;c- = wi;else break;if （c>0） xi=c/wi; ;return maxsum;答：（共5个空，每空2分，总计10分）0int i=1 ； i<=n ；i +wi<=Cpi maxsum+ = pi * c / wi四、算法设计及分析题（共45分）1. （20分）请用分治策略设计递归的二分检索算法，并分析其时间

7、复杂性（要求给出每个阶段所花的时间， 在此基础上列出递归方程， 并求出其解的渐进阶) 答：（此题解法不唯一）算法：int bsearch（A,K,L,H）（ 1 分） if （H<L） return（-1）;（2 分 ）else mid=（L+H） /2;（2 分 ）if （Amid = K）（1 分 ）return（mid） ；（1 分）else if （Amid>K ）（2 分）return（bsearch（A,K,L, mid-1） ;（2 分）else return（bsearch（K, mid+1,H）;（2 分）算法时间复杂性分析：（1分）（1分）（1分）（2分）（2分

8、） Divide阶段所花时间为0(1)Conquer 阶段所花时间为 T(n/2)merge 阶段没有花时间(或者说， merge 阶段所花时间为 0(1) 算法时间复杂性递归方程如下：T(n)=0(1)当 nW 0T(n)= T(n/2)+0 (1)当 n>1用套用公式法( master method )求解递归方程：a=1,b=2, nlogba nlog21 1f(n)=0(1),二 nlogba 与 f(n)同阶 T(n) = 0( log n) 2(15 分)请用回溯法设计算法，用四种颜色给地图着色(若在调用了其它算 法，也需将该算法写出) 。请在每个循环语句和条件判断语句后加

9、注释。 答：(此题解法不唯一)算法：boolColor:0k(int k) for (int j=1; jvk; j+)/检查前k-1个点与当前点(第k点)颜色是否冲突(2分) if (akj=1)&&(xj=xk)判断第j点与当前点(第k点)颜色是否冲突(2分)return false;(1 分 )else return true;(1 分 )void Color:Backtrack（int t）（1分） if （t > n） / 判断是否到叶节点 sum+;for （int i=1;i<=n; i+） / 输出每个点的色号cout << xi<

10、< ' 'cout << endl;elsefor （int i=1; i<=4; i+）/依次检查当前点（第 t点）是否可着第i（1 < i < 4）种颜色 xt=i;if （Ok（t） Backtrack（t+1）; /若当前点（第t点）可着第i种颜色，则递归调用2 分）（2分）（1 分 ）（3分）3（ 10 分） 请设计一个算法，实现优先队列的出队操作。要求：（2）用 C 语言描述算法。 答：（此题解法不唯一）（1）用堆实现优先队列。（2）算法 SIFT（k,i,m） temp = ki;j=2*i; while （j<=m） if （ j<m）&&2 分）（1分）（1分）Rj.key<Rj+1.key ）j+;（1分）（1）指出用什么数据