. 下列关于算法的说法中正确的有（ ）。  

. 求解某一类问题的算法是唯一的  

. 算法必须在有限步操作之后停止  

. 算法的每一步操作必须是明确的，不能有歧义或含义模糊  

. 算法执行后一定产生确定的结果  

. T ( n ) 表示当输入规模为 n 时的算法效率，以下算法效率最优的是（ ）。  

. 什么是算法？算法有哪些特征？  

. 判断一个大于 2 的正整数 n 是否为素数的方法有多种，给出两种算法，说明其中  

一种算法更好的理由。  

有一个含 n （ n >2 ）个整数的数组 a ，判断其中是否存在出现次数超过所有元素一  

. 一个字符串采用 string 对象存储，设计一个算法判断该字符串是否为回文。  

. 有一个整数序列，设计一个算法判断其中是否存在两个元素和恰好等于给定的整  

0. 有两个整数序列，每个整数序列中所有元素均不相同。设计一个算法求它们的公  

共元素，要求不使用 STL 的集合算法。  

1. 正整数 n （ n >1 ）可以写成质数的乘积形式，称为整数的质因数分解。例如，  

2. 有一个整数序列，所有元素均不相同，设计一个算法求相差最小的元素对的个  

数。如序列 4 、 1 、 2 、 3 的相差最小的元素对的个数是 3 ，其元素对是（

，设计一个算法出栈从栈顶  

到栈底的第 k （ 1 ≤ k ≤ n ）个元素，其他栈元素不变。  

答： 由于算法具有有穷性、确定性和输出性，因而Ⅱ、Ⅲ、Ⅳ正确，而解决某一  

类问题的算法不一定是唯一的。答案为 C 。  

答： 选项 A 的时间复杂度为 O( n ) 。选项 B 的时间复杂度为 O(

答： 算法是求解问题的一系列计算步骤。算法具有有限性、确定性、可行性、输  

入性和输出性 5 个重要特征。  

方法 1 的时间复杂度为 O( n ) ，方法 2 的时间复杂度为 ⁿ

)) ，存在正常数 c ₁ 和正常数 n ₁ ，使得对所有 n ≥

)) ，存在正常数 c ₂ 和自然数 n ₂ ，使得对所有 n ≥

. 解： 先将 a 中元素递增排序，再求出现次数最多的次数 maxnum ，最后判断是否满  

足条件。对应的程序如下：  

上述程序的执行结果如图 1.1 所示。  

. 解： 采用前后字符判断方法，对应的程序如下：  

上述程序的执行结果如图 1.2 所示。  

. 解： 先将 a 中元素递增排序，然后从两端开始进行判断。对应的程序如下：  

// 区间中存在两个或者以上元素  

上述程序的执行结果如图 1.3 所示。  

0. 解： 采用集合 set<int> 存储整数序列，集合中元素默认是递增排序的，再采用二  

路归并算法求它们的交集。对应的程序如下：  

上述程序的执行结果如图 1.4 所示。  

1. 解： 对于正整数 n ，从 i =2 开始查找其质因数， ic 记录质因数 i 出现的次数，当找  

到这样质因数后，将（ i ， ic ）作为一个元素插入到 vector 容器 v 中。最后输出 v

上述程序的执行结果如图 1.5 所示。  

2. 解： 先递增排序，再求相邻元素差，比较求最小元素差，累计最小元素差的个  

数。对应的程序如下：  

上述程序的执行结果如图 1.6 所示。  

将前者的 value 作为后者的关键字。遍历 mymap ，累计 tmap 中相同关键字的次数。一个  

参考程序及其输出结果如下：  

上述程序的执行结果如图 1.7 所示。  

二个分量存放质因数出现次数。对应的程序如下：  

上述程序的执行结果如图 1.8 所示。  

5. 解： 栈容器不能顺序遍历，为此创建一个临时 tmpst 栈，将 st 的 k 个元素出栈并  

栈到 st 中。对应的程序如下：  

