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

GESP-C++五级 题库

共 297 道题 ,第 9 / 15 页 · 按题型筛选,点「查看答案」核对解析
161 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

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

int solve(vector<int>& a, int l, int r){
    if(l == r) return a[l];

    int mid = l + (r - l) / 2;

    int left = solve(a, l, mid);
    int right = solve(a, mid + 1, r);

    int sum = 0, lmax = INT_MIN;
    for(int i = mid; i >= l; i--){
        sum += a[i];
        lmax = max(lmax, sum);
    }

    sum = 0;
    int rmax = INT_MIN;
    for(int i = mid + 1; i <= r; i++){
        sum += a[i];
        rmax = max(rmax, sum);
    }

    return max({left, right, lmax + rmax});
}
A
B
C
D
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
162 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

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

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

int i = 0, j = 0;
vector<int> result;

while (i < A.size() && j < B.size()) {
    if (A[i] <= B[j]) {
        result.push_back(A[i++]);
    } else {
        result.push_back(B[j++]);
    }
}

while (i < A.size()) {
    result.push_back(A[i++]);
}

while (j < B.size()) {
    result.push_back(B[j++]);
}
A
A[i] >= B[j]
B
A[i] <= B[j]
C
i >= j
D
i <= j
答案与解析
正确答案:B
初始化两个指针分别指向两组的起始位置,通过循环比较当前指针所指元素的大小,将较小元素加入结果序列,并移动对应指针。循环继续的条件是两个指针均未越界。每次比较需判断当前A组元素是否小于B组元素,以决定取哪个数组的元素。当某一组元素处理完毕后,另一组剩余元素依次加入结果。核心在于维护两个独立索引的同步推进与边界控制。
题目详情
163 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

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

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

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

A
冒泡排序和插入排序都是稳定的排序算法
B
快速排序和归并排序都是不稳定的排序算法
C
冒泡排序和插入排序最好时间复杂度均为O(n)
D
归并排序在最好、最坏和平均三种情况的时间复杂度均为
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
165 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

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

int main(){
    string s;
    int b;
    cin >> s >> b;

    vector<int> a;
    for(char c : s){
        a.push_back(c - '0');
    }

    vector<int> c;
    long long rem = 0;

    for(int i = 0; i < a.size(); i++){
        rem = rem * 10 + a[i];
        int q = rem / b;
        c.push_back(q);
        ---------------------
    }

    int pos = 0;
    while(pos < c.size() - 1 && c[pos] == 0) pos++;

    for(int i = pos; i < c.size(); i++){
        cout << c[i];
    }

    cout << endl;
    cout << rem << endl;
    return 0;
}


A
rem /= b;
B
rem %= b;
C
rem = b;
D
rem = q;
答案与解析
正确答案:B
遍历被除数的每一位,将当前余数乘以10并加上该位得到新的被除数部分;计算该部分与除数的商,并将商加入结果数组;需要更新余数为当前被除数部分与除数整除后的余值,以用于下一位的计算;余数更新必须反映模运算的结果,确保后续位的正确处理;整个过程模拟手工长除法的步骤,每一步依赖前一步的余数继续向下计算。
题目详情
166 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

数组和链表都是线性表。链表的优点是插入删除不需要移动元素,并且能随机查找。

A
对
B
错
答案与解析
正确答案:错
分析线性表的存储结构特性,比较数组与链表在元素插入、删除操作中的数据移动机制,考察链表通过指针关联元素的方式是否支持随机访问,明确随机查找的定义与实现条件。
题目详情
167 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.2 最大公约数与最小公倍数

假设函数 gcd() 函数能正确求两个正整数的最大公约数,则下面的 lcm(a,b) 函数能正确找到两个正整数 a 和 b 的最小公倍数。

int lcm(int a, int b) { 
    return a / gcd(a, b) * b; 
}


A
对
B
错
答案与解析
正确答案:对
分析函数 lcm(a, b) 的表达式结构,观察其运算顺序与数学关系。确认 a 和 b 是否通过 gcd(a, b) 进行整除操作,并判断该操作是否在整数除法下保持精度。检查表达式 a / gcd(a, b) * b 是否等价于 (a * b) / gcd(a, b) 的数学变换形式。验证该计算过程是否符合最小公倍数的定义,即能被 a 和 b 整除的最小正整数。考虑整数溢出与除法截断对结果的影响,分析运算顺序对中间结果的影响。
题目详情
168 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

在单链表中,已知指针 p 指向要删除的结点(非尾结点),想在删除 p ,可行做法是用 p->next 覆盖 p 的值与 next ,然后删除 p->next 。

A
对
B
错
答案与解析
正确答案:对
将 p->next 所指向结点的数据复制到 p 指向的结点;更新 p 的 next 指针,使其指向 p->next->next;释放原 p->next 结点所占用的内存;通过修改当前结点内容与指针实现逻辑删除目标结点的效果。
题目详情
169 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

在求解所有不大于 n 的素数时,线性筛法(欧拉筛)都应当优先于埃氏筛法使用,因为线性筛法的时间复杂度为O(n),低于埃氏筛法的O(n log log n)。

