算法设计与分析2009-2010_1(B卷)

试卷编号： ( B )卷 课程编号： 课程名称： 算法设计与分析 考试形式： 闭卷 适用班级： 姓名： 学号： 班级： 学院： 专业： 考试日期： 题 号 题 分 得 分 考生注意事项：1、本试卷共 5 页，查看试卷中是否有缺页或破损。如有立即举手报告以便更换。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。 一 20 二 20 三 60 总 分 100 累分人 签 名 南昌大学 2009～2010学年第一学期期末考试试卷

一、求解下列递推方程(每题10分，共20分) 得分 评阅人 (1)用生成函数法求解： T(1)1 n2 T(n)T(n1)2 第 1 页 共 5页

T(n)4T(n1)4T(n2)2n（2）用公式法求解： T(0)0,T(1)1 二、将如下递归程序改成非递归程序 (每小题10分，共20分) 得分 评阅人 (1)Function f(n:int) : int begin if n=0 then f:=0； Else if n=1 then f:=1； Else f:=f(n-1)+f(n-2)； endp;

第 2 页 共 5页

(2)Procedure p(int k) begin if (k>0) then begin P(k-1)； write(k)； end； endp； 三、算法应用题（每小题12分，共60分） 得分 评阅人 （1）令n=5，(p1,p2,p3,p4,p5)=(20,15,10,5,1)和(d1,d2,d3,d4,d5)=(2,2,1,3,3)，按照教材第二章有限期的计算机作业调度算法，其最终的最优作业调度是什么？

第 3 页 共 5页

（2）设w={5,10,12,13,15,18}和m=30，使用回溯法找出w中使得和数等于m的全部子集，并画出所生成的部分状态空间树。 （3）设有n=5堆沙子，沙子堆的质量向量W=(8，16，21，4，18)，请画出将n堆沙子归并成一堆的最小代价树，并写出归并过程中的动态方程和求解过程。（规则：每次只能将相邻的两堆沙子堆成一堆，经过n-1次归并之后成为一堆，其总代价为进行过程中新产生的沙堆的质量之和。） 第 4 页 共 5页

（4）若有4项任务J1、J2、J3、J4要先后使用机器M1、M2，使用机器M1、M2的时间见下表： M1 M2 求任务的最佳安排。 J1 3 6 J2 4 2 J3 8 9 J4 10 15 （5）有n=2块金币，其中混了一枚假币，真币质量相同，假币比真币轻。要求用一天平将假币找出来，请设计一种算法，并求出该算法使用天平的最多、最少和平均次数。 k

第 5 页 共 5页