算法设计与分析复习题_第1页
算法设计与分析复习题_第2页
算法设计与分析复习题_第3页
算法设计与分析复习题_第4页
全文预览已结束

下载本文档

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

文档简介

1、精选优质文档-倾情为你奉上算法设计与分析复习题1、分治法的基本思想:是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题互相独立且与原问题相同。递归地解这些子问题,然后将各子问题的解合并得到原问题的解。2、贪心选择性质:指所求问题的整体最优解可以通过一系列局部最优的选择,3、什么是剪枝函数:回溯法搜索解空间树时,通常采用两种策略避免无效搜索,提高回溯法的搜索效率。其一是用约束函数在扩展结点处剪去不满足约束的子树;其二是用限界函数剪去得不到最优解的子树。这两类函数统称为剪枝函数。4、分支限界法的基本思想:(1)分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。(

2、2)在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。(3)此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程,这个过程一直持续到找到所需的解或活结点表这空时为止。5、什么是算法的复杂性:是该算法所需要的计算机资源的多少,它包括时间和空间资源。6、最优子结构性质:该问题的最优解包含着其子问题的最优解。7、回溯法:是一个既带有系统性又带有跳跃性的搜索算法。这在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空

3、间树的任一结点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对以该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。8、什么是分支定界法:对有约束条件的最优化问题所有可行解定向、适当地进行搜索。将可行解空间不断地划分为越来越小的子集(分支),并为每一个子集的解计算一个上界和下界(定界)。9、算法满足的性质:输入、输出、确定性、有限性。10、递归算法的优点:结构清晰,可读性强,容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序带来很大方便。11、回溯法效率的因素:(1)产生xk的时间。(2)满足显约束的xk值的个数。(3)计算约束函数co

4、nstraint的时间。 (4)计算上界函数bound的时间。(5)满足约束函数和上界函数约束的所有xk的个数12、最常见的分支限界法有两种:队列式(FIFO)分支限界法和优先队列式分支限界法。13、 什么是算法, 算法具有的特性是什么?是解决问题的方法和过程, 1) 输入0个或多个信息 2) 输出至少一个信息 3) 确定性:组成算法的每个指令是清晰的,无二义的,整个过程是确定的 4) 有限性:14、 什么是动态规划法:将问题分解成多级或许多子问题,然后顺序求解子问题,前一个子问题的解为后一个子问题的求解提供有用的信息。15、 什么是贪心法:从问题某一初始或推测值出发,一步步的攀登给定目标,尽

5、可能快的去逼近更好的解,当达到某一步不能继续时终止。16、递归算法的缺点:运行效率较低,耗费的计算时间和占用的存储空间都多。为了达到此目的,根据具体程序的特点对递归调用工作栈进行简化,尽量减少栈操作,压缩栈存储空间以达到节省计算时间和存储空间的目的。17、合并排序的时间复杂度是:T(n)=O(nlogn)。18、快速排序的时间复杂度是:T(n)=O(nlogn)。19、动态规划算法的基本要素:最优子结构性质和子问题重叠性质。20、贪心算法的基本要素:贪心选择性质和最优子结构性质。选择题1、二分搜索算法是利用(分治策略 )实现的算法。A、分治策略 B、动态规划法 C、贪心法 D、回溯法2、下列不

6、是动态规划算法基本步骤的是(D )。A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解3、下列算法中通常以深度优先方式系统搜索问题解的是(c )。A、备忘录法 B、动态规划法 C、贪心法 D、回溯法4、最大效益优先是(C )的搜索方式。A、分支界限法 B、动态规划法 C、贪心法 D、回溯法5、0-1背包问题的回溯算法所需的计算时间为( b)O(n2n) B、O(nlogn) C、O(2n) D、O(n)简答题1、写出设计流水作业调度算法的主要步骤。2、举例说明贪心算法与动态规划算法的的主要差别。3、写出用回溯法搜索子集树的一般算法。4、简述利用贪心算法解决“单源最短路径”问题

7、的基本思想。5、简述分治法的基本思想。6、写出设计动态规划算法的主要步骤。7、简述分支限界法与回溯法的异同。8、写出用回溯法搜索排列树的算法。算法题:01背包问题:给定n种物品和一背包,物品i的重量是wi,其价值为vi,背包的容量为C。问应该如何装入背包中物品的总价值最大?写出用分支限界算法解决该问题的算法。例题1.选择范例(1)分支限界法与回溯法都是在问题的解空间树T上搜索问题的解,二者()。A求解目标不同,搜索方式相同B求解目标不同,搜索方式也不同C求解目标相同,搜索方式不同D求解目标相同,搜索方式也相同(2)下列是动态规划算法基本要素的是( )。A、最优子结构 B、构造最优解 C、算出最

8、优解 D、定义最优解(3)Strassen矩阵乘法是利用( )实现的算法。A、分治策略 B、动态规划法 C、贪心法 D、回溯法(4)下面不是分支界限法搜索方式的是( )。A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先2.判断范例(1)所有的递归函数都能找到对应的非递归定义。(2)满足最优子结构性质必满足贪心选择性质。(3)满足贪心选择性质必满足最优子结构性质。(4)状态空间树中,只有展开了所有子结点的结点才称为死结点。(5)变治法是基于变换的思想。分两个阶段工作,即“变”阶段和“治”阶段.变治法的三种类型:1)实例化简(instance simplification)2)改变表

9、现(representation change)3)问题化简(problem reduction)。例如AVL树,多路查找树都是实例化简的具体应用。(6)时空权衡是指在算法的设计中,对算法的时间和空间作出权衡。常见的以空间换取时间的方法有:输入增强(计数排序,串匹配算法的改进)预构造(散列法,B树) (7)动态规划算法基本思想是将待求解问题分解成若干个子问题,并且经分解得到的子问题是互相独立的。求解时有些子问题被重复计算了许多次。2解释下面术语哈密尔顿环贪心算法分枝限界方法0/1背包问题算法3.简答范例简述回溯法求解问题的一般步骤。简述状态空间树的广度优先展开方法。状态空间树中的活结点、E-结

10、点、死结点简述用回溯法设计算法的步骤。举例说明最小生成树在实际中的应用。4.分析设计题上课反复讲、反复强调的几个问题,要求懂原理,会设计(关键是思路,表达方法可以是语言、伪代码、代码),会进行复杂度分析。建议:答题时不要把所有的东西写一大段,适当分步骤、分要点,如XXX算法原理做什么,怎么做做什么,怎么做做什么,怎么做等8. 以下是分数背包问题的贪心算法算法 GREEDY_KANPSACK输入:表示背包容量的实数C, 物品数n, 表示n个物品的体积和价值的实数数组s1.n和v1.n。输出:装入背包物品的最大总价值maxv和相应的最优解x1.n。 for i=1 to n yi=vi/si /求n个物品的单位体积价值y1.n。 end for /对y1.n按降序地址排序,排序结果返回到数组d1.n /中, 使得yd1=yd2=ydn。 d=sort(y, n) for i=1 to n xi=0 /对x1.n初始化。 i=1; maxv=0; rc=C /以下rc表示当前背包的剩余容量。while _ and i=nj

温馨提示

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

评论

0/150

提交评论