CSP-S 卷

假设一个长度为 $n$ 的整数数组中每个元素值互不相同，且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少？（ ）

以下排序方法中，（ ）是不稳定的。

考虑对 $n$ 个数进行排序，以下最坏时间复杂度低于 $O(n^2)$ 的排序方法是（ ）。

冒泡排序和插入排序都是稳定排序算法。

由于选择排序和插入排序的时间复杂度均为 $O(n^2)$，在任何实际场景下两者的性能表现几乎相同，可以互相替代。

选择排序算法在寻找每一轮最小值时，如果遇到相等的元素不进行交换，则选择排序是一种稳定的排序算法。

如果使用带 flag 的冒泡排序，且待排序数组一开始就是有序的，那么算法只需一轮扫描即可结束，时间复杂度为 O(n)。

下算法中，（ ）是不稳定的排序。

归并排序的最好、最坏和平均时间复杂度均为 $O(n \log n)$。

快速排序和归并排序都是稳定的排序算法。

下列关于排序的说法，正确的是（ ）。

排序的算法很多，若按排序的稳定性和不稳定性分类，则（ ）是不稳定排序。

设 $A$ 和 $B$ 是两个长度为 $n$ 的有序数组，现在需要将 $A$ 和 $B$ 合并成一个排序好的数组。请问任何以元素比较作为基本运算的归并算法，在最坏情况下至少要做多少次比较？（ ）

以比较为基本运算，对于 $2n$ 个数，同时找到最大值和最小值，最坏情况下需要的最少比较次数为（ ）。

假设在基数排序过程中，受宇宙射线的影响，某项数据异变为一个完全不同的值。请问排序算法结束后，可能出现的最坏情况是（ ）。

对于给定的 $n$，分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为（ ）。

01int i, j, k = 0;
02for (i = 0; i < n; i++) {
03    for (j = 0; j < n; j *= 2) {
04        k = k + n / 2;
05    }
06}

假设快速排序算法的输入是一个长度为 $n$ 的已排序数组，且该快速排序算法在分治过程中总是选择第一个元素作为基准元素。以下哪个选项描述的是这种情况下的快速排序行为？（ ）

递归关系式 $T(n) = 2T(n/2) + O(n^2)$ 描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少？

一般说来，冒泡排序算法优于归并排序。

C++ 语言中的 qsort 库函数是不稳定排序。

插入排序有时比快速排序时间复杂度更低。

在快速排序中，选择的主元素（pivot）会影响算法的（ ）。

归并排序和快速排序都采用递归实现，也都是不稳定排序。

假设快速排序算法的输入是一个长度为 $n$ 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。下面选项（ ）描述的是在这种情况下的快速排序行为。

快速排序和归并排序的平均时间复杂度均为 $O(n \log n)$，且都是稳定排序。

下面关于归并排序，描述正确的是（ ）。

关于下述 C++ 代码的快速排序算法，说法错误的是（ ）。

01int randomPartition(std::vector<int>& arr, int low, int high) {
02    int random = low + rand() % (high - low + 1);
03    std::swap(arr[random], arr[high]);
04
05    int pivot = arr[high];
06    int i = low - 1;
07
08    for (int j = low; j < high; j++) {
09        if (arr[j] <= pivot) {
10            i++;
11            std::swap(arr[i], arr[j]);
12        }
13    }
14    std::swap(arr[i + 1], arr[high]);
15    return i + 1;
16}
17
18void quickSort(std::vector<int>& arr, int low, int high) {
19    if (low < high) {
20        int pi = randomPartition(arr, low, high);
21
22        quickSort(arr, low, pi - 1);
23        quickSort(arr, pi + 1, high);
24    }
25}

下述 C++ 代码实现了快速排序算法，下面说法错误的是（ ）。

01int partition(vector<int>& arr, int low, int high) {
02    int i = low, j = high;
03    int pivot = arr[low];                 // 以首元素为基准
04    while (i < j) {
05        while (i < j && arr[j] >= pivot) j--;   // 从右往左查找
06        while (i < j && arr[i] <= pivot) i++;   // 从左往右查找
07        if (i < j) swap(arr[i], arr[j]);
08    }
09    swap(arr[i], arr[low]);
10    return i;
11}
12
13void quickSort(vector<int>& arr, int low, int high) {
14    if (low >= high) return;
15    int p = partition(arr, low, high);
16    quickSort(arr, low, p - 1);
17    quickSort(arr, p + 1, high);
18}

下面代码实现了归并排序。下述关于归并排序的说法中，不正确的是（ ）。

01void merge(vector<int>& arr, vector<int>& temp, int l, int mid, int r) {
02    int i = l, j = mid + 1, k = l;
03    while (i <= mid && j <= r) {
04        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
05        else temp[k++] = arr[j++];
06    }
07    while (i <= mid) temp[k++] = arr[i++];
08    while (j <= r)  temp[k++] = arr[j++];
09    for (int p = l; p <= r; p++) arr[p] = temp[p];
10}
11
12void mergeSort(vector<int>& arr, vector<int>& temp, int l, int r) {
13    if (l >= r) return;
14    int mid = l + (r - l) / 2;
15    mergeSort(arr, temp, l, mid);
16    mergeSort(arr, temp, mid + 1, r);
17    merge(arr, temp, l, mid, r);
18}

归并排序和快速排序在平均情况下的时间复杂度均为 $O(n\log n)$。但在稳定性方面，归并排序通常是不稳定的，而快速排序是稳定的。

选择排序一般是不稳定的。（ ）

快速排序一般是不稳定的。

下列关于排序稳定性的说法，正确的是（ ）。

冒泡排序是稳定的排序算法。（ ）

归并排序每次把长度为 $n$ 的序列分成两个规模约为 $n/2$ 的子序列，递归排序后再用线性时间合并。该算法的时间复杂度通常为（ ）。