首页 › 题库 › GESP编程能力等级认证 › GESP-C++五级

GESP-C++五级 题库

共 297 道题 ,第 14 / 15 页 · 按题型筛选,点「查看答案」核对解析
261 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 8.1 贪心思想

贪心算法的解可能不是最优解。(2023.9C++五级)

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
262 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 7.1 归并排序

一般说来,冒泡排序算法优于归并排序。(2023.9C++五级)

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
263 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

C++语言中的 qsort 库函数是不稳定排序。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
264 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

质数的判定和筛法的目的并不相同,质数判定旨在判断特定的正整数是否为质数,而质数筛法意在筛选出范围内的所有质数。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
265 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

下面的C++代码执行后将输出 0 5 1 6 2 3 4 。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
266 判断题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

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

A
正确
B
错误
答案与解析
正确答案:对
分析数组和单链表的存储特性。数组通过下标直接计算内存地址,实现O(1)时间访问任意元素。单链表中每个结点包含数据和指向下一结点的指针,已知某结点指针时,插入新结点只需修改指针和连接关系,无需移动其他结点,因此插入操作为O(1)。两种结构在指定条件下各自具备特定操作的时间效率优势,不依赖于整体结构遍历或元素移动。
题目详情
267 判断题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

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

int lowerBound(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;
}
A
正确
B
错误
答案与解析
正确答案:对
初始化左边界 l 为 0,右边界 r 为数组长度,形成左闭右开区间 [l, r)。循环条件为 l < r,确保搜索区间非空。每次取中点 mid = (l + r) / 2,若 a[mid] >= x,则第一个满足条件的位置不会在 mid 右侧,故将 r 更新为 mid;否则位置必定在 mid 右侧,将 l 更新为 mid + 1。循环结束时 l 等于 r,返回 l 即为第一个大于等于 x 的元素位置。代码逻辑基于二分查找的下界变种,维护了“答案在 [l, r) 内”的不变式。
题目详情
268 判断题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

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

A
正确
B
错误
答案与解析
正确答案:错
分析排序算法的稳定性需考察相等元素的相对位置在排序前后是否发生变化。快速排序通过枢轴划分区间,每次将元素按与枢轴的大小关系移动到不同子区间。选取中间元素作为枢轴仅影响划分策略,不改变元素在划分过程中的移动方式。当存在相等元素分布在枢轴两侧时,划分操作可能导致它们的相对位置发生交换。稳定性取决于相等元素在交换过程中是否被强制改变顺序,而该过程与枢轴的选择方式无直接关联。算法整体执行路径由递归划分和元素交换共同决定,枢轴选取得当仅影响效率,不决定交换行为对相等元素顺序的保持能力。
题目详情
269 判断题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

A
正确
B
错误
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
270 判断题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

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

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

long long cnt=0;
void merge_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++;
        }
    }
}


A
正确
B
错误
答案与解析
正确答案:错
1. 将区间 [l,r] 拆分为两个已排序的子区间 [l,m] 和 [m+1,r]; 2. 使用双指针 i 和 j 分别指向两个子区间的起始位置; 3. 当 a[i] <= a[j] 时,a[i] 不构成与右区当前元素及后续元素的逆序关系,i++; 4. 当 a[i] > a[j] 时,左区从 i 到 m 的所有元素均大于 a[j],累计贡献 (m - i + 1) 到计数器; 5. j++,继续处理下一个右区元素; 6. 循环直至任一子区间遍历完毕。
题目详情
271 判断题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

根据唯⼀分解定理,如果⼤于1的整数不能被任何不超其平⽅根的质数整除,那么n 必定是质数。

A
正确
B
错误
答案与解析
正确答案:对
分析一个大于1的整数n是否为质数,可通过检查其能否被不超过√n的质数整除来实现。若n能被某个不超过√n的质数整除,则n具有该质因数,说明n是合数。反之,若所有不超过√n的质数都不能整除n,则n无法分解为更小的质因数乘积。根据唯一分解定理,每个大于1的整数均可唯一表示为质因数的乘积,若不存在这样的质因数,则n本身即为质数。因此,判断过程依赖于对√n以内质数的试除,并结合唯一分解定理对结果进行推导。
题目详情
272 判断题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

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
错误
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
273 判断题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

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

