算法设计与分析补考试卷.docVIP

南昌大学 2009～2010学年第二学期补考试卷 试卷编号： (A )卷 课程编号： 课程名称： 算法设计与分析 考试形式： 闭卷 适用班级： 姓名： 学号： 班级： 学院： 专业： 考试日期： 题 号 一 二 三 总分 累分人 签 名 题 分 20 20 60 100 得 分 考生注意事项：1、本试卷共 5页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。 一、求解下列递推方程(每小题10分，共20分) 1．用生成函数法求解:  2．用公式解法求解递归方程的一个特解 二、递归算法应用题 (每小题10分，共20分) 1．将如下递归程序改成非递归程序： Procedure f(n:int) : int begin if n=0 then f:=1 Else if n=1 then f:=1 Else f:=f(n-1)*n endp; 2．写出如下程序的运行结果： procedure printRV(N:int) begin if N0 then begin write (N mod 10); printRV(N div 10); end; endp; 调用printRV(12345). 三、算法应用题（每小题15分，共60分） 1．求下面背包问题的最优解： 已知n=7,M=15,(p1,p2,p3,p4,p5,p6,p7)=(10,5,15,7,6,18,3),(w1,w2,w3,w4,w5,w6,w7)=(2,3,5,7,1,4,1) 2．用图解法给出分治方法求数组S={30，41，42，12，1，55，21，43}最大元素的过程。 3．设有一批排好顺序的数据存放在数组s[1..n]中，请设计数法求元素x。  4．设有n=5堆沙子，沙子堆的质量向量W=(13，7，8，16，21)，请画出将n堆沙子归并成一堆的最小代价树，并写出归并过程中的动态方程和求解过程。（规则：每次只能将相邻的两堆沙子堆成一堆，经过n-1次归并之后成为一堆，其总代价为进行过程中新产生的沙堆的质量之和。） 第4页 共5页