《算法设计与分析》期末必考复习及答案题整理
、分治法的基本思想：是将一个规模为 的问题分解为 个规模较小的子问题，这些子问题互相独立且与原问题相
同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
、贪心选择性质：指所求问题的整体最优解可以通过一系列局部最优的选择，
、S 算法：设 是连通带权图，。构造 的最小生成树的 算法的基本思想是：首先置
，然后，只要 是 的真子集，就作如下的贪心选择：选取满足条件 ，，且 最小的边，将顶点 添
加到 中。这个过程一直进行到 时为止。
、什么是剪枝函数：回溯法搜索解空间树时，通常采用两种策略避免无效搜索，提高回溯法的搜索效率。其一是用
约束函数在扩展结点处剪S去不满足约束的子树；其二是用限界函数剪去得不到最优解的子树。这两类函数统称为剪枝
函数。
、SS分支限界法的基本思想：
分支限界法常以广度优先或以最小耗费最大效益优先的方式S搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子
结点。在这些儿子结点中，导致不可行解或导致S非最优解的儿子结点被舍弃，其余儿子结点S被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程，这个过程一直持续到找到所需的解
或活结点表这空时为止。
、S什么是算法的复杂性：是该算法所需要的计算机资源的多少，它包括时间和空间资源。
、S最优子结构性质：该问题的最优解包含着其子问题的最优解。
、S回溯法：是一个既带有系统性又带有跳跃性的搜索算法。这在问题的解空间树中，按深度优先策略，从根结点出
发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对
以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
、!"#$% 算法构造 的最小生成树的基本思想是，首先将 的 个顶点看成 个孤立的连通分支。将所有的边按
权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接 个不同的连通分支：
当查看到第 # 条边&'时，如果端点 & 和 ' 分别是当前 个不同的连通分支 ( 和 ( 中的顶点时，就用边&'将 (
和 ( 连接成一个连通分支，然后继续查看第 #) 条边；如果端点 & 和 ' 在当前的同一个连通分支中，就直接再查看
第 #) 条边。这个过程一直进行到只剩下一个连通分支时为止。
*、S算法满足的性质：输入、输出、确定性、有限性。
+、程序与算法不同：程序不满足有限性。
、输入：有零个或多个外部量作为输入。
、输出：算法产生至少一个量作为输出。
、确定性：组成算法的每条指令是清晰的，无歧义的。
、有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。
、递归算法的优点：结构清晰，可读性强，容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序
带来很大方便。
、递归算法的缺点：运行效率较低，耗费的计算时间和占用的存储空间都多。为了达到此目的，根据具体程序的特
点对递归调用工作栈进行简化，尽量减少栈操作，压缩栈存储空间以达到节省计算时间和存储空间的目的。
、合并排序的时间复杂度是：(,%-.。
、快速排序的时间复杂度是：(,%-.。
*、动态规划算法的基本要素：最优子结构性质和子问题重叠性质。
+、贪心算法的基本要素：贪心选择性质和最优子结构性质。
、S前缀码：对每一个字符规定一个 +、 串作为其代码，并要求任一字符的代码都S不是其他字符代码的前缀，这种
编码称为前缀码。
、S哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。
、哈夫曼编码的平均码长为 /(
、0#"1$ 算法是解单源最短路径问题的贪心算法。时间复杂度是 ,（2）。
、生成树上各边权的总和称为该生成树的耗费。在 的所有生成树中，耗费最小的生成树称为 的最小生成树。
、最常见的分支限界法有两种：队列式（343,）分支限界法和优先队列式分支限界法。
资源评论
