算法设计与分析补考试卷

南昌大学20092010学年第二学期补考试卷试卷编号：（A卷课程编号：课程名称：算法设计与分析考试形式:闭卷适用班级： 姓名： 学号： 班级： 学院：专业：考试日期：题号一二三总分累分人题分202060100签名得分考生注意事项：1、本试卷共_5页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、求解下列递推方程（每小题10分，共20分）” T （1）二 11用生成函数法求解：< 丫（n）二2T （n - 1） + 1 （n > 2）2.写出如下程序的运行结果:procedure printRV(N:int) beginf N>0 thenbeginwrite (N mod 10); printRV(N div 10); end;endp;调用 printRV(12345).三、算法应用题(每小题15分，共60分)1 求下面非0/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)4.设有n=5堆沙子，沙子堆的质量向量W=(13, 7, 8, 16, 21),请画出将n堆 沙子归并成一堆的最小代价树，并写出归并过程中的动态方程和求解过程。(规则：每 次只能将相邻的两堆沙子堆成一堆，经过n-1次归并之后成为一堆，其总代价为进行 过程中新产生的沙堆的质量之和。)