算法设计与分析答案2023

第五章测试

1.回溯法是指具有限界函数的深度优先生成法。（ ）
A:对 B:错
答案:A
2.用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。（ ）
A:对 B:错 3.用回溯法解批处理作业调度问题时，该问题的解空间结构为子集树结构。（ ）
A:错 B:对 4.在对问题的解空间树进行搜索的方法中，一个结点有多次机会成为活结点的是（ ）。
A:回溯法和分支限界法
B:回溯法
C:分支限界法
D:动态规划
5.回溯法在解空间树T上的搜索方式是（ ）。
A:最小耗费优先
B:深度优先
C:广度优先
D:活结点优先
6.回溯算法和分支限界法的问题的解空间树不会是（ ）。
A:无序树
B:有序树
C:排列树
D:子集树
7.回溯法求问题的所有解时，要回溯到根，且根结点的子树都要已被搜索遍才结束。（ ）
A:错 B:对 8.下列问题中可以用回溯算法解决的是？（ ）
A:货箱装船问题
B:0/1背包问题
C:旅行商问题
D:N皇后问题
9.回溯法的效率不依赖于以下哪一个因素？（ ）
A:满足显约束的 x[k] 值的个数
B:问题的解空间的形式
C:产生 x[k] 的时间
D:计算上界函数 bound 的时间
10.用回溯法解图的 m 着色问题时，使用下面的函数 OK 检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限）（ ）。
A:O(n)
B:O(mn)
C:O(m2)
D:O(m)