GESP-C++五级 题库

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

关于单链表、双链表和循环链表,下列说法正确的是( )。

A
在单链表中,若已知任意结点的指针,则可以在 O(1)时间内删除该结点。
B
循环链表中一定不存在空指针。
C
在循环双链表中,尾结点的 next 指针一定为 nullptr 。
D
在带头结点的循环单链表中,判定链表是否为空只需判断头结点的 next 是否指向自身。
答案与解析
正确答案:D
分析链表结构特性时,需明确各类链表的指针连接方式。单链表中结点仅含指向后继的指针,删除操作依赖前驱结点访问。双链表每个结点具备前驱和后继两个指针,支持双向遍历。循环链表的尾结点与头结点相连,形成闭合环路,无终结空指针。带头结点的循环链表通过头结点的 next 指针是否指向自身判断空状态。指针行为由结构定义决定,不依赖外部条件或运行时配置。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

双向循环链表中要在结点 p 之前插入新结点 s (均非空),以下指针操作正确的是( )。

A
s -> 下一个 = p;p -> 前文 = s;p -> 接下来 = s;s -> prev = p;
B
s -> prev = p;s -> 下一个 = p -> 次;p -> 下一个 -> 前文 = s;p -> 接下来 = s;
C
s -> 下一个 = p;s -> 前述 = p->前述;p -> 前述 -> 下一站 = s;p -> 前文 = s;
D
s -> next = p; s -> prev = nullptr; p -> prev = s;
答案与解析
正确答案:C
在双向循环链表中插入结点时,需修改四个指针:新结点的前驱和后继,以及前后相邻结点的后继和前驱。首先使新结点的前驱指向目标结点的前驱,新结点的后继指向目标结点。然后将原目标结点的前驱结点的后继指向新结点,目标结点的前驱指向新结点。所有指针更新必须保持原有连接不断裂,且顺序不能破坏链表结构的完整性。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

下面函数用“哑结点”统一处理删除单向链表中的头结点与中间结点。横线处应填( )。

struct Node{
    int val;
    Node* next;
    Node(int v):val(v),next(nullptr){}
};

Node* eraseAll(Node* head, int x){
    Node dummy(0);
    dummy.next = head;
    Node* cur = &dummy;
    while(cur->next){
        if(cur->next->val == x){
            Node* del = cur->next;
            cur->next = del->next;  // 空白处:让当前节点跳过待删除节点,直接指向后一个节点
            delete del;
        }else cur = cur->next;
    }
    return dummy.next;
}
A
cur = cur->next;
B
cur->next = del->next;
C
del->next = cur->next;
D
cur->next = nullptr;
答案与解析
正确答案:B
创建哑结点并将其后继指向头结点,用指针遍历链表。循环中判断当前节点的后继值是否等于目标值。若相等,则记录待删节点,将当前节点的后继更新为待删节点的后继,释放待删节点内存。若不相等,将当前节点指针推进到下一节点。遍历结束后返回哑结点的后继作为新的头结点。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

对如下代码实现的欧几里得算法(辗转相除法),执行 gcd(48, 18) 得到的调用序列为( )。

int gcd(int a, int b) { 
    return b == 0 ? a : gcd(b, a % b); 
}
A
gcd(48,18) -> gcd(18,12) -> gcd(12,6) -> gcd(6,0)
B
gcd(48,18) -> gcd(30,18) -> gcd(12,18)
C
gcd(48,18) -> gcd(18,30) -> gcd(30,6)
D
gcd(48,18) -> gcd(12,18) -> gcd(6,12)
答案与解析
正确答案:A
分析函数调用过程时,观察递归条件:当b不为0时,递归调用gcd(b, a % b)。每次调用将第二个参数更新为当前两数的模运算结果,第一个参数更新为原第二个参数。递归持续直到第二个参数变为0,此时返回第一个参数。跟踪该过程中每一对传入参数的变化序列,可得连续的参数对演化路径。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

下面代码实现了欧拉(线性)筛,横线处应填写( )。

vector<int> euler_sieve(int n) {
    vector<bool> is_composite(n + 1, false);
    vector<int> primes;

    for (int i = 2; i <= n; i++) {
        if (!is_composite[i])
            primes.push_back(i);

        for (int j = 0; j < primes.size() && (long long)i * primes[j] <= n; j++) {
            is_composite[i * primes[j]] = true;
            if (i % primes[j] == 0)
                break;
        }
    }
    return primes;
}
A
j <= n
B
j < sqrt(n)
C
j < primes.size()
D
j < i
答案与解析
正确答案:C
遍历从2开始的每个整数i,若i未被标记为合数,则将其加入素数列表。对当前素数列表中的每个素数p,标记i与p的乘积为合数,直到p能整除i时停止内层循环,确保每个合数仅被其最小的质因子筛去一次。横线处需填入控制筛法过程中最小质因子判定的变量。
题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

埃氏筛中将内层循环从 j = i*i 开始而不是 j = 2*i 的主要原因是( )。

