A.31

B.41

C.32

D.28

正确答案：31

5、分治法能解决的问题一般具有（）等特征。

A.该问题缩小到一定程度时可以容易地解决

B.分解出的子问题的解可以合并为原问题的解

C.子问题相互独立

D.最优子结构

正确答案：该问题缩小到一定程度时可以容易地解决；分解出的子问题的解可以合并为原问题的解；子问题相互独立；最优子结构

6、在使用分治法设计算法时，最好使子问题的规模大致相同，即将一个问题分成大小相等的多个子问题的处理方法是行之有效的。

A.正确

B.错误

正确答案：正确

7、给定递归公式T（n）=4T（n/2）+O（n），由主定理可以得知T（n）=（）。

A.O（logn）

B.O（nlogn）

C.O（n^2）

D.O（n）

正确答案：O（n^2）

8、已知某楼房共20层，如果采用二分查找，请问最多猜（）次就能猜出任意一个楼层。

A.5

B.3

C.6

D.4

正确答案：5

9、关于快速排序的时间复杂度，（）是正确的。

A.在平均情况下时间复杂度为O（nlogn）

B.在最坏情况下时间复杂度为O（n^2）

C.在平均情况下时间复杂度为O（n^2）

D.在最好情况下时间复杂度为O（nlogn）

正确答案：在平均情况下时间复杂度为O（nlogn）；在最坏情况下时间复杂度为O（n^2）；在最好情况下时间复杂度为O（nlogn）

10、快速排序是对传统排序算法（）的一种改进。

A.归并排序

B.冒泡排序

C.插入排序

D.选择排序

正确答案：冒泡排序

第三章单元测试

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，2

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

A.O（n^2）

B.O（m^n）

C.O（nlogm）

D.O（n*m）

正确答案：O（n*m）

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

A.1

B.4

C.3

D.2

正确答案：3

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

A.1

B.3