《算法设计与分析2009--1(b卷)》由会员分享，可在线阅读，更多相关《算法设计与分析2009--1(b卷)（12页珍藏版）》请在装配图网上搜索。
1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date算法设计与分析2009-2010-1(B卷)南昌大学 / 学年第 学期考试试卷南昌大学 20092010学年第一学期期末考试试卷 试卷编号： ( B )卷课程编号： 课程名称： 算法设计与分析 考试形式： 闭卷 适用班级： 姓名： 学号： 班级： 学院： 专业： 考试日期： 题 号一二三总 分累分人签 名题 分202060 100得 分考生注意事项：1、本试卷共 5
2、页，查看试卷中是否有缺页或破损。如有立即举手报告以便更换。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、求解下列递推方程(每题10分，共20分)得分评阅人 (1)用生成函数法求解： -（2）用公式法求解：二、将如下递归程序改成非递归程序 (每小题10分，共20分)得分评阅人 (1)Function f(n:int) : intbegin 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 (k0) then begin P(k-1)； w
3、rite(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的全部子集，并画出所生成的部分状态空间树。（3）设有n=5堆沙子，沙子堆的质量向量W=(8，16，21，4，18)，请画出将n堆沙子归并成一堆的最小代价树，并写出归并过程中的动态方程和求解过程。（规则：每次只能将相邻的两堆沙子堆成一堆，经过n-1次归并之后成为一堆，其总代价为进行过程中新产生的沙堆的质量之和。）（4）若有4项任务J1、J2、J3、J4要先后使用机器M1、M2，使用机器M1、M2的时间见下表：J1J2J3J4M134810M262915求任务的最佳安排。（5）有n=2k块金币，其中混了一枚假币，真币质量相同，假币比真币轻。要求用一天平将假币找出来，请设计一种算法，并求出该算法使用天平的最多、最少和平均次数。
算法设计与分析2009--1(b卷)
