GESP 2025年3月_C++五级试卷

从PDF导入：GESP 2025年3月_C++五级试卷

C++ 180分钟 总分 100.0 27 题
试卷题目预览
第1题 中级 2.0分 单选
链表不具备的特点是( )。
A. 可随机访问任何一个元素
B. 插入、删除操作不需要移动元素
C. 无需事先估计存储空间大小
D. 所需存储空间与存储元素个数成正比
第2题 中级 2.0分 单选
双向链表中每个结点有两个指针域prev和next，分别指向该结点的前驱及后继结点。设p指向链表中的一个结点，它的前驱结点和后继结点均非空。要删除结点p，则下述语
A. p->next->prev = p->next; p->prev->next = p->prev; delete p;
B. p->prev->next = p->next; p->next->prev = p->prev; delete p;
C. p->next->prev = p->prev; p->next->prev->next = p->next; delete p;
D. p->prev->next = p->next; p->prev->next->prev = p->prev; delete p;
第3题 中级 2.0分 单选
假设双向循环链表包含头尾哨兵结点(不存储实际内容)，分别为head和tail，链表中每个结点有两个指针域prev和next。下面代码实现了一个空的双向循环链表，

A. list->head->prev = list->head; list->tail->prev = list->head;
B. list->head->next = list->tail; list->tail->prev = list->head;
C. list->head->next = list->tail; list->tail->next = list->head;
D. list->head->next = list->tail; list->tail->next = nullptr;
第4题 中级 2.0分 单选
用以下辗转相除法（欧几里得算法）求gcd(84, 60)的步骤中，第二步计算的数是（ ）。
A. 84和60
B. 60和24
C. 24和12
D. 12和0
第5题 中级 2.0分 单选
根据唯一分解定理，下面整数的唯一分解是正确的（ ）。

18 = 3 × 6 28 = 4 × 7 36 = 2 × 3 × 6 30 = 2 × 3 × 5

第6题 中级 2.0分 单选
下述代码实现素数表的线性筛法，筛选出所有小于等于n的素数，横线上应填的最佳代码是( )。
A. j < primes.size()
B. i * primes[j] <= n
C. j < primes.size() && i * primes[j] <= n
D. j <= n
第7题 中级 2.0分 单选
在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。
A. 系统分配的栈空间溢出
B. 系统分配的堆空间溢出
C. 系统分配的队列空间溢出
D. 系统分配的链表空间溢出
第8题 中级 2.0分 单选
对下面两个函数，说法错误的是（ ）。

A. 两个函数的实现的功能相同。
B. 两个函数的时间复杂度均为O(n)。
C. factorialA采用递归方式。
D. factorialB采用递归方式。
第9题 中级 2.0分 单选
下面算法中，（ ）是不稳定的排序。
A. 选择排序
B. 插入排序
C. 归并排序
D. 冒泡排序
第10题 中级 2.0分 单选
考虑以下C++代码实现的快速排序算法，将数据从小到大排序，则横线上应填的最佳代码是( )。

A. if (arr[j] > pivot) { i++; swap(arr[i], arr[j]); }
B. if (arr[j] < pivot) { i++; swap(arr[i], arr[j]); }
C. if (arr[j] < pivot) { swap(arr[i], arr[j]); i++; }
D. if (arr[j] == pivot) { i++; swap(arr[i], arr[j]); }
第11题 中级 2.0分 单选
若用二分法在[1, 100]内猜数，最多需要猜（ ）次。
A. 100
B. 10
C. 7
D. 5
第12题 中级 2.0分 单选
下面代码实现了二分查找算法，在数组arr找到目标元素target的位置，则横线上能填写的最佳代码是（ ）。