上述程序的执行结果如图 1.9 所示。  

. 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？  

. 分析以下程序的执行结果：  

. 采用直接推导方法求解以下递归方程：  

. 采用特征方程方法求解以下递归方程：  

. 采用递归树方法求解以下递归方程：  

. 采用主方法求解以下题的递归方程。  

数列的首项 a ₁ =0 ，后续奇数项和偶数项的计算公式分别为 a _{2 n} =a

对于一个采用字符数组存放的字符串 str ，设计一个递归算法求其字符个数（长  

对于一个采用字符数组存放的字符串 str ，设计一个递归算法判断 str 是否为回  

1. 对于不带头结点的单链表 L ，设计一个递归算法正序输出所有结点值。  

2. 对于不带头结点的单链表 L ，设计一个递归算法逆序输出所有结点值。  

3. 对于不带头结点的非空单链表 L ，设计一个递归算法返回最大值结点的地址（假  

设这样的结点唯一）。  

4. 对于不带头结点的单链表 L ，设计一个递归算法返回第一个值为 x 的结点的地  

5. 对于不带头结点的单链表 L ，设计一个递归算法删除第一个值为 x 的结点。  

6. 假设二叉树采用二叉链存储结构存放，结点值为 int 类型，设计一个递归算法求  

二叉树 bt 中所有叶子结点值之和。  

7. 假设二叉树采用二叉链存储结构存放，结点值为 int 类型，设计一个递归算法求  

二叉树 bt 中所有结点值大于等于 k 的结点个数。  

8. 假设二叉树采用二叉链存储结构存放，所有结点值均不相同，设计一个递归算法  

求值为 x 的结点的层次（根结点的层次为 1 ），没有找到这样的结点时返回 0 。  

答： 一个 f 函数定义中直接调用 f 函数自己，称为直接递归。一个 f 函数定义中调  

用 g 函数，而 g 函数的定义中调用 f 函数，称为间接递归。消除递归一般要用栈实现。  

是引用参数，所以递归函数的状态为  

n ）。程序执行结果如下：  

. 解： 整数一个常系数的线性齐次递推式，用 x ⁿ 代替 H ( n )

解： 构造的递归树如图 1.10 所示，第 1 层的问题规模为 n ，第 2 的层的子问题的  

问题规模为 n /2 ，依此类推，当展开到第 k +1 层，其规模为 n /2 ^k

第 1 层有 1 个结点，其时间为 n ，第 2 层有 4 个结点，其时间为

个，其时间为 n 。将递归树每一层的时间加起来，可得：  

= n ² ，它与 f ( n ) 一样大，满足主定理中的情况（ 2 ），所以

对应的递归算法如下：  

对应的递归程序如下：  

上述程序的执行结果如图 1.11 所示。  

str 是否为回文，其递归模型如下：  

对应的递归算法如下：  

上述程序的执行结果如图 1.12 所示。  

1. 解： 设 f (L) 正序输出单链表 L 的所有结点值，其递归模型如下：  

对应的递归程序如下：  

// 包含单链表的基本运算算法  

上述程序的执行结果如图 1.13 所示。  

2. 解： 设 f (L) 逆序输出单链表 L 的所有结点值，其递归模型如下：  

对应的递归程序如下：  

// 包含单链表的基本运算算法  

上述程序的执行结果如图 1.14 所示。  

3. 解： 设 f (L) 返回单链表 L 中值最大结点的地址，其递归模型如下：  

对应的递归程序如下：  

// 包含单链表的基本运算算法  

上述程序的执行结果如图 1.15 所示。  

的结点的地址，其递归模型如下：  

对应的递归程序如下：  

// 包含单链表的基本运算算法  

上述程序的执行结果如图 1.16 所示。  

的结点，其递归模型如下：  

对应的递归程序如下：  

// 包含单链表的基本运算算法  

上述程序的执行结果如图 1.17 所示。  

