超星 - 第五章回溯法 - 查题吧

单选题

用回溯法解批处理作业调度问题时，考虑不同的调度顺序对应不同的解向量，解空间构造为（）形式。

A. 子集树
B. 排列树
C. 最小堆
D. 最大堆

单选题

以下是回溯法解决批处理作业调度问题的关键代码，缺少代码为：for (int j = i; j <= n; j++){ f1+=M[x[j]][1];f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];f+=f2[i];if (f < bestf) {Swap(x[i], x[j]);Backtrack(i+1);Swap(x[i], x[j]);}}

A. f1- =M[x[j]][1];f2[i]- =M[x[j]][2];
B. f2[i]- =M[x[j]][2];f- =f2[i];
C. f1- =M[x[j]][2];f- =f2[i];
D. f1- =M[x[j]][1];f- =f2[i];

单选题

n后问题中,放在同一斜线上的2个皇后(i,j)和(k,l)满足的条件是()。

A. i*j=k*l
B. j=l
C. i-j=k-l
D. |i-k|=|j-l|

单选题

在回溯法求解0-1背包问题时,对第i层的右儿子使用限界函数bound(i+1)判断是否有更优解,该限界函数内部计算过程采用的是()算法。

A. 动态规划
B. 贪心法
C. 回溯法
D. 分治法

单选题

回溯法求解问题时,用于剪去导致不可行解的结点的函数称为( )。

A. 上界函数
B. 限界函数
C. 约束函数
D. 下界函数

判断题

回溯法中使用剪枝策略可以加快解空间树的搜索进程。

A. 对
B. 错

判断题

回溯法是一种穷举式搜索,其时间复杂度达到指数级或对数级,速度较慢。

A. 对
B. 错

1