算法设计与分析答案2023

第五章测试

1.使用回溯法求解0-1背包问题时，计算右子树上界的方法是通过贪心策略求得上界（ ）
A:错 B:对
答案:B
2.适用回溯法解旅行售货员问题，只有当搜索到最后一个城市时，才能判断当前路径是否是该问题的一个解。（ ）
A:错 B:对 3.下面关于用回溯法解题说法，正确的是( ).
A:显式地存储整个解空间 ；
B:这种方法适用于解一些组合数相当大的问题。
C:解空间树有子集树与排列树两种;
D:在搜索过程中动态产生问题的解空间；
4.回溯法中的剪枝函数包括( )。
A:随机数生成函数
B:限界函数
C:约束函数
D:递归函数
5.回溯法解题步骤,正确的是（ ）
A:针对所给问题，定义问题的解空间;
B:确定最优子结构的性质;
C:以深度优先方式搜索解空间，在搜索过程中用剪枝函数避免无效搜索;
D:确定易于搜索的解空间结构;
6.四色定理是第一个主要由计算机证明的理论（ ）
A:对 B:错