算法设计与分析考点精讲串烧

算法设计与分析考点精讲串烧

ID:32726162

大小:103.29 KB

页数:12页

时间:2019-02-15

算法设计与分析考点精讲串烧_第1页
算法设计与分析考点精讲串烧_第2页
算法设计与分析考点精讲串烧_第3页
算法设计与分析考点精讲串烧_第4页
算法设计与分析考点精讲串烧_第5页
资源描述:

《算法设计与分析考点精讲串烧》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

1、一、选择题(每小题3分,共15分)1.算法与程序的主要区别在于算法具有()。A.能行性B.确定性C.有限性D.输入和输出答案:Co2.对一个有序序列,以比较为基础的搜索算法的最坏情况时间复杂性的下界为()。A.Q(/?)B.Q(刀2)C.Q(Mogz?)D.Q(log/?)答案:Do3.背包问题:77=6,010,7(1:6)=(15,59,21,30,60,5),风1:6)二(1,5,2,3,6,1)。该问题的最大价值为()。A.101氏110C.115D.120答案:Co4.矩阵连乘积问题:Mi(5xl0),M2(10x4),5(4x6)。矩阵链乘M1M2M3^:要

2、的最少乘法次数为()。A.348B.328C.720D.320答案:Do5.用贪心策略设计算法的关键是()。A.将问题分解为多个子问题來分别处理B.选好贪心策略C.获取各阶段间的递推关系式D.满足最优性原理答案:Bo二、填空题(每小题4分,共20分)1.某算法的计算时间T3)满足递归关系式:T(/7)=2T(/t-1)+0(1),/7>1;T⑴二1。则T(/7)二0答案:2=2.用方法对状态空间树进行搜索时,每个结点有可能多次成为扩展结点。3.子集和数问题一般陈述如下:己知卅1个正数:叭(lWfW/?)和必要求找出旳的和数是〃的所有子集。其解可以表示为/7■元组(加,左

3、,…,几),这里尢€{0,1},1W2W/7。如果没有选择肥,则相应的脸=0;如果选择了旳,则出=1。此解空间的空间树上有个叶结点,共有个结点。答案:2n,2n,1-lo1.已知将两个分别包含〃个和/〃个记录的己分类文件归并在一起得到一个分类文件需作卅刃次记录移动。现有五个已分类文件用,忆碍M,阿,它们的记录个数分别为25,40,15,10,40,将这五个文件归并成一个分类文件需作次记录移动。注:每次只能归并两个文件。答案:285o2.两个序列A二“xyxxzxyzxy”和B二“zxzyyzxxyxxz”的最长的公共子序列的长度为。其屮一个最长公共子序列为o答案:6,x

4、zyzxy0三、问答题(每小题5分,共20分)1.快速排序算法是根据分治策略来设计的,简述其基木思想。答:快速分类算法是根据分治策略设计出來的算法。其关键步骤就是“划分”:根据某个元素卩为标准,将序列中的元素重新整理,使得整理后的序列中孑之前的元素都不大于-而/之后的元索都不小于厶此时,元素亍即找到了其最终的位置。要得到序列的排序结果,再只需对yZ前的元素和yZ后的元素分别排序即可,这可通过递归处理来完成。2.简述蒙特卡罗算法的特点及提高蒙特卡罗算法得到的为正确的概率的措施?答:在某些实际应用中经常会遇到一些问题,不论采用确定性算法还是概率算法都无法保证每次得到正确的解

5、。蒙特卡罗算法在一般情况下,可以保证对问题的所有实例都以高概率给出正确解,但是通常无法判定一个具体解是否止确。使用蒙特卡罗算法肯定能得到问题的一个解,但是这个解未必是正确的。可以通过重复调用同一个蒙特卡洛算法多次來提高获得正确解的概率。3.简述回溯法的基本思想。答:冋溯法的基本思想是:深度优先搜索+剪枝。从根结点开始,以深度优先的方式进行搜索,搜索的过程屮,每搜索到一个结点,检查是否满足约束函数和限界函数,如果满足,则更深一层的搜索,如果不满足,则剪枝,搜索过程直到找到问题的解或所有活结点变成死结点为止。回溯法用来求问题的多个解。4•简述最小生成树的Kruskal算法的

6、基本思想。答:按照图川边权由大到小的次序依次考虑每条边是否加入最小生成树中。当考虑到某条边时,如果该边与已经加入到最小生成树屮的边不形成回路,则将该边加入进去。四、求解题1.(5分)设f(?0、g(N)是定义在正数集上的正函数。如果存在正的常数C和自然数使得当时有f(肋则成函数f(肋当艸充分大时上有界,且是它的一个上界,记为(妙)。证明:0(广(旳)+0@(旳)二O(max{/'(A),g(M})。解:对于任意£S)e0(fS),存在正常数。和自然数〃,使得对所有n>n^有£(刀)

7、,使得对所有虑处,有g(/?)773,有fS+g(/7)=N1,有:F(N)<=C1f[N];同理令:G[N]=O[g],则

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。