算法设计与分析复习题 1、分治法的基本思想：是将一个规模为 N 的问题分解为 K 个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解 这些子问题，然后将各子问题的解合并得到原问题的解。 2、贪心选择性质：指所求问题的整体最优解可以通过一系列局部最优的选择， 3、 Prim 算法：设 G=(V,E)是连通带权图，V={1,2,…,n}。构造 G 的最小生成树的 Prim 算法的基本思想是：首先置 S={1}，然后， 只要 S 是 V 的真子集，就作如下的贪心选择：选取满足条件 i?S，j?V-S，且 c[j]最小的边，将顶点 j 添加到 S 中。这个过程一直进 行到 S=V 时为止。 4、什么是剪枝函数：回溯法搜索解空间树时，通常采用两种策略避免无效搜索，提高回溯法的搜索效率。其一是用约束函数在扩 展结点处剪 去不满足约束的子树；其二是用限界函数剪去得不到最优解的子树。这两类函数统称为剪枝函数。 6、 分支限界法的基本思想： (1)分支限界法常以广度优先或以最小耗费(最大效益)优先的方式 搜索问题的解空间树。 (2)在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些 儿子结点中，导致不可行解或导致 非最优解的儿子结点被舍弃，其余儿子结点 被加入活结点表中。 (3)此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程，这个过程一直持续到找到所需的解或活结点表这 空时为止。 5、 什么是算法的复杂性：是该算法所需要的计算机资源的多少，它包括时间和空间资源。 6、 最优子结构性质：该问题的最优解包含着其子问题的最优解。 7、 回溯法：是一个既带有系统性又带有跳跃性的搜索算法。这在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间 树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索， 逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。 8、Kruskal 算法构造 G 的最小生成树的基本思想是，首先将 G 的 n 个顶点看成 n 个孤立的连通分支。将所有的边按权从小到大排 序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接 2 个不同的连通分支：当查看到第 k 条边(v,w)时， 如果端点 v 和 w 分别是当前 2 个不同的连通分支 T1 和 T2 中的顶点时，就用边(v,w)将 T1 和 T2 连接成一个连通分支，然后继续查 看第 k+1 条边；如果端点 v 和 w 在当前的同一个连通分支中，就直接再查看第 k+1 条边。这个过程一直进行到只剩下一个连通分支 时为止。 9、 算法满足的性质：输入、输出、确定性、有限性。 10、程序与算法不同：程序不满足有限性。 11、输入：有零个或多个外部量作为输入。 12、输出：算法产生至少一个量作为输出。 13、确定性：组成算法的每条指令是清晰的，无歧义的。 14、有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 15、递归算法的优点：结构清晰，可读性强，容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 16、递归算法的缺点：运行效率较低，耗费的计算时间和占用的存储空间都多。为了达到此目的，根据具体程序的特点对递归调用 工作栈进行简化，尽量减少栈操作，压缩栈存储空间以达到节省计算时间和存储空间的目的。 17、合并排序的时间复杂度是：T(n)=O(nlogn)。 18、快速排序的时间复杂度是：T(n)=O(nlogn)。 19、动态规划算法的基本要素：最优子结构性质和子问题重叠性质。 20、贪心算法的基本要素：贪心选择性质和最优子结构性质。 21、 前缀码：对每一个字符规定一个 0、1 串作为其代码，并要求任一字符的代码都 不是其他字符代码的前缀，这种编码称为前缀 码。 22、 哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。 23、哈夫曼编码的平均码长为 B(T)= 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、 ）的一种。A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法 回溯法 7、蒙特卡罗算法是（ 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。问应该如何装入背包中物品的总价值 最大？写出用分支限界算法解决该问题的算法。 2） 输出至少一个信息 1、 什么是算法, 算法具有的特性是什么？ 是解决问题的方法和过程, 1） 输入 0 个或多个信息 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，双递归） 【知道】汉诺塔问题：基本思想、基本步骤 【掌握】二分搜索技术：思想、原理，基本步骤、描述，最坏情况下的时间复杂度 O(log n) 【理解】合并排序：思想、原理、步骤、复杂度 O(nlog n) 【知道】实际上，对排序算法而言，一般好的算法复杂度 O(nlog n)，不好的算法 O(n^2) 【掌握】快速排序：思想、原理、步骤、复杂度（平均 O(nlog n)，为什么平均情况下是这个复杂度？最坏呢？） 如何改进？（随机化算法） 【理解】动态规划：基本思想，与分治法区别，好处；动态规划解题的基本步骤 P48、动态规划基本要素：最优 子结构、子问题重叠 【知道】备忘录方法与动态规划的主要区别（计算方向）：动态规划保留前面计算结果，牺牲部分空间换取效率， 自底向上计算； 【掌握】动态规划和贪心法的区别联系（联系就是都得具有最有子结构性质，可举例：背包问题与 0-1 背包问题）； 局部最优、全局最优；可应用贪心法需满足什么性质？（贪心选择，什么叫贪心选择？可举例） 【掌握】哈夫曼编码：可进行文件压缩（压缩率会算），原理；构造最优前缀码的二叉树；平均码长（会计算）， 复杂度。 【理解】单源最短路径：原理、实现的基本思路（会描述） 【掌握】最小生成树：概念（最小生成树有多少条边？忘了就画图试试）、应用、两种方法 【理解】回溯法：解空间、解向量、解空间树的表示，活结点、死结点、扩展结点，活结点有几次机会变成扩展 结点？ 【知道】回溯法基本思想：深度优先搜索。 【掌握】排列树、子集树：问题类型特点、节点数目，知道哪类问题对应哪种树。 【掌握】装载问题：原理、思想、步骤、解空间、解空间树结构、算法设计、策略、上界函数（如何定义的？）、 复杂性分析 【掌握】n 后问题：原理、解空间（树结构）、复杂性分析，要掌握其解空间树的表示方法，给出问题会画出解空 间树，并在解空间树中求解。 【掌握】0-1 背包问题、旅行售货员问题，都要仔细看，解空间树的结点搜索顺序。 【知道】分支限界法：与回溯的区别联系，广度优先或最大受益（最小耗费）优先，活结点只有一次机会成为扩 展节点 【知道】选择下一个活结点（方式、特点）：队列式 FIFO、优先队列式（堆） 【掌握】装载、0-1 背包、TSP：上界函数的定义、搜索截至的条件（在特定上界函数的定义下，叶子节点变为扩 展结点即结束） 

【掌握】n 后：解空间树的搜索顺序，会画解空间树，会在解空间树中求解。 【理解】随机化算法思想、特点、随机数、伪随机数 【知道】四类算法、特点：数值随机化、蒙特卡罗法、拉斯维加斯算法、舍伍德算法