GESP C++ 五级 · 2025 年 9 月认证理论卷

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

2. 函数removeElements删除单链表中所有结点值等于 val 的结点，并返回新的头结点，其中链表头结点为head，则横线处填写（ ）。 ```cpp // 结点结构体 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; } ```

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

4. 函数isPerfectNumber判断一个正整数是否为完全数（该数是否即等于它的真因子之和），则横线上应填写（ ）。一个正整数n的真因子包括所有小于n的正因子，如28的真因子为1, 2, 4, 7, 14。 ```cpp 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; } ```

5. 以下代码计算两个正整数的最大公约数(GCD)，横线上应填写（ ）。 ```cpp int gcd0(int a, int b) { if (a < b) { swap(a, b); } while(b != 0) { int temp = a % b; a = b; b = temp; } return ______; } ```

6. 函数sieve实现埃拉托斯特尼筛法(埃氏筛)，横线处应填入（ ）。 ```cpp vector<bool> sieve(int n) { vector<bool> 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; } ```

7. 函数linearSieve实现线性筛法(欧拉筛)，横线处应填入（ ）。 ```cpp vector<int> linearSieve(int n) { vector<bool> is_prime(n+1, true); vector<int> primes; for(int i = 2; i <= n; i++) { if(is_prime[i]) primes.push_back(i); for(int p : primes) { if(p * i > n) break; is_prime[p * i] = false; if(________) break; } } return primes; } ```

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

9. 唯一分解定理描述的是( )。

10. 给定一个 n x n 的矩阵 matrix，矩阵的每一行和每一列都按升序排列。函数countLE返回矩阵中第k小的元素，则两处横线上应分别填写（ ）。 ```cpp // 统计矩阵中 <= x 的元素个数：从左下角开始 int countLE(const vector<vector<int>>& matrix, int x) { int n = (int)matrix.size(); int i = n - 1, j = 0, cnt = 0; while (i >= 0 && j < n) { if (matrix[i][j] <= x) { cnt += i + 1; ++j; } else { --i; } } return cnt; } int kthSmallest(vector<vector<int>>& matrix, int k) { int n = (int)matrix.size(); int lo = matrix[0][0]; int hi = matrix[n - 1][n - 1]; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (countLE(matrix, mid) >= k) { ________________ // 在此处填入代码 } else { ________________ // 在此处填入代码 } } return lo; } ```

11. 下述C++代码实现了快速排序算法，下面说法错误的是（ ）。 ```cpp int partition(vector<int>& arr, int low, int high) { int i = low, j = high; int pivot = arr[low]; // 以首元素为基准 while (i < j) { while (i < j && arr[j] >= pivot) j--; //从右往左查找 while (i < j && arr[i] <= pivot) i++; //从左往右查找 if (i < j) swap(arr[i], arr[j]); } swap(arr[i], arr[low]); return i; } void quickSort(vector<int>& arr, int low, int high) { if (low >= high) return; int p = partition(arr, low, high); quickSort(arr, low, p - 1); quickSort(arr, p + 1, high); } ```

12. 下述C++代码实现了归并排序算法，则横线上应填写（ ）。 ```cpp void merge(vector<int> &nums, int left, int mid, int right) { // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right] vector<int> tmp(right - left + 1); int i = left, j = mid + 1, k = 0; while (i <= mid && j <= right) { if (nums[i] <= nums[j]) tmp[k++] = nums[i++]; else tmp[k++] = nums[j++]; } while (i <= mid) { tmp[k++] = nums[i++]; } while (________) { // 在此处填入代码 tmp[k++] = nums[j++]; } for (k = 0; k < tmp.size(); k++) { nums[left + k] = tmp[k]; } } void mergeSort(vector<int> &nums, int left, int right) { if (left >= right) return; int mid = (left + right) / 2; mergeSort(nums, left, mid); mergeSort(nums, mid + 1, right); merge(nums, left, mid, right); } ```

13. 假设你是一家电影院的排片经理，只有一个放映厅。你有一个电影列表 movies，其中 movies[i] = [start_i, end_i] 表示第i部电影的开始和结束时间。请你找出最多能安排多少部不重叠的电影，则横线上应分别填写的代码为（ ）。 ```cpp int maxMovies(vector<vector<int>>& movies) { if (movies.empty()) return 0; sort(movies.begin(), movies.end(), [](const vector<int>& a, const vector<int>& b) { return ______; // 在此处填入代码 }); int count = 1; int lastEnd = movies[0][1]; for (int i = 1; i < movies.size(); i++) { if (movies[i][0] >= lastEnd) { count++; ______ = movies[i][1]; // 在此处填入代码 } } return count; } ```

