高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上DC是一种面向过程的高级计算机语言【答案】CD。19在下列关于算法复杂性的说法中，正确的有（）。
A算法的时间复杂度，是指它在某台计算机上具体实现时的运行时间B算法的时间复杂度，是指对于该算法的一种或几种主要的运算，运算的次数与问题的规模之间的函数关系C一个问题如果是NPC类的，就意味着在解决该问题时，不存在一个具有多项式时间复杂度的算法但这一点还没有得到理论上证实，也没有被否定D一个问题如果是NP类的，与C有相同的结论【答案】BC。简单地说：①P（多项式时间）问题：这个问题可以找到一个能在多项式的时间里解决它的算法；②NP问题：不是非P问题，而是指可以在多项式的时间里验证一个解是否正确的问题；③NPC问题：NP完全问题，是目前还不能找到多项式时间复杂度的算法，即难解问题。【注】时间复杂度被分为两种级别，其中后者的复杂度无论如何都远远大于前者：一种是O1Olog
O
a等，我们把它叫做多项式级的复杂度，因为它的规模
出现在底数的位
18
f马鞍山二中
NOIP20062008初赛（提高组）试题＆解析
置；另一种是Oa
和O
型复杂度，它是非多项式级的，其复杂度计算机往往不能承受。当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。20近20年来，许多计算机专家都大力推崇递归算法，认为它是解决较复杂问题的强有力的工具在下列关于递归的说法中，正确的是（）。
A在1977年前后形成标准的计算机高级语言