跟老马一起“升级打怪”学编程！

旨在为小朋友们提供全面的学习材料，共同为等级考试做好准备。

添加小助手微信，回复【GESP 2026.03 C++五级】，获取本套试题答案。

2026年GESP03月认证C++五级试卷分数：100 题数：27

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

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

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

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

• A.

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

• B.

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

• C.

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

• D.

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

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

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

• A.

cur = cur->next;

• B.

cur->next = del->next;

• C.

del->next = cur->next;

• D.

cur->next = nullptr;

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

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

• A.

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

• B.

gcd(48,18) -> gcd(30,18) -> gcd(12,18)

• C.

gcd(48,18) -> gcd(18,30) -> gcd(30,6)

• D.

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; __________________________             && (longlong)i * primes[j] <= n; j++) {            is_composite[i * primes[j]] = true;if (i % primes[j] == 0)break;        }    }return primes;}

• A.

j <= n

• B.

j < sqrt(n)

• C.

j < primes.size()

• D.

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 (longlong j = (longlong)i * i; j <= n; j += i)            is_composite[j] = true;    }return primes;}

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

7、下面程序的运行结果为？（ ）

boolcheck(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;}intsolve(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;}intmain(){int a[] = {1, 2, 8, 4, 9};int n = 5;int k = 3;std::cout << solve(n, a, k) << std::endl;return 0;}

• A. 2
• B. 3
• C. 4
• D. 5

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

intlowerBound(constvector<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;}

• A.

r = mid;

• B.

r = mid - 1;

• C.

l = mid;

• D.

l = mid + 1;

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

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

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

constint MAXN = 100005;long long a[MAXN];int n, m;boolcheck(longlong 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;}intmain(){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;}

• A.

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

• B.

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

• C.

l = mid + 1;r = mid;

• D.

l = mid;r = mid + 1;

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

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

• A. 
• B. 
• C. 
• D. 

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

• A. A[i] >= B[j]
• B. A[i] <= B[j]
• C. i >= j
• D. i <= j

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

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

• A. 
• B. 
• C. 
• D. 

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

• A. 冒泡排序和插入排序都是稳定的排序算法
• B. 快速排序和归并排序都是不稳定的排序算法
• C. 冒泡排序和插入排序最好时间复杂度均为
• D. 归并排序在最好、最坏和平均三种情况的时间复杂度均为 

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

intmain(){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;}

• A.

rem /= b;

• B.

rem %= b;

• C.

rem = b;

• D.

rem = q;

二、判断题（共10题，每题2分，共20分）

1、有一个存储了个整数的线性表，分别用数组和单链表两种方式实现。在已知下标（或结点指针）的前提下，数组的随机访问是 ， 而在链表中已知某结点的指针时，在该结点之后插入一个新结点的操作也是 。

• 正确（）；
• 错误（）；

2、若数组 a 已按升序排列，则下面代码可以正确实现 “在 a 中查找第一个大于等于 x 的元素的位置”。

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

• 正确（）；
• 错误（）；

3、快速排序只要每次都选取中间元素作为枢轴，就一定是稳定排序。

• 正确（）；
• 错误（）；

4、若某算法满足递推式：，则其时间复杂度为 。

• 正确（）；
• 错误（）；

5、在一个数组中，如果两个元素 a[i] 和 a[j]满足i < j且 a[i] > a[j]，则a[i] 和 a[j]是一个逆序对。下面代码可以正确统计数组a区间 [l,r] 内的逆序对总数。

longlong cnt=0;voidmerge_count(vector<int>& a, int l, int m, int r){int i = l, j = m + 1;while(i <= m && j <= r) {if(a[i] <= a[j]) i++;else {            cnt += (m -  i+ 1);            j++;        }    }}

• 正确（）；
• 错误（）；

6、唯一分解定理保证：若一个数未被任何不超过其平方根的质数筛去，则它一定是质数。

• 正确（）；
• 错误（）；

7、假设数组的值域范围是，以下程序的时间复杂度是。

boolcheck(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;}intsolve(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;}intmain(){int a[] = {1, 2, 8, 4, 9};int n = 5;int k = 3;std::cout << solve(n, a, k) << std::endl;return 0;}

• 正确（）；
• 错误（）；

8、若一个问题满足最优子结构性质，则一定可以用贪心算法得到最优解。

• 正确（）；
• 错误（）；

9、线性筛相比埃氏筛的核心改进在于：埃氏筛中一个合数可能被多个质数重复标记，线性筛通过"每个合数只被其最大质因子筛去"的策略，保证每个合数恰好被标记一次，从而实现  的时间复杂度。

• 正确（）；
• 错误（）；

10、任何递归程序都可以改写为等价的非递归程序，但改写后的非递归程序一定需要显式地使用栈来模拟递归调用过程。

• 正确（）；
• 错误（）；

三、编程题（共2题，共50分）

1、有限不循环小数

【提交】

https://www.luogu.com.cn/problem/P15798

【问题描述】

若  可化为一个有限的，不循环的小数，则称  为终止数。

请你求出在  到  中终止数的数量。

【输入描述】

输入一行，包含两个整数 。

【输出描述】

输出一行，包含一个整数，表示  到  中终止数的数量。

【样例输入1】

2 11

【样例输出1】

5

【样例解释】

在  终止数有 。

【数据范围】

保证 。

2、找数

【提交】

https://www.luogu.com.cn/problem/P15799

【问题描述】

给定一个包含  个互不相同的正整数的数组  与一个包含  个互不相同的正整数的数组 ，请你帮忙计算有多少数在数组  与 数组  中均出现。

【输入描述】

第一行包含两个整数 。

第二行包含  个正整数  表示数组 。

第二行包含  个正整数  表示数组 。

【输出描述】

输出一个整数，表示在数组  与 数组  中均出现的数的个数。

【样例输入1】

3 54 2 33 1 5 4 6

【样例输出1】

2

【样例解释】

样例 1 中，、 在数组  与  中均出现。

【数据范围】

对于 40% 的数据，保证 。

对于 100% 的数据，保证 ，。

青少年编程竞赛交流