A
对
B
错
答案与解析
正确答案:错
分析两种筛法的执行机制:线性筛法通过每个合数仅被其最小质因子标记一次,确保每个数被访问的次数为常数级;埃氏筛法对每个质数的倍数进行标记,存在重复标记同一合数的情况。比较两者操作步骤的数量增长趋势,观察内层循环的触发条件及执行频率,推导各自的时间复杂度表达式。注意算法实现中是否包含冗余操作,以及标记过程的范围和终止条件如何影响总体运算量。
题目详情
170 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 5.1 二分查找

二分查找仅适用于有序数据。若输入数据无序,当仅进行一次查找时,为了使用二分而排序通常不划算。

A
对
B
错
答案与解析
正确答案:对
二分查找的前提是数据有序,因其每次比较后可排除一半元素,依赖序列的单调性实现对数时间定位。若数据无序,无法直接应用二分查找。排序操作的时间复杂度通常为O(n log n),而单次线性查找的时间复杂度为O(n)。在仅需查找一次的情况下,执行排序的成本高于直接遍历。因此,为单次查找引入排序会改变整体操作的时间开销结构。是否执行排序取决于原始数据状态与后续操作需求,但排序本身不是二分查找的必要前置步骤,而是条件满足手段。
题目详情
171 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

通过在数组的第一个、最中间和最后一个这3个数据中选择中间值作为枢轴(比较基准),快速排序算法可降低落入最坏情况的概率。

A
对
B
错
答案与解析
正确答案:对
确定数组的第一个、最中间和最后一个元素的值;比较这三个元素的大小;选取其中数值上处于中间位置的元素作为枢轴;将该枢轴用于划分操作,使小于枢轴的元素置于其左,大于枢轴的元素置于其右;完成一次划分后递归处理左右子数组。
题目详情
172 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 8.1 贪心思想

贪心算法在每一步都做出当前看来最优的局部选择,并且一旦做出选择就不再回溯;而分治算法将问题分解为若干子问题分别求解,再将子问题的解合并得到原问题的解。

A
对
B
错
答案与解析
正确答案:对
分析贪心算法每一步选择的局部最优性及其不可回溯特性;考察分治算法将原问题划分成独立子问题的过程;明确子问题求解的独立性与后续合并操作的关系;对比两种算法在决策过程与结构处理上的差异;区分局部最优策略与递归分解再合并的解决机制。
题目详情
173 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

以下 fib 函数计算第 n 项斐波那契数( fib(0)=0 , fib(1)=1 ),其时间复杂度为为O(n)。

int fib(int n) { 
    if (n <= 1) return n; 
    return fib(n-1) + fib(n-2); 
}
A
对
B
错
答案与解析
正确答案:错
分析函数的递归调用结构,识别是否存在重复计算。若函数使用循环或递归但未优化,需统计每层递归或每次迭代的执行次数。考察输入n与基本操作执行频次的关系,确定时间复杂度是否随n线性增长。检查是否有记忆化机制或动态规划思想减少冗余计算。对比标准O(n)实现方式,确认其状态转移是否仅依赖前两项且每个状态仅计算一次。
题目详情
174 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 6.1 递归概念

递归函数一定要有终止条件,否则可能会造成栈溢出。

A
对
B
错
答案与解析
正确答案:对
递归函数每次调用自身时,都会在调用栈中新增一个栈帧,用于保存当前调用的上下文信息。若未设置终止条件,递归调用将无法结束,持续向调用栈压入新的栈帧。调用栈的容量受限于系统或运行环境,当栈帧数量超过最大限制时,栈空间被耗尽,导致栈溢出。终止条件的作用是使递归在特定情况下停止调用自身,从而允许栈帧逐层回退并释放内存。
题目详情
175 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 8.1 贪心思想

使用贪心算法解决问题时,通过对每一步求局部最优解,最终一定能找到全局最优解。

A
对
B
错
答案与解析
正确答案:错
分析贪心算法的决策机制:每一步选择当前状态下的局部最优解,依据问题是否具有贪心选择性质和最优子结构性质,决定局部最优解的累积是否构成全局最优解。验证该机制需考察问题特性与选择策略之间的匹配关系,不保证所有问题通过局部最优能达到全局最优。
题目详情
176 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

基于下面定义的函数,通过判断 isDivisibleBy9(n) == isDigitSumDivisibleBy9(n) 代码可验算如果 一个数能被9整除,则它的各位数字之和能被9整除。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
177 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.2 最大公约数与最小公倍数

假设函数 gcd() 能正确求两个正整数的最大公约数,则下面的 findMusicalPattern(4,6) 函数返回2。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
178 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 2.1 多项式复杂度

下面递归实现的斐波那契数列的时间复杂度为 。

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

链表通过更改指针实现高效的结点插入与删除,但结点访问效率低、占用内存较多,且对缓存利用不友好。

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

线性筛关键是“每个合数只会被最小质因子筛到一次”,因此为 。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情