算法分析与设计习题课.ppt_第1页
算法分析与设计习题课.ppt_第2页
算法分析与设计习题课.ppt_第3页
算法分析与设计习题课.ppt_第4页
算法分析与设计习题课.ppt_第5页
免费预览已结束，剩余9页可下载查看

下载本文档

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

文档简介

算法分析与设计,习题课,填空题,1.算法的复杂性有复杂性和复杂性之分。2.快速排序算法是基于的一种排序算法。3.适用于贪心算法求解的问题一般具有两个特性：和，其中是运用该算法解决问题的核心。4.贪心算法和动态规划算法的主要区别在于。5.分析0/1背包问题时，可使用贪心法、动态规划法和回溯法，其中需要对数据进行事先排序的是和；不需要排序的是。6.算法具有5个特征，分别是、。,选择题,1二分搜索算法是利用（）实现的算法。A.分治策略B.动态规划法C.贪心法D.回溯法2.贪心算法的基本要素的是（）。A.重叠子问题B.构造最优解C.贪心选择性质D.定义最优解3.为避免无效搜索，在回溯算法中采用哪种函数（）。A.递归函数B.剪枝函数C.随机数函数D.搜索函数,4.贪心算法与动态规划算法的共同点是（）。A.重叠子问题B.构造最优解C.贪心选择性质D.最优子结构性质5.使用分治法求解不需要满足的条件是（）。A.子问题必须是一样的B.子问题不能够重复C.子问题的解可以合并D.原问题和子问题使用相同的方法解6.下面不能使用贪心法解决的是（）。A.单源最短路径问题B.N皇后问题C.最小代价生成树问题D.背包问题7.以深度优先方式系统搜索问题解的算法是()。A.分枝界限算法B.概率算法C.贪心算法D.回溯算法,多段图,设G=(V,E)是一个有向图，其顶点集V被划成K2个不相交的子集vi,求由s到t的最小成本路径。,求解过程：每个节点处的序偶（p,q),p表示节点到t的成本，q表示后继结点编号。最优路径,矩阵相乘,已知k=1,2,3,4,5,6,r1=5,r2=10,r3=3,r4=12,r5=5,r6=50,r7=6,求矩阵连乘积A1A2A3A4A5A6的最佳求积顺序。,完全加括号形式,0/1背包问题,假设有7个物品，它们的重量和价值如下表所示，若这些物品均不能被分割，且背包容量M=150，使用回溯法求解该背包问题。请写出状态空间搜索树。,按照单位效益从大到小依次排列：FBGDECA,序号分别记为17.则产生如下状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：,练习,设有子集和数问题的实例W=（w0,w1,w2,w3,w4,w5,w6）=（5,7,10,12,15,18,20）和M=35。求W中元素之和等于M的所有子集。画出对于这一实例由SumOfSub算法实
人人文库> 全部分类> 行业资料 > 信息产业

温馨提示

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

最新文档

评论

0/150

提交评论