202603 GESP认证 C++编程五级真题试卷

单选题共 15 题

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

在单链表中，若已知任意结点的指针，则可以在O(1)时间内删除该结点。

循环链表中一定不存在空指针。

在循环双链表中，尾结点的 next 指针一定为 nullptr 。

在带头结点的循环单链表中，判定链表是否为空只需判断头结点的 next 是否指向自身。

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

1 s -> next = p;
2 p -> prev = s;
3 q -> next = s;
4 s -> prev = q;

1 s -> prev = p;
2 s -> next = p -> next;
3 p -> next -> prev = s;
4 p -> next = s;

1 s -> next = p;
2 s -> prev = p->prev;
3 p -> prev -> next = s;
4 p -> prev = s;

1 s -> next = p;
2 s -> prev = nullptr;
3 p -> prev = s;

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

1 struct Node{
2  int val;
3  Node* next;
4  Node(int v):val(v),next(nullptr){}
5 };
6
7 Node* eraseAll(Node* head, int x){
8  Node dummy(0);
9  dummy.next = head;
10  Node* cur = &dummy;
11  while(cur->next){
12   if(cur->next->val == x){
13    Node* del = cur->next;
14    ______________________
15    delete del;
16   }else cur = cur->next;
17  }
18  return dummy.next;
19 }

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

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

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

1 vector<int> euler_sieve(int n) {
2  vector<bool> is_composite(n + 1, false);
3  vector<int> primes;
4
5  for (int i = 2; i <= n; i++) {
6   if (!is_composite[i])
7    primes.push_back(i);
8
9   for (int j = 0; __________________________ && (long long)i * primes[j] <= n; j++) {
10    is_composite[i * primes[j]] = true;
11
12    if (i % primes[j] == 0)
13     break;
14   }
15  }
16  return primes;
17 }

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

1 vector<int> eratosthenes_sieve(int n) {
2  vector<bool> is_composite(n + 1, false);
3  vector<int> primes;
4
5  for (int i = 2; i <= n; i++) {
6   if (is_composite[i]) continue;
7
8   primes.push_back(i);
9
10   for (long long j = (long long)i * i; j <= n; j += i)
11    is_composite[j] = true;
12  }
13  return primes;
14 }

因为 2*i 一定不是合数

i*i 一定是质数

小于 i*i 的 i 的倍数已被更小质因子筛过

这样可以把时间复杂度降为O(n)

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

1 bool check(int n, int a[], int k, int dist) {
2  int cnt = 1;
3  int last = a[0];
4
5  for (int i = 1; i < n; i++) {
6   if (a[i] - last >= dist) {
7    cnt++;
8    last = a[i];
9   }
10  }
11
12  return cnt >= k;
13 }
14
15 int solve(int n, int a[], int k) {
16  std::sort(a, a + n);
17
18  int l = 0;
19  int r = a[n - 1] - a[0];
20
21  while (l < r) {
22   int mid = (l + r + 1) / 2;
23
24   if (check(n, a, k, mid))
25    l = mid;
26   else
27    r = mid - 1;
28  }
29
30  return l;
31 }
32
33 int main() {
34  int a[] = {1, 2, 8, 4, 9};
35  int n = 5;
36  int k = 3;
37
38  std::cout << solve(n, a, k) << std::endl;
39
40  return 0;
41 }

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

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

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

递归调用层次过深时，可能会耗尽栈空间导致栈溢出

尾递归函数可以通过编译器优化来避免栈溢出

所有递归函数都可以通过循环结构来改写，从而避免栈溢出

栈溢出发生时，程序会抛出异常并可以继续执行后续代码

10.

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

1 const int MAXN = 100005;
2 long long a[MAXN];
3 int n, m;
4
5 bool check(long long x){
6  long long cnt = 0;
7  for(int i = 1; i <= n; i++){
8   if(x == 0) return true;
9   cnt += a[i] / x;
10   if(cnt >= m) return true;
11  }
12  return false;
13 }
14
15 int main(){
16  cin >> n >> m;
17  long long mx = 0;
18  for(int i = 1; i <= n; i++){
19   cin >> a[i];
20   mx = max(mx, a[i]);
21  }
22
23  long long l = 1, r = mx;
24  long long ans = 0;
25
26  while(l <= r){
27   long long mid = l + (r - l) / 2;
28
29   if(check(mid)){
30    ans = mid;
31    ______________________
32   }else{
33    ______________________
34   }
35  }
36
37  cout << ans << endl;
38  return 0;
39 }

11.

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

1 int solve(vector<int>& a, int l, int r){
2  if(l == r) return a[l];
3
4  int mid = l + (r - l) / 2;
5
6  int left = solve(a, l, mid);
7  int right = solve(a, mid + 1, r);
8
9  int sum = 0, lmax = INT_MIN;
10  for(int i = mid; i >= l; i--){
11   sum += a[i];
12   lmax = max(lmax, sum);
13  }
14
15  sum = 0;
16  int rmax = INT_MIN;
17  for(int i = mid + 1; i <= r; i++){
18   sum += a[i];
19   rmax = max(rmax, sum);
20  }
21
22  return max({left, right, lmax + rmax});
23 }

O(n²)

O(nlogn)

O(logn)

O(n)

12.

游戏大赛决赛，两组选手分别按得分从小到大排好队，现在要把他们合并成一个有序排行榜。

A组： A = {12, 35, 67, 89} ，B组： B = {20, 45, 55, 78} ，下面是归并合并函数的核心循环，横线处应填入（）。

