itgle.com

20、P类问题、NP类问题、NPC类问题是计算机科学领域关于可求解性可计算性很重要的概念。关于P、NP和NPC类问题，下列说法不正确的是_____。A．P类问题是计算机可以在有限时间内能够求解的问题B．NP类问题是计算机可以在有限时间内能够验证“解”的正确性的问题C．NPC类问题是对问题的每一个可能解，计算机都可以在有限时间内验证“解”的正确性的问题，被称为NP完全问题D．上述说法有不正确的

题目

20、P类问题、NP类问题、NPC类问题是计算机科学领域关于可求解性可计算性很重要的概念。关于P、NP和NPC类问题，下列说法不正确的是_____。

A．P类问题是计算机可以在有限时间内能够求解的问题

B．NP类问题是计算机可以在有限时间内能够验证“解”的正确性的问题

C．NPC类问题是对问题的每一个可能解，计算机都可以在有限时间内验证“解”的正确性的问题，被称为NP完全问题

D．上述说法有不正确的

相似考题

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

2.传输电平的单位分贝和奈培的换算关系为()。A.1Np=8.686dBB.1dB=8.686NpC.1Np=0•1151dBD.ldB=4.343Np

3.螺纹的导程Ph和螺距P的关系是()(n是螺纹的线数)。A.P=nPhB.Ph=nPC.P=PhD.Ph=2nP

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

更多“20、P类问题、NP类问题、NPC类问题是计算机科学领域关于可求解性可计算性很重要的概念。关于P、NP和NPC类问题，下列说法不正确的是_____。”相关问题

  • 第1题：

    决定流感病毒型别的是( )

    A．HA+NA

    B．NP

    C．MP

    D．RNP

    E．NP+MP


    正确答案：E

  • 第2题：

    设随机变量x服从b(n，p)，则（ ）。

    B. E(X) =np
    C. Var(X)=np(1-p)
    D. Var(X) = np(1-p)2
    E. Var(X) =p(1-p)


    答案：A,B,C
    解析：

  • 第3题：

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


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

  • 第4题：

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


    正确答案:错误

  • 第5题：

    请解释什么是P问题，NP问题。


    正确答案: 如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。P是英文单词多项式的第一个字母。
    NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。

  • 第6题：

    二项概率分布的方差是（）。

    • A、var（x）=P（1-P）
    • B、var（x）=nP
    • C、var（x）=n（1-P）
    • D、var（x）=nP（1-P）

    正确答案:D

  • 第7题：

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


    正确答案:正确

  • 第8题：

    何谓P、NP、NPC问题？


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

  • 第9题：

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

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

  • 第10题：

    问答题
    请解释什么是P问题，NP问题。

    正确答案： 如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。P是英文单词多项式的第一个字母。
    NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。
    解析： 暂无解析

  • 第11题：

    单选题
    关于波士顿矩阵，下列说法不正确的是（　　）。
    A

    对问题类业务一般可采取选择性投资战略

    B

    对明星类业务一般可采取收获战略

    C

    对于金牛类业务一般可采取收获战略

    D

    对于瘦狗类业务一般可采取放弃战略


    正确答案： B
    解析：
    B项，明星类业务是指处于高增长率、高市场占有率的业务，这类业务可能成为企业的金牛业务，需要加大投资以支持其迅速发展。明星类业务一般可采取积极发展战略，以长远利益为目标，积极扩大经济规模以增加市场机会，提高市场占有率，增强竞争地位。

  • 第12题：

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

    P类问题

    B

    NP难问题

    C

    NP完全问题

    D

    P类语言


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

  • 第13题：

    设随机变量x服从b(n，p)，则( )。

    A．分布列：P(X=x)=(1-p) n-x (x=0，1，2，…，n)

    B．E(X)=np

    C．Var(X)=np(1-p)

    D．Var(X)=np(1-p)2

    E．Var(X)=p(1-p)


    正确答案：ABC

  • 第14题：

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

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

    正确答案:A

  • 第15题：

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

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

    正确答案:B

  • 第16题：

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

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

    正确答案:C

  • 第17题：

    二项概率分布的标准差是（）。

    • A、σ（x）=P（1-P）
    • B、σ（x）=nP
    • C、σ（x）=nP（1-P）
    • D、以上均错误

    正确答案:D

  • 第18题：

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

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

    正确答案:B

  • 第19题：

    排序问题是属于（）。

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

    正确答案:A

  • 第20题：

    多选题
    在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。

  • 第21题：

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

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

    B

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

    C

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

    D

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


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

  • 第22题：

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

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

  • 第23题：

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

    对

    B

    错


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

  • 第24题：

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

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

    B

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

    C

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

    D

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


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

相关内容