算法设计与分析复习考试exam_第1页
算法设计与分析复习考试exam_第2页
全文预览已结束

下载本文档

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

文档简介

1、一、 （20）判断请在正确的陈述前面括号中打，在错误的陈述前面括号中F）回溯法用深度优先或广度优先法搜索状态空间树（ T）O(f(n)+O(g(n) = （F）f(n)=（F）已知团问题（Cliqueproblem）为NP题，那么下列问题是一个判定问题：给定一个图 G，求G 中最大团的尺寸（size）K。（F）随机化快速排序的worstcase现于输入数组恰好为已按非（T）基于比较的排序问题的下界是(nlogn（ F）所有问题当中最难的一组问题被称为NP 完备 （F）P和NP问题的关系用PNP来表示是错误T）动态规划算法通过增加空间复杂性来降低时间复杂性二、 （30）简答题当n3求解 TSP

2、问题的最近邻居算法的性能比是多少？这一性能比是请给出基于比较的寻找数组A1n中最大和最小元素问题的最紧的下界，并说明这个下界是用了课上介绍的哪种或哪几种寻找3n/2-函数f(n)跟在g(n)的后面则说明应该满足g(n)是（f(n)：f (n) 10nf (n) n1/3 f (n) nnf4 (n) 2 logc nf5 (n) log策略和树中各节点代表的状态（化简的 CNF 形式。 三、 （15）设计一求解以下问题的分治算法，写出伪代码，分去的某天开始对一支给定的连续 n天（这些天数记为 i 1,2,.n 对每天 i，有当天这只每股的价格 p(i)（为简单起见，假设这个价格在每一天之内是固

3、定的。 假设在这 n 天内，举例说，假设 n=4，p(1)=4，p(2)=1，p(3)=1.5，p(4)=3，那么你的算法应该返回“24（在第2天买并且在第4天卖意味着每股将挣 2 ，是这个期间最大的收益。 四、 （15 分）写出用动态规划方法求两个序列的最长公共子序列下A 和B 的最长公共子序列：五、 （15 分）设计一求解以下问题的贪心算法，写出伪代码，并给定m台机器M1 M 2 Mm 和n项作业，要把每一项作配给一台机器来完每一项作业 j有处理时间t j . 若 A(i)表示分配给机Mi的作业集，则Mi需要工作的总时间（亦称Mi的负载）为Ti t 完成n项作业的工期T为所有机器的最大负载，即 T maxi要求找到一种分配方案，使得完成这 n 项作业的工期例如，下图即为将处理时间分别为 2，3，7，4，2，2 的六项作业分配给三台机器的一种分配方案，其中M 1 的负载最大，为 9，则该方案完成这六项作业的工期为 9。273273242对各作业处理时间进行排序，安排时间最长的作业先执行。时间复杂度为O（nlogn。六、

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论