2011.2算法设计与分析试题A答案

山东理工大学山东理工大学 算法设计与分析算法设计与分析 参考答案及评分标准参考答案及评分标准 A 卷 10 11 学年第 一学期 班级 姓名 学号 装 订 线 适用专业07 计算机科学 1 4考核性质考试开 卷命题教师石少俭考试时间100 分钟 题号一二三四五六七八九十十一总分 得分 评阅人 复核人 一 简答题 每题 5 分 共 20 分 1 程序的时间复杂性和空间复杂性 算法的复杂性是算法运行所需要的计算机资源的量 需要时间资源的量称为时间复杂性 需要空间资源的量称为空间复 杂性 2 回溯法与分支限界法的区别 两者都是问题的解空间树上搜索问题解的算法 回溯法与分支限界法的的求解目标不同 回溯法的求解目标是找出解 空间树中满足约束条件的所有解 而分支限界法的求解目标是找出解空间树中满足约束条件的一个解 或是在满足约束条 件的 解中找出使某一目标函数值达到极大或极小的解 即在某种意义下的最优解 3 写出 3 个 NP 完全问题 团问题 子集和问题 旅行售货员问题 4 概率算法特征 对所求问题的同一实例用同一概率算法求解两次可能得到完全不同的效果 二 解下列递推方程 10 分 T n 1 n 1 T n 3T n 3 n 3 log3 n 3 n 1 T n 3T n 3 n 3 log3 n 3 3 3T n 32 n 3 log3 n 3 n 3 log3 n 32 32T n 32 n 3 log3 n 3 log3 n 32 3kT n 3k n 3 log3 n 3 log3 n 32 log3 n 3k 3kT n 3k n 3 log3 nk 3k k 1 2 n 3k n n 3 k 1 2 log3n O n log23n 三 实例题 每题 10 分 共 40 分 1 货物装箱问题 设有一艘货船装物品 共有 n 6 件物品 它们的重量如下表示 w1 w6 100 200 50 90 50 20 船的限载重量是 c 300 试用贪心算法装船 要求物品装得最多 贪心准则 从剩下的货箱中选择重量最小的货箱 设 xi 1 表示第 i 件物品装船 xi 0 表示第 i 件物品不装船 则贪心算法如下 1 x6 1 船的限载重量 c 300 20 280 2 x3 1 船的限载重量 c 280 50 230 3 x5 1 船的限载重量 c 230 50 180 4 x4 1 船的限载重量 c 180 90 90 解为 0 0 1 1 1 1 2 给出一个赋权无向图如下 求顶点 S 到 T 的最短路 6 6586 3775 S T 368 6 49 共共 4 4 页页 第第 1 1 页页 山东理工大学山东理工大学 算法设计与分析算法设计与分析 答案答案 装 订 线 3 用分治算法计算 123 789 令 X 123 Y 789 则把 X Y 分为两段得 X 1 102 23 Y 7 102 89 记 A 1 B 23 C 7 D 89 则由大整数乘法得公式得 X Y AC104 A B D C AC BD 102 BD 1 23 104 22 82 1 23 23 89 102 23 89 97047 4 0 1 背包问题 n 4 w 2 4 6 7 p 6 10 12 13 c 11 使用回溯法的求解过程为 由以上解空间树得知 当 X 1 1 1 1 时 w 19 11 因此 X 1 1 1 1 不是一个可行解 当 X 1 1 1 0 时 w 12 11 因此 X 1 1 1 0 不是一个可行解 当 X 1 1 0 1 时 w 13 11 因此 X 1 1 0 1 不是一个可行解 当 X 1 1 0 0 时 w 611 因此 X 1 0 1 1 不是一个可行解当 X 1 0 1 0 时 w 8 11 因此 X 1 0 1 0 是一个可行解 P 18 当 X 1 0 0 1 时 w 9 11 因此 X 1 0 0 1 是一个可行解 P 19 当 X 1 0 0 0 时 w 211 因此 X 0 1 1 1 不是一个可行解 当 X 0 1 1 0 时 w 10 11 因此 X 0 1 1 0 是一个可行解 P 22 当 X 0 1 0 1 时 w 11 11 因此 X 0 1 0 1 是一个可行解 P 23 当 X 0 1 0 0 时 w 411 因此 X 0 0 1 1 不是一个可行解 当 X 0 0 1 0 时 w 6 11 因此 X 0 0 1 0 是一个可行解 P 12 当 X 0 0 0 1 时 w 7 11 因此 X 0 0 0 1 是一个可行解 P 13 当 X 0 0 0 0 时 w 0 11 因此 X 0 0 0 0 是一个可行解 P 0 因此 X 0 1 0 1 问题的一个最优解 即不装入物品 1 装入物品 2 不装入物品 3 装入物品 4 其最优值 为 23 共共 4 4 页页 第第 2 2 页页 山东理工大学山东理工大学 算法设计与分析算法设计与分析 答案答案 装 订 线 共共 4 4 页页 第第 3 3 页页 山东理工大学山东理工大学 算法设计与分析算法设计与分析 试卷纸试卷纸 四 编程题 每题 15 分 共 30 分 1 一个人有一捆草 一只羊 一头老虎 他想把草 羊 老虎运过河 但是老虎要吃羊 羊要吃草 他要羊不吃草 虎不羊 完整运过去 请问他应怎样运 人 羊 人回来 人 草 人 羊 人 虎 人 人 羊 3 求矩阵连乘 A1 A2 A3 A4 A5的最优计算次序 各矩阵阶数依次为 30 35 35 5 5 10 10 20 20 30 M 1 2 30 35 5 5250 m 2 3 10 20 30 6000 M 3 4 5 10 20 1000 m 4 5 10 20 30 6000 M 1 5 min m 1 k m k 1 5 P1PkP5 13750 K 1 m 1 1 m 2 5 30 35 30 9250 31500 K 2 m 1 2 m 3 5 30 5 30 5250 4000 4500 13750 K 3 m 1 3 m 4 5 30 10 30 21750 K 4 m 1 4 m 5 5 30 20 30 27250 M 2 5 min m 2 k m k 1 5 P2PkP5 9250 K 2 m 2 2 m 3 5 35 5 30 9250 K 3 m 2 3 m 4 5 35 10 30 1750 6000 10500 K 4 m 2 4 m 5 5 35 20 30 4500 21000 M 3 5 min m 3 k m k 1 5 P3PkP5 4000 K 3 m 3 3 m 4 5 5 10 30 6000 1500 7500 K 4 m 3 4 m 5 5 5 20 30 4000 M 1 4 min m 1 k m k 1 4 P1PkP4 9250 K 1 m 1 1 m 2 4 30 35 20 4500 21000 K 2 m 1 2 m 3 4 30 5 20 9250 K 3 m 1 3 m 4 4 30 10 20 12750 M 1 3 min m 1 k m k 1 3 P1PkP3 6750 K 1 m 1 1 m 2 3 30 35 10 12500 K 2 m 1 2 m 3 3 30 5 10 6750 M 2 4 min m 2 k m k 1 4 P2PkP4 4500 K 2 m 2 2 m 3 4 35 5 20 4500 K 3 m 2 3 m 4 4 35 10 20 8750 最优解为 12 34 5 最优值为 13750 装 订 线 3 二维 0 1 背包问题 n 件物品装船 已知物品 i 的重量为 wi 体积为 hi 价值为 vi 船舱的体积为 H 限重 W 试用动态 规划编程 求选择那些物品装船 可使得装入物品的总价值最大 1 1 templatetemplate classType 2 2 TypeType knapsack dynamic intknapsack dynamic int w Typew Type p intp int n intn int m BOOLm BOOL x x 3 3 intint i j k i j k 5 5 TypeType v optp m 1 v optp m 1 newnew Type n 1 m 1 Type n 1 m 1 分配工作单元分配工作单元 6 6 forfor i 0 i n i i 0 i n i 初始化第初始化第 0 0 列列 7 7 optp i 0 optp i 0 0 0 x i x i FALSE FALSE 解向量初始化为解向量初始化为 FALSEFALSE 8 8 9 9 forfor i 0 i m i i 0 i m i 初始化第初始化第 0 0 行行 10 10 optp 0 i optp 0 i 0 0 11 11 forfor i 1 i n i i 1 i n i 计算计算 optp i j optp i j 12 12 forfor j 1 j m j j 1 j w i optp i 1 j w i p i 16 16 17 17 18 18 j j m m 递推装入背包的物体递推装入背包的物体 19 19 forfor i n i 0 i i n i 0 i 20 20 ifif optp i j op