NP类语言在图灵机下的定义为（）

单项选择题NP类语言在图灵机下的定义为（）

A.NP={L∣L是一个能在非多项式时间内被一台NDTM所接受的语言}
B.NP={L∣L是一个能在非多项式时间内被一台DTM所接受的语言}
C.NP={L∣L是一个能在多项式时间内被一台DTM所接受的语言}
D.NP={L∣L是一个能在多项式时间内被一台NDTM所接受的语言}

1.单项选择题k带图灵机的空间复杂性S（n）是指（）

A.k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最大方格数
B.k带图灵机处理所有长度为n的输入时，在k条带上所使用过的方格数的总和
C.k带图灵机处理所有长度为n的输入时，在k条带上所使用过的平均方格数
D.k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最小方格数

2.单项选择题常见的两种分支限界法为（）

A.广度优先分支限界法与深度优先分支限界法
B.队列式（FIFO）分支限界法与堆栈式分支限界法
C.排列树法与子集树法
D.队列式（FIFO）分支限界法与优先队列式分支限界法

3.单项选择题回溯法的效率不依赖于以下哪一个因素？（）

A.产生x[k]的时间
B.满足显约束的x[k]值的个数
C.问题的解空间的形式
D.计算上界函数bound的时间
E.满足约束函数和上界函数约束的所有x[k]的个数
F.计算约束函数constraint的时间

4.单项选择题程序块（）是回溯法中遍历排列树的算法框架程序。

A.
B.
C.
D.

5.单项选择题分支限界法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树。

A.广度优先
B.活结点优先
C.扩展结点优先
D.深度优先

6.单项选择题回溯法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树。

A.广度优先
B.活结点优先
C.扩展结点优先
D.深度优先

7.单项选择题能采用贪心算法求最优解的问题，一般具有的重要性质为：（）

A.最优子结构性质与贪心选择性质
B.重叠子问题性质与贪心选择性质
C.最优子结构性质与重叠子问题性质
D.预排序与递归调用

8.单项选择题 Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（）

A.
B.
C.
D.

9.单项选择题以下关于渐进记号的性质是正确的有：（）

A.f（n）=Θ（g（n）），g（n）=Θ（h（n））→f（n）=Θ（h（n））
B.f（n）=O（g（n）），g（n）=O（h（n））→h（n）=O（f（n））
C.O（f（n））+O（g（n））=O（min{f（n），g（n）}）
D.f（n）=O（g（n））→g（n）=O（f（n））

10.单项选择题算法分析中，记号O表示（）。

A.渐进下界
B.渐进上界
C.非紧上界
D.紧渐进界
E.非紧下界