6. 解： 设 f (bt) 返回二叉树 bt 中所有叶子结点值之和，其递归模型如下：  

对应的递归程序如下：  

// 包含二叉树的基本运算算法  

上述程序的执行结果如图 1.18 所示。  

k 的结点个数，其递归模型  

对应的递归程序如下：  

// 包含二叉树的基本运算算法  

上述程序的执行结果如图 1.19 所示。  

次，初始调用时， bt 指向根结点， h 置为 1 。其递归模型如下：  

对应的递归程序如下：  

// 包含二叉树的基本运算算法  

// 在左子树中找到，返回其层次 l  

上述程序的执行结果如图 1.20 所示。  

分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分  

别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题  

A. 问题规模相同，问题性质相同  

B. 问题规模相同，问题性质不同  

C. 问题规模不同，问题性质相同  

D. 问题规模不同，问题性质不同  

在寻找 n 个元素中第 k 小元素问题中，如快速排序算法思想，运用分治算法对 n  

个元素进行划分，如何选择划分基准？下面（ ）答案解释最合理。  

A. 随机选择一个元素作为划分基准  

B. 取子序列的第一个元素作为划分基准  

C. 用中位数的中位数方法寻找划分基准  

D. 以上皆可行。但不同方法，算法复杂度上界可能不同  

. 对于下列二分查找算法，以下正确的是（ ）。  

. 快速排序算法是根据分治策略来设计的，简述其基本思想。  

. 以下哪些算法采用分治策略：  

. 适合并行计算的问题通常表现出哪些特征？  

. 有 4 个数组 a 、 b 、 c 和 d ，都已经排好序，说明找出这 4 个数组的交集的方法。  

0. 设计一个算法，采用分治法求一个整数序列中的最大最小元素。  

2. 假设二叉树采用二叉链存储结构进行存储。设计一个算法采用分治法求一棵二叉  

3. 假设二叉树采用二叉链存储结构进行存储。设计一个算法采用分治法求一棵二叉  

4. 有一种二叉排序树，其定义是空树是一棵二叉排序树，若不空，左子树中所有结  

点值小于根结点值，右子树中所有结点值大于根结点值，并且左右子树都是二叉排序树。  

现在该二叉排序树采用二叉链存储，采用分治法设计查找值为 x 的结点地址，并分析算法  

的最好的平均时间复杂度。  

5. 设有 n 个互不相同的整数，按递增顺序存放在数组 a [0.. n - 1] 中，若存在一个下标  

6. 请你模仿二分查找过程设计一个三分查找算法。分析其时间复杂度。  

8. 设计一个基于 BSP 模型的并行算法，假设有 p 台处理器，计算整数数组 a [0.. n -

的所有元素之和。并分析算法的时间复杂度。  

5} 为例说明。选项 A 中在查找 5 时出现死循环。选项 B  

4. 答： 对于无序序列 a [low..high] 进行快速排序，整个排序为“大问题”。选择其中的  

一个基准 base= a [ i ] （通常以序列中第一个元素为基准），将所有小于等于 base 的元素移动  

到它的前面，所有大于等于 base 的元素移动到它的后面，即将基准归位到 a [ i ] ，这样产生  

两个无序序列，它们的排序为“小问题”。当 a [low..high] 序列只  

有一个元素或者为空时对应递归出口。  

所以快速排序算法就是采用分治策略，将一个“大问题”分解为两个“小问题”来求  

解。由于元素都是在 a 数组中，其合并过程是自然产生的，不需要特别设计。  

答： 此时快速排序对应的递归树高度为 O( n ) ，每一次划分对应的时间为 O( n ) ，所  

. 答： 其中二路归并排序和折半查找算法采用分治策略。  

. 答： 适合并行计算的问题通常表现出以下特征：  

1 ）将工作分离成离散部分，有助于同时解决。例如，对于分治法设计的串行算  

法，可以将各个独立的子问题并行求解，最后合并成整个问题的解，从而转化为并行算  

