#1169. GESP C++ 五 级 2026年3月真题 · 单选题

GESP C++ 五 级 2026年3月真题 · 单选题

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

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

1. 关于单链表、双链表和循环链表，下列说法正确的是（）。

{{ select(1) }}

  • 在单链表中，若已知任意结点的指针，则可以在O(1)时间内删除该结点。
  • 循环链表中一定不存在空指针。
  • 在循环双链表中，尾结点的next指针一定为nullptr。
  • 在带头结点的循环单链表中，判定链表是否为空只需判断头结点的next是否指向自身。

2. 双向循环链表中要在结点p之前插入新结点s（均非空），以下指针操作正确的是（）。

{{ select(2) }}

  • s -> next = p;
    p -> prev = s;
    p -> next = s;
    s -> prev = p;
  • s -> prev = p;
    s -> next = p -> next;
    p -> next -> prev = s;
    p -> next = s;
  • s -> next = p;
    s -> prev = p->prev;
    p -> prev -> next = s;
    p -> prev = s;
  • s -> next = p;
    s -> prev = nullptr;
    p -> prev = s;

3. 下面函数用“哑结点”统一处理删除单向链表中的头结点与中间结点。横线处应填（）。

struct Node{
   int val;
   Node* next;
   Node(int v):val(v),next(nullptr){}
};
Node* eraseAll(Node* head, int x){
   Node dummy(0);
   dummy.next = head;
   Node* cur = &dummy;
   while(cur->next){
       if(cur->next->val == x){
           Node* del = cur->next;
           ______________________
           delete del;
      }else cur = cur->next;
  }
   return dummy.next;
}

{{ select(3) }}

  • cur = cur->next;
  • cur->next = del->next;
  • del->next = cur->next;
  • cur->next = nullptr;

4. 对如下代码实现的欧几里得算法（辗转相除法），执行gcd(48, 18)得到的调用序列为（）。

int gcd(int a, int b) {
   return b == 0 ? a : gcd(b, a % b);
}

{{ select(4) }}

  • gcd(48,18) -> gcd(18,12) -> gcd(12,6) -> gcd(6,0)
  • gcd(48,18) -> gcd(30,18) -> gcd(12,18)
  • gcd(48,18) -> gcd(18,30) -> gcd(30,6)
  • gcd(48,18) -> gcd(12,18) -> gcd(6,12)

5. 下面代码实现了欧拉（线性）筛，横线处应填写（）。

vector<int> euler_sieve(int n) {
   vector<bool> is_composite(n + 1, false);
   vector<int>  primes;                    
   for (int i = 2; i <= n; i++) {
       if (!is_composite[i])
           primes.push_back(i);
       for (int j = 0; __________________________ && (long long)i * primes[j] <= n; j++) {
           is_composite[i * primes[j]] = true;
           if (i % primes[j] == 0)
               break;
      }
  }
   return primes;
}

{{ select(5) }}

  • j <= n
  • j < sqrt(n)
  • j < primes.size()
  • j < i

6. 埃氏筛中将内层循环从j = i*i 开始而不是j = 2*i的主要原因是（）。

vector<int> eratosthenes_sieve(int n) {
   vector<bool> is_composite(n + 1, false);
   vector<int>  primes;
   for (int i = 2; i <= n; i++) {
       if (is_composite[i]) continue;
       primes.push_back(i);
       for (long long j = (long long)i * i; j <= n; j += i)
           is_composite[j] = true;
  }
   return primes;
}

{{ select(6) }}

  • 因为2*i一定不是合数
  • i*i一定是质数
  • 小于i*i的i的倍数已被更小质因子筛过
  • 这样可以把时间复杂度降为O(n)

7. 下面程序的运行结果为（）。

bool check(int n, int a[], int k, int dist) {
   int cnt = 1;
   int last = a[0];
   for (int i = 1; i < n; i++) {
       if (a[i] - last >= dist) {
           cnt++;
           last = a[i];
      }
  }
   return cnt >= k;
}

int solve(int n, int a[], int k) {
   std::sort(a, a + n);
   int l = 0;
   int r = a[n - 1] - a[0];
   while (l < r) {
       int mid = (l + r + 1) / 2;
       if (check(n, a, k, mid))
           l = mid;
       else
           r = mid - 1;
  }
   return l;
}

int main() {
   int a[] = {1, 2, 8, 4, 9};
   int n = 5;
   int k = 3;
   
   std::cout << solve(n, a, k) << std::endl;
   return 0;
}

{{ select(7) }}

  • 2
  • 3
  • 4
  • 5

8. 在升序数组中查找第一个大于等于x的位置，下面循环中横线应填（）。

int lowerBound(const vector<int>& a, int x){
   int l=0, r=a.size();
   while(l<r){
       int mid = l + (r - l)/2;
       if(a[mid] >= x)  _____________;
       else l = mid + 1;
  }
   return l;
}

{{ select(8) }}

  • r = mid;
  • r = mid - 1;
  • l = mid;
  • l = mid + 1;

9. 关于递归函数调用，下列说法错误的是（）。

