2024知到答案 Advanced Operations Research（上海大学） 最新智慧树满分章节测试答案

1、单选题：
求解一个规模为n的问题，一个特定的算法所需要的计算步数是2358+1000000log(n)+67n2+9n4，那么这个算法的时间复杂度应该是（ ）。
选项：
A:O(9n4)
B:O(n2)
C:O(n4)
D:O(log(n))
答案: 【O(n4)】

2、单选题：
已知c>1, 以下算法复杂度，效率最高的是（ ）。
选项：
A:O(nc)
B:O(n2)
C:O((log(n))c) ,
D:O(n)
答案: 【O((log(n))c) ,】

3、判断题：
NP完全问题是最难的P问题。（ ）
选项：
A:对
B:错
答案: 【错】

4、判断题：
NP完全问题是求解难度最低的NP-Hard问题。（ ）
选项：
A:错
B:对
答案: 【对】

5、判断题：
如果一个问题A可以多项式时间可解，那么问题B就一定多项式时间可解，我们就说问题A可以多项式规约到问题B。（ ）
选项：
A:错
B:对
答案: 【错】

6、判断题：
如果我们找到了一个求解SAT问题的多项式时间算法，那么P问题就等于NP问题。（ ）
选项：
A:错
B:对
答案: 【对】

7、判断题：
如果我们找到了一个求解3划分问题的多项式时间算法，那么划分问题也就可以多项式时间可解了。（ ）
选项：
A:对
B:错
答案: 【对】

8、判断题：
判定性问题是答案只有对和错的问题。（ ）
选项：
A:对
B:错
答案: 【对】

9、判断题：
因为所有的NP完全问题都没有办法在多项式时间内求解，而NP-hard的难度最小又是NP完全问题的难度，所以不存在求解NP-hard问题的多项式时间算法（ ）
选项：
A:错
B:对
答案: 【错】

10、判断题：
时间复杂度为O(1.01n)的算法优于时间复杂度为O(n8888)的算法。（ ）
选项：
A:对
B:错
答案: 【错】

11、判断题：
NP-Hard问题可能是NP完全问题，但是NP完全问题不一定是NP-Hard问题。（ ）
选项：
A:对
B:错
答案: 【错】