itgle.com

P类问题、NP类问题、NPC类问题是计算机科学领域关于可求解性可计算性很重要的概念。关于P、NP和NPC类问题，可解性问题是指能够找到多项式时间复杂性算法进行求解的问题，难解性问题是指找不到多项式时间复杂性算法进行求解的问题。下列说法不正确的是_____。A．P类问题是可解性问题，NP类问题是难解性问题B．NP类问题不一定是难解性问题，因为P类问题也一定是NP类问题C．NP类问题不确定是否是P类问题，但NPC类问题一定是难解性问题D．其他三个选项的说法有不正确的

题目

P类问题、NP类问题、NPC类问题是计算机科学领域关于可求解性可计算性很重要的概念。关于P、NP和NPC类问题，可解性问题是指能够找到多项式时间复杂性算法进行求解的问题，难解性问题是指找不到多项式时间复杂性算法进行求解的问题。下列说法不正确的是_____。

A．P类问题是可解性问题，NP类问题是难解性问题

B．NP类问题不一定是难解性问题，因为P类问题也一定是NP类问题

C．NP类问题不确定是否是P类问题，但NPC类问题一定是难解性问题

D．其他三个选项的说法有不正确的

相似考题

1.下面关于NP问题说法正确的是()A.NP问题都是不可能解决的问题B.P类问题包含在NP类问题中C.NP完全问题是P类问题的子集D.NP类问题包含在P类问题中

2.下列关于算法的概念，( )是不正确的。A.算法是计算机求解问题的步骤 B.算法产生的结果不能有二义性 C.算法必须执行有限步之后结束 D.算法必须有输入

3.关于0－1背包问题以下描述正确的是（）A、可以使用贪心算法找到最优解B、能找到多项式时间的有效算法C、使用教材介绍的动态规划方法可求解任意0－1背包问题D、对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做0－1背包问题

4.NP类问题包含在P类问题中。()此题为判断题(对，错)。

