GESP 五级 · 2025 真题

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

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

01// 结点结构体
02struct Node {
03    int val;
04    Node* next;
05    Node() : val(0), next(nullptr) {}
06    Node(int x) : val(x), next(nullptr) {}
07    Node(int x, Node *next) : val(x), next(next) {}
08};
09
10Node* removeElements(Node* head, int val) {
11    Node dummy(0, head);        // 哑结点，统一处理头结点
12    Node* cur = &dummy;
13    while (cur->next) {
14        if (cur->next->val == val) {
15            ____________        // 在此填入代码
16        }
17        else {
18            cur = cur->next;
19        }
20    }
21    return dummy.next;
22}

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

01struct Node {
02    int val;
03    Node *next;
04    Node(int x) : val(x), next(nullptr) {}
05};
06
07bool hasCycle(Node *head) {
08    if (!head || !head->next)
09        return false;
10    Node* slow = head;
11    Node* fast = head->next;
12    while (fast && fast->next) {
13        if (slow == fast) return true;
14        ____________        // 在此填入代码
15    }
16    return false;
17}

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

01bool isPerfectNumber(int n) {
02    if(n <= 1) return false;
03    int sum = 1;
04    for(int i = 2; ____________; i++) {
05        if(n % i == 0) {
06            sum += i;
07            if(i != n/i) sum += n/i;
08        }
09    }
10    return sum == n;
11}

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

01int gcd0(int a, int b) {
02    if (a < b) {
03        swap(a, b);
04    }
05    while(b != 0) {
06        int temp = a % b;
07        a = b;
08        b = temp;
09    }
10    return ____________;
11}

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

01vector<bool> sieve(int n) {
02    vector<bool> is_prime(n+1, true);
03    is_prime[0] = is_prime[1] = false;
04    for(int i = 2; i <= n; i++) {
05        if(is_prime[i]) {
06            for(int j = ____________; j <= n; j += i) {
07                is_prime[j] = false;
08            }
09        }
10    }
11    return is_prime;
12}

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

01vector<int> linearSieve(int n) {
02    vector<bool> is_prime(n+1, true);
03    vector<int> primes;
04    for(int i = 2; i <= n; i++) {
05        if(is_prime[i]) primes.push_back(i);
06        for(int p : primes) {
07            if(p * i > n) break;
08            is_prime[p * i] = false;
09            if(____________) break;
10        }
11    }
12    return primes;
13}

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

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

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

01// 统计矩阵中 <= x 的元素个数：从左下角开始
02int countLE(const vector<vector<int>>& matrix, int x) {
03    int n = (int)matrix.size();
04    int i = n - 1, j = 0, cnt = 0;
05    while (i >= 0 && j < n) {
06        if (matrix[i][j] <= x) {
07            cnt += i + 1;
08            ++j;
09        }
10        else {
11            --i;
12        }
13    }
14    return cnt;
15}
16
17int kthSmallest(vector<vector<int>>& matrix, int k) {
18    int n = (int)matrix.size();
19    int lo = matrix[0][0];
20    int hi = matrix[n - 1][n - 1];
21    while (lo < hi) {
22        int mid = lo + (hi - lo) / 2;
23        if (countLE(matrix, mid) >= k) {
24            ____________        // 在此处填入代码
25        } else {
26            ____________        // 在此处填入代码
27        }
28    }
29    return lo;
30}

下述 C++ 代码实现了快速排序算法，下面说法错误的是（ ）。

01int partition(vector<int>& arr, int low, int high) {
02    int i = low, j = high;
03    int pivot = arr[low];                 // 以首元素为基准
04    while (i < j) {
05        while (i < j && arr[j] >= pivot) j--;   // 从右往左查找
06        while (i < j && arr[i] <= pivot) i++;   // 从左往右查找
07        if (i < j) swap(arr[i], arr[j]);
08    }
09    swap(arr[i], arr[low]);
10    return i;
11}
12
13void quickSort(vector<int>& arr, int low, int high) {
14    if (low >= high) return;
15    int p = partition(arr, low, high);
16    quickSort(arr, low, p - 1);
17    quickSort(arr, p + 1, high);
18}

下述 C++ 代码实现了归并排序算法，则横线上应填写（ ）。

01void merge(vector<int> &nums, int left, int mid, int right) {
02    // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
03    vector<int> tmp(right - left + 1);
04    int i = left, j = mid + 1, k = 0;
05    while (i <= mid && j <= right) {
06        if (nums[i] <= nums[j])
07            tmp[k++] = nums[i++];
08        else
09            tmp[k++] = nums[j++];
10    }
11    while (i <= mid) {
12        tmp[k++] = nums[i++];
13    }
14    while (____________) {    // 在此处填入代码
15        tmp[k++] = nums[j++];
16    }
17    for (k = 0; k < tmp.size(); k++) {
18        nums[left + k] = tmp[k];
19    }
20}
21
22void mergeSort(vector<int> &nums, int left, int right) {
23    if (left >= right)
24        return;
25    int mid = (left + right) / 2;
26    mergeSort(nums, left, mid);
27    mergeSort(nums, mid + 1, right);
28    merge(nums, left, mid, right);
29}

