第三章单元测试

当前位置：首页 ＞课程 ＞算法分析与设计

1、能够使用动态规划算法来求解的问题通常需要具备两个重要的性质，它们分别是( )。

A、贪心选择性质
B、最优子结构
C、重叠子问题
D、递归调用

参考答案：请扫码使用小程序查看答案

2、关于备忘录法，以下说法正确的是( )。

A、备忘录法又称为记忆化搜索，它采用一种自底向上的方式求解问题。
B、备忘录法可以避免相同子问题的重复求解。
C、备忘录法的控制结构与直接使用递归方法的控制结构相同。
D、备忘录法为每个解过的子问题建立备忘录以备需要时查看，又称查表法。

参考答案：请扫码使用小程序查看答案

3、字符序列abcde与字符序列abdge的最长公共子序列长度为( )，最长公共子串长度为( )。

A、4,6
B、3,5
C、4,2
D、4,1

参考答案：请扫码使用小程序查看答案

4、使用动态规划算法求两条长度分别为m和n的序列的最长公共子序列，其时间复杂度为( )。

A、O(n^2)
B、O(m^n)
C、O(nlogm)
D、O(n*m)

参考答案：请扫码使用小程序查看答案

5、输入数组（-1, 0, 1, -2, 3），它的最大子段和是( )。

A、1
B、4
C、3
D、2

参考答案：请扫码使用小程序查看答案

6、序列（1，7，3，4，9，2，3）的最长递增子序列的长度为( )。

A、1
B、3
C、2
D、4

参考答案：请扫码使用小程序查看答案

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

A、O(n^2)
B、O(n^n)
C、O(n*2^n)
D、O(nlogn)

参考答案：请扫码使用小程序查看答案

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

A、O(n)
B、O(nlogn)
C、O(logn)
D、O(2^n)

参考答案：请扫码使用小程序查看答案

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

A、A
B、D
C、C
D、B

参考答案：请扫码使用小程序查看答案

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

A、错
B、对

参考答案：请扫码使用小程序查看答案

算法分析与设计