算法设计与分析考试题及答案要点.pdf
《算法设计与分析考试题及答案要点.pdf》由会员分享,可在线阅读,更多相关《算法设计与分析考试题及答案要点.pdf(14页珍藏版)》请在三一文库上搜索。
1、1. 一个算法就是一个有穷规则的集合, 其中之规则规定了解决某一特 殊类型问题的一系列运算,此外,算法还应具有以下五个重要特 性:_,_,_,_,_ 。 2. 算法的复杂性有 _ 和_ 之分,衡量一个算法 好坏的标准是 _ 。 3. 某 一 问 题 可 用 动 态 规 划 算 法 求 解 的 显 著 特 征 是 _ 。 4. 若序列 X=B,C,A,D,B,C,D ,Y=A,C,B,A,B,D,C,D,请给出序列 X 和 Y的一个最长公共子序列 _ 。 5. 用回溯法解问题时, 应明确定义问题的解空间, 问题的解空间至少 应包含_ 。 6. 动 态 规 划 算 法 的 基 本 思 想 是 将
2、待 求 解 问 题 分 解 成 若 干 _ ,先求解 _,然后从这些 _的 解得到原问题的解。 7. 以深度优先方式系统搜索问题解的算法称为_ 。 8.0-1 背包问题的回溯算法所需的计算时间为_,用动态 规划算法所需的计算时间为_ 。 9. 动态规划算法的两个基本要素是_ 和_。 10. 二分搜索算法是利用 _ 实现的算法。 二、综合题 (50分) 1. 写出设计动态规划算法的主要步骤。 2. 流水作业调度问题的johnson 算法的思想。 3. 若 n=4,在机器 M1和 M2上加工作业 i 所需的时间分别为ai和 bi, 且(a1,a2,a3,a4)=(4,5,12,10),(b1,b2
3、,b3,b4)=(8,2,15,9)求 4 个作业 的最优调度方案,并计算最优值。 4. 使用回溯法解 0/1 背包问题: n=3,C=9 ,V=6,10,3 ,W=3,4,4, 其解空间有长度为3 的 0-1 向量组成,要求用一棵完全二叉树表示其 解空间(从根出发,左1 右 0),并画出其解空间树,计算其最优值 及最优解。 5. 设 S= X1,X2, ,Xn是严格递增的有序集,利用二叉树的结点 来存储 S中的元素,在表示S的二叉搜索树中搜索一个元素X,返回 的结果有两种情形,(1)在二叉搜索树的内结点中找到X=Xi,其概率 为 bi。 (2)在二叉搜索树的叶结点中确定X(Xi,Xi+1)
4、,其概率为 ai。在表示 S的二叉搜索树 T中,设存储元素 Xi的结点深度为 Ci;叶 结点(Xi,Xi+1)的结点深度为 di,则二叉搜索树 T的平均路长 p 为多 少?假设二叉搜索树Tij=Xi,Xi+1, ,Xj最优值为 mij, Wij= ai-1+bi+ +bj+aj,则 mij(1=bi ;将 N1中作业按 ai的非减序排 序得到 N1 ,将 N2中作业按 bi的非增序排序得到N2 ;N1中作业 接 N2中作业就构成了满足Johnson 法则的最优调度。 3. 步骤为: N1=1,3 ,N2=2,4; N1=1,3 , N2=4,2; 最优值为: 38 4. 解空间为 (0,0,0
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 分析 考试题 答案 要点
链接地址:https://www.31doc.com/p-5229398.html