算法分析与设计答案2023

第九章测试

1.

分支限界法在对问题的解空间树进行搜索的方法中，一个活结点有多次机会成为活结点。

A:错 B:对
答案:A
2.

分支限界法找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

A:对 B:错 3.

队列式分支限界法以最小耗费优先的方式搜索解空间树。

A:错 B:对 4.

优先队列式分支限界法按照队列先进先出的原则，选取下一个节点为扩展结点。

A:错 B:对 5.

分支限界法解旅行商问题时的解空间树是

A:子集树 B:排列树 C:深度优先生成树 D:广度优先生成树 6.

优先队列式分支限界法选取扩展结点的原则是

A:结点的优先级 B:随机 C:先进先出 D:后进先出 7.

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

A:以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索 B:针对所给问题，定义问题的解空间（对解进行编码） C:定义最优子结构 D:确定易于搜索的解空间结构（按树或图组织解） 8.

分支限界法与回溯法的不同点是什么？

A:存储空间的要求不同 B:求解目标不同 C:对扩展结点的扩展方式不同 D:搜索方式不同 9.

FIFO是（  ）的搜索方式。

A:回溯算法 B:贪心算法

C:动态规划 D:分支限界
10.

下面说法不正确的是（）

A: 用约束函数在扩展结点处剪去不满足约束的子树 B:回溯和分支限界都是动态生成解空间树 C:使用限界函数作优先级, 第一个加入队列的叶子就是最优解 D:用限界函数剪去得不到最优解的子树 11.

在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（    ）。

A:回溯求解子集树问题
B:分支限界
C:回溯和分支限界
D:回溯
12.使用限界函数作优先级, 第一个扩展的叶子就是最优解
A:对 B:错 13.分支限界法不能解决0/1背包问题
A:错 B:对