回溯法解旅行商问题时的解空间树是排列树

第1题：

第2题：

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

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

正确答案:A

第3题：

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

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

正确答案:D

第4题：

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

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

正确答案:B

第5题：

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

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

第6题：

用回溯法解0/1背包问题时，该问题的解空间结构为（）结构。

正确答案:子集树

第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题：

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

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

第16题：

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

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

正确答案:B

第17题：

图的m着色问题可用（）法求解，其解空间树中叶子结点个数是（），解空间树中每个内结点的孩子数是（）。

正确答案:回溯；mⁿ；m

第18题：

用回溯法解批处理作业调度问题时，该问题的解空间结构为（）结构。

正确答案:排列树

第19题：

用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含（）。

正确答案:一个（最优）解

第20题：

第21题：

第22题：

第23题：

第24题：