算法分析与设计答案2023

第八章测试

1.

回溯法是按广度优先策略搜索解空间树。

A:错 B:对
答案:A
2.

死结点是正在产生儿子的结点。

A:错 B:对 3.

回溯法的一个显著特征是在搜索过程中动态产生问题的解空间。

A:对 B:错 4.

回溯法不适用于解一些组合数相当大的问题。

A:对 B:错 5.

好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。

A:对 B:错 6.

下列算法中，通常以深度优先方式系统搜索问题解的是（     ）。

A:动态规划法 B:回溯法 C:贪心法 D:备忘录法 7.

装载问题的回溯算法所需的计算时间为

A:O（n） B:O（nlogn） C:O（n²） D:O（2ⁿ） 8.

问题的状态生成法有（）

A:排列树生成法 B:子集树生成法 C:深度优先生成法 D:宽度优先生成法 9.回溯法解题步骤
A:以深度优先方式搜索解空间，在搜索过程中用剪枝函数避免无效搜索。 B:确定易于搜索的解空间结构 C:针对所给问题，定义问题的解空间 D:确定最优子结构的性质 10.回溯法的效率依赖于下列哪些因素（       ）
A:计算约束函数的时间  B:计算限界函数的时间 C:确定解空间的时间 D:满足显约束的值的个数 11.

剪枝函数包括（ ）和约束函数

A:启发式函数
B:最优函数 C:估计函数 D: 限界函数
12.

回溯法搜索解空间时，在搜索试探时选取x[i]的值顺序是任意的，顺序对于计算量没有差别。

A:错 B:对 13.

回溯法中，如果解空间树是排列树，所给问题的规模为n时，遍历排列树需 O( n! ) 计算时间.  

A:错 B:对 14.回溯法的两种解空间树为（）
A:子集树 B:递归树 C:排列树
D:祖先树