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

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

C++ 180分钟 总分 100.0 27 题
试卷题目预览
第1题 中级 2.0分 单选
以下哪种情况使用链表比数组更合适？
A. 数据量固定且读多写少
B. 需要频繁在中间或开头插入、删除元素
C. 需要高效随机访问元素
D. 存储空间必须连续
第2题 中级 2.0分 单选
函数removeElements删除单链表中所有结点值等于val的结点，并返回新的头结点，则横线处填写（ ）。

A. Node* del = cur; cur = del->next; delete del;
B. Node* del = cur->next; cur->next = del; delete del;
C. Node* del = cur->next; cur->next = del->next; delete del;
D. Node* del = cur->next; delete del; cur->next = del->next;
第3题 中级 2.0分 单选
函数hasCycle采用Floyd快慢指针法判断一个单链表中是否存在环，即用两个指针在链表上前进：slow每次走1步，fast每次走2步，若存在环，fast终会

A. slow = slow->next; fast = fast->next->next;
B. slow = fast->next; fast = slow->next->next;
C. slow = slow->next; fast = slow->next->next;
D. slow = fast->next; fast = fast->next->next;
第4题 中级 2.0分 单选
函数isPerfectNumber判断一个正整数是否为完全数（该数是否等于它的真因子之和），则横线上应填写（ ）。

A. i <= n
B. i*i <= n
C. i <= n/2
D. i < n
第5题 中级 2.0分 单选
以下代码计算两个正整数的最大公约数(GCD)，横线上应填写（ ）。

A. b
B. a
C. temp
D. a * b
第6题 中级 2.0分 单选
函数sieve实现埃拉托斯特尼筛法(埃氏筛)，横线处应填入（ ）。

A. i
B. i+1
C. i*2
D. i*i
第7题 中级 2.0分 单选
函数linearSieve实现线性筛法(欧拉筛)，横线处应填入（）。
A. i % p == 0
B. p % i == 0
C. i == p
D. i * p == n
第8题 中级 2.0分 单选
关于埃氏筛和线性筛的比较，下列说法错误的是（ ）。
A. 埃氏筛可能会对同一个合数进行多次标记
B. 线性筛的理论时间复杂度更优，所以线性筛的速度往往优于埃氏筛
C. 线性筛保证每个合数只被其最小质因子筛到一次
D. 对于常见范围（n<=10^7），埃氏筛因实现简单，常数较小，其速度往往优于线性筛
第9题 中级 2.0分 单选
唯一分解定理描述的是( )。
A. 每个整数都能表示为任意素数的乘积
B. 每个大于1的整数能唯一分解为素数幂乘积（忽略顺序）
C. 合数不能分解为素数乘积
D. 素数只有两个因子：1和自身
第10题 中级 2.0分 单选
给定一个n×n的矩阵matrix，矩阵的每一行和每一列都按升序排列。函数countLE返回矩阵中第k小的元素，则两处横线上应分别填写（ ）。
A. hi = mid - 1; 和 lo = mid + 1;
B. hi = mid; 和 lo = mid;
C. hi = mid; 和 lo = mid + 1;
D. hi = mid + 1; 和 lo = mid;
第11题 中级 2.0分 单选
下述C++代码实现了快速排序算法，下面说法错误的是（ ）。

A. 快速排序在平均情况下运行速度较快，常数小、就地排序，实践中通常比归并排序更高效。
B. 在平均情况下，划分的递归层数为O(log n)，每层中的总循环数为O(n)，总时间为O(n log n)。
C. 在最差情况下，每轮划分将长度为n的数组划分为长度为0和n-1的两个子数组，此时递归层数达到O(n)，总时间为O(n²)。
D. 划分函数partition中"从右往左查找"与"从左往右查找"的顺序可以交换。
第12题 中级 2.0分 单选
下述C++代码实现了归并排序算法，则横线上应填写（ ）。