{{ select(9) }}

  • 递归调用层次过深时，可能会耗尽栈空间导致栈溢出
  • 尾递归函数可以通过编译器优化来避免栈溢出
  • 所有递归函数都可以通过循环结构来改写，从而避免栈溢出
  • 栈溢出发生时，程序会抛出异常并可以继续执行后续代码

10. 给定n根木头，第 i 根长度为 a[i] 要切成不少于 m 段等长木段求最大可能长度，则横线上应填写（）。

const int MAXN = 100005;
long long a[MAXN];
int n, m;
bool check(long long x){
   long long cnt = 0;
   for(int i = 1; i <= n; i++){
       if(x == 0) return true;
       cnt += a[i] / x;
       if(cnt >= m) return true;
  }
   return false;
}
int main(){
   cin >> n >> m;
   long long mx = 0;
   for(int i = 1; i <= n; i++){
       cin >> a[i];
       mx = max(mx, a[i]);
  }
   long long l = 1, r = mx;
   long long ans = 0;
   while(l <= r){
       long long mid = l + (r - l) / 2;
       if(check(mid)){
           ans = mid;
           ______________________
      }else{
           ______________________
      }
  }
   cout << ans << endl;
   return 0;
}

{{ select(10) }}

  • l = mid + 1;
    r = mid - 1;
  • l = mid - 1;
    r = mid + 1;
  • l = mid + 1;
    r = mid;
  • l = mid;
    r = mid + 1;

11. 下面代码用分治求“最大连续子段和”，其时间复杂度为（）。

int solve(vector<int>& a, int l, int r){
   if(l == r) return a[l];
   int mid = l + (r - l) / 2;
   int left = solve(a, l, mid);
   int right = solve(a, mid + 1, r);
   int sum = 0, lmax = INT_MIN;
   for(int i = mid; i >= l; i--){
       sum += a[i];
       lmax = max(lmax, sum);
  }
   sum = 0;
   int rmax = INT_MIN;
   for(int i = mid + 1; i <= r; i++){
       sum += a[i];
       rmax = max(rmax, sum);
  }
   return max({left, right, lmax + rmax});
}

{{ select(11) }}

  • O( n2 )
  • O( n log n )
  • O( log n )
  • O( n )

12. 游戏⼤赛决赛，两组选⼿分别按得分从⼩到⼤排好队，现在要把他们合并成⼀个有序排⾏榜。A组： :A={12,35,67,89}, B组:B={20,45,55,78}下面是归并合并函数的核心循环，横线处应填入（）。

int i = 0, j = 0;
vector<int> result;
while (i < A.size() && j < B.size()) {
   if (___________________) {
       result.push_back(A[i++]);
  } else {
       result.push_back(B[j++]);
  }
}
while (i < A.size()) {
   result.push_back(A[i++]);
}
while (j < B.size()) {
   result.push_back(B[j++]);
}

{{ select(12) }}

  • A[i] >= B[j]
  • A[i] <= B[j]
  • i >= j
  • i <= j

13. 有 n 位同学的成绩已经从小到大排好序，现在对它执行下面这段以第一个元素为pivot的快速排序，请问此次排序的时间复杂度是（）。

void quicksort(vector<int>& a, int l, int r) {
   if (l >= r) return;
   int pivot = a[l];        
   int i = l, j = r;
   while (i < j) {
       while (i < j && a[j] >= pivot) j--;
       while (i < j && a[i] <= pivot) i++;
       if (i < j) swap(a[i], a[j]);
  }
   swap(a[l], a[i]);
   quicksort(a, l, i - 1);
   quicksort(a, i + 1, r);
}

{{ select(13) }}

  • O( n )
  • O( n log n )
  • O( n2 )
  • O( log n )

14. 下面关于排序算法的描述中，不正确的是（）。

{{ select(14) }}

  • 冒泡排序和插入排序都是稳定的排序算法
  • 快速排序和归并排序都是不稳定的排序算法
  • 冒泡排序和插入排序最好时间复杂度均为 O(n)
  • 归并排序在最好、最坏和平均三种情况的时间复杂度均为 O( n log n )

15. 下面代码实现两个整数除法，其中被除数为一个'大整数''用字符串表示，除数是一个小整数'用 Int 表示，则横线处应该填写（）。

int main(){
   string s;
   int b;
   cin >> s >> b;
   vector<int> a;
   for(char c : s){
       a.push_back(c - '0');
  }
   vector<int> c;
   long long rem = 0;
   for(int i = 0; i < a.size(); i++){
       rem = rem * 10 + a[i];
       int q = rem / b;
       c.push_back(q);
       ______________________
  }
   int pos = 0;
   while(pos < c.size() - 1 && c[pos] == 0) pos++;
   for(int i = pos; i < c.size(); i++){
       cout << c[i];
  }
   cout << endl;
   cout << rem << endl;
   return 0;
}

{{ select(15) }}

  • rem /= b;
  • rem %= b;
  • rem = b;
  • rem = q;

相关

在下列比赛中:

GESP C++ 五 级 2026年3月真题

  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 21ms
  4. Powered by Hydro v5.0.4 Community