更多“P类问题、NP类问题、NPC类问题是计算机科学领域关于可求解性可计算性很重要的概念。关于P、NP和NPC类问题，可解性问题是指能够找到多项式时间复杂性算法进行求解的问题，难解性问题是指找不到多项式时间复杂性算法进行求解的问题。下列说法不正确的是_____。”相关问题

  • 第1题：

    若L是一个NP完全问题，L经过多项式时间变换后得到问题l，则l是（）

    • A、P类问题
    • B、NP难问题
    • C、NP完全问题
    • D、P类语言

    正确答案:A

  • 第2题：

    下面关于NP问题说法正确的是（）

    • A、NP问题都是不可能解决的问题
    • B、P类问题包含在NP类问题中
    • C、NP完全问题是P类问题的子集
    • D、NP类问题包含在P类问题中

    正确答案:B

  • 第3题：

    研究问题是指社会研究所涉及的某一类现象领域或问题领域。


    正确答案:错误

  • 第4题：

    下列关于运输问题与线性规划问题的关系，（）是正确的。

    • A、运输问题和线性规划问题是两类不同的优化问题
    • B、运输问题和线性规划问题是两类相同的优化问题，但不能用相同的方法求解
    • C、运输问题是一类特殊的线性规划问题
    • D、该两类问题的关系无法确定

    正确答案:C

  • 第5题：

    邮递员问题，或者叫做最短路径问题是（）。

    • A、P问题
    • B、NP问题
    • C、P和NP问题
    • D、以上都不是

    正确答案:B

  • 第6题：

    排序问题是属于（）。

    • A、P问题
    • B、NP问题
    • C、P和NP问题
    • D、以上都不是

    正确答案:A

  • 第7题：

    多选题
    在ABC分类法中，关于A类问题的说法，正确的有（）。
    A

    A类问题为不重要的问题

    B

    A类问题应按照常规适当加强管理

    C

    A类问题为次重点问题

    D

    A类问题是累计频率在0～80%区间的问题

    E

    A类问题应进行重点管理


    正确答案： D,A
    解析： 【考点】排列图法的应用。
    【解析】根据统计数据画排列图时，将其中累计频率0～80%定为A类问题，即主要问题，进行重点管理；将累计频率在80%～90%区间的问题定为B类问题，即次要问题，作为次重点管理；将其余累计频率在90%～100%区间的问题定为C类问题，即一般问题，按照常规适当加强管理。
    因此，正确选项是DE。

  • 第8题：

    单选题
    关于0－1背包问题以下描述正确的是（）
    A

    可以使用贪心算法找到最优解

    B

    能找到多项式时间的有效算法

    C

    使用教材介绍的动态规划方法可求解任意0－1背包问题

    D

    对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做0－1背包问题


    正确答案： B
    解析： 暂无解析

  • 第9题：

    问答题
    何谓P、NP、NPC问题？

    正确答案： 1.P（Polynomial问题）：也即是多项式复杂程度的问题。
    2.NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。
    3.NPC（NP Complete）问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。
    解析： 暂无解析

  • 第10题：

    问答题
    关于页面调度算法的3个条件、5个求解问题是什么？

    正确答案： 3个条件：
    （1）作业开始的几页是否在主存。
    （2）作业第几页在主存。
    （3）上面两点都没有。
    5个求解问题：
    （1）写出正确的页面调度次序。
    （2）求缺页次数F。
    （3）求缺页中断率f=缺页中断数F/被访问页面总数A。
    （4）写出被淘汰的页面次序。
    （5）写出最后驻留在主存的页面次序。
    解析： 暂无解析

  • 第11题：

    单选题
    关于算法的时间复杂性，下列叙述正确的是（）。
    A

    时间复杂性是衡量一个算法优劣的唯一标准

    B

    所有算法都与问题的规模有关，问题规模越大，时间复杂性越大

    C

    通常不能简单地以算法运行时间度量算法的时间复杂性

    D

    同一个算法可以编写为不同的程序，程序的执行时间不同，因此一个算法有多种不同的时间复杂性


    正确答案： B
    解析： 暂无解析

  • 第12题：

    单选题
    若L是一个NP完全问题，L经过多项式时间变换后得到问题l，则l是（）
    A

    P类问题

    B

    NP难问题

    C

    NP完全问题

    D

    P类语言


    正确答案： A
    解析： 暂无解析

  • 第13题：

    什么是P类问题？什么是NP类问题？请描述集合覆盖问题的近似算法的基本思想。


    正确答案:用确定的图灵机可以在多项式实践内可解的判定问题称为P类问题。
    用不确定的图灵机在多项式实践内可解的判定问题称为P类问题。
    集合覆盖问题的近似算法采用贪心思想：对于问题，每次选择F中覆盖了尽可能多的未被覆盖元素的子集S，然后将U中被S覆盖的元素删除，并将S加入C中，最后得到的C就是近似最优解。

  • 第14题：

    对于0－1背包问题和背包问题的解法，下面（）答案解释正确。

    • A、0－1背包问题和背包问题都可用贪心算法求解
    • B、0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解
    • C、0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解
    • D、因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解

    正确答案:C

  • 第15题：

    关于算法，以下表述正确的是（）。

    • A、算法就是指解决问题的方法和步骤
    • B、算法就是计算方法
    • C、算法的某些步骤具有不确定性
    • D、求解某一类问题的算法是唯一的

    正确答案:A

  • 第16题：

    关于页面调度算法的3个条件、5个求解问题是什么？


    正确答案: 3个条件：
    （1）作业开始的几页是否在主存。
    （2）作业第几页在主存。
    （3）上面两点都没有。
    5个求解问题：
    （1）写出正确的页面调度次序。
    （2）求缺页次数F。
    （3）求缺页中断率f=缺页中断数F/被访问页面总数A。
    （4）写出被淘汰的页面次序。
    （5）写出最后驻留在主存的页面次序。

  • 第17题：

    P问题是可计算问题，NP问题也是可计算问题


    正确答案:正确

  • 第18题：

    何谓P、NP、NPC问题？


    正确答案: 1.P（Polynomial问题）：也即是多项式复杂程度的问题。
    2.NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。
    3.NPC（NP Complete）问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。

  • 第19题：

    问答题
    什么是P类问题？什么是NP类问题？请描述集合覆盖问题的近似算法的基本思想。

    正确答案： 用确定的图灵机可以在多项式实践内可解的判定问题称为P类问题。
    用不确定的图灵机在多项式实践内可解的判定问题称为P类问题。
    集合覆盖问题的近似算法采用贪心思想：对于问题，每次选择F中覆盖了尽可能多的未被覆盖元素的子集S，然后将U中被S覆盖的元素删除，并将S加入C中，最后得到的C就是近似最优解。
    解析： 暂无解析

  • 第20题：

    单选题
    下面关于NP问题说法正确的是（）
    A

    NP问题都是不可能解决的问题

    B

    P类问题包含在NP类问题中

    C

    NP完全问题是P类问题的子集

    D

    NP类问题包含在P类问题中


    正确答案： D
    解析： 暂无解析

  • 第21题：

    单选题
    关于算法，以下表述正确的是（）。
    A

    算法就是指解决问题的方法和步骤

    B

    算法就是计算方法

    C

    算法的某些步骤具有不确定性

    D

    求解某一类问题的算法是唯一的


    正确答案： B
    解析： A项描述准确，算法是指解决问题的方法和步骤，解决问题方式不唯一。

  • 第22题：

    单选题
    对于计算机求解问题，下列叙述正确的是（）。
    A

    利用计算机进行问题求解，是用机器代替人，属于人工智能应用

    B

    计算机求解问题主要适用于自然系统，社会系统无法建模

    C

    计算机进行问题求解是利用了计算机运行速度快、精度高、自动化和不知疲倦的特性

    D

    只有通过计算机执行求解算法才能得到问题的解


    正确答案： B
    解析： 暂无解析

  • 第23题：

    判断题
    P问题是可计算问题，NP问题也是可计算问题
    A

    对

    B

    错


    正确答案： 错
    解析： 暂无解析

  • 第24题：

    单选题
    下列关于运输问题与线性规划问题的关系，（）是正确的。
    A

    运输问题和线性规划问题是两类不同的优化问题

    B

    运输问题和线性规划问题是两类相同的优化问题，但不能用相同的方法求解

    C

    运输问题是一类特殊的线性规划问题

    D

    该两类问题的关系无法确定


    正确答案： A
    解析： 暂无解析

相关内容