网友您好， 请在下方输入框内输入要搜索的题目：
题目内容
（请给出正确答案）
41、可解性问题是指能够找到多项式时间复杂性算法进行求解的问题，难解性问题是指找不到多项式时间复杂性算法进行求解的问题。下列说法不正确的是_____。
A．P类问题是可解性问题，NP类问题是难解性问题
B．NP类问题不一定是难解性问题，因为P类问题也一定是NP类问题
C．NP类问题不确定是否是P类问题，但NPC类问题一定是难解性问题
D．上述说法有不正确的
参考答案和解析
A
更多 “41、可解性问题是指能够找到多项式时间复杂性算法进行求解的问题，难解性问题是指找不到多项式时间复杂性算法进行求解的问题。下列说法不正确的是_____。A．P类问题是可解性问题，NP类问题是难解性问题B．NP类问题不一定是难解性问题，因为P类问题也一定是NP类问题C．NP类问题不确定是否是P类问题，但NPC类问题一定是难解性问题D．上述说法有不正确的” 相关考题
考题
设求解某问题的递归算法如下：求解该算法的计算时间时，仅考虑算法Move所做的计算为主要计算，且Move为常数级算法，并设算法Move的计算时间为k，当n=5时，算法F的计算时间为(62)。A．7kB．15kC．31kD．63k
考题
设求解某问题的递归算法如下： F(int n){ if n==1{ Move(1); } else{ F(n-1); Move(n); F(n-1); } } 求解该算法的计算时间时，仅考虑算法Move所进行的计算为主要计算，且Move为常数级算法，设算法Move的计算时间为k，当n=5时，算法F的计算时间为(42)。A．7kB．15kC．31kD．63k
考题
关于概率算法，下述说法中错误的是(15)。A．数值概率算法所求得的往往是近似解，且精度随着计算时间的增长而不断提高，常用于数值计算B．舍伍德算法能求得问题的一个解，但未必正确，正确的概率随着计算时间的增加而提高，通常用于求问题的精确解C．若能用拉斯维加斯算法求得一个解，那么它一定正确，其找到解的概率也随着计算时间的增加而提高D．蒙特卡罗算法的缺点就是无法有效地判断所求解的正确性
考题
关于0－1背包问题以下描述正确的是（）A、可以使用贪心算法找到最优解B、能找到多项式时间的有效算法C、使用教材介绍的动态规划方法可求解任意0－1背包问题D、对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做0－1背包问题
考题
对于0－1背包问题和背包问题的解法，下面（）答案解释正确。A、0－1背包问题和背包问题都可用贪心算法求解B、0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解C、0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解D、因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解
考题
采用动态规划策略求解问题的显著特征是满足最优性原理，其含义是（）。A、当前所作决策不会影响后面的决策B、原问题的最优解包含其子问题的最优解C、问题可以找到最优解，但利用贪心算法不能找到最优解D、每次决策必须是当前看来的最优决策才可以找到最优解
考题
单选题关于0－1背包问题以下描述正确的是（）A
可以使用贪心算法找到最优解B
能找到多项式时间的有效算法C
使用教材介绍的动态规划方法可求解任意0－1背包问题D
对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做0－1背包问题
考题
单选题在下列关于计算机算法的说法中，不正确的是（）A
一个正确的算法至少要有一个输入B
算法的改进，在很大程度上推动了计算机科学与技术的进步C
判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性D
目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法
考题
单选题对于计算机求解问题，下列叙述正确的是（）。A
利用计算机进行问题求解，是用机器代替人，属于人工智能应用B
计算机求解问题主要适用于自然系统，社会系统无法建模C
计算机进行问题求解是利用了计算机运行速度快、精度高、自动化和不知疲倦的特性D
只有通过计算机执行求解算法才能得到问题的解
考题
单选题关于算法的时间复杂性，下列叙述正确的是（）。A
时间复杂性是衡量一个算法优劣的唯一标准B
所有算法都与问题的规模有关，问题规模越大，时间复杂性越大C
通常不能简单地以算法运行时间度量算法的时间复杂性D
同一个算法可以编写为不同的程序，程序的执行时间不同，因此一个算法有多种不同的时间复杂性
考题
填空题Prim算法利用（）策略求解（）问题，其时间复杂度是（）。
热门标签
最新试卷