2 ）随时并及时地执行多个程序指令。  

3 ）多计算资源下解决问题的耗时要少于单个计算资源下的耗时。  

答： 采用基本的二路归并思路，先求出 a 、 b 的交集 ab ，再求出 c 、 d

最后求出 ab 和 cd 的交集，即为最后的结果。也可以直接采用 4 路归并方法求解。  

0. 解： 采用类似求求一个整数序列中的最大次大元素的分治法思路。对应的程序如  

上述程序的执行结果如图 1.21 所示。  

，采用分治法求解对应的递归模型如下：  

对应的递归程序如下：  

上述程序的执行结果如图 1.22 所示。  

对应的程序如下：  

// 包含二叉树的基本运算算法  

上述程序的执行结果如图 1.23 所示。  

3. 解： 设 f (bt) 返回二叉树 bt 中度为 2 的结点个数，对应的递归模型如下：  

对应的算法如下：  

// 包含二叉树的基本运算算法  

上述程序的执行结果如图 1.24 所示。  

x 结点的地址，若没有找到返回  

空，对应的递归模型如下：  

对应的程序如下：  

// 包含二叉树的基本运算算法  

上述程序的执行结果如图 1.25 所示。  

Search(bt ， x ) 算法采用的是减治法，最好的情况是某个结点左右子树高度大致相同，  

15. 解： 采用二分查找方法。 a [ i ]= i 时表示该元素在有序非重复序列 a 中恰好第

说明右区间的所有元素都大于其位置，只能在左区间中查找；若 a [mid]<mid 说明左区间  

的所有元素都小于其位置，只能在右区间中查找。对应的程序如下：  

// 这样的元素只能在右区间中出现  

// 这样的元素只能在左区间中出现  

上述程序的执行结果如图 1.26 所示。  

) 级别。对应的算法如下：  

上述程序的执行结果如图 1.27 所示。  

以此类推，可以看出 f ( n ) 为 n 的所有因数的不同分解式个数之和，即 f ( n

上述程序的执行结果如图 1.28 所示。  

8. 解： 对应的并行算法如下：  

每个处理器的执行时间为 O( n / p ) ，同步开销为 O( p ) ，所以该算法的时间复杂度为

. 简要比较蛮力法和分治法。  

. 在采用蛮力法求解时什么情况下使用递归？  

考虑下面这个算法，它求的是数组 a 中大小相差最小的两个元素的差。请对这个  

算法做尽可能多的改进。  

对。例如数组（ 3 ， 1 ， 4 ， 5 ， 2 ）的逆序对有

个算法采用蛮力法求 A 中逆序对的个数即逆序数。  

有一群鸡和一群兔，它们的只数相同，它们的脚数都是三位数，且这两个三位数  

。设计一个算法用蛮力法求鸡和兔的只数各是多  

少？它们的脚数各是多少？  

有一个三位数，个位数字比百位数字大，而百位数字又比十位数字大，并且各位  

数字之和等于各位数字相乘之积，设计一个算法用穷举法求此三位数。  

. 某年级的同学集体去公园划船，如果每只船坐 10 人，那么多出 2 个座位；如果每  

只船多坐 2 人，那么可少租 1 只船，设计一个算法用蛮力法求该年级的最多人数？  

已知：若一个合数的质因数分解式逐位相加之和等于其本身逐位相加之和，则称  

求解涂棋盘问题。小易有一块 n * n 的棋盘，棋盘的每一个格子都为黑色或者白  

色，小易现在要用他喜欢的红色去涂画棋盘。小易会找出棋盘中某一列中拥有相同颜色的  

最大的区域去涂画，帮助小易算算他会涂画多少个棋格。  

输入描述：输入数据包括 n +1 行：第一行为一个整数 n （ 1 ≤  

小，接下来的 n 行每行一个字符串表示第 i 行棋盘的颜色， 'W' 表示白色， 'B' 表示黑色。  

输出描述：输出小易会涂画的区域大小。  

1. 给定一个含 n （ n >1 ）个整数元素的 a ，所有元素不相同，采用蛮力法求出 a

有元素的全排列。  

答： 蛮力法是一种简单直接地解决问题的方法，适用范围广，是能解决几乎所有  

问题的一般性方法，常用于一些非常基本、但又十分重要的算法（排序、查找、矩阵乘法  

和字符串匹配等），蛮力法主要解决一些规模小或价值低的问题，可以作为同样问题的更  

高效算法的一个标准。而分治法采用分而治之思路，把一个复杂的问题分成两个或更多的  

相同或相似的子问题，再把子问题分成更小的子问题直到问题解决。分治法在求解问题  

时，通常性能比蛮力法好。  

答： 如果用蛮力法求解的问题可以分解为若干个规模较小的相似子问题，此时可  

以采用递归来实现算法。  

. 解： 上述算法的时间复杂度为 O( n ² ) ，采用的是最基本的蛮力法。可以先对 a 中元

素递增排序，然后依次比较相邻元素的差，求出最小差，改进后的算法如下：  

上述算法的主要时间花费在排序上，算法的时间复杂度为 O( n log ₂ n ) 。  

. 解： 采用两重循环直接判断是否为逆序对，算法的时间复杂度为 O(n2) ，比第 3 章  

实验 3 算法的性能差。对应的算法如下：  

. 解： 直接采用蛮力法求解算法如下：  

1) 的结果。改进后的算法如  