1 int i = 0, j = 0;
2 vector<int> result;
3
4 while (i < A.size() && j < B.size()) {
5  if (___________________) {
6   result.push_back(A[i++]);
7  } else {
8   result.push_back(B[j++]);
9  }
10 }
11
12 while (i < A.size()) {
13  result.push_back(A[i++]);
14 }
15
16 while (j < B.size()) {
17  result.push_back(B[j++]);
18 }

A[i] >= B[j]

A[i] <= B[j]

i >= j

i <= j

13.

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

1 void quicksort(vector<int>& a, int l, int r) {
2  if (l >= r) return;
3  int pivot = a[l];
4  int i = l, j = r;
5  while (i < j) {
6   while (i < j && a[j] >= pivot) j--;
7   while (i < j && a[i] <= pivot) i++;
8   if (i < j) swap(a[i], a[j]);
9  }
10  swap(a[l], a[i]);
11  quicksort(a, l, i - 1);
12  quicksort(a, i + 1, r);
13 }

O(n)

O(nlogn)

O(n²)

O(logn)

14.

下面关于排序算法的描述中，不正确的是( )。

冒泡排序和插入排序都是稳定的排序算法

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

冒泡排序和插入排序最好时间复杂度均为O(n)

归并排序在最好、最坏和平均三种情况的时间复杂度均为O(nlogn)

15.

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

1 int main(){
2  string s;
3  int b;
4  cin >> s >> b;
5
6  vector<int> a;
7  for(char c : s){
8   a.push_back(c - '0');
9  }
10
11  vector<int> c;
12  long long rem = 0;
13
14  for(int i = 0; i < a.size(); i++){
15   rem = rem * 10 + a[i];
16   int q = rem / b;
17   c.push_back(q);
18   ______________________
19  }
20
21  int pos = 0;
22  while(pos < c.size() - 1 && c[pos] == 0) pos++;
23
24  for(int i = pos; i < c.size(); i++){
25   cout << c[i];
26  }
27
28  cout << endl;
29  cout << rem << endl;
30  return 0;
31 }

判断题共 10 题

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

A 正确 B 错误

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

1 int lowerBound(vector<int>& a,int x){
2  int l=0, r=a.size();
3  while(l < r) {
4   int mid = (l + r) / 2;
5   if( a[mid] >= x) r = mid;
6   else l = mid + 1;
7  }
8  return l;
9 }

A 正确 B 错误

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

A 正确 B 错误

若某算法满足递推式：T(n) =2T(n/2)+O(n) ，则其时间复杂度为O(nlogn) 。

A 正确 B 错误

在一个数组中，如果两个元素 a[i] 和 a[j] 满足 i < j 且 a[i] > a[j] ，则 a[i] 和 a[j] 是一个逆序对。

下面代码可以正确统计数组 a 区间 [l,r] 内的逆序对总数。

1 long long cnt=0;
2 void merge_count(vector<int>& a, int l, int m, int r){
3  int i = l, j = m + 1;
4  while(i <= m && j <= r) {
5   if(a[i] <= a[j]) i++;
6   else {
7    cnt += (m - i+ 1);
8    j++;
9   }
10  }
11 }

A 正确 B 错误

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

A 正确 B 错误

假设数组的值域范围是D，以下程序的时间复杂度是O(nlogn+nlogD)。

1 bool check(int n, int a[], int k, int dist) {
2  int cnt = 1;
3  int last = a[0];
4
5  for (int i = 1; i < n; i++) {
6   if (a[i] - last >= dist) {
7    cnt++;
8    last = a[i];
9   }
10  }
11
12  return cnt >= k;
13 }
14
15 int solve(int n, int a[], int k) {
16  std::sort(a, a + n);
17
18  int l = 0;
19  int r = a[n - 1] - a[0];
20  
21  while (l < r) {
22   int mid = (l + r + 1) / 2;
23
24   if (check(n, a, k, mid))
25    l = mid;
26   else
27    r = mid - 1;
28  }
29
30  return l;
31 }
32
33 int main() {
34  int a[] = {1, 2, 8, 4, 9};
35  int n = 5;
36  int k = 3;
37
38  std::cout << solve(n, a, k) << std::endl;
39
40  return 0;
41 }

A 正确 B 错误

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

A 正确 B 错误

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

A 正确 B 错误

10.

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

A 正确 B 错误

问答题共 2 题

试题名称：有限不循环小数

时间限制：1.0 s

内存限制：512.0 MB

3.1.1 题目描述

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

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

3.1.2 输入格式

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

3.1.3 输出格式

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

3.1.4 样例

3.1.4.1 输入样例

3.1.4.2 输出样例

3.1.5 样例解释

在[2,11]终止数有2、4、5、8、10。

3.1.6 数据范围

保证1≤L≤R≤10⁶。

试题名称：找数

时间限制：1.0 s

内存限制：512.0 MB

3.2.1 题目描述

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

3.2.2 输入格式

第一行包含两个整数n,m。

第二行包含n个正整数a₁,a₂,…,a_n表示数组A。

第二行包含m个正整数b₁,b₂,…,b_m表示数组B。

3.2.3 输出格式

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

3.2.4 样例

3.2.4.1 输入样例

3.2.4.2 输出样例

3.2.5 样例解释

样例 1 中，4、3在数组A与B中均出现。

3.2.6 数据范围

对于40%的数据，保证1≤n,m≤1000。

对于100%的数据，保证1≤n,m≤10⁵，1≤a_i,b_i≤10⁹。

提交试卷

退出练习

正在提交