GESP 五级 · 2024 真题

下面关于链表和数组的描述，错误的是（ ）。

通过（ ）操作，能完成在双向循环链表结点 p 之后插入结点 s 的功能（其中 next 域为结点的直接后继，prev 域为结点的直接前驱）。

对下面两个函数，说法错误的是（ ）。

01int sumA(int n) {
02    int res = 0;
03    for (int i = 1; i <= n; i++) {
04        res += i;
05    }
06    return res;
07}
08
09int sumB(int n) {
10    if (n == 1)
11        return 1;
12    int res = n + sumB(n - 1);
13    return res;
14}

有如下函数 fun，则 fun(20, 12) 的返回值为（ ）。

01int fun(int a, int b) {
02    if (a % b == 0)
03        return b;
04    else
05        return fun(b, a % b);
06}

下述代码实现素数表的埃拉托斯特尼筛法，筛选出所有小于等于 n 的素数，则横线上应填的最佳代码是（ ）。

01void sieve_Eratosthenes(int n) {
02    vector<bool> is_prime(n + 1, true);
03    vector<int> primes;
04
05    for (int i = 2; i * i <= n; i++) {
06        if (is_prime[i]) {
07            primes.push_back(i);
08            ____________ {   // 在此处填入代码
09                is_prime[j] = false;
10            }
11        }
12    }
13
14    for (int i = sqrt(n) + 1; i <= n; i++) {
15        if (is_prime[i]) {
16            primes.push_back(i);
17        }
18    }
19
20    return primes;
21}

下述代码实现素数表的线性筛法，筛选出所有小于等于 n 的素数，则横线上应填的代码是（ ）。

01vector<int> sieve_linear(int n) {
02    vector<bool> is_prime(n + 1, true);
03    vector<int> primes;
04
05    for (int i = 2; i <= n / 2; i++) {
06        if (is_prime[i])
07            primes.push_back(i);
08            ____________ {   // 在此处填入代码
09                is_prime[i * primes[j]] = 0;
10                if (i % primes[j] == 0)
11                    break;
12            }
13    }
14
15    for (int i = n / 2 + 1; i <= n; i++) {
16        if (is_prime[i])
17            primes.push_back(i);
18    }
19
20    return primes;
21}

下面函数可以将 n 的所有质因数找出来，其时间复杂度是（ ）。

01#include <iostream>
02#include <vector>
03
04vector<int> get_prime_factors(int n) {
05    vector<int> factors;
06
07    while (n % 2 == 0) {
08        factors.push_back(2);
09        n /= 2;
10    }
11
12    for (int i = 3; i * i <= n; i += 2) {
13        while (n % i == 0) {
14            factors.push_back(i);
15            n /= i;
16        }
17    }
18
19    if (n > 2) {
20        factors.push_back(n);
21    }
22
23    return factors;
24}

现在用如下代码来计算 $x^n$（$n$ 个 $x$ 相乘），其时间复杂度为（ ）。

01double quick_power(double x, unsigned n) {
02    if (n == 0) return 1;
03    if (n == 1) return x;
04    return quick_power(x, n / 2) * quick_power(x, n / 2) * ((n & 1) ? x : 1);
05}

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

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

01void merge(int arr[], int left, int mid, int right) {
02    int n1 = mid - left + 1;
03    int n2 = right - mid;
04
05    int L[n1], R[n2];
06
07    for (int i = 0; i < n1; i++)
08        L[i] = arr[left + i];
09    for (int j = 0; j < n2; j++)
10        R[j] = arr[mid + 1 + j];
11
12    int i = 0, j = 0, k = left;
13    while (i < n1 && j < n2) {
14        if (L[i] <= R[j]) {
15            arr[k] = L[i];
16            i++;
17        }
18        else {
19            arr[k] = R[j];
20            j++;
21        }
22        k++;
23    }
24
25    while (i < n1) {
26        arr[k] = L[i];
27        i++;
28        k++;
29    }
30    while (j < n2) {
31        arr[k] = R[j];
32        j++;
33        k++;
34    }
35}
36
37void merge_sort(int arr[], int left, int right) {
38    if (left < right) {
39        int mid = left + (right - left) / 2;
40
41        merge_sort(arr, left, mid);
42        merge_sort(arr, mid + 1, right);
43
44        merge(arr, left, mid, right);
45    }
46}

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

现在有 n 个人要过河，每只船最多载 $2$ 人，船的承重为 $100\text{kg}$。下列代码中，数组 weight 中保存有 n 个人的体重（单位为 $\text{kg}$），已经按从小到大排好序，代码输出过河所需要的船的数目，采用的思想为（ ）。

01int i, j;
02int count = 0;
03for (i = 0, j = n - 1; i < j; j--) {
04    if (weight[i] + weight[j] <= 100) {
05        i++;
06    }
07    count++;
08}
09printf("过河的船数: %d\n", count);

关于分治算法，以下哪个说法正确？

根据下述二分查找法，在排好序的数组 $1, 3, 6, 9, 17, 31, 39, 52, 61, 79$ 中查找数值 $31$，循环 while (left <= right) 执行的次数为（ ）。

01int binary_search(vector<int>& nums, int target) {
02    int left = 0;
03    int right = nums.size() - 1;
04
05    while (left <= right) {
06        int mid = left + (right - left) / 2;
07
08        if (nums[mid] == target) {
09            return mid;
10        }
11        else if (nums[mid] < target) {
12            left = mid + 1;
13        }
14        else {
15            right = mid - 1;
16        }
17    }
18    return -1; // 如果找不到目标元素，返回-1
19}

以下关于高精度运算的说法错误的是（ ）。

当 $n = 7$ 时，下面函数的返回值为（ ）。

01int fun(int n) {
02    if (n == 1) return 1;
03    else if (n >= 5) return n * fun(n - 2);
04    else return n * fun(n - 1);
05}

在操作系统中，需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循环操作可以通过环形链表来实现。

找出自然数 n 以内的所有质数，常用算法有埃拉托斯特尼（埃氏）筛法和线性筛法，其中线性筛法效率更高。

唯一分解定理表明任何一个大于 $1$ 的整数都可以唯一地分解为素数之和。

贪心算法通过每一步选择局部最优解，从而一定能获得最优解。

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

插入排序的时间复杂度总是比快速排序低。

引入分治策略往往可以提升算法效率。一方面，分治策略减少了操作数量；另一方面，分治后有利于系统的并行优化。

二分查找要求被搜索的序列是有序的，否则无法保证正确性。

在 C++ 语言中，递归的实现方式通常会占用更多的栈空间，可能导致栈溢出。

对于已经定义好的标准数学函数 sin(x)，应用程序中的语句 y=sin(sin(x)); 是一种递归调用。