算法设计与分析答案2023

第二章测试

1.可用Master方法求解的递归方程的形式为（ ）。
A:T(n)= T(n/a) +T(n/b) +f(n)， a≥1, b＞1
B:T(n)=aT(n/b)+f(n) , a≥1, b＞1, 为整数, f(n)＞0.
C:T(n)= T(n-a) +T(a) +f(n)， a≥1
D:T(n)= T(n-a) +T(n-b) +f(n)， a≥1, b＞1

答案:B
2.

A:对 B:错 3.假定，, 递归方程的解是. ( )
A:对 B:错 4.假设数组A包含n个不同的元素，需要从数组A中找出n/2个元素，要求所找的n/2个元素的中点元素也是数组A的中点元素。针对该问题的任何算法需要的时间复杂度的下限必为。 ( )
A:错 B:对 5.使用Master方法求解递归方程的解为（ ）.
A:
B:
C:
D:
6.考虑包含n个二维坐标点的集合S，其中n为偶数，且所有坐标点中的均不相同。一条竖直的直线若能把S集合分成左右两部分坐标点个数相同的子集合，则称直线L为集合S的一条分界线。若给定集合S，则可在时间内找到这条分界线L。 ( )
A:对 B:错 7.

A:
B:
C:
D:
8.从n个数中找出前k个最小的元素并对所选择的前k个最小的元素进行排序。使用归并排序算法将这n个数进行排序的时间复杂度为，从排好序的数组中提取有序的k个最小数的时间复杂度为，因此总的运行时间复杂度为. ( )
A:对 B:错 9.假定问题对于规模为n的所有不同输入，存在一个分治算法其平均时间复杂度为，则算法在最坏情形下的时间复杂度可能为 （ ）
A:对 B:错 10.使用分治算法求解最大最小问题。假定问题的规模, 每次将问题分成规模接近的两个子问题，递归地对子问题求解并将子问题的解合并得到大问题的解，该分治算法的复杂度函数可写为 ( )
A: ,
B:
C:
D: