北语16秋《算法与数据分析》作业3

17春16秋《算法与数据分析》3

一、单选（共 10 道，共 50 分。）

1. 下面问题哪个不能使用贪心法解决 A. 单源最短路径问题 B. N皇后问题

C. 最小花费生成树问题 D. 背包问题 标准解：

2. 实现最长公共子序列利用的算法是 A. 分治策略 B. 动态规划法 C. 贪心法 D. 回溯法 标准解：

3. 下列随机算法中运行时有时候成功有时候失败的是 A. 数值概率算法 B. 舍伍德算法 C. 拉斯维加斯算法 D. 蒙特卡罗算法 标准解：

4. 合并排序算法是利用 A. 分治策略 B. 动态规划法 C. 贪心法 D. 回溯法 标准解：

5. 实现合并排序利用的算法是 A. 分治策略 B. 动态规划法 C. 贪心法 D. 回溯法 标准解：

6. Strassen矩阵乘法是利用什么实现的算法 A. 分治策略 B. 动态规划法 C. 贪心法 D. 回溯法

标准解：

7. 下列是动态规划算法基本要素的是 A. 定义最优解 B. 构造最优解 C. 算出最优解

D. 子问题重叠性质 标准解：

8. 采用广度优先策略搜索的算法是 A. 分支界限法 B. 动态规划法 C. 贪心法 D. 回溯法 标准解：

9. 分支限界法与回溯法的相同点是 A. 求解目标相同 B. 搜索方式相同

C. 对扩展结点的扩展方式相同

D. 都是一种在问题的解空间树T中搜索问题解的算法 标准解：

10. 下列算法中不能解决0/1背包问题的是 A. 贪心法 B. 动态规划 C. 回溯法

D. 分支限界法 标准解：

16秋《算法与数据分析》3

二、判断（共 10 道，共 50 分。）

1. 快速排序算法的性能取决于划分的对称性 A. 错误 B. 正确 标准解：

2. 任何可用计算机求解的问题所需的时间都与其规模无关。 A. 错误 B. 正确 标准解：

3. 回溯法是一种既带有系统性又带有跳跃性的搜索算法。

A. 错误 B. 正确 标准解：

4. 动态规划算法的两个基本要素是.最优子结构性质和重叠子问题性质。 A. 错误 B. 正确 标准解：

5. 分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解 A. 错误 B. 正确 标准解：

6. 设计动态规划算法的主要步骤有5步 A. 错误 B. 正确 标准解：

7. 分支限界法主要有队列式（FIFO）分支限界法和优先队列式分支限界法。 A. 错误 B. 正确 标准解：

8. 分支限界法与回溯法的求解目标相同 A. 错误 B. 正确 标准解：

9. 回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和限界函数。 A. 错误 B. 正确 标准解：

10. 优先队列式分支限界法是指按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点 A. 错误 B. 正确 标准解：