GESP C++ 五 级 2025年9月真题（180 分钟，总分 100 分）

单选题（共 15 题，每题 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⁷），埃氏筛因实现简单，常数较小，其速度往往优于线性筛

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

{{ select(9) }}

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

10. 给定一个 n x 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 - 1;
lo = mid + 1;
• hi = mid;
lo = mid;
• hi = mid;
lo = mid + 1;
• hi = mid + 1;
lo = mid;

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

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

{{ select(11) }}

• 快速排序之所以叫“快速”，是因为它在平均情况下运行速度较快，常数小、就地排序，实践中通常比归并排序更高效。
• 在平均情况下，划分的递归层数为 log n，每层中的总循环数为 n，总时间为 O(n log n)。
• 在最差情况下，每轮划分操作都将长度为 n 的数组划分为长度为 0 和 n-1 的两个子数组，此时递归层数达到  n，每层中的循环数为 n，总时间为 O(n²)。
• 划分函数 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) {
       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;
}

{{ 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，下面代码找到一个具有最大和的连续子数组，并返回该最大和。则下面说法错误的是（   ）。

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;