单选题

1 应用 Johnson 法则的流水作业调度采用的算法是（  ）。

A 动态规划算法

B 贪心算法

C 分治法

D 分支限界法

答案是： A

2 动态规划算法的基本要素为（  ）。

A 重叠子问题性质与贪心选择性质

B 最优子结构性质与重叠子问题性质

C 最优子结构性质与贪心选择性质

D 预排序与递归调用

答案是： B

3 二分搜索算法是利用（  ）实现的算法。

A 回溯法

B 分治策略

C 贪心法

D 动态规划法

答案是： B

4 下列不是动态规划算法基本步骤的是（  ）。

A 算出最优解

B 找出最优解的性质

C 构造最优解

D 定义最优解

答案是： B

5FIFO 是（  ）的一搜索方式。

A 回溯法

B 贪心法

C 动态规划法

D 分治界限法

答案是： D

6 秦始皇吞并六国使用的远交近攻，逐个击破的连横策略采用了以下哪种算法思想？

（  ）。

A 分治

B 迭代

C 递归

D 模拟

答案是： A

7k 带图灵机的空间复杂性 S(n) 是指（  ）。

Ak 带图灵机处理所有长度为 n 的输入时，在 k 条带上所使用过的方格数的总和。

B k 带图灵机处理所有长度为 n 的输入时，在某条带上所使用过的最大方格数。

C k 带图灵机处理所有长度为 n 的输入时，在 k 条带上所使用过的平均方格数。

Dk 带图灵机处理所有长度为 n 的输入时，在某条带上所使用过的最小方格数。

答案是： A

8 最大效益优先是（  ）的一搜索方式。

A 分支界限法

B 动态规划法

C

贪心法

D 回溯法

答案是： A

9 最长公共子序列算法利用的算法是（  ）。

A 分支界限法

B 回溯法

C 动态规划法

D 贪心法

答案是： C

10 下列算法中通常以自底向上的方式求解最优解的是（  ）。

A 动态规划法

B 回溯法

C 备忘录法

D 贪心法

答案是： A

11 衡量一个算法好坏的标准是（  ）。

A 代码短

B 运行速度快

C 时间复杂度低

D 占用空间少

答案是： C

12 以下不可以使用分治法求解的是（  ）。

A 归并排序

B0/1 背包问题

C 棋盘覆盖问题

D 选择问题

答案是： B

13 实现循环赛日程表利用的算法是（  ）。

A 回溯法

B 分治策略

C 贪心法

D 动态规划法

答案是： B