2-1 分数 2

下列多少种排序算法用了分治法？

• 堆排序
• 插入排序
• 归并排序
• 快速排序
• 选择排序
• 希尔排序

A.2

B.3

C.4

D.5

正确答案 A

2-2 分数 2

分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决问题，最后将子问题的解组合起来形成原问题的解，这要求原问题和子问题____。

A.问题规模相同，问题性质相同

B.问题规模相同，问题性质不同

C.问题规模不同，问题性质相同

D.问题规模不同，问题性质不同

正确答案 C

2-3 分数 2

在寻找n个元素中第k小元素的问题中，如采用快速排序算法思想，运用分治法对n个元素进行划分，如何选择划分基准?下面____答案最合理。

A.随机选择一个元素作为划分基准

B.取子序列的第一个元素作为划分基准

C.用中位数的方法寻找划分基准

D.以上皆可行，但不同方法的算法复杂度上界可能不同

正确答案 D

2-4 分数 2

在寻找n个元素中第k小元素的问题中，如采用快速排序算法思想，运用分治法对n个元素进行划分，如何选择划分基准？下面()答案最合理。

A.随机选择一个元素作为划分基准

B.取子序列的第一个元素作为基准

C.用中位数的中位数方法寻找划分基准

D.以上皆可行，但不同方法的算法复杂度上界可能不同

正确答案 D

2-5分数 2

（）关于分治法描述不正确的是：

A.分治法的基本思想是将规模较大的问题划分为规模较小的子问题来求解。

B.随机生成100个整数并存放在一个数组中，然后从中指定一个整数，则可用二分搜索算法在O(logn)的时间内找到该整数。

C.用分治法求解大整数乘法和Strassen矩阵乘法的基本思想均是通过合理的运算变换来减少乘法的次数。

D.合并排序和快速排序的时间复杂性均为O(nlogn)。

正确答案 B