A
正确
B
错误
答案与解析
正确答案:错
分析问题是否具备最优子结构性质,即全局最优解包含子问题的最优解。确认贪心选择性质是否存在,即每一步的局部最优选择能否导向全局最优解。验证贪心策略与最优子结构之间的对应关系,检查是否存在反例表明贪心选择无法保持最优性。考察动态规划与贪心算法在结构上的差异,明确两者对最优子结构的不同依赖方式。
题目详情
274 判断题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

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

A
正确
B
错误
答案与解析
正确答案:错
分析线性筛的机制,观察其如何通过记录每个合数的最小质因子,使得每个合数仅在其被最小质因子作用时被标记;对比埃氏筛中合数可能被多个质因子重复标记的过程;考察线性筛在遍历过程中对每个数是否进行标记操作的条件判断逻辑,特别是当当前质数能整除该数时提前终止内层循环的设计;确认该机制是否实现了每个合数恰好被标记一次的特性,并验证其时间复杂度推导过程中对总操作次数的累加方式。
题目详情
275 判断题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

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

A
正确
B
错误
答案与解析
正确答案:错
分析递归程序转化为非递归程序时控制流和状态保存的机制;考察是否所有此类转换都必须引入显式栈结构来模拟函数调用栈的行为;比较直接迭代、队列、循环变量等替代方式能否在不使用显式栈的前提下实现相同计算过程;确认改写后程序维持等价功能时对数据结构依赖的可能性与必要性。
题目详情
276 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

数字移动

时间限制:1.0 s

内存限制:512.0 MB

题目描述

输入格式

输出格式

输出一行,代表满足要求的 的最小值。

输入样例

6
1 2 1 3 2 3

输出样例

2

数据范围

答案与解析
参考答案
#include <iostream>
using namespace std;
const int N = 100010;
int a[N];
int b[N];
int pos;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int left = 1, right = 1e6, ans = 1e6;
    while (left <= right) {
        int mid = (left + right) / 2;
        bool possible = true;
        pos = 0;

        for (int i = 0; i < n; i++) {
            if (a[i] > mid) {
                b[pos++] = a[i];
            }
        }

        for (int i = 0; i < pos; i += 2) {
            if (b[i] != b[i + 1]) {
                possible = false;
                break;
            }
        }

        if (possible) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}
题目详情
277 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

相等序列

时间限制: 1.0 s

内存限制:512.0 MB

题目描述

小 A 有一个包含 N 个正整数的序列A = {A1 , A2 , · ·  ,AN} 。小 A 每次可以花费 1 个金币执行以下任意一种操作:

 选择序列中一个正整数 Ai ( 1 ≤ i ≤ N) ,将 Ai 变为 Ai * P ,P 为任意质数;

 选择序列中一个正整数 Ai ( 1 ≤ i ≤ N) ,将 Ai 变为 Ai /P ,P 为任意质数,要求Ai能被p整除。

小 A 想请你帮他计算出令序列中所有整数都相同 ,最少需要花费多少金币。

输入格式

第一行一个正整数N ,含义如题面所⽰ 。

第二行包含 N 个正整数 A1 , A2 , ·  … ,AN ,代表序列 A。

输出格式

输出一行 ,代表最少需要花费的金币数量。

输入样例

5
10  6  35  105  42

输出样例

8

数据范围

对于60%的测试点 ,保证 1 ≤ N, Ai ≤ 100 。

对于所有测试点 ,保证 1 ≤ N, Ai ≤ 105 。

答案与解析
参考答案
#include <iostream>
using namespace std;
const int N = 100010;
int num[N][20];
int n, a[N];

void calc_prime_factor(int x)
{
    for (int i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
        {
            int cnt = 0;
            while (x % i == 0)
            {
                x /= i;
                cnt++;
            }
            num[i][cnt]++;
        }
    }
    if (x > 1)
    {
        num[x][1]++;
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        calc_prime_factor(a[i]);
    }

    long long ans = 0;
    for (int i = 2; i < 100001; i++)
    {
        int pos = 0;
        for (int j = 0; j < 20; j++)
        {
            pos += num[i][j];
        }
        num[i][0] = n - pos;

        int median_exponent = 0;
        pos = 0;
        for (int j = 0; j < 20; j++)
        {
            pos += num[i][j];
            if (pos * 2 >= n)
            {
                median_exponent = j;
                break;
            }
        }

        for (int j = 0; j < 20; j++)
        {
            ans += num[i][j] * abs(j - median_exponent);
        }
    }
    printf("%lld\n", ans);
    return 0;
}
题目详情
278 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

