第2章-分治法
第2章-分治法 总分：100分 得分：20.0分
1 . 多选题 中等 10分
有关以下代码，说法正确的是（ ABCE）
def BinarySearch(s, x, low, high):if (low > high):return -1middle = (low + high) / 2if (x == s[middle]):return middleelif(x > s[middle]):return BinarySearch(s, x, middle + 1, high)else :return BinarySearch(s, x, low, middle - 1）
A.
BinarySearch的功能是针对有序序列s[] ，采用二分搜索技术查找指定元素x.
B.
if (low>high) return -1;该语句为递归的边界条件。
C.
将问题规模一份为二的语句是middle=(low+high)/2;
D.
递归序列左半部分的语句是BinarySearch (s, x, middle+1, high);
E.
递归序列左半部分的语句是BinarySearch (s, x, low, middle-1);
2 . 多选题 中等 10分
以下问题中，哪些问题的分治算法消耗的时间与输入序列无关.（ BD）
A.
二分查找
B.
合并排序
C.
快速排序
D.
最小值问题
3 . 填空题 中等 10分
填写以下二分搜索的代码中空缺的部分。
def BinarySearch(s, x, low, high):if (low > high):return -1middle = ___; //分解if (x == s[middle]):return middleelif(x > s[middle]):return BinarySearch(s, x, middle + 1, high)else :return BinarySearch(s, x, low, middle - 1)
学生答案
(low+high)/2
回答正确
答案
(low+high)/2
4 . 填空题 简单 10分
n个元素中找第二大元素的分治算法时间复杂度的是___
学生答案
O(log2n)
回答错误
答案
O（nlogn）
5 . 填空题 中等 10分
根据下面斐波那契数列的递归算法，可知斐波那契数列递推方程的停止条件是___。
def Fibonacci(int num):
if(num == 0 || num == 1):
return num
return Fibonacci(num-1)+Fibonacci(num - 2)
学生答案
num == 0 || num == 1
回答错误
答案
n=0或n=1
6 . 填空题 中等 10分
下面代码为求n！的递归算法，该代码反应的n!问题递归实现的停止条件（边界条件）为（）。
def fun(n):if (n == 1):return 1else :return fun(n - 1) * n
学生答案
n!=1 当n=1时
回答错误
答案
当n=1时n!=1
7 . 填空题 简单 10分
对可排序的序列s[left:right]进行合并排序，其分治算法分解操作为mid = (left+right)//2，得到的两个子问题序列是___
学生答案
s＞s[mid]和s＜s[mid]
回答错误
答案
s[left:mid],s[mid+1,right]
8 . 填空题 中等 10分
2k×2k的棋盘覆盖问题，用k表示问题的规模，则时间复杂度为___。
答案
O(4k)
9 . 填空题 中等 10分
线性时间选择问题寻找基准元素的方法是___。
学生答案
舍伍德选择算法
回答错误
答案
将n个元素按照5个元素一组进行分组，取每组的中位数，然后再取中位数的中位数作为基准
10 . 填空题 中等 10分
4个运动员的循环赛日程表算法安排的结果是___。
答案
第一天1-2，3-4，第二天1-3，2-4，第三天：1-4，2-3
解析