A. int mid = left + (right - left) / 2;
B. int mid = left;
C. int mid = (left + right) / 2;
D. int mid = right;
第13题 中级 2.0分 单选
贪心算法的核心特征是（ ）。
A. 总是选择当前最优解
B. 回溯尝试所有可能
C. 分阶段解决子问题
D. 总能找到最优解
第14题 中级 2.0分 单选
函数int findMax(int arr[], int low, int high)计算数组中最大元素，其中数组arr从索引low到high，（ ）正确实现
A. if (low == high) return arr[low]; int mid = (low + high) / 2; return arr[mid];
B. if (low >= high) return arr[low]; int mid = (low + high) / 2; int leftMax = findMax(arr, low, mid - 1); int rightMax = findMax(arr, mid, high); return leftMax + rightMax;
C. if (low > high) return 0; int mid = low + (high - low) / 2; int leftMax = findMax(arr, low, mid); int rightMax = findMax(arr, mid + 1, high); return leftMax * rightMax;
D. if (low == high) return arr[low]; int mid = low + (high - low) / 2; int leftMax = findMax(arr, low, mid); int rightMax = findMax(arr, mid + 1, high); return (leftMax > rightMax) ? leftMax : rightMax;
第15题 中级 2.0分 单选
小杨编写了一个如下的高精度乘法函数，则横线上应填写的代码为（ ）。
A. int temp = c[k];
B. int temp = c[k] + carry;
C. int temp = c[k] - carry;
D. int temp = c[k] * carry;
第16题 中级 2.0分 判断
要删除单链表中某个结点p(非尾结点)，但不知道头结点，可行的操作是将p->next的数据拷贝到p的数据域，将p->next设置为p->next->next，然后
T. 正确
F. 错误
第17题 中级 2.0分 判断
链表存储线性表时要求内存中可用存储单元地址是连续的。
T. 正确
F. 错误
第18题 中级 2.0分 判断
线性筛相对于埃拉托斯特尼筛法，每个合数只会被它的最小质因数筛去一次，因此效率更高。
T. 正确
F. 错误
第19题 中级 2.0分 判断
贪心算法通过每一步选择当前最优解，从而一定能获得全局最优解。
T. 正确
F. 错误
第20题 中级 2.0分 判断
递归函数必须具有一个终止条件，以防止无限递归。
T. 正确
F. 错误
第21题 中级 2.0分 判断
快速排序算法的时间复杂度与输入是否有序无关，始终稳定为O(n log n)。
T. 正确
F. 错误
第22题 中级 2.0分 判断
归并排序算法的时间复杂度与输入是否有序无关，始终稳定为O(n log n)。
T. 正确
F. 错误
第23题 中级 2.0分 判断
二分查找适用于对无序数组和有序数组的查找。
T. 正确
F. 错误
第24题 中级 2.0分 判断
小杨有100元去超市买东西，每个商品有各自的价格，每种商品只能买1个，小杨的目标是买到最多数量的商品。小杨采用的策略是每次挑价格最低的商品买，这体现了分治思想。
T. 正确
F. 错误
第25题 中级 2.0分 判断
归并排序算法体现了分治算法，每次将大的待排序数组分成大小大致相等的两个小数组，然后分别对两个小数组进行排序，最后对排好序的两个小数组合并成有序数组。
T. 正确
F. 错误
第26题 中级 25.0分 编程
平均分配

小A有2n件物品，小B和小C想从小A手上买走这些物品。对于第i件物品，小B会以bi的价格购买，而小C会以ci的价格购买。为了平均分配这2n件物品，小A决定小B和小C各自只能买走恰好n件物品。你能帮小A求出他卖出这2n件物品所能获得的最大收入吗？

【输入格式】
第一行，一个正整数n。
第二行，2n个整数b1, b2, ..., b2n。
第三行，2n个整数c1, c2, ..., c2n。
【输出格式】
一行，一个整数，表示答案。
【样例输入】

3
1 3 5 6 8 10
2 4 6 7 9 11
【样例输出】

36
对于50%的测试点，保证n<=5000。
对于另外50%的测试点，保证n<=50000，bi,ci<=10^9。
对于所有测试点，保证1<=n<=10^5，0<=bi,ci<=10^9。
第27题 中级 25.0分 编程
原根判断

小A知道，对于质数p而言，p的原根a是满足以下条件的正整数： 1. 1 <= a < p； 2. 对于任意1<=k

【输入格式】
第一行，一个正整数T，表示测试数据组数。
每组测试数据包含一行，两个正整数a, p。
【输出格式】
对于每组测试数据，输出一行，如果a是p的原根则输出Yes，否则输出No。
【样例输入】

3
3 998244353
5 998244353
7 998244353
【样例输出】

Yes
Yes
No
对于30%的测试点，保证p<=1000。
对于所有测试点，保证1<=T<=100，1<=a<p<=10^9，p为质数。
💬