下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、精选优质文档-倾情为你奉上一、 单选题(每小题1分,共10分)1、下列函数中,渐近紧致界为的是( C )。A; B; C; D 。2、下列函数中,渐近非紧上界为的是( D )。A; B; C; D 。3、以下描述中,不正确的有( A )。A在渐进复杂性概念下,等式在时成立;B在渐进复杂性概念下,有成立; C在渐进复杂性概念下,与无法渐近比较; D对于任意函数, (为空集)。4、在快速排序中,以下描述不正确的是( D )。A在快速排序,最好时间复杂性和平均时间复杂性均为;B若精心挑选一个划分元,每次经过Partition算法后,分成两个子问题,从而使得 其 最坏时间复杂性为; C若随机挑选一个划
2、分元,每次经过RandomizedPartition算法后,分成两个期望均长的子问题,从而使得其期望时间复杂性为; D不管是精心挑选还是随机挑选划分元,快速排序的最坏时间复杂性均为。 6、Dijkstra算法是解单源最短路径问题的一个贪心算法,工作过程与Prim算法是一样的,不同点在于它比较的是路径的长度而不是边的长度。以下哪种权重的图,Dijkstra算法总是能够产生一个正确的解。( D )A自然数; B整数; C实数; D非负实数。 8、分支限界法与回溯法都是在问题的解空间树T上搜索问题的解,二者(B )。 A求解目标不同,搜索方式相同;B求解目标不同,搜索方式也不同;C求解目标相同,搜索
3、方式不同; D求解目标相同,搜索方式也相同。9、回溯法在解空间树T上的搜索方式是( A )。A深度优先; B广度优先; C最小耗费优先; D活结点优先。10、在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为扩展结点的是( B )。A回溯法; B分支限界法; C回溯法和分支限界法; D回溯法求解子集树问题。二、 填空题(每空1分,共10分)1、 在空格处填上合适的大函数使得下列关系,在渐进复杂性概念下成立。 _。2、 分治策略求解问题可以分为三步:分解;递归地解子问题;组合。有的问题分解难而组合容易,如_快速排序_,有的问题分解容易而组合难,如归并排序_。3、 活动安排问题既可以
4、用动态规划算法求解也可以用贪心算法求解。其中用动态规划算法求解的时间复杂性为:_;用贪心算法求解的时间复杂性为:_(假定个活动已经按照结束时间单调有序)。4、 哈夫曼编码是用于_数据文件_压缩的一个十分有效的编码方法。其中算法Huffman Tree用最小堆来实现优先队列。而退出优先队列算法DeleteMin和进入优先队列算法Insert均需要_时间。三、 求以下递推式的渐近上界(每小题8分,共16分)1 () (2分)迭代次后,将有 (4分)直到()时 (6分) () () (8分)2nnnn总共 (4分)在将递归树各层的值加起来时,发现每一层的值都为。从根到叶的最长的一条路经是。因为当时,
5、该树的高度为。因而,该递归式的解至多是。(8分)四、 简答题(每小题4分,共20分)1试论和的区别。2简述回溯法和分支限界法的异同。(1)相同点:都是用来求解组合难题的系统方法,需要在解空间按照某种策略搜索,但都不同于一般的穷举搜索方法。(1分)(2)不同点:搜索方式不同。回溯法按照深度优先搜索原则,而分支限界法按照广度优先或是最佳优先原则;(3分)所用的数据结构不同。栈和队列或优先队列。(4分)3分析以下程序,然后指出程序返回(return)的结果是多少,为什么? Darts() ;for =1 to do uniform(0,1); /随机生成一个大于等于0小于1的实数 ; if () t
6、hen ; return ; 五、 计算题(每小题7分,共14分)1计算题:请用动态规划算法找出矩阵连乘的最佳计算次序(即最佳完全加括号方式),其中,。列出计算过程。因为, (2分)所以,; (3分)= (4分)(5分)(6分)则最佳完全加括号方式为: (7分)。2在0-1背包问题中,有四种物品,其重量(价值)分别为:2kg(12$),1kg(10$),3kg(20$),2kg(15$)。并且背包总容量。请用动态规划算法,找出一个最优解的装包情形及其装包的总价值。列出计算过程。解:设是背包容量为,可选物品为前个物品时,0-1背包问题的最优值,即能够装进承重量为的背包中前个物品最有价值子集的总价
7、值。则有: (2分)初始条件:当时,当时,。计算过程见下表:i j012345000000010012121212201012222222401015253037(6分)故:第1、2、4物品装包其它不装,总价值为37$ (7分)六、 算法设计题(每小题10分,共30分)要求:说明所使用的算法策略;写出算法实现的主要步骤;分析算法的时间复杂性。1某次选举中有个候选人,编号从到,有个选民参与了选举,每个选民只能选择一位候选人,当某个候选人获得超过一半的选票时,则认为该候选人获胜。试设计一个算法,在选举结束后,可在的时间内判断是否有某个候选人获胜。2在一个直线跑道上摆放着一行共堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将堆石子合并成一堆的最小得分。3假定我军计划炸毁敌方整个通信网络。敌方通信网络由各个驻点加上其
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024园林苗木购销合同范本
- 2024土地流转规范合同书
- 2.1位置(拔尖作业)2024-2025学年五年级上册数学人教版(含解析)
- 质量课件下载教学课件
- 3.3.2 海陆的变迁(教学设计)七年级地理上册同步高效备课课件(人教版2024)
- Unit 1 How can we become good learners-解析版-单元测试卷九年级英语上册单元速记·巧练(贵州专用人教版)
- 05 正确使用词语(知识梳理+考点精讲精练+实战训练)-【学考复习】2024年高中语文学业水平考试考点归纳与测试(新教材专用)(原卷版 )
- 部编版一年级下册语文期末考试试题及答案
- 一氧化碳中毒课件
- 桥梁板相关项目投资计划书
- 《热射病教学查房》课件
- 一例乳腺癌术后并发淋巴水肿患者的个案护理
- 2023年秋季学期《职业素养》考试试题(上)
- 创新能力培训
- 抗菌药物的管理与合理使用
- 叉车维修方案
- 高中生物必修一期末考试试题及答案
- 小学生主题班会 我的职业梦想 课件
- 施工总平面图样本
- 数字化时代下的中小学语文阅读素养培养
- 第三次月考质量分析会课件
评论
0/150
提交评论