用 6 重循环，求出鸡只数 x1= y /2 （ y 是 2 的倍数），兔只数

x1=x2 时输出结果。对应的程序如下：  

上述程序的执行结果如图 1.29 所示。  

上述程序的执行结果如图 1.30 所示。  

. 解： 设该年级的人数为 x ，租船数为 y 。因为每只船坐 10 人正好多出 2 个座位，则

只船（没有说恰好全部座位占满），有  

的结果是相同的）、 z 从 0 到 11 枚举，求出最大的 x 即可。对应的程序如下：  

上述程序的执行结果如图 1.31 所示。  

. 解： 采用蛮力法求出一个正整数 n 的各位数字和 sum1 ，以及 n 的所有质因数的数  

数，输出，本次结束，否则 n ++ 继续查找大于 n 的最小 Smitch 数。对应的完整程序如  

0. 解： 采用蛮力法，统计每一列相邻相同颜色的棋格个数 countj ，在 countj 中求最  

大值。对应的程序如下：  

// 统计第 j 列中相同颜色相邻棋格个数  

1. 解： 与《教程》中求全排列类似，但需要将求 1 ～ n 的全排列改为按下标 0 ～ n -

求 a 的全排列（下标从 0 开始）。采用非递归的程序如下：  

上述程序的执行结果如图 1.32 所示。  

. 回溯法在问题的解空间树中，按（ ）策略，从根结点出发搜索解空间树。  

. 关于回溯法以下叙述中不正确的是（ ）。  

A. 回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解  

B. 回溯法是一种既带系统性又带有跳跃性的搜索算法  

C. 回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径  

D. 回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果  

肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯  

3. 回溯法的效率不依赖于下列哪些因素（ ）。  

. 下面（ ）函数是回溯法中为避免无效搜索采取的策略。  

. 回溯法的搜索特点是什么？  

. 用回溯法解 0/1 背包问题时，该问题的解空间是何种结构？用回溯法解流水作业调  

度问题时，该问题的解空间是何种结构？  

的排列一定最先出现吗？为什么？  

考虑 n 皇后问题，其解空间树为由 1 、 2 、…、 n 构成的 n ! 种排列所组成。现用回  

溯法求解，要求：  

1 ）通过解搜索空间说明 n =3 时是无解的。  

3 ）最坏情况下在解空间树上会生成多少个结点？分析算法的时间复杂度。  

设计一个算法求解简单装载问题，设有一批集装箱要装上一艘载重量为 W 的轮  

