算法分析与设计答案2023

第六章测试

1.

分治法分解的子问题与原问题形式相同。

A:错 B:对
答案:B
2.

N个元素排序的时间复杂度不可能是线性时间。

A:对 B:错 3.

三分法的判定树是三叉树。

A:错 B:对 4.

减治法减一个常量就是每次迭代减去一个相同的常数因子(一般为2)

A:错 B:对 5.

设有5000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用(   )法。

A:基数排序 B:快速排序 C:冒泡排序 D:合并排序 6.

堆排序的时间复杂度是O（）。

A:O（n²） B:O（n） C:O（2ⁿ） D:O（nlogn） 7.

改进分治算法的方法有（ ）和改进划分的对称性。

A:减少子问题数 B:加速原理 C:备忘录 D:拟阵原理 8.

通过减少子问题个数，降低分治算法时间复杂度的有（）

A:最接近点对 B:Strassen矩阵乘法 C:大整数乘法 D:线性时间选择 9.

分治法在每一层递归上有三个步骤（）

A:合并 B:选择 C:分解 D:解决
10.

使用分治法求解不需要满足的条件是（ ）。

A:子问题的解可以合并 B:子问题必须是一样的 C:子问题不能够重复 D:原问题和子问题使用相同的方法求解 11.

最小堆中每个元素调整的次数不超过树高。

A:错 B:对 12.

分治算法的思想是将难以直接解决的大问题，分割成一些规模较小的子问题，以便各个击破，分而治之。

A:错 B:对 13.

任何排序算法至少需要O(n log n)次比较。

A:对 B:错 14.

找n个元素的中位数的分治算法的时间复杂度为O().

A:n
B:nlogn
C:logn D:n^2