算法设计与分析试题(A).doc_第1页
算法设计与分析试题(A).doc_第2页
算法设计与分析试题(A).doc_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

2006级计算机专业20062007学年第二学期算法设计与分析期末试题 (A卷)一、 填空题(10题2分=20分)1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括（ ）和（ ）。2、对于函数，如果存在，使得当时有，就说是当时的（ ）。3、多项式的上界为（ ）。4、直接或间接地调用自身的算法称为（ ），用函数自身给出定义的函数称为（ ）。5、（ ）与（ ）是递归函数的两个要素。6、（ ）是问题能用动态规划算法求解的前提。7、贪心算法的两个基本要素是（ ）和（ ）。8、回溯法的含义是（ ）。9、回溯法中的解空间树结构通常有两种，分别是（ ）、（ ）。10、用分支限界法解布线问题时，对空间树搜索结束的标志是（ ）。二、判断题(10题2分=20分)1、如果g(N)=O(f(N)，则O(f)+O(g)=O(f)。2、所有的递归函数都能找到对应的非递归定义。3、动态规划算法中，通常不同子问题的个数随问题规模呈指数级增长。4、备忘录方法求解时采用与递归定义一致的自上而下的方式。5、用贪心算法解找零钱问题时，总能得到整体最优解。6、满足贪心选择性质必满足最优子结构性质。7、哈夫曼算法以自上而下的方式构造表示最优前缀码的二叉树T。8、回溯法中限界函数的目的是剪去得不到最优解的子树。9、每个优化问题都是由目标函数和约束条件组成。10、状态空间树中，只有展开了所有子结点的结点才称为死结点。三、简答题(6题5分=30分)1、简述分治法和动态规划算法的联系和区别。2、简述回溯法求解问题的一般步骤。3、简述回溯法和分支限界法的相同点和不同点。4、设序列和的最长公共子序列为。（1）分析该问题的最优子结构性质。（2）若用记录序列和的公共子序列长度，给出用动态规划法求解时子问题的递归公式。5、给出01背包问题的文字及数学描述，指出用回溯法求解时的解空间树结构，并分析该问题的约束条件和限界函数。6、简述什么是P类判定问题，什么是NP类判定问题。四、计算题(2题7分=14分)1、描述流水作业调度问题及其Johnson法则，应用该法则求解以下作业的调度次序，使得所有作业加工完成所需的时间最少，要求写出求解的方法步骤。已知：给定6个作业，其在第一台机器上加工所需时间分别为：，在第二台机器上加工所需时间分别为：。2、对给定的连通带权图，画出用Kruskal算法求最小生成树的选边过程。1623456245516643五、算法分析题(2题8分=16分)1、设个不同的整数按从小到大排好序后存于中。若存在下标，使得,请找到这个下标并输出，否则给出不存在的输出信息。要求：设计一个有效算法求解该问题，并且算法在最坏情况下的时间复杂度为。（注：假定若存在这样的下标，只需找到一个即可）。2、设有个顾客同时等待一项服务。顾客需要的服务时间为。应如何安排个顾客的服务次序使总的等待时间最小？总的等待时间是每个顾客等待服务时间（每个顾客等待服务时间是指：从到达目的地到服务完毕的时间
人人文库> 全部分类> 教育资料 > 考试试卷

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论