第十三章单元测试

当前位置：首页 ＞课程 ＞算法分析与设计

1、给定问题p，若有算法A，存在一个常数K>=0，使得问题p的所有实例I，总有：|A(I)-OPT(I)|<=K,则称算法A为解答问题p的绝对近似算法。

A、对
B、错

参考答案：请扫码使用小程序查看答案

2、NP-hard 问题属于NP

A、对
B、错

参考答案：请扫码使用小程序查看答案

3、当P不等于NP时，NP-hard优化问题存在多项式时间绝对近似算法。

A、对
B、错

参考答案：请扫码使用小程序查看答案

4、绝大多数NP-hard问题存在多项式时间绝对近似算法

A、对
B、错

参考答案：请扫码使用小程序查看答案

5、若P不等于NP，则最大独立集问题存在多项式时间绝对近似算法。

A、对
B、错

参考答案：请扫码使用小程序查看答案

6、最大优化问题的近似性能比小于1，越接近1越说明算法好

A、对
B、错

参考答案：请扫码使用小程序查看答案

7、多项式时间近似方案的近似性能比是1 + q，q>0.

A、对
B、错

参考答案：请扫码使用小程序查看答案

8、多项式时间近似方案的时间复杂度是P(n, 1/ q) ，P是多项式函数, q>0。

A、对
B、错

参考答案：请扫码使用小程序查看答案

9、近似算法的设计方法有（）

A、贪心
B、组合技术
C、定价法
D、线性规划和舍入

参考答案：请扫码使用小程序查看答案

10、下面说法错误的是（）

A、近似性能比不可能小于1
B、完全多项式时间近似方案的近似性能比是1+p，p>
0
C、NP-hard 与NPC 区别是否属于NP NP-hard 与NPC 区别是否属于NP
D、旅行商问题的近似性能比不会小于2

参考答案：请扫码使用小程序查看答案

算法分析与设计