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

单选题

回溯算法解0-1背包问题所需的计算时间为()。

A. O(nlogn)
B. O(2n)
C. O(n2)
D. O(n2n)

单选题

回溯算法解最大团问题所需的计算时间为()。

A. O(nlogn)
B. O(n2n)
C. O(n2)
D. O(2n)

单选题

回溯算法解旅行售货员问题所需的计算时间为()。

A. O(nlogn)
B. O(n2n)
C. O(n!)
D. O(2n)

单选题

在用回溯法解具体问题的具体实例时,可用()方法估算将产生的节点数。

A. 猜测方法
B. 枚举方法
C. 概率方法
D. 预设方法

单选题

在回溯法解连续邮资问题时,用n元组x[1:n]表示n种不同的邮票面值,并约定它们从小到大排列。x[1]=1是唯一选择,此时最大连续邮资区间为[1:m]。x[2]的可取值范围是[2:m+1]。一般情况下,已选定x[1:i-1],最大连续邮资区间为[1:r]。则x[i]的可取值范围为()。

A. [x[i-1]+1:r+1]
B. [x[i-1]*2:r]
C. [x[i-1]+1:l+1]
D. [x[i-1]*2:l]

单选题

电路板排列问题,是()。

A. P问题,不大可能找到解此问题的多项式时间算法
B. NPC问题,可找到解此问题的多项式时间算法
C. NP问题,不大可能找到解此问题的多项式时间算法
D. P问题,可找到解此问题的多项式时间算法

单选题

当n>10时,圆排列问题产生的解空间树的节点数,明显()装载问题所产生的解空间树节点数。

A. 大于
B. 小于
C. 等于
D. 近似于

单选题

在用回溯法解符号三角形问题时,可以用()来表示其解空间。

A. 无向图
B. 完全二叉树
C. 有向图
D. 任意二叉树

单选题

在用回溯法解题时,若解空间树中从根节点到叶节点的最长路径为h(n),则回溯法所需的计算空间通常为()。

A. O(2h(n))
B. O(h(n)2)
C. O(h(n))
D. O(n2)

单选题

在用回溯法解题时,若解空间树中从根节点到叶节点的最长路径为h(n),则显式地存储整个解空间树所需空间通常为O(2h(n))或()。

A. O(2h(n))
B. O(h(n)!)
C. O(h(n))
D. O(n2)

8