《计算机算法基础》试题及答案「」_第1页
《计算机算法基础》试题及答案「」_第2页
《计算机算法基础》试题及答案「」_第3页
全文预览已结束

下载本文档

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

文档简介

《计算机算法根底》试题及答案「完整版」142、算法的时间复杂性是指需要时间的量，它依赖于求解问题的要解的问题的规模、算法的输入、算法本身的函数。4、选择算法的一个重要准那么是复杂性最低。5、一个直接或间接地调用身的算法称为递归算法，一个使用函数自身定义的函数称为递归函数，每个递归函数都必须有非递归定的的初始值。6、关于N个字符的哈夫曼算法的计算时间为O（nlogn）。7、回溯法解题时常遇到的两类典型解空间树是：a：排列树、b：子集树，假设问题有N个元素，其中树通常有a2?个叶结点，其结点总个数为n！2^(n+1)-1，遍历它的任何算法均需Ω（n！）Ω（2?）的计算时间。8、一个问题能用动态规划算法求解的两个重要特征是最优子构造和计算重要性。9、回溯法是一个既带有系统性又带有跳跃性的搜索算法。它按照深度优先用约束函数在扩展结点处剪去不满足约束的子树、用限界函数剪去不能得到最优解的子树优先的策略对空间树进展搜索，通常采用如下两种策略来防止无效搜索，提高回溯法的搜索效，其一是剪枝函数，其二是递归回溯，这两类函数统称为选代回溯。10、分支限界法最常见的两种方式分别是队列式（FIFO）分支限界法和优先队列式分支限界法。11、概率算法的一个根本特征是对所求解问题的同一实例用同一概率算法，求解两次可能得到完全不同的效果。1、贪心算法的核心是排序（×）2、贪心算法对所有问题都能得到整体最优解（√）3、0/1背包问题和背包问题都可以用贪心法求解（×）4、概率算法在执行过程中每一计算步骤都是确定的（×）1、为什么分治法与递归像一对孪生兄弟，经常同时应用在算法设计中？52、表达回溯法解题通常的三个步骤。①针对所给问题，定义问题的解空间②确定易于搜索的解空间构造33、表达回溯法与分支限界算法的异同之处。都是在问题的状态空间树上搜索解，但求解目标不同；回溯法只通过约束条件，而分支限界法不仅通过约束条件，而且通过目标函数的限界来减少无效搜索，回溯法采用深度优先策略，而分支限界法采用先广后深的策略。4、表达分支限界算法的分支和限界的涵意。分支：剪去不何能产生最优答案结点限界：包括上界函数U和下界函数所有C*(X)>U5、解释什么是活结点，扩展结点，死结点？活结点：被激活后还未完全生成其儿子结点的结点扩展结点：当前正在生成其儿子结点的结点死结点：已生成完其儿子结点的结点6、说出优先队列式分支限界法解题的详细步骤。①针对所给问题，定义问题的解空间②定义上界和下界③以先广后深的方式搜索状态空间树，并且在搜索过程中用剪枝函数防止无效搜索7型。求解的例子（不必写出每种详细解法过程）。分治法、动态规划、贪心法、回溯法、分支限界法（1，1，0，0，1）、（1，0，1，1）、（0，0，1，0，0，1）分别对应于：5+10+15=305+12+13=3012+18=30实际生成

人人文库> 全部分类> 应用文书 > 项目管理

温馨提示

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

最新文档

评论

0/150

提交评论