船，其中编号为 i （ 0 ≤ i ≤ n - 1 ）的集装箱的重量为 w _i 。现要从 n 个集装箱中选出若干装上  

轮船，使它们的重量之和正好为 W 。如果找到任一种解返回 true ，否则返回 false 。  

_{- 1} ，从中选出若干数，使它们的和恰好为 k ，  

要求找选择元素个数最少的解。  

1. 设计求解有重复元素的排列问题的算法，设有 n 个元素 a []={ a ₀ ， a

其中可能含有重复的元素，求这些元素的所有不同排列。如 a []={1 ， 1 ， 2} ，输出结果是  

2. 采用递归回溯法设计一个算法求 1 ～ n 的 n 个整数中取出 m 个元素的排列，要求每个  

元素最多只能取一次。例如， n =3 ， m =2 的输出结果是（ 1 ， 2 ），（

3. 对于 n 皇后问题，有人认为当 n 为偶数时，其解具有对称性，即 n 皇后问题的解个  

数恰好为 n /2 皇后问题的解个数的 2 倍，这个结论正确吗？请编写回溯法程序对 n =4 、 6

4. 给定一个无向图，由指定的起点前往指定的终点，途中经过所有其他顶点且只经  

过一次，称为哈密顿路径，闭合的哈密顿路径称作哈密顿回路（ Hamiltonian cycle ）。设计  

一个回溯算法求无向图的所有哈密顿回路。  

. 答： 回溯算法是采用深度优先遍历的，需要借助系统栈结构来保存从根结点到当  

前扩展结点的路径。答案为 C 。  

. 答： 回溯法解空间是虚拟的，不必确定整个解空间。答案为 A 。  

答： 回溯法在解空间树中采用深度优先遍历方式进行解搜索，即用约束条件和限  

界函数考察解向量元素 x [ i ] 的取值，如果 x [ i ] 是合理的就搜索

. 答： 用回溯法解 0/1 背包问题时，该问题的解空间是子集树结构。用回溯法解流水  

作业调度问题时，该问题的解空间是排列树结构。  

答： 是的。对应的解空间是一棵排列树，如图 1.33 所示给出前面 3 层部分，显然  

最先产生的排列是从 G 结点扩展出来的叶子结点，它们就是以 1 、 2 开头的排列。  

答： （ 1 ） n =3 时的解搜索空间如图 1.34 所示，不能得到任何叶子结点，所有无  

2 ）剪枝操作是任何两个皇后不能同行、同列和同两条对角线。  

3 ）最坏情况下每个结点扩展 n 个结点，共有 n ⁿ 个结点，算法的时间复杂度为  

解： 用数组 w [0.. n - 1] 存放 n 个集装箱的重量，采用类似判断子集和是否存在解的  

方法求解。对应完整的求解程序如下：  

// 左孩子结点剪枝：选取满足条件的集装箱 w[i]  

// 右孩子结点剪枝：剪除不可能存在解的结点  

// 判断简单装载问题是否存在解  

0. 解： 这是一个典型的解空间为子集树的问题，采用子集树的回溯算法框架。当找  

到一个解后通过选取的元素个数进行比较求最优解 minpath 。对应的完整程序如下：  

// 如果找到一个解，不一定到叶子结点  

上述程序的执行结果如图 1.36 所示。  

1. 解： 在回溯法求全排列的基础上，增加元素的重复性判断。例如，对于 a []={1 ，  

6 个，有 3 个是重复的。重复性判断是这样的，对于在扩  

的位置，如果出现，对应的排

列已经在前面求出了。对应的完整程序如下：  

// 求有重复元素的排列问题  

上述程序的执行结果如图 1.37 所示。  

2. 解： 采用求全排列的递归框架。选取的元素个数用 i 表示（ i 从 1 开始），当 i

时达到一个叶子结点，输出一个排列。为了避免重复，用 used 数组实现， used[ i ]=0 表示  

// 继续搜索排列的下一个元素  

上述程序的执行结果如图 1.38 所示。  

3. 解： 这个结论不正确。验证程序如下：  

上述程序的执行结果如图 1.39 所示。从执行结果看出结论是不正确的。  

4. 解： 假设给定的无向图有 n 个顶点（顶点编号从 0 到 n - 1 ），采用邻接矩阵数组

0/1 矩阵）存放，求从顶点 v 出发回到顶点 v 的哈密顿回路。采用回溯法，解向量为  

v 有边对应一个解；否则继续查找下一个顶点。如果不能  

为 x [ i ] 找到一个合适的顶点，则回溯。采用非递归回溯框架（与《教程》中求解 n 皇后问  

题的非递归回溯框架类似）的完整程序如下：  

上述程序对如图 1.40 所示的无向图求从每个顶点出发的哈密顿回路，程序执行结果  

. 分枝限界法在问题的解空间树中，按（ ）策略，从根结点出发搜索解空间树。  

. 常见的两种分枝限界法为（ ）。  

A. 广度优先分枝限界法与深度优先分枝限界法  

B. 队列式（ FIFO ）分枝限界法与堆栈式分枝限界法  

D. 队列式（ FIFO ）分枝限界法与优先队列式分枝限界法  

. 分枝限界法求解 0/1 背包问题时，活结点表的组织形式是（ ）。  

. 采用最大效益优先搜索方式的算法是（ ）。  

. 优先队列式分枝限界法选取扩展结点的原则是（ ）。  

. 简述分枝限界法的搜索策略。  

2 ， 25 ， 12 ），背包最大载重量 W =10 ，给出采用优先队列式分枝限界法求最优解的过程。  

用优先队列式分枝限界法求一个解的过程。  

有一个含 n 个顶点（顶点编号为 0 ～ n - 1 ）的带权图，采用邻接矩阵数组 A 表示，

采用分枝限界法求从起点 s 到目标点 t 的最短路径长度，以及具有最短路径长度的路径条  

0. 采用优先队列式分枝限界法求解最优装载问题。给出以下装载问题的求解过程和  

优装载方案是集装箱个数最少的方案。  

答： 分枝限界法的搜索策略是广度优先遍历，通过限界函数可以快速找到一个解  

7 ）出队结点 8 ：左孩子超重；右孩子结点 10 被剪枝。  

8 ）出队结点 6 ：左孩子结点 11 超重；右孩子结点 12 被剪枝。  

2 ）出队结点 1 ：扩展结点如下：  

3 ）出队结点 2 ：扩展结点如下：  

4 ）出队结点 8 ：扩展结点如下：  

5 ）出队结点 10 ，扩展一个 j =2 的子结点，有 e.i=4 ，到达叶子结点，产生的一个解  

该解对应的调度方案是：第 1 步执行作业 1 ，第 2 步执行作业 4 ，第 3 步执行作业

解： 采用优先队列式分枝限界法求解，队列中结点的类型如下：  

从顶点 s 开始广度优先搜索，找到目标点 t 后比较求最短路径长度及其路径条数。对  

应的完整程序如下：  

上述程序的执行结果如图 1.39 所示。  

解： 采用优先队列式分枝限界法求解。设计优先队列  

行比较，即 ub 值越大的结点越先出队。对应的完整程序如下：  

// 搜索空间中结点数累计 , 全局变量  

// 当前结点在解空间中的层次  

上述程序的执行结果如图 1.40 所示。  

. 下面是贪心算法的基本要素的是（ ）。  

. 下面问题（ ）不能使用贪心法解决。  

采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排  

序，故算法的时间复杂度为（ ）。  

. 关于 0/ 1 背包问题以下描述正确的是（ ）。  

A. 可以使用贪心算法找到最优解  

B. 能找到多项式时间的有效算法  

C. 使用教材介绍的动态规划方法可求解任意 0 － 1 背包问题  

D. 对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做 0/1 背包问  

. 一棵哈夫曼树共有 215 个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码