单选题库 - E心E意

EXY-SC-1150

第 351 题

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

A

归并排序是一个不稳定的排序算法。

B

归并排序的时间复杂度在最优、最差和平均情况下都是 $O(n \log n)$。

C

归并排序需要额外的 $O(1)$ 空间。

D

对于输入数组 $\{12, 11, 13, 5, 6, 7\}$，代码输出结果为：$7\ 6\ 5\ 13\ 12\ 11$。

语言： C++

GESP真题五级

2024.12

单选题号： 10

EXY-SC-1149

第 352 题

考虑以下 C++ 代码实现的快速排序算法：

int partition(vector<int>& arr, int left, int right) {
    int pivot = arr[right]; // 基准值
    int i = left - 1;
 
    for (int j = left; j < right; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[right]);
    return i + 1;
}
 
// 快速排序
void quickSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int pi = partition(arr, left, right);
        quickSort(arr, left, pi - 1);
        quickSort(arr, pi + 1, right);
    }
}

以下关于快速排序的说法，正确的是（）。

A

快速排序通过递归对子问题进行求解。

B

快速排序的最坏时间复杂度是 $O(n \log n)$。

C

快速排序是一个稳定的排序算法。

D

在最优情况下，快速排序的时间复杂度是 $O(n)$。

语言： C++

GESP真题五级

2024.12

单选题号： 9

EXY-SC-1148

第 353 题

下述代码实现素数表的线性筛法，筛选出所有小于等于 $n$ 的素数。下面说法正确的是（）。

vector<int> sieve_linear(int n) {
    vector<bool> is_prime(n +1, true);
    vector<int> primes;
 
    for (int i = 2; i <= n/2; i++) {
        if (is_prime[i])
            primes.push_back(i);
 
        for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
            is_prime[ i * primes[j] ] = 0;
            if (i % primes[j] == 0)
                break;
        }
    }
 
    for (int i = n/2 +1; i <= n; i++) {
        if (is_prime[i])
            primes.push_back(i);
    }
 
    return primes;
}

A

线性筛的时间复杂度是 $O(n)$。

B

每个合数会被其所有的质因子标记一次。

C

线性筛和埃拉托色尼筛的实现思路完全相同。

D

以上都不对

语言： C++

GESP真题五级

2024.12

单选题号： 8

EXY-SC-1147

第 354 题

下述代码实现素数表的埃拉托色尼（埃氏）筛法，筛选出所有小于等于 $n$ 的素数。

vector<int> sieve_Eratosthenes(int n) {
    vector<bool> is_prime(n +1, true);
    vector<int> primes;
 
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
 
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
 
    for (int i = sqrt(n) + 1; i <= n; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
    }
 
    return primes;
}

下面说法，正确的是（）。

A

代码的时间复杂度是 $O(n\sqrt{n})$。

B

在标记非素数时，代码从 $i^2$ 开始，可以减少重复标记。

C

代码会输出所有小于等于 $n$ 的奇数。

D

调用函数 sieve_Eratosthenes(10)，函数返回值的数组中包含的元素有：$2$，$3$，$5$，$7$，$9$。

语言： C++

GESP真题五级

2024.12

单选题号： 7

EXY-SC-1146

第 355 题

唯一分解定理表明，每个大于 $1$ 的自然数可以唯一地写成若干个质数的乘积。下面函数将自然数 $n$ 的所有质因素找出来，横线上能填写的最佳代码是（）。

#include <vector>
vector<int> get_prime_factors(int n) {
    vector<int> factors;
    if (n <= 1) {
        cout << "输入的数必须是大于1的正整数" << endl;
        return;
    }
    while (n % 2 == 0) {
        factors.push_back(2);
        n /= 2;
    }
 
    ________________________________  // 在此处填入代码
    while (n % i == 0) {
        factors.push_back(i);
        n /= i;
    }
 
    if (n > 2) {
        factors.push_back(n);
    }
    return factors;
}

A

for (int i = 3; i <= n; i++)

B

for (int i = 3; i * i <= n; i++)

C

for (int i = 3; i <= n; i += 2)

D

for (int i = 3; i * i <= n; i += 2)

语言： C++

GESP真题五级

2024.12

单选题号： 6