动态规划·单选训练1（2）

第 1 题（单选）

下列关于深度优先搜索（DFS）和广度优先搜索（BFS）的描述，正确的是（）。

{{ select(1) }}

• DFS 使用队列，BFS 使用栈
• DFS 通常用于求最短路径
• BFS 一定能找到最短路径（无边权情况下）
• 两者均不能用于有向图

第 2 题（单选）

下列代码中，s1->draw(); 和 s2->draw(); 输出不同结果的主要原因是（）。 public: cout draw(); s2->draw(); delete s1; delete s2; return 0; }

{{ select(2) }}

- draw() 是普通成员函数
- Shape 中的 draw() 被声明为虚函数
- Circle 和 Rectangle 中使用了 public 继承
- 指针变量名不同

## 第 3 题（单选）

关于动态规划算法特性的描述，正确的是（）。

{{ select(3) }}

- 贪心选择性质
- 最优子结构和重叠子问题
- 分而治之
- 局部最优

## 第 4 题（单选）

下列关于动态规划与分治算法的说法，正确的是（）。

{{ select(4) }}

- 两者都要求子问题相互独立
- 动态规划适用于子问题重叠的情况，分治适用于子问题不重叠的情况
- 两者都是将大问题分解为子问题，但动态规划一定使用递归
- 分治算法一定比动态规划更优

## 第 5 题（单选）

下列关于 0-1 背包问题的动态规划解法，说法正确的是（）。

{{ select(5) }}

- 状态转移方程为 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])，其中 i 表示物品编号，j 表示容量
- 一维数组实现时，内层循环应从小到大遍历容量
- 完全背包问题可以用相同的一维数组解法，但内层循环同样需要从大到小
- 0-1 背包问题不能使用贪心算法求解，但动态规划一定能找到最优解