版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、计算机算法设计与分析期末考试复习题1、二分搜索算法是利用()实现的算法。 A、分治策略(正确答案)B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是()。 A、找出最优解的性质(正确答案)B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是()的一搜索方式。 A、分支界限法(正确答案)B、动态规划法C、贪心法D、回溯法4、最长公共子序列算法利用的算法是()。 A、分支界限法B、动态规划法(正确答案)C、贪心法D、回溯法5. 回溯法解TSP问题时的解空间树是()。 A、子集树(正确答案)B、排列树C、深度优先生成树D、广度优先生成树6下列算法中通常以自底向上的方式求解
2、最优解的是()。 A、备忘录法B、动态规划法(正确答案)C、贪心法D、回溯法7、衡量一个算法好坏的标准是()。 A 运行速度快B 占用空间少C 时间复杂度低(正确答案)D 代码短8、以下不可以使用分治法求解的是()。 A 棋盘覆盖问题B 选择问题C 归并排序D 0/1背包问题(正确答案)9. 实现循环赛日程表利用的算法是()。 A、分治策略(正确答案)B、动态规划法C、贪心法D、回溯法10、实现最长公共子序列利用的算法是()。 A、分治策略B、动态规划法(正确答案)C、贪心法D、回溯法11下面不是分支界限法搜索方式的是()。 A、广度优先B、最小耗费优先C、最大效益优先D、深度优先(正确答案)
3、12下列算法中通常以深度优先方式系统搜索问题解的是()。 A、备忘录法B、动态规划法C、贪心法D、回溯法(正确答案)13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的 ( B )。(正确答案)A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14广度优先是()的一搜索方式。 A、分支界限法(正确答案)B、动态规划法C、贪心法D、回溯法15背包问题的贪心算法所需的计算时间为()。 A、O(n2)B、O(nlogn)(正确答案)C、O(2)D、O(n)16实现最大子段和利用的算法是()。 A、分治策略B、动态规划法(正确答案)C、贪心法D、回溯法17实现棋盘覆盖算法
4、利用的算法是()。 A、分治法(正确答案)B、动态规划法C、贪心法D、回溯法18.下面是贪心算法的基本要素的是()。 A、重叠子问题B、构造最优解C、贪心选择性质(正确答案)D、定义最优解19.回溯法的效率不依赖于下列哪些因素() A.满足显约束的值的个数B. 计算约束函数的时间C. 计算限界函数的时间D. 确定解空间的时间(正确答案)20.下面哪种函数是回溯法中为避免无效搜索采取的策略() A递归函数B.剪枝函数(正确答案)C。随机数函数D.搜索函数21、以深度优先方式系统搜索问题解的算法称为 () 。 A、分支界限算法B、概率算法C、贪心算法D、回溯算法(正确答案)22、贪心算法与动态规划
5、算法的主要区别是()。 A、最优子结构B、贪心选择性质(正确答案)C、构造最优解D、定义最优解23. 采用最大效益优先搜索方式的算法是()。 A、分支界限法(正确答案)B、动态规划法C、贪心法D、回溯法24. ()是贪心算法与动态规划算法的共同点。 A、重叠子问题B、构造最优解C、贪心选择性质D、最优子结构性质(正确答案)25. 矩阵连乘问题的算法可由()设计实现。 A、分支界限算法B、动态规划算法(正确答案)C、贪心算法D、回溯算法26. 0-1背包问题的回溯算法所需的计算时间为() A、O(n2n)(正确答案)B、O(nlogn)C、O(2n)D、O(n)27、背包问题的贪心算法所需的计算
6、时间为() A、O(n2)B、O(nlogn)(正确答案)C、O(2)D、O(n)29、使用分治法求解不需要满足的条件是()。 A 子问题必须是一样的(正确答案)B 子问题不能够重复C 子问题的解可以合并D 原问题和子问题使30、下面问题()不能使用贪心法解决。 A 单源最短路径问题B N皇后问题(正确答案)C 最小花费生成树问题D 背包问题31、下列算法中不能解决0/1背包问题的是() A 贪心法(正确答案)B 动态规划C 回溯法D 分支限界法32、回溯法搜索状态空间树是按照()的顺序。 A 中序遍历B 广度优先遍历C 深度优先遍历(正确答案)D 层次优先遍历33、采用广度优先策略搜索的算法
7、是()。 A、分支界限法(正确答案)B、动态规划法C、贪心法D、回溯法34实现合并排序利用的算法是()。 A、分治策略(正确答案)B、动态规划法C、贪心法D、回溯法35下列是动态规划算法基本要素的是()。 A、定义最优解B、构造最优解C、算出最优解D、子问题重叠性质(正确答案)36下列算法中通常以自底向下的方式求解最优解的是()。 A、分治法B、动态规划法(正确答案)C、贪心法D、回溯法二、 填空题1.算法的复杂性有 _ 复杂性和 _ 复杂性之分。 空1答案:时间空2答案:空间2、程序是 _ 用某种程序设计语言的具体实现。 空1答案:算法3、算法的“确定性”指的是组成算法的每条 _ 是清晰的,
8、无歧义的。 空1答案:指令4.矩阵连乘问题的算法可由 _ 设计实现。 空1答案:动态规划5、算法是指解决问题的 _ 或 _ 。 空1答案:一种方法空2答案:一个过程6、快速排序算法的性能取决于 _ 。 空1答案:划分的对称性7、从分治法的一般设计模式可以看出,用它设计出的程序一般是 _ 。 空1答案:递归算法8、问题的 _ 是该问题可用动态规划算法或贪心算法求解的关键特征。 空1答案:最优子结构性质9、以深度优先方式系统搜索问题解的算法称为 _ 。 空1答案:回溯法10、任何可用计算机求解的问题所需的时间都与其 _ 有关。 空1答案:规模11、计算一个算法时间复杂度通常可以计算 循环次数 、
9、_ 或计算步。 空1答案:基本操作的频率12、回溯法搜索解空间树时,常用的两种剪枝函数为 _ 和 限界函数 空1答案:约束函数14、解决0/1背包问题可以使用动态规划、回溯法和分支限界法,其中不需要排序的是 _ ,需要排序的是 _ ,_ 。 空1答案:动态规划法空2答案:回溯法空3答案:分支限界法15、使用回溯法进行状态空间树裁剪分支时一般有两个标准:约束条件和目标函数的界,N 皇后问题和0/1背包问题正好是两种不同的类型,其中同时使用约束条件和目标函数的界进(正确答案)行裁剪的是 0/1背包问题 ,只使用约束条件进行裁剪的是 N皇后问题 。17、回溯法是一种既带有 _ 又带有 _ 的搜索算法。 空1答案:系统性空2答案:跳跃性18. 动态规划算法的两个基本要素是. 最优子结构性质和 _ 性质 空1答案:重叠子问题19.贪心算法的基本要素是 _性质和 _ 性质 。 空1答案:贪心选择空2答案:最优子结构21. 动态规划算法的基本思想是将待求解问题分解成若干 _ ,先求解 _ ,然后从这些 _ 的解得到原问题的解。 空1答案:子问题空2答案:子问题空
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 建筑制图课程设计作品
- 卫生间漏水维修协议书
- 化工基础课程设计 大纲
- 立式停车场课程设计
- 皮尔斯振荡器课程设计
- 数字称量勺市场环境与对策分析
- 空气监测课程设计稿
- 氢氧燃烧器项目评价分析报告
- 拆除平房施工方案
- 七年级语文老师在家长会上的发言稿
- 视光中心眼部健康记录册
- 2022江西上饶经济技术开发区招商集团限公司招聘29人上岸笔试历年难、易错点考题附带参考答案与详解
- 大棚钢管下沉施工方案
- CA6140车床控制线路原理详解
- 小学奥数-行程问题三省名师优质课赛课获奖课件市赛课一等奖课件
- 落实立德树人根本任务构建协同育人新格局建设方案
- 高中英语-Natural Disasters教学课件设计
- 郦道元《水经注·序》原文翻译注释与鉴赏
- 高中体育与健康-足球-运球过人教学课件设计
- 北师大版七年级上册生物教学课件 第4章 生物体的结构层次 第1节 细胞分化形成组织
- 对白:文字、舞台、银幕的言语行为艺术
评论
0/150
提交评论