所谓最优子结构性质是指（）。

填空题所谓最优子结构性质是指（）。

参考答案： 问题的最优解包含了其子问题的最优解

您可能感兴趣的试卷

你可能感兴趣的试题

1.填空题所谓贪心选择性质是指（）。

参考答案：所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到

2.问答题 有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合），得到的最大相容活动子集合为多少？

参考答案：

{1，4，8，11}

3.单项选择题记号Ω的定义正确的是（）。

A.O（g（n））={f（n）∣存在正常数c和n₀使得对所有n≧n₀有：0≦f（n）≦cg（n）}
B.O（g（n））={f（n）∣存在正常数c和n₀使得对所有n≧0有：0≦g（n）≦（n）}
C.O（g（n））={f（n）∣对于任何正常数c>0，存在正数和n₀>0使得对所有n≧n₀有：0≦f（n）<cg（n）}
D.O（g（n））={f（n）∣对于任何正常数c>0，存在正数和n₀>0使得对所有n≧n₀有：0≦cg（n）<f（n）}

点击查看答案

4.单项选择题记号O的定义正确的是（）。

点击查看答案

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

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

点击查看答案

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

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

点击查看答案

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

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

点击查看答案