A. i < mid
B. j < right
C. i <= mid
D. j <= right
第13题 中级 2.0分 单选
假设你是一家电影院的排片经理，只有一个放映厅。你有一个电影列表movies，其中movies[i] = [start_i, end_i]表示第i部电影的开始和结
A. a[0] < b[0] 和 lastEnd
B. a[1] < b[1] 和 lastEnd
C. a[0] < b[0] 和 movies[i][0]
D. a[1] < b[1] 和 movies[i][0]
第14题 中级 2.0分 单选
给定一个整数数组nums，下面代码找到一个具有最大和的连续子数组，并返回该最大和。则下面说法错误的是（ ）。

A. 上述代码采用分治算法实现
B. 上述代码采用贪心算法
C. 上述代码时间复杂度为O(n log n)
D. 上述代码采用递归方式实现
第15题 中级 2.0分 单选
给定一个由非负整数组成的数组digits，表示一个非负整数的各位数字，其中最高位在数组首位。下面代码对该整数执行+1操作，并返回结果数组，则横线上应填写（

A. digits[i] = 0;
B. digits[i] = 9;
C. digits[i] = 1;
D. digits[i] = 10;
第16题 中级 2.0分 判断
基于下面定义的函数，通过判断isDivisibleBy9(n) == isDigitSumDivisibleBy9(n)代码可验算如果一个数能被9整除，则它的各
T. 正确
F. 错误
第17题 中级 2.0分 判断
假设函数gcd()能正确求两个正整数的最大公约数，则下面的findMusicalPattern(4, 6)函数返回2。

T. 正确
F. 错误
第18题 中级 2.0分 判断
下面递归实现的斐波那契数列的时间复杂度为O(n)。

T. 正确
F. 错误
第19题 中级 2.0分 判断
链表通过更改指针实现高效的结点插入与删除，但结点访问效率低、占用内存较多，且对缓存利用不友好。
T. 正确
F. 错误
第20题 中级 2.0分 判断
二分查找依赖数据的有序性，通过循环逐步缩减一半搜索区间来进行查找，且仅适用于数组或基于数组实现的数据结构。
T. 正确
F. 错误
第21题 中级 2.0分 判断
线性筛关键是"每个合数只会被最小质因子筛到一次"，因此为O(n)。
T. 正确
F. 错误
第22题 中级 2.0分 判断
快速排序和归并排序都是稳定的排序算法。
T. 正确
F. 错误
第23题 中级 2.0分 判断
下面代码采用分治算法求解标准3柱汉诺塔问题，时间复杂度为O(2^n)。
T. 正确
F. 错误
第24题 中级 2.0分 判断
所有递归算法都可以转换为迭代算法。
T. 正确
F. 错误
第25题 中级 2.0分 判断
贪心算法总能得到全局最优解。
T. 正确
F. 错误
第26题 中级 25.0分 编程
数字选取

给定正整数N，现在有1, 2, ..., N共计N个整数。你需要从这N个整数中选取一些整数，使得所选取的整数中任意两个不同的整数均互质（也就是说，这两个整数的最大公因数为1）。请你最大化所选取整数的数量。 例如，当N=6时，可以选择1, 2, 3, 5共计4个整数。可以验证不存在数量更多的选取整数的方案。

【输入格式】
一行，一个正整数N，表示给定的正整数。
【输出格式】
一行，一个正整数，表示所选取整数的最大数量。
【样例输入】

6
【样例输出】

4
对于50%的测试点，保证N<=1000。
对于所有测试点，保证N<=10^5。
第27题 中级 25.0分 编程
有趣的数字和

如果一个正整数的二进制表示包含奇数个1，那么小A就会认为这个正整数是有趣的。 例如，3的二进制表示为11，包含1的个数为2个，所以3不是有趣的。但是5包含2个1，所以5也不是有趣的。 给定正整数L和R，请你统计满足L<=x<=R的有趣的整数x之和。

【输入格式】
一行，两个正整数L, R，表示给定的正整数。
【输出格式】
一行，一个正整数，表示L到R之间有趣的整数之和。
【样例输入】

3 8
【样例输出】

19
对于30%的测试点，保证L,R<=1000。
对于另外30%的测试点，保证L=1并且R=2^k-1，其中k是大于0的正整数。
对于所有测试点，保证1<=L<=R<=10^9。
💬