算法设计与分析2009-2010 1(B卷).doc

算法设计与分析2009-2010_1(B卷)南昌大学 2009~2010学年第一学期期末考试试卷

试卷编号: ( B )卷
课程编号: 课程名称: 算法设计与分析考试形式: 闭卷
适用班级: 姓名: 学号: 班级:
学院: 专业: 考试日期:
题号
一
二
三
总分
累分人
签名
题分
20
20
60
100
得分
考生注意事项:1、本试卷共 5 页,查看试卷中是否有缺页或破损。如有立即举手报告以便更换。
2、考试结束后,考生不得将试卷、答题纸和草稿纸带出考场。
一、求解下列递推方程(每题10分,共20分)
得分
评阅人

(1)用生成函数法求解:

(2)用公式法求解:
二、将如下递归程序改成非递归程序(每小题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)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),按照教材第二章有限期的计算机作业调度算法,其最终的最优作业调度是什么?
(2)设w={5,10,12,13,15,18}和m=30,使用回溯法找出w中使得和数等于m的全部子集,并画出所生成的部分状态空间树。