GESP C++ 5级 2025.09

以下哪种情况使用链表比数组更合适？

函数 removeElements 删除单链表中所有结点值等于 val 的结点，并返回新的头结点，其中链表头结点为 head，则横线处填写（ ）。

// 结点结构体
struct Node {
 int val;
 Node* next;

 Node() : val(0), next(nullptr) {}
 Node(int x) : val(x), next(nullptr) {}
 Node(int x, Node *next) : val(x), next(next) {}
};

Node* removeElements(Node* head, int val) {
 Node dummy(0, head); // 哑结点，统一处理头结点
 Node* cur = &dummy;
 while (cur->next) {
 if (cur->next->val == val) {
 _______________________ // 在此填入代码
 }
 else {
 cur = cur->next;
 }
 }
 return dummy.next;
}

函数 hasCycle 采用 Floyd 快慢指针法判断一个单链表中是否存在环，链表的头节点为 head，即用两个指针在链表上前进：slow 每次走 $1$ 步，fast 每次走 $2$ 步，若存在环，fast 终会追上 slow（相遇）；若无环，fast 会先到达 nullptr，则横线上应填写（ ）。

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

bool hasCycle(Node *head) {
 if (!head || !head->next) 
 return false;
 Node* slow = head;
 Node* fast = head->next;
 while (fast && fast->next) {
 if (slow == fast) return true;
 _______________________ // 在此填入代码
 }
 return false;
}

函数 isPerfectNumber 判断一个正整数是否为完全数（该数是否即等于它的真因子之和），则横线上应填写（ ）。一个正整数 $n$ 的真因子包括所有小于 $n$ 的正因子，如 $28$ 的真因子为 $1, 2, 4, 7, 14$。

bool isPerfectNumber(int n) {
 if (n <= 1) return false;
 int sum = 1;
 for (int i = 2; ______; i++) {
 if (n % i == 0) {
 sum += i;
 if (i != n / i) sum += n / i;
 }
 }
 return sum == n;
}

以下代码计算两个正整数的最大公约数（GCD），横线上应填写（ ）。

int gcd0(int a, int b) {
 if (a < b) {
 swap(a, b);
 }
 while (b != 0) {
 int temp = a % b;
 a = b;
 b = temp;
 }
 return ______;
}

函数 sieve 实现埃拉托斯特尼筛法（埃氏筛），横线处应填入（ ）。

vector sieve(int n) {
 vector is_prime(n + 1, true);
 is_prime[0] = is_prime[1] = false;
 for (int i = 2; i <= n; i++) {
 if (is_prime[i]) {
 for (int j = ______; j <= n; j += i) {
 is_prime[j] = false;
 }
 }
 }
 return is_prime;
}

函数 linearSieve 实现线性筛法（欧拉筛），横线处应填入（ ）。

vector linearSieve(int n) {
 vector is_prime(n + 1, true);
 vector primes;
 for (int i = 2; i n) break;
 is_prime[p * i] = false;
 if (________) break;
 }
 }
 return primes;
}

关于 埃氏筛 和 线性筛 的比较，下列说法错误的是（ ）。

唯一分解定理描述的是（ ）。

给定一个 $n \times n$ 的矩阵 matrix ，矩阵的每一行和每一列都按升序排列。函数 countLE 返回矩阵中第 $k$ 小的元素，则两处横线上应分别填写（ ）。

// 统计矩阵中 >& matrix, int x) {
 int n = (int)matrix.size();
 int i = n - 1, j = 0, cnt = 0;
 while (i >= 0 && j >& matrix, int k) {
 int n = (int)matrix.size();
 int lo = matrix[0][0];
 int hi = matrix[n - 1][n - 1];

 while (lo = k) {
 _______________ // 在此处填入代码
 } else {
 _______________ // 在此处填入代码
 }
 }
 return lo;
}