数字选取

答案与解析
参考答案
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5 + 5;
int n, p[N], cnt, minp[N];
bool np[N], used[N];

int main() {
    scanf("%d", &n);
    // 欧拉筛,同时求最小质因子minp
    for (int i = 2; i <= n; i++) {
        if (!np[i]) {
            p[++cnt] = i;
            minp[i] = i;
        }
        for (int j = 1; j <= cnt && 1LL * i * p[j] <= n; j++) {
            np[i * p[j]] = true;
            minp[i * p[j]] = p[j];
            if (i % p[j] == 0) break;
        }
    }
    int k = n / 2;
    int res = 0;
    for (int i = k + 1; i <= n; i++) {
        int prime = minp[i];
        if (!used[prime]) {
            used[prime] = true;
            res++;
        }
    }
    res += 1; // 选数字1
    printf("%d\n", res);
    return 0;
}
题目详情
279 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

有趣的数字和

答案与解析
参考答案
#include <algorithm>
#include <cstdio>
#include <utility>
using namespace std;

int L, R;
long long ans;

pair<int, long long> cal2(int n, int p) {
    if (n == 0) {
        return {1 - p, 0};
    }
    if (n == 1) {
        return {1, p};
    }
    return {(n + 1) / 2, 1LL * n * (n + 1) / 4};
}

pair<int, long long> cal(int n, int p) {
    if (n <= 1) {
        return cal2(n, p);
    }
    long long x = 1LL << (31 - __builtin_clz(n)); // ≤n的最大2的幂
    auto left_part = cal2(x - 1, p);
    auto right_part = cal(n - x, 1 - p);
    return {
        left_part.first + right_part.first,
        left_part.second + right_part.second + x * right_part.first
    };
}

int main() {
    scanf("%d%d", &L, &R);
    ans += cal(R, 1).second;
    ans -= cal(L - 1, 1).second;
    printf("%lld\n", ans);
    return 0;
}
题目详情
280 简答题 偏难 GESP编程能力等级认证 ·GESP-C++五级 · 1.3 同余与模运算

奖品兑换

时间限制:1 s,内存限制:512 MB

【问题描述】

班主任给上课专心听讲、认真完成作业的同学们分别发放了若干张课堂优秀券和作业优秀券。同学们可以使用这两种券找班主任兑换奖品。

具体来说,可以使用 a 张课堂优秀券和 b 张作业优秀券兑换一份奖品,或者使用 b 张课堂优秀券和 a 张作业优秀券兑换一份奖品。

现在小 A 有 n 张课堂优秀券和 m 张作业优秀券,他最多能兑换多少份奖品呢?

【输入描述】

第一行,两个正整数 n、m,分别表示小 A 持有的课堂优秀券和作业优秀券的数量。

第二行,两个正整数 a、b,表示兑换一份奖品所需的两种券的数量。

【输出描述】

输出共一行,一个整数,表示最多能兑换的奖品份数。

【样例输入1】

8 8
2 1

【样例输出1】

5

【样例输入2】

314159 2653589
27 1828

【样例输出2】

1599

【数据范围】

对于60%测试点,保证 1 <= a、b <= 100,1 <= n、m <= 500。

对于所有测试点,保证 1 <= a、b <= 10^4,1 <= n、m <= 10^9。

答案与解析
参考答案
#include <iostream>
using namespace std;
int n, m, a, b;
int l, r;
int check(int v) {
    long long x, y, t;
    x = 1ll * v * a;
    y = 1ll * v * b;
    if (y > m) {
        t = (y - m + (b - a) - 1) / (b - a);
        y -= t * (b - a);
        x += t * (b - a);
    }
    return x <= n && y <= m;
}
int main() {
    cin >> n >> m >> a >> b;
    if (n > m)
        swap(n, m);
    if (a > b)
        swap(a, b);
    if (a == b) {
        cout << n / a << endl;
        return 0;
    }
    l = 0;
    r = n;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    cout << r << endl;
    return 0;
}
题目详情