GESP-C++五级 题库
共 27 道题
,第 2 / 2 页
· 按题型筛选,点「查看答案」核对解析
21
判断题
适中
根据唯⼀分解定理,如果⼤于1的整数不能被任何不超其平⽅根的质数整除,那么n 必定是质数。
A
正确
B
错误
答案与解析
正确答案:对
分析一个大于1的整数n是否为质数,可通过检查其能否被不超过√n的质数整除来实现。若n能被某个不超过√n的质数整除,则n具有该质因数,说明n是合数。反之,若所有不超过√n的质数都不能整除n,则n无法分解为更小的质因数乘积。根据唯一分解定理,每个大于1的整数均可唯一表示为质因数的乘积,若不存在这样的质因数,则n本身即为质数。因此,判断过程依赖于对√n以内质数的试除,并结合唯一分解定理对结果进行推导。
22
判断题
适中
![]()
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;
}
A
正确
B
错误
答案与解析
正确答案:对
这道题暂未补解析。
23
判断题
适中
若一个问题满足最优子结构性质,则一定可以用贪心算法得到最优解。
A
正确
B
错误
答案与解析
正确答案:错
分析问题是否具备最优子结构性质,即全局最优解包含子问题的最优解。确认贪心选择性质是否存在,即每一步的局部最优选择能否导向全局最优解。验证贪心策略与最优子结构之间的对应关系,检查是否存在反例表明贪心选择无法保持最优性。考察动态规划与贪心算法在结构上的差异,明确两者对最优子结构的不同依赖方式。
24
判断题
适中
线性筛相比埃氏筛的核心改进在于:埃氏筛中一个合数可能被多个质数重复标记,线性筛通过"每个合数只 被其最大质因子筛去"的策略,保证每个合数恰好被标记一次,从而实现 O(n)的时间复杂度。
A
正确
B
错误
答案与解析
正确答案:错
分析线性筛的机制,观察其如何通过记录每个合数的最小质因子,使得每个合数仅在其被最小质因子作用时被标记;对比埃氏筛中合数可能被多个质因子重复标记的过程;考察线性筛在遍历过程中对每个数是否进行标记操作的条件判断逻辑,特别是当当前质数能整除该数时提前终止内层循环的设计;确认该机制是否实现了每个合数恰好被标记一次的特性,并验证其时间复杂度推导过程中对总操作次数的累加方式。
25
判断题
适中
任何递归程序都可以改写为等价的非递归程序,但改写后的非递归程序一定需要显式地使用栈来模拟递归 调用过程。
A
正确
B
错误
答案与解析
正确答案:错
分析递归程序转化为非递归程序时控制流和状态保存的机制;考察是否所有此类转换都必须引入显式栈结构来模拟函数调用栈的行为;比较直接迭代、队列、循环变量等替代方式能否在不使用显式栈的前提下实现相同计算过程;确认改写后程序维持等价功能时对数据结构依赖的可能性与必要性。
26
简答题
适中
有限不循环小数

答案与解析
参考答案
#include <iostream>
using namespace std;
int main() {
int l, r, ans = 0;
cin >> l >> r;
for(int i = l; i <= r; i++) {
int t = i;
while(t && t % 2 == 0)
t /= 2;
while(t && t % 5 == 0)
t /= 5;
if(t == 1)
ans++;
}
cout << ans << endl;
return 0;
}
27
简答题
适中
找数

答案与解析
参考答案
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n);
for(int i = 0; i < n; i++)
cin >> a[i];
sort(a.begin(), a.end());
int ans = 0;
int b;
for(int i = 0; i < m; i++){
cin >> b;
if(binary_search(a.begin(), a.end(), b)){
ans++;
}
}
cout << ans;
return 0;
}