GESP C++ 5级 2024.12

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

在循环单链表中，节点的 next 指针指向下一个节点，最后一个节点的 next 指针指向（ ）。

为了方便链表的增删操作，一些算法生成一个虚拟头节点，方便统一删除头节点和其他节点。下面代码实现了删除链表中值为 $val$ 的节点，横线上应填的最佳代码是（ ）。

struct LinkedNode {
 int val;
 LinkedNode* next;
 LinkedNode(int val) : val(val), next(nullptr) {}
};

void removeElements(LinkedNode* head, int val) {
 if (head == nullptr) {
 return;
 }
 LinkedNode* cur;
 LinkedNode* dummyHead = new LinkedNode(0); //虚拟头节点
 _________________// 在此处填入代码
 while (cur->next!= nullptr) {
 if (cur->next->val == val) {
 LinkedNode* tmp = cur->next;
 cur->next = cur->next->next;
 delete tmp;
 tmp = nullptr;
 } else { 
 cur = cur->next;
 }
 }
 head = dummyHead->next;
 delete dummyHead;
 dummyHead = nullptr;
}

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

int fibA(int n) {
 if (n <= 1) return n;
 int f1 = 0, f2 = 1;
 for (int i = 2; i <= n; ++i) {
 int temp = f2;
 f2 = f1 + f2;
 f1 = temp;
 }
 return f2;
}

int fibB(int n) {
 if (n <= 1) return n;
 return fibB(n - 1) + fibB(n - 2);
}

两块长方形土地的长宽分别为 $24$ 和 $36$ 米，要将它们分成正方形的小块，使得正方形的尺寸尽可能大。小杨采用如下的辗转相除函数 gcd(24, 36) 来求正方形分块的边长，则函数 gcd 调用顺序为（ ）。

int gcd(int a, int b) {
 int big = a > b? a : b;
 int small = a < b? a : b;
 if (big % small == 0) {
 return small;
 }
 return gcd(small, big % small);
}

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

#include 
vector get_prime_factors(int n) {
 vector factors;
 if (n 2) {
 factors.push_back(n);
 }
 return factors;
}

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

vector sieve_Eratosthenes(int n) {
 vector is_prime(n + 1, true);
 vector 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;
}

下面说法，正确的是（）

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

vector sieve_linear(int n) {
 vector is_prime(n + 1, true);
 vector 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]] = false;
 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;
}

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

int partition(vector& arr, int left, int right) {
 int pivot = arr[right];//基准值
 int i = left - 1;
 for (int j = left; j & arr, int left, int right) {
 if (left < right) {
 int pi = partition(arr, left, right);
 quickSort(arr, left, pi - 1);
 quickSort(arr, pi + 1, right);
 }
}

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

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