束。

有两种常用的方法可用来选择下一个E-节点（虽然也可能存在其他的方法）： 1) 先进先出（F I F O） 即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活

节点表的性质与队列相同。

2) （优先队列）最小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益。如果查找 一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个E-节点就是具有最小耗费 的活节点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，下一个 E-节点是具有最大收益的活节点

16. 分支限界法与回溯法的相同点是：都是一种在问题的解空间树T中搜索问题解的算法。

不同点：（1）求解目标不同；

（2）搜索方式不同；

（3）对扩展结点的扩展方式不同； （4）存储空间的要求不同。

17. 分治法所能解决的问题一般具有的几个特征是： （1）该问题的规模缩小到一定的程度就可以容易地解决；

（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质;

（3）利用该问题分解出的子问题的解可以合并为该问题的解；

（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

18. 用分支限界法设计算法的步骤是：

(1)针对所给问题，定义问题的解空间（对解进行编码）； (2)确定易于搜索的解空间结构（按树或图组织解） ；

(3)以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

19. 常见的两种分支限界法的算法框架：

（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。

（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

20. 回溯法中常见的两类典型的解空间树是子集树和排列树。

当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。这类子集树通常有2n个叶结点，遍历子集树需O(2n)计算时间 。

当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O(n!)计算时间。

21. 分支限界法的搜索策略是：

在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。

22. 请叙述动态规划算法与贪心算法的异同。

共同点：

都需要最优子结构性质， 都用来求有优化问题。 不同点：

动态规划：每一步作一个选择—依赖于子问题的解。 贪心方法：每一步作一个选择—不依赖于子问题的解。

动态规划方法的条件：子问题的重叠性质。

可用贪心方法的条件：最优子结构性质；贪心选择性质。

动态规划：自底向上求解； 贪心方法： 自顶向下求解。

可用贪心法时，动态规划方法可能不适用； 可用动态规划方法时，贪心法可能不适用。 23. 请说明动态规划方法为什么需要最优子结构性质。 答：

最优子结构性质是指大问题的最优解包含子问题的最优解。

动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构.

24. 请说明：

(1)优先队列可用什么数据结构实现？ (2)优先队列插入算法基本思想？ (3)优先队列插入算法时间复杂度？ 答：（1）堆。

（2）在小根堆中，将元素x插入到堆的末尾，

然后将元素x的关键字与其双亲的关键字比较， 若元素x的关键字小于其双亲的关键字，

则将元素x与其双亲交换，然后再将元素x与其新双亲的关键字相比，直到元素x的关键字大于双亲的关键字，或元素x到根为止。 （3）O( log n)

25. 衡量算法时间效率的方法有哪两种？请叙述。 答：有事前分析法和事后分析法两种。

事后分析法：先将算法用程序设计语言实现，然后度量程序的运行时间。 事前分析法：算法的时间效率是问题规模的函数，假如，随着问题规模n的增长，算法执行时间的增长率和函数f(n)的增长率相同，则可记作： T(n)=○(f(n)) 称T(n)为算法的渐进时间复杂度。简称时间复杂度。

26. 在算法复杂性分析中，O、Ω、Θ这三个记号的意义是什么？在忽略常数因子的情况

下，O、Ω、Θ分别提供了算法运行时间的什么界？

答：

如果存在两个正常数c和N0,对于所有的N≥N0，有|f(N)|≤C|g(N)|，则记作：f(N)= O(g(N))。这时我们说f(N)的阶不高于g(N)的阶。

若存在两个正常数C和自然数N0，使得当N ≥ N0时有|f(N)|≥C|g(N)|，记为f(N)=?(g(N))。这时我们说f(N)的阶不低于g(N)的阶。

如果存在正常数c1，c2和n0，对于所有的n≥n0，有c1|g(N)| ≤|f(N)| ≤ c2|g(N)| 则记作 f(N)= (g,(N))

O、Ω、Θ分别提供了算法运行时间的上界、下界、平均

27. 概率算法

很多算法的每一个计算步骤都是固定的，而概率算法允许算法在执行的过程中随机选择下一个计算步骤。许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。因此概率算法可在很大程度上降低算法的复杂度。 28.概率算法的一个基本特征

是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。

29．概率算法大致分为四类:

数值概率算法，蒙特卡罗（Monte Carlo）算法，拉斯维加斯（Las Vegas）算法和舍伍德（Sherwood）算法。 30.数值概率算法

常用于数值问题的求解。这类算法所得到的往往是近似解。而且近似解的精度随计算时间的增加不断提高。在许多情况下，要计算出问题的精确解是不可能或没有必要的，因此用数值概率算法可得到相当满意的解。 31.蒙特卡罗算法

用于求问题的准确解。对于许多问题来说，近似解毫无意义。例如，一个判定问题其解为“是”或“否”，二者必居其一，不存在任何近似解答。又如，我们要求一个整数的因子时所给出的解答必须是准确的，一个整数的近似因子没有任何意义。用蒙特卡罗算法能求得问题的一个解，但这个解未必是正确的。求得正确解的概率依赖于算法所用的时间。算法所用的

?