GESP C++ 五级 2025年09月考试试卷

1 单选题（每题 2 分，共 30 分）

第 1 题

以下哪种情况使用链表比数组更合适？ {{ select(1) }}

• 数据量固定且读多写少
• 需要频繁在中间或开头插入、删除元素
• 需要高效随机访问元素
• 存储空间必须连续

第 2 题

函数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;
}

{{ select(2) }}

• Node* del = cur; cur = del->next; delete del;
• Node* del = cur->next; cur->next = del; delete del;
• Node* del = cur->next; cur->next = del->next; delete del;
• Node* del = cur->next; delete del; cur->next = del->next;

第 3 题

函数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;
}

{{ select(3) }}

• slow = slow->next; fast = fast->next->next;
• slow = fast->next; fast = slow->next->next;
• slow = slow->next; fast = slow->next->next;
• slow = fast->next; fast = fast->next->next;

第 4 题

函数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;
}

{{ select(4) }}

• i <= n
• i*i <= n
• i <= n/2
• i < n

第 5 题

以下代码计算两个正整数的最大公约数（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 ______;
}

{{ select(5) }}

• b
• a
• temp
• a * b

第 6 题

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

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;
}

{{ select(6) }}

• i
• i+1
• i*2
• i*i

第 7 题

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

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;
}

{{ select(7) }}

• i % p == 0
• p % i == 0
• i == p
• i * p == n

第 8 题

关于埃氏筛和线性筛的比较，下列说法错误的是( )。 {{ select(8) }}

• 埃氏筛可能会对同一个合数进行多次标记
• 线性筛的理论时间复杂度更优，所以线性筛的速度往往优于埃氏筛
• 线性筛保证每个合数只被其最小质因子筛到一次
• 对于常见范围 ((n ≤10^{7}))，埃氏筛因实现简单，常数较小，其速度往往优于线性筛

第 9 题

唯一分解定理描述的是( )。 {{ select(9) }}

• 每个整数都能表示为任意素数的乘积
• 每个大于1的整数能唯一分解为素数幂乘积（忽略顺序）
• 合数不能分解为素数乘积
• 素数只有两个因子：1和自身

第 10 题

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

// 统计矩阵中<=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;
}

{{ select(10) }}

• hi = mid;；lo = mid + 1;
• hi = mid - 1;；lo = mid;
• hi = mid;；lo = mid;
• hi = mid + 1;；lo = mid;

第 11 题

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

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[low]; // 以首元素为基准
    int i = low, j = high;
    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);
}

{{ select(11) }}

• 快速排序之所以叫“快速”，是因为它在平均情况下运行速度较快，常数小、就地排序，实践中通常比归并排序更高效
• 在平均情况下，划分的递归层数为 (O(\log n))，每层中的总循环数为 (O(n))，总时间为 (O(n\log n))
• 在最差情况下，每轮划分操作都将长度为(n)的数组划分为长度为0和 (n-1) 的两个子数组，此时递归层数达到 (O(n))，每层中的循环数为(O(n))，总时间为 (O(n^2))
• 划分函数partition中“从右往左查找”与“从左往右查找”的顺序可以交换

第 12 题

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

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);
}

{{ select(12) }}

• i < mid
• j < right
• i <= mid
• j <= right

第 13 题

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

int maxMovies(vector<vector<int>>& movies) {
    if (movies.empty()) 
        return 0;
    sort(movies.begin(), movies.end(), [](const vector<int>& a, const vector<int>& b) { 
        ________________ // 在此处填入代码
    });
    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;
}

{{ select(13) }}

• a[0] < b[0] 和 lastEnd
• a[1] < b[1] 和 lastEnd
• a[0] < b[0] 和 movies[i][0]
• a[1] < b[1] 和 movies[i][0]

第 14 题

给定一个整数数组nums，函数maxSubArray求解最大子数组和，下面说法错误的是( )。

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);
}

{{ select(14) }}

• 上述代码采用分治算法实现
• 上述代码采用贪心算法
• 上述代码时间复杂度为 (O(n\log n))
• 上述代码采用递归方式实现

第 15 题

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

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;
}

{{ select(15) }}

• digits[i] = 0;
• digits[i] = 9;
• digits[i] = 1;
• digits[i] = 10;

2 判断题（每题 2 分，共 20 分）

第 16 题

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

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;
}

{{ select(16) }}

• 正确
• 错误

第 17 题

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

void findMusicalPattern(int rhythm1, int rhythm2) { 
    int commonDivisor = gcd(rhythm1, rhythm2);
    int patternLength = (rhythm1 * rhythm2) / commonDivisor;
    return patternLength;
}

{{ select(17) }}

• 正确
• 错误

第 18 题

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

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;
}

{{ select(18) }}

• 正确
• 错误

第 19 题

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

• 正确
• 错误

第 20 题

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

• 正确
• 错误

第 21 题

线性筛关键是“每个合数只会被最小质因子筛到一次”，因此时间复杂度为 (O(n))。( ) {{ select(21) }}

• 正确
• 错误

第 22 题

快速排序和归并排序都是稳定的排序算法。( ) {{ select(22) }}

• 正确
• 错误

第 23 题

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

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);
}

{{ select(23) }}

• 正确
• 错误

第 24 题

所有递归算法都可以转换为迭代算法。( ) {{ select(24) }}

• 正确
• 错误

第 25 题

贪心算法总能得到全局最优解。( ) {{ select(25) }}

• 正确
• 错误