假设你是一家电影院的排片经理，只有一个放映厅。你有一个电影列表 movies，其中 movies[i] = [start_i, end_i] 表示第 $i$ 部电影的开始和结束时间。请你找出最多能安排多少部不重叠的电影，则横线上应分别填写的代码为（ ）。

01int maxMovies(vector<vector<int>>& movies) {
02    if (movies.empty()) return 0;
03    sort(movies.begin(), movies.end(), [](const vector<int>& a, const vector<int>& b) {
04        return ____________; // 在此处填入代码
05    });
06    int count = 1;
07    int lastEnd = movies[0][1];
08    for (int i = 1; i < movies.size(); i++) {
09        if (movies[i][0] >= lastEnd) {
10            count++;
11            ____________ = movies[i][1]; // 在此处填入代码
12        }
13    }
14    return count;
15}

给定一个整数数组 nums，下面代码找到一个具有最大和的连续子数组，并返回该最大和。则下面说法错误的是（ ）。

01int crossSum(vector<int>& nums, int left, int mid, int right) {
02    int leftSum = INT_MIN, rightSum = INT_MIN;
03    int sum = 0;
04    for (int i = mid; i >= left; i--) {
05        sum += nums[i];
06        leftSum = max(leftSum, sum);
07    }
08    sum = 0;
09    for (int i = mid + 1; i <= right; i++) {
10        sum += nums[i];
11        rightSum = max(rightSum, sum);
12    }
13    return leftSum + rightSum;
14}
15
16int helper(vector<int>& nums, int left, int right) {
17    if (left == right)
18        return nums[left];
19    int mid = left + (right - left) / 2;
20    int leftMax = helper(nums, left, mid);
21    int rightMax = helper(nums, mid + 1, right);
22    int crossMax = crossSum(nums, left, mid, right);
23    return max({leftMax, rightMax, crossMax});
24}
25
26int maxSubArray(vector<int>& nums) {
27    return helper(nums, 0, nums.size() - 1);
28}

给定一个由非负整数组成的数组 digits，表示一个非负整数的各位数字，其中最高位在数组首位，且 digits 不含前导 $0$（除非是 $0$ 本身）。下面代码对该整数执行 $+1$ 操作，并返回结果数组，则横线上应填写（ ）。

01vector<int> plusOne(vector<int>& digits) {
02    for (int i = (int)digits.size() - 1; i >= 0; --i) {
03        if (digits[i] < 9) {
04            digits[i] += 1;
05            return digits;
06        }
07        ____________        // 在此处填入代码
08    }
09    digits.insert(digits.begin(), 1);
10    return digits;
11}

基于下面定义的函数，通过判断 isDivisibleBy9(n) == isDigitSumDivisibleBy9(n) 代码可验算如果一个数能被 $9$ 整除，则它的各位数字之和能被 $9$ 整除。

01bool isDivisibleBy9(int n) {
02    return n % 9 == 0;
03}
04
05bool isDigitSumDivisibleBy9(int n) {
06    int sum = 0;
07    string numStr = to_string(n);
08    for (char c : numStr) {
09        sum += (c - '0');
10    }
11    return sum % 9 == 0;
12}

假设函数 gcd() 能正确求两个正整数的最大公约数，则下面的 findMusicalPattern(4, 6) 函数返回 $2$。

01void findMusicalPattern(int rhythm1, int rhythm2) {
02    int commonDivisor = gcd(rhythm1, rhythm2);
03    int patternLength = (rhythm1 * rhythm2) / commonDivisor;
04    return patternLength;
05}

下面递归实现的斐波那契数列的时间复杂度为 $O(2^n)$。

01long long fib_memo(int n, long long memo[]) {
02    if (n <= 1) return n;
03    if (memo[n] != -1) return memo[n];
04    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
05    return memo[n];
06}
07
08int main() {
09    int n = 40;
10    long long memo[100];
11    fill_n(memo, 100, -1);
12    long long result2 = fib_memo(n, memo);
13    return 0;
14}

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

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

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

快速排序和归并排序都是稳定的排序算法。

下面代码采用分治算法求解标准 $3$ 柱汉诺塔问题，时间复杂度为 $O(n \log n)$。

01void move(vector<int> &src, vector<int> &tar) {
02    int pan = src.back();
03    src.pop_back();
04    tar.push_back(pan);
05}
06
07void dfs(int n, vector<int> &src, vector<int> &buf, vector<int> &tar) {
08    if (n == 1) {
09        move(src, tar);
10        return;
11    }
12    dfs(n - 1, src, tar, buf);
13    move(src, tar);
14    dfs(n - 1, buf, src, tar);
15}
16
17void solveHanota(vector<int> &A, vector<int> &B, vector<int> &C) {
18    int n = A.size();
19    dfs(n, A, B, C);
20}

所有递归算法都可以转换为迭代算法。

贪心算法总能得到全局最优解。