第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

解析