GESP 5级客观题｜分治与递归｜课后作业

考试频率：高频。本卷共 6 题。

1. 关于分治算法，以下说法中不正确的是（ ）。

   {{ select(1) }}

• 分治算法将问题分成子问题，然后分别解决子问题，最后合并结果。
• 归并排序采用了分治思想。
• 快速排序采用了分治思想。
• 冒泡排序采用了分治思想。

2. 在上题的归并排序算法中， mergeSort(listData, start, middle); 和 mergeSort(listData, middle+ 1, end); 涉及到的算法为（ ）

   {{ select(2) }}

• 搜索算法
• 分治算法
• 贪心算法
• 递推算法

3. 下面C++代码用于有序 list 的二分查找，有关说法错误的是（ ）。

int _binarySearch(vector<int>lst, int Low, int High, int Target){
	if (Low > High)
		return -1;
	int Mid = (Low + High) / 2;
	if (Target == lst[Mid])
		return Mid;
	else if (Target < lst[Mid])
		return _binarySearch(lst, Low, Mid - 1, Target);
	else
		return _binarySearch(lst, Mid + 1, High, Target);
}
int bSearch(vector<int>lst, int Val){
	return _binarySearch(lst, 0, lst.size(), Val);
}

{{ select(3) }}

• 代码采用二分法实现有序 list 的查找
• 代码采用分治算法实现有序 list 的查找
• 代码采用递归方式实现有序 list 的查找
• 代码采用动态规划算法实现有序 list 的查找

4. 考虑以下C++代码实现的归并排序算法：

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int L[n1], R[n2];

    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

对长度为 n 的数组 arr ，挑⽤函数 merge_sort(a, 0, n-1) ，在排序过程中 merge 函数的递归调⽤次数⼤约是（ ）。

{{ select(4) }}

• $O(1)$
• $O(n)$
• $O(log n)$
• $O(n log n)$

5. 归并排序算法体现了分治算法，每次将大的待排序数组分成大小大致相等的两个小数组，然后分别对两个小数组进行排序，最后对排好序的两个小数组合并成有序数组。

   {{ select(5) }}

• 对
• 错

6. 归并排序的基本思想是（ ）。

   {{ select(6) }}

• 动态规划
• 分治
• 贪心算法
• 回溯算法