算法设计与分析答案2023

第七章测试

1.快速排序问题属于( )
A:难解问题 B:NP难问题
C:易解问题 D:不可解问题
答案:C
2.能够用动态规划算法求解的问题一定属于( )
A:易解问题 B:难解问题 C:NP问题 D:NP难问题
3.停机问题不属于( )
A:NP难问题
B:难解问题 C:不可计算问题 D:决策问题 4.下面的问题属于NP问题的有（ ）
A:定理识别问题
B:矩阵乘法链问题
C:找出图中所有点对的最短路径问题
D:计算两个正整数的最大公约数
5.NP完全题可能属于( )
A:P类问题
B:NP类问题
C:NP难问题
D:难解问题
6.关于多项式规约，下面叙述正确的是( )
A:所有的NPC问题都可以多项式地规约到NP难问题
B:所有的NP类问题都可以多项式地规约到P类问题
C:所有的P类问题都可以多项式地规约到NP类问题
D:所有的NP类问题都可以多项式地规约到NP难问题
7.素数检验问题属于难解问题（ ）
A:错 B:对 8.利用穷举因子的方法判断一个数是否为合数的算法时间复杂性具有伪多项式界。（ ）
A:错 B:对 9.非确定性算法与算法的确定性是相互矛盾的。（ ）
A:对 B:错 10.问题X可以多项式地规约到Y，意味着X至多与Y一样难。 （ ）
A:错 B:对