超星 - 第5章课后练习 - 查题吧

单选题

用()方法对解空间树进行搜索时,每个节点有多次机会成为()。

A. 深度优先、活节点
B. 广度优先、死节点
C. 深度优先、死节点
D. 广度优先、活节点

单选题

旅行售货商问题是()。

A. P问题
B. NPC问题
C. NP问题
D. NC问题

单选题

在使用回溯算法求解问题时,解空间的结构一经选定,只有()因问题实例不同而改变。

A. 产生x[k]的时间
B. 计算约束函数的时间
C. 满足约束函数和上界函数约束的所有x[k]的个数
D. 满足显约束x[k]值得个数

单选题

回溯法解题通常包含的步骤中,不包含()。

A. 确定易于搜索的解空间结构
B. 针对所给问题,定义问题的解空间
C. 枚举所有可能的解,并通过搜索到的解优化解空间结构
D. 以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索

单选题

已知n+1个正数:Wi(1<=i<=n)和M,要找出Wi的和数是M的所有子集。其解可以表示为n元组(x1,x2,…,xn),xi∈{0,1},(1<=i<=n)。即若选择Wi,则xi=1,否则,xi=0。此解空间的状态空间树有()个节点。

A. 2n-1
B. 2n-1
C. 2n
D. 2n

单选题

回溯法解批处理作业调度问题时的解空间树是()。

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

单选题

通常衡量回溯法实现方式及优化方法好坏的标准是()。

A. 运行速度快
B. 代码短
C. 占用空间少
D. 时间复杂度低

单选题

下列算法中,通常使用深度优先方式系统搜索问题的解的是()。

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

单选题

回溯法的效率不依赖于()。

A. 计算约束函数的时间
B. 确定解空间的时间
C. 计算限界函数的时间
D. 满足显约束的值的个数

单选题

下面在回溯法中为避免无效搜索所采取的函数是()。

A. 递归函数
B. 迭代函数
C. 剪枝函数
D. 随机数函数

9