C.2

D.4

正确答案：4

7、使用穷举法求解最长递增子序列的时间复杂度为（）。

A.O（n^2）

B.O（n^n）

C.O（n*2^n）

D.O（nlogn）

正确答案：O（n*2^n）

8、使用动态规划算法求最大子段和的时间复杂度为（）。

A.O（n）

B.O（nlogn）

C.O（logn）

D.O（2^n）

正确答案：O（n）

9、某工厂预计明年有A，B，C，D四个新建项目，每个项目的投资额分别为15，10，12，8（万元），投资收益分别为12，8，9，5（万元），投资总额为30万元，选择项目（）可以使总收益最大。（不允许部分投资某个项目）

A.A

B.D

C.C

D.B

正确答案：D；C；B

10、在使用动态规划算法求解0-1背包问题时，若m[i][j]=m[i+1][j-w[i]]+v[i]，说明第i个物品在剩余背包容量为j时可以装入，并且装入比不装入的背包总价值更大，装入后，背包剩余容量减少w[i]，价值增加v[i]。

A.正确

B.错误

正确答案：正确

第四章单元测试

1、能够使用贪心算法求解的问题需具备的基本要素包括（）。

A.贪心选择性质

B.最优子结构性质

C.平衡子问题

D.递归调用

E.重复子问题

正确答案：贪心选择性质；最优子结构性质

2、下列关于贪心算法与动态规划算法说法正确的是（）。

A.贪心算法与动态规划算法的主要区别是贪心算法要求问题具有贪心选择性质

B.贪心算法与动态规划算法求解的问题都具有重复子问题性质

C.贪心算法与动态规划算法求解的问题都具备最优子结构性质

D.贪心算法与动态规划算法的主要区别是动态规划算法要求问题具有贪心选择性质

正确答案：贪心算法与动态规划算法的主要区别是贪心算法要求问题具有贪心选择性质；贪心算法与动态规划算法求解的问题都具备最优子结构性质

3、在解决活动安排问题时应首先对活动进行排序，排序的依据是（）。

A.按照活动结束时间降序排列

B.按照活动开始时间降序排列

C.按照活动结束时间升序排列

D.按照活动开始时间升序排列

正确答案：按照活动结束时间升序排列

4、使用贪心算法求解最优装载问题，其时间复杂度为（）。

A.O（nlogn）

B.O（n3n）

C.O（n5n）

D.O（n2n）

正确答案：O（nlogn）

5、（）能够使用贪心算法求解。

A.最小生成树问题

B.单源最短路径问题

C.活动安排问题

D.0-1背包问题

E.部分背包问题

F.最优装载问题

正确答案：最小生成树问题；单源最短路径问题；活动安排问题；部分背包问题；最优装载问题

6、0-1背包问题与部分背包问题的区别在于（）。

A.在0-1背包问题中，物品只有装入和不装入两种情况，而部分背包问题允许只装入物品的一部分

B.若用贪心算法解决0-1背包问题，只能得到近似最优解

C.没有区别，它们的含义相同

D.若用贪心算法解决部分背包问题，只能得到近似最优解

正确答案：在0-1背包问题中，物品只有装入和不装入两种情况，而部分背包问题允许只装入物品的一部分；若用贪心算法解决0-1背包问题，只能得到近似最优解