单选题回溯法在解空间树T上的搜索方式是（）A 深度优先B 广度优先C 最小耗费优先D 活结点优先

第1题：

第2题：

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

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

正确答案:A

第3题：

回溯法搜索状态空间树是按照（）的顺序。

• A、中序遍历
• B、广度优先遍历
• C、深度优先遍历
• D、层次优先遍历

正确答案:C

第4题：

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

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

第5题：

回溯法解旅行售货员问题时的解空间树是（）。

• A、子集树
• B、排列树
• C、深度优先生成树
• D、广度优先生成树

正确答案:B

第6题：

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

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

正确答案:D

第7题：

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

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

正确答案:D

第8题：

第9题：

第10题：

第11题：

第12题：

第13题：

回溯法在解空间树T上的搜索方式是（）

• A、深度优先
• B、广度优先
• C、最小耗费优先
• D、活结点优先

正确答案:A

第14题：

回溯法中常见的两类典型的解空间树是什么？并简述其定义。

正确答案: 回溯法中常见的两类典型的解空间树是子集树和排列树。
当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。这类子集树通常有2n个叶结点，遍历子集树需O（2n）计算时间。
当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O（n!）计算时间。

第15题：

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

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

正确答案:D

第16题：

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

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

第17题：

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

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

正确答案:B

第18题：

回溯法搜索解空间树时，常用的两种剪枝函数为（）和（）。

正确答案:约束函数；限界函数

第19题：

第20题：

第21题：

第22题：

第23题：