在对问题的解空间树进行搜索的方法中，一个活结点有多次机会成为活结点的是（）A、回溯法B、分支限界法C、回溯法和分支限界法D、动态规划

第1题：

第2题：

解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是（），需要排序的是（），（）。

正确答案:动态规划；回溯法；分支限界法

第3题：

用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h（n），则回溯法所需的计算空间通常为（）

正确答案:O(h(n))

第4题：

比较回溯法和分支限界法的搜索方式，哪种方法更适合找最优解问题？

正确答案: 1）回溯法是在约束下带跳跃的深度优先搜索。
2）分枝限界是广度优先方式的按最小代价选择扩展节点，以上界函数对活节点进行限界的搜索。
3）分枝限界法更适合找最优解。

第5题：

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

• A、回溯法
• B、分支限界法
• C、回溯法和分支限界法
• D、回溯法求解子集树问题

正确答案:B

第6题：

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

• A、广度优先
• B、活结点优先
• C、扩展结点优先
• D、深度优先

正确答案:D

第7题：

第8题：

第9题：

第10题：

第11题：

第12题：

第13题：

第14题：

回溯算法和分支限界法的问题的解空间树不会是（）

• A、有序树
• B、子集树
• C、排列树
• D、无序树

正确答案:D

第15题：

关于回溯算法和分支限界法，以下（）是不正确描述。

• A、回溯法中，每个活结点只有一次机会成为扩展结点
• B、分支限界法中，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子加入活结点表中
• C、回溯法采用深度优先的结点生成策略
• D、分支限界法采用广度优先或最小耗费优先（最大效益优先）的结点生成策略

正确答案:A

第16题：

下列算法中不能解决0/1背包问题的是（）

• A、贪心法
• B、动态规划
• C、回溯法
• D、分支限界法

正确答案:A

第17题：

关于回溯搜索法的介绍，下面（）是不正确描述。

• A、回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解
• B、回溯法是一种既带系统性又带有跳跃性的搜索算法
• C、回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯
• D、回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径

正确答案:D

第18题：

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

• A、广度优先
• B、活结点优先
• C、扩展结点优先
• D、深度优先

正确答案:A

第19题：

第20题：

第21题：

第22题：

第23题：