14. 给定一个整数数组nums，下面代码找到一个具有最大和的连续子数组，并返回该最大和。则下面说法错误的是（ ）。 ```cpp int crossSum(vector<int>& nums, int left, int mid, int right) { int leftSum = INT_MIN, rightSum = INT_MIN; int sum = 0; for (int i = mid; i >= left; i--) { sum += nums[i]; leftSum = max(leftSum, sum); } sum = 0; for (int i = mid + 1; i <= right; i++) { sum += nums[i]; rightSum = max(rightSum, sum); } return leftSum + rightSum; } int helper(vector<int>& nums, int left, int right) { if (left == right) return nums[left]; int mid = left + (right - left) / 2; int leftMax = helper(nums, left, mid); int rightMax = helper(nums, mid + 1, right); int crossMax = crossSum(nums, left, mid, right); return max({leftMax, rightMax, crossMax}); } int maxSubArray(vector<int>& nums) { return helper(nums, 0, nums.size() - 1); } ```

15. 给定一个由非负整数组成的数组digits，表示一个非负整数的各位数字，其中最高位在数组首位，且digits不含前导0（除非是0本身）。下面代码对该整数执行 +1 操作，并返回结果数组，则横线上应填写（ ）。 ```cpp vector<int> plusOne(vector<int>& digits) { for (int i = (int)digits.size() - 1; i >= 0; --i) { if (digits[i] < 9) { digits[i] += 1; return digits; } ________________ // 在此处填入代码 } digits.insert(digits.begin(), 1); return digits; } ```

1. 基于下面定义的函数，通过判断isDivisibleBy9(n) == isDigitSumDivisibleBy9(n)代码可验算如果一个数能被9整除，则它的各位数字之和能被9整除。 ```cpp bool isDivisibleBy9(int n) { return n % 9 == 0; } bool isDigitSumDivisibleBy9(int n) { int sum = 0; string numStr = to_string(n); for (char c : numStr) { sum += (c - '0'); } return sum % 9 == 0; } ``` ( )

2. 假设函数gcd()能正确求两个正整数的最大公约数，则下面的findMusicalPattern(4，6)函数返回2。 ```cpp void findMusicalPattern(int rhythm1, int rhythm2) { int commonDivisor = gcd(rhythm1, rhythm2); int patternLength = (rhythm1 * rhythm2) / commonDivisor; return patternLength； } ``` ( )

3. 下面递归实现的斐波那契数列的时间复杂度为 $O(n)$。 ```cpp long long fib_memo(int n, long long memo[]) { if (n <= 1) return n; if (memo[n] != -1) return memo[n]; memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo); return memo[n]; } int main() { int n = 40; long long memo[100]; fill_n(memo, 100, -1); long long result2 = fib_memo(n, memo); return 0; } ``` ( )

4. 链表通过更改指针实现高效的结点插入与删除，但结点访问效率低、占用内存较多，且对缓存利用不友好。 ( )

5. 二分查找依赖数据的有序性，通过循环逐步缩减一半搜索区间来进行查找，且仅适用于数组或基于数组实现的数据结构。 ( )

6. 线性筛关键是"每个合数只会被最小质因子筛到一次"，因此为 $O(n)$。 ( )

7. 快速排序和归并排序都是稳定的排序算法。 ( )

8. 下面代码采用分治算法求解标准 3 柱汉诺塔问题，时间复杂度为 $O(2^n)$。 ```cpp void move(vector<int> &src, vector<int> &tar) { int pan = src.back(); src.pop_back(); tar.push_back(pan); } void dfs(int n, vector<int> &src, vector<int> &buf, vector<int> &tar) { if (n == 1) { move(src, tar); return; } dfs(n - 1, src, tar, buf); move(src, tar); dfs(n - 1, buf, src, tar); } void solveHanota(vector<int> &A, vector<int> &B, vector<int> &C) { int n = A.size(); dfs(n, A, B, C); } ``` ( )

9. 所有递归算法都可以转换为迭代算法。 ( )

10. 贪心算法总能得到全局最优解。 ( )