vector<int> eratosthenes_sieve(int n) {
    vector<bool> is_composite(n + 1, false);
    vector<int> primes;

    for (int i = 2; i <= n; i++) {
        if (is_composite[i]) continue;

        primes.push_back(i);

        for (long long j = (long long)i * i; j <= n; j += i)
            is_composite[j] = true;
    }
    return primes;
}
A
因为 2*i 一定不是合数
B
i*i 一定是质数
C
小于 i*i 的 i 的倍数已被更小质因子筛过
D
这样可以把时间复杂度降为O(n)
答案与解析
正确答案:C
在埃氏筛法中,对于当前质数i,需要标记其倍数为合数。内层循环从j = i*i开始,是因为所有小于i*i且为i的倍数的数,必定存在一个比i小的因子,因此这些数已经被之前更小的质数筛除。从i*i开始可以避免重复标记,确保每个合数仅在其最小质因子被处理时被筛去。该起始点选择不影响最终结果,但优化了执行效率,减少了冗余操作。循环起始位置与时间复杂度渐进行为无本质关联,也不依赖特定数值的质合属性。
题目详情
7 单选题 适中 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
2
B
3
C
4
D
5
答案与解析
正确答案:B
函数check用于判断在给定距离dist下,数组a中最多能选出多少个元素满足相邻元素间距离不小于dist。通过贪心策略遍历已排序的数组,统计满足条件的元素个数cnt,并与k比较。函数solve对数组a进行排序,确定答案的二分查找范围为[0, a[n-1]-a[0]]。在二分过程中,根据check返回值调整边界,寻找最大可行的dist值。整个过程基于二分答案与贪心验证的结合,逐步缩小搜索空间直至收敛到最终结果。
题目详情
8 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

在升序数组中查找第一个大于等于 x 的位置,下面循环中横线应填( )。

int lowerBound(const vector<int>& a, int x){
    int L=0, r=a.size();
    while(L<r){
        int mid = L + (r - l)/2;
        if(a[mid] >= x) r = mid;
        else L = mid + 1;
    }
    return L;
}
A
r = mid;
B
r = mid - 1;
C
L = mid;
D
L = mid + 1;
答案与解析
正确答案:A
使用二分查找在升序数组中定位第一个大于等于 x 的元素。初始化左边界 L 为 0,右边界 r 为数组长度。循环条件为 L < r。每次计算中点 mid = L + (r - L) / 2。若 a[mid] >= x,则该位置可能是目标位置,因此将 r 更新为 mid,保留 mid 在搜索范围内。否则 a[mid] < x,说明 mid 及其左侧都不可能满足条件,将 L 更新为 mid + 1。循环结束时 L 等于 r,且指向第一个满足条件的位置。更新 r 时必须包含 mid,更新 L 时必须排除 mid 及其左侧。
题目详情
9 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

关于递归函数调用,下列说法错误的是( )。

A
递归调用层次过深时,可能会耗尽栈空间导致栈溢出
B
尾递归函数可以通过编译器优化来避免栈溢出
C
所有递归函数都可以通过循环结构来改写,从而避免栈溢出
D
栈溢出发生时,程序会抛出异常并可以继续执行后续代码
答案与解析
正确答案:D
递归函数每次调用自身时,会在调用栈中创建新的栈帧,用于保存局部变量和返回地址。若递归深度过大,栈帧累积超出栈空间限制,则引发栈溢出。尾递归在特定条件下可被编译器优化为循环,避免新增栈帧。任何递归逻辑均可通过显式栈结构与循环模拟,实现相同计算过程。栈溢出属于运行时严重错误,导致程序控制流中断,无法保证后续代码的正常执行。
题目详情
10 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

给定 n 根木头,第 i 根长度为 a[i] 。要切成不少于 m 段等长木段,求最大可能长度,则横线上应填 写( )。

const int MAXN = 100005;
Long Long a[MAXN];
int n, m;

bool check(Long Long x){
    Long Long cnt = 0;
    for(int i = 1; i <= n; i++){
        if(x == 0) return true;
        cnt += a[i] / x;
        if(cnt >= m) return true;
    }
    return false;
}

int main(){
    cin >> n >> m;
    Long Long mx = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        mx = max(mx, a[i]);
    }

    Long Long L = 1, r = mx;
    Long Long ans = 0;

    while(L <= r){
        Long Long mid = L + (r - l) / 2;

        if(check(mid)){
            ans = mid;
           ----------------------
        }else{
           ----------------------
        }
    }

    cout << ans << endl;
    return 0;
}
A
L= mid + 1; r = mid - 1;
B
L = mid - 1; r = mid + 1;
C
L = mid + 1; r = mid;
D
L = mid; r = mid + 1;
答案与解析
正确答案:A
使用二分查找确定最大可能长度。定义左边界为最小可行长度,右边界为最长木头长度。每次取中点作为候选长度,通过检查函数判断是否能切出至少 m 段。检查函数统计每根木头可切段数,累加并比较与 m 的关系。若满足条件,说明当前长度可行,尝试更大的长度;否则尝试更小的长度。根据检查结果更新边界,持续缩小搜索范围直至收敛。
题目详情
11 单选题 适中 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
这道题暂未补解析。
题目详情
12 单选题 适中 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组元素,以决定取哪个数组的元素。当某一组元素处理完毕后,另一组剩余元素依次加入结果。核心在于维护两个独立索引的同步推进与边界控制。
题目详情
13 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

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

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

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

A
冒泡排序和插入排序都是稳定的排序算法
B
快速排序和归并排序都是不稳定的排序算法
C
冒泡排序和插入排序最好时间复杂度均为O(n)
D
归并排序在最好、最坏和平均三种情况的时间复杂度均为
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
15 单选题 适中 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并加上该位得到新的被除数部分;计算该部分与除数的商,并将商加入结果数组;需要更新余数为当前被除数部分与除数整除后的余值,以用于下一位的计算;余数更新必须反映模运算的结果,确保后续位的正确处理;整个过程模拟手工长除法的步骤,每一步依赖前一步的余数继续向下计算。
题目详情
16 判断题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 未分类

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

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

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

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

A
正确
B
错误
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
20 判断题 适中 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. 循环直至任一子区间遍历完毕。
题目详情