还剩2页未读,继续阅读
文本内容:
算法设计与分析复习题
1、分治法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题互相独立且与原问题相同递归地解这些子问题,然后将各子问题的解合并得到原问题的解
2、贪心选择性质指所求问题的整体最优解可以通过一系列局部最优的选择,
3、 Prim算法设G=VE是连通带权图,V={12…n}构造G的最小生成树的Prim算法的基本思想是首先置S={1},然后,只要S是V的真子集,就作如下的贪心选择选取满足条件iS,jV-S,且c[j]最小的边,将顶点j添加到S中这个过程一直进行到S=V时为止
4、什么是剪枝函数回溯法搜索解空间树时,通常采用两种策略避免无效搜索,提高回溯法的搜索效率其一是用约束函数在扩展结点处剪 去不满足约束的子树;其二是用限界函数剪去得不到最优解的子树这两类函数统称为剪枝函数
6、 分支限界法的基本思想1分支限界法常以广度优先或以最小耗费最大效益优先的方式 搜索问题的解空间树2在分支限界法中,每一个活结点只有一次机会成为扩展结点活结点一旦成为扩展结点,就一次性产生其所有儿子结点在这些儿子结点中,导致不可行解或导致 非最优解的儿子结点被舍弃,其余儿子结点 被加入活结点表中3此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程,这个过程一直持续到找到所需的解或活结点表这空时为止
5、 什么是算法的复杂性是该算法所需要的计算机资源的多少,它包括时间和空间资源
6、 最优子结构性质该问题的最优解包含着其子问题的最优解
7、 回溯法是一个既带有系统性又带有跳跃性的搜索算法这在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树算法搜索至解空间树的任一结点时,先判断该结点是否包含问题的解如果肯定不包含,则跳过对以该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索
8、Kruskal算法构造G的最小生成树的基本思想是,首先将G的n个顶点看成n个孤立的连通分支将所有的边按权从小到大排序然后从第一条边开始,依边权递增的顺序查看每一条边,并按下述方法连接2个不同的连通分支当查看到第k条边vw时,如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时,就用边vw将T1和T2连接成一个连通分支,然后继续查看第k+1条边;如果端点v和w在当前的同一个连通分支中,就直接再查看第k+1条边这个过程一直进行到只剩下一个连通分支时为止
9、 算法满足的性质输入、输出、确定性、有限性
10、程序与算法不同程序不满足有限性
11、输入有零个或多个外部量作为输入
12、输出算法产生至少一个量作为输出
13、确定性组成算法的每条指令是清晰的,无歧义的
14、有限性算法中每条指令的执行次数有限,执行每条指令的时间也有限
15、递归算法的优点结构清晰,可读性强,容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序带来很大方便
16、递归算法的缺点运行效率较低,耗费的计算时间和占用的存储空间都多为了达到此目的,根据具体程序的特点对递归调用工作栈进行简化,尽量减少栈操作,压缩栈存储空间以达到节省计算时间和存储空间的目的
17、合并排序的时间复杂度是Tn=Onlogn
18、快速排序的时间复杂度是Tn=Onlogn
19、动态规划算法的基本要素最优子结构性质和子问题重叠性质
20、贪心算法的基本要素贪心选择性质和最优子结构性质
21、 前缀码对每一个字符规定一个
0、1串作为其代码,并要求任一字符的代码都 不是其他字符代码的前缀,这种编码称为前缀码
22、 哈夫曼提出构造最优前缀码的贪心算法,由此产生的编码方案称为哈夫曼编码
23、哈夫曼编码的平均码长为BT=
24、Dijkstra算法是解单源最短路径问题的贪心算法时间复杂度是O(n )
25、生成树上各边权的总和称为该生成树的耗费在G的所有生成树中,耗费最小的生成树称为G的最小生成树
26、最常见的分支限界法有两种队列式(FIFO)分支限界法和优先队列式分支限界法
27、 概率算法可分为4类数值概率算法、蒙特卡罗算法、拉斯维加斯算法和舍伍德算法
28、数值概率算法常用于数值问题的求解这类算法所得到的往往是近似解
29、蒙特卡罗算法用于求问题的准确解能求得问题的一个解,但这个解未必是正确的
30、拉斯维加斯算法不会得到不正确的解但有时用拉斯维加斯算法找不到解
31、舍伍德算法总能求得问题的一个解,且所求得的解总是正确的
32、回溯法效率的因素
(1)产生x[k]的时间
(2)满足显约束的x[k]值的个数
(3)计算约束函数constraint的时间
(4)计算上界函数bound的时间
(5)满足约束函数和上界函数约束的所有x[k]的个数
5、使用( )可以使函数的定义和算法的描述简洁且易于理解
6、大整数乘积算法是用( )来设计的
7、动态规划算法的两个基本要素是( )和( )
8、( )是贪心算法与动态规划算法的共同点
9、以广度优先或以最小耗费方式搜索问题解的算法称为( )
10、舍伍德算法总能求得问题的( )
1、算法是指解决问题的()或()
3、二分搜索算法是利用( )实现的算法A、分治策略 B、动态规划法 C、贪心法 D、回溯法
4、下列不是动态规划算法基本步骤的是( )A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解
5、下列算法中通常以深度优先方式系统搜索问题解的是( )A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
6、最大效益优先是( )的一搜索方式A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
7、蒙特卡罗算法是( )的一种A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法
9、在下列算法中总能得到问题正确解的是()A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法
10、0-1背包问题的回溯算法所需的计算时间为()A、O(n2n)B、O(nlogn)C、O(2n)D、O(n)
1、写出设计流水作业调度算法的主要步骤
2、举例说明贪心算法与动态规划算法的的主要差别
3、写出用回溯法搜索子集树的一般算法
4、简述利用贪心算法解决“单源最短路径”问题的基本思想
1、简述分治法的基本思想
2、写出设计动态规划算法的主要步骤
3、简述分支限界法与回溯法的异同
4、写出用回溯法搜索排列树的算法算法题0—1背包问题给定n种物品和一背包,物品i的重量是wi,其价值为vi,背包的容量为C问应该如何装入背包中物品的总价值最大?写出用分支限界算法解决该问题的算法
1、什么是算法算法具有的特性是什么?是解决问题的方法和过程1)输入0个或多个信息 2)输出至少一个信息3)确定性组成算法的每个指令是清晰的,无二义的,整个过程是确定的4)有限性
2、什么是动态规划法将问题分解成多级或许多子问题,然后顺序求解子问题,前一个子问题的解为后一个子问题的求解提供有用的信息
3、什么是贪心法从问题某一初始或推测值出发,一步步的攀登给定目标,尽可能快的去逼近更好的解,当达到某一步不能继续时终止
4、什么是分支定界法对有约束条件的最优化问题所有可行解定向、适当地进行搜索将可行解空间不断地划分为越来越小的子集(分支),并为每一个子集的解计算一个上界和下界(定界)例题(重点看后面的要点)
1.选择范例分支限界法与回溯法都是在问题的解空间树T上搜索问题的解,二者()A.求解目标不同,搜索方式相同B.求解目标不同,搜索方式也不同C.求解目标相同,搜索方式不同D.求解目标相同,搜索方式也相同下列是动态规划算法基本要素的是()A、最优子结构B、构造最优解C、算出最优解D、定义最优解在下列算法中总能得到问题正确解的是()A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法下面不是分支界限法搜索方式的是()A、广度优先B、最小耗费优先C、最大效益优先D、深度优先Strassen矩阵乘法是利用()实现的算法A、分治策略B、动态规划法C、贪心法D、回溯法
2.填空范例算法的“确定性”指的是组成算法的每条()是清晰的,无歧义的最小优先队列分支限界法中,优先值较()的结点优先级较高,通常用()实现,体现()的原则最优子结构性质的含义是()()和()是贪心算法的基本要素回溯法中的解空间树结构通常有两种,分别是()、()
3.判断范例所有的递归函数都能找到对应的非递归定义备忘录方法求解时采用与递归定义一致的自上而下的方式满足贪心选择性质必满足最优子结构性质状态空间树中,只有展开了所有子结点的结点才称为死结点满足最优子结构性质必满足贪心选择性质
4.简答范例简述回溯法求解问题的一般步骤简述状态空间树的广度优先展开方法状态空间树中的活结点、E-结点、死结点简述用回溯法设计算法的步骤举例说明最小生成树在实际中的应用
5.分析设计题上课反复讲、反复强调的几个问题,要求懂原理,会设计(关键是思路,表达方法可以是语言、伪代码、代码),会进行复杂度分析建议答题时不要把所有的东西写一大段,适当分步骤、分要点,如XXX算法原理
①做什么,怎么做
②做什么,怎么做
③做什么,怎么做……等复习要点及要求【理解】算法性质输入、输出、确定性(涵义)、有限性(涵义)【知道】算法复杂性算法需要的计算机资源;时间、空间;最好、最坏、平均,最坏情况时间复杂性【知道】算法复杂性的表示方法渐进复杂度(为什么用渐进表示?爱因斯坦那句话)【掌握】算法复杂性的表示方法O(一些运算规则),o,Ω,θ,图形曲线长成什么样?分别对应上界?下界?紧确上界?紧确下界?大小写字母在图形表示上有何区别?【知道】并非一切递归函数都能用非递归定义(知道,如Ackerman,双递归)【知道】汉诺塔问题基本思想、基本步骤【掌握】二分搜索技术思想、原理,基本步骤、描述,最坏情况下的时间复杂度Ologn【理解】合并排序思想、原理、步骤、复杂度Onlogn【知道】实际上,对排序算法而言,一般好的算法复杂度Onlogn,不好的算法On^2【掌握】快速排序思想、原理、步骤、复杂度(平均Onlogn,为什么平均情况下是这个复杂度?最坏呢?)如何改进?(随机化算法)【理解】动态规划基本思想,与分治法区别,好处;动态规划解题的基本步骤P
48、动态规划基本要素最优子结构、子问题重叠【知道】备忘录方法与动态规划的主要区别(计算方向)动态规划保留前面计算结果,牺牲部分空间换取效率,自底向上计算;【掌握】动态规划和贪心法的区别联系(联系就是都得具有最有子结构性质,可举例背包问题与0-1背包问题);局部最优、全局最优;可应用贪心法需满足什么性质?(贪心选择,什么叫贪心选择?可举例)【掌握】哈夫曼编码可进行文件压缩(压缩率会算),原理;构造最优前缀码的二叉树;平均码长(会计算),复杂度【理解】单源最短路径原理、实现的基本思路(会描述)【掌握】最小生成树概念(最小生成树有多少条边?忘了就画图试试)、应用、两种方法【理解】回溯法解空间、解向量、解空间树的表示,活结点、死结点、扩展结点,活结点有几次机会变成扩展结点?【知道】回溯法基本思想深度优先搜索【掌握】排列树、子集树问题类型特点、节点数目,知道哪类问题对应哪种树【掌握】装载问题原理、思想、步骤、解空间、解空间树结构、算法设计、策略、上界函数(如何定义的?)、复杂性分析【掌握】n后问题原理、解空间(树结构)、复杂性分析,要掌握其解空间树的表示方法,给出问题会画出解空间树,并在解空间树中求解【掌握】0-1背包问题、旅行售货员问题,都要仔细看,解空间树的结点搜索顺序【知道】分支限界法与回溯的区别联系,广度优先或最大受益(最小耗费)优先,活结点只有一次机会成为扩展节点【知道】选择下一个活结点(方式、特点)队列式FIFO、优先队列式(堆)【掌握】装载、0-1背包、TSP上界函数的定义、搜索截至的条件(在特定上界函数的定义下,叶子节点变为扩展结点即结束)【掌握】n后解空间树的搜索顺序,会画解空间树,会在解空间树中求解【理解】随机化算法思想、特点、随机数、伪随机数【知道】四类算法、特点数值随机化、蒙特卡罗法、拉斯维加斯算法、舍伍德算法。