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

GESP-C++五级 题库

共 297 道题 ,第 3 / 15 页 · 按题型筛选,点「查看答案」核对解析
41 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

下面的 C++ 代码用于在升序数组 lst 中查找目标值 target 最后一次出现的位置。相关说法,正确的是?( )

int binary_search_last_occurrence(const vector<int>& lst, int target) {
    if (lst.empty()) return -1;
    int low = 0, high = lst.size() - 1;
    while (low < high) {
        int mid = (low + high + 1) / 2;
        if (lst[mid] <= target) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    if (lst[low] == target)
        return low;
    else
        return -1;
}
A
当 lst 中存在重复的 target 时,该函数总能返回最后一个 target 的位置,即便 lst 全由相同元素组成
B
当 target 小于 lst 中所有元素时,该函数会返回 0
C
循环条件改为 while (low <= high) 程序执行效果相同,且能提高准确性
D
将代码中 (low + high + 1) / 2 修改为 (low + high) / 2 效果相同
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
42 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

有关下面C++代码的说法,【错误】的是?( )

double sqrt_binary(long long n, double epsilon = 1e-10) {
    if (n < 0) {
        throw invalid_argument("输入必须为非负整数");
    }
    if (n == 0 || n == 1) return n;
    // 阶段 1
    long long low = 1, high = n;
    long long k = 0;
    while (low <= high) {
        long long mid = (low + high) / 2;
        long long mid_sq = mid * mid;
        if (mid_sq == n) {
            return mid;
        } else if (mid_sq < n) {
            k = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    long long next_k = k + 1;
    if (next_k * next_k == n) {
        return next_k;
    }
    // 阶段 2
    double low_d = (double)k;
    double high_d = (double)(k + 1);
    double mid;
    while (high_d - low_d >= epsilon) {
        mid = (low_d + high_d) / 2;
        double mid_sq = mid * mid;
        if (mid_sq < n) {
            low_d = mid;
        } else {
            high_d = mid;
        }
    }
    double result = (low_d + high_d) / 2;
    long long check_int = (long long)(result + 0.5);
    if (check_int * check_int == n) {
        return check_int;
    }
    return result;
}
A
“阶段1”的目标是寻找正整数 n 可能的正完全平方根
B
“阶段2”的目标是如果正整数 n 没有正完全平方根,则在可能产生完全平方根附近寻找带小数点的平方根
C
代码 check_int = (long long)(result + 0.5) 是检查因浮点误差是否为正完全平方根
D
阶段2的二分法中 high_d - low_d >= epsilon 不能用于浮点数比较,会进入死循环
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
43 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

硬币找零问题中要求找给客户最少的硬币。 coins 存储可用硬币规格,单位为角,假设规格都小于10角,且一定有1角规格。 

amount 为要找零的金额,约定必须为1角的整数倍。输出为每种规格及其数量,按规格从大到小输出,如果某种规格不必要,则输出为0。

下面是其实现代码,相关说法正确的是?( )

const int MAX_COINS = 10;
int result[MAX_COINS] = {0}; // 假设最多10种面额
int find_coins(const vector<int>& coins, int amount) {
    sort(coins.begin(), coins.end(), greater<int>());
    int n = coins.size();
    for (int i = 0; i < n; ++i) {
        int coin = coins[i];
        int num = amount / coin;
        result[i] = num;
        amount -= num * coin;
        if (amount == 0) break;
    }
    cout << "找零方案如下:" << endl;
    for (int i = 0; i < n; ++i) {
        cout << sorted_coins[i] << "角需要" << result[i] << "枚" << endl;
    }
    return 0;
}
A
上述代码采用贪心算法实现
B
针对本题具体要求,上述代码总能找到最优解
C
上述代码采用枚举算法
D
上述代码采用分治算法
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
44 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

关于下述C++代码的快速排序算法,说法【错误】的是?( )

int randomPartition(std::vector<int>& arr, int low, int high) {
    int random = low + rand() % (high - low + 1);
    std::swap(arr[random], arr[high]);
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = randomPartition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
A
在 randomPartition 函数中,变量 i 的作用是记录大于基准值的元素的边界
B
randomPartition 函数随机选择基准值,可以避免输入数据特定模式导致的最坏情况下时间复杂度
C
快速排序平均时间复杂度是 O(n log n)
D
快速排序是稳定排序算法
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
45 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 3.1 高精度加法

小杨编写了一个如下的高精度除法函数,则横线上应填写的代码为?( )

const int MAXN = 1005; // 最大位数
struct BigInt {
    int d[MAXN]; // 存储数字,d[0]是个位,d[1]是十位,...
    int len; // 数字长度
    BigInt() {
        memset(d, 0, sizeof(d));
        len = 0;
    }
};
// 比较两个高精度数的大小
int compare(BigInt a, BigInt b) {
    if(a.len != b.len) return a.len > b.len ? 1 : -1;
    for(int i = a.len - 1; i >= 0; i--) {
        if(a.d[i] != b.d[i]) return a.d[i] > b.d[i] ? 1 : -1;
    }
    return 0;
}
// 高精度减法
BigInt sub(BigInt a, BigInt b) {
    BigInt c;
    for(int i = 0; i < a.len; i++) {
        c.d[i] += a.d[i] - b.d[i];
        if(c.d[i] < 0) {
            c.d[i] += 10;
            c.d[i+1]--;
        }
    }
    c.len = a.len;
    while(c.len > 1 && c.d[c.len-1] == 0) c.len--;
    return c;
}
// 高精度除法(a/b,返回商和余数)
pair<BigInt, BigInt> div(BigInt a, BigInt b) {
    BigInt q, r; // q是商,r是余数
    if(compare(a, b) < 0) { // 如果a<b,商为0,余数为a
        q.len = 1;
        q.d[0] = 0;
        r = a;
        return make_pair(q, r);
    }
    // 初始化余数r为a的前b.len位
    r.len = b.len;
    for(int i = a.len - 1; i >= a.len - b.len; i--) {
        r.d[i - (a.len - b.len)] = a.d[i];
    }
    // 逐位计算商
    for(int i = a.len - b.len; i >= 0; i--) {
        // 把下一位加入余数
        if(r.len > 1 || r.d[0] != 0) {
            for(int j = r.len; j > 0; j--) {
                r.d[j] = r.d[j-1];
            }
            _______________________
        } else {
            r.d[0] = a.d[i];
            r.len = 1;
        }
        // 计算当前位的商
        while(compare(r, b) >= 0) {
            r = sub(r, b);
            q.d[i]++;
        }
    }
    // 确定商的长度
    q.len = a.len - b.len + 1;
    while(q.len > 1 && q.d[q.len-1] == 0) q.len--;
    // 处理余数前导零
    while(r.len > 1 && r.d[r.len-1] == 0) r.len--;
    return make_pair(q, r);
}
A
r.d[0] = a.d[i];r.len++;
B
r.d[i] = a.d[i];r.len++;
C
r.d[i] = a.d[i];r.len = 1;
D
r.d[0] = a.d[i];r.len = 1;
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
46 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

链表【不具备】的特点是?( )

A
可随机访问任何一个元素
B
插入、删除操作不需要移动元素
C
无需事先估计存储空间大小
D
所需存储空间与存储元素个数成正比
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
47 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

双向链表中每个结点有两个指针域 prev 和 next ,分别指向该结点的前驱及后继结点。

设 p 指向链表中的一个结点,它的前驱结点和后继结点均非空。要删除结点 p ,则下述语句中【错误】的是?( )

A
p->next->prev = p->next;p->prev->next = p->prev;delete p;
B
p->prev->next = p->next;p->next->prev = p->prev;delete p;
C
p->next->prev = p->prev;p->next->prev->next = p->next;delete p;
D
p->prev->next = p->next;p->prev->next->prev = p->prev;delete p;
答案与解析
正确答案:A

要删除双向链表中的结点 p,需要正确调整其前驱(prev)和后继(next)结点的指针:

让 p->prev->next 指向 p->next(前驱的后继指向 p 的后继)。

让 p->next->prev 指向 p->prev(后继的前驱指向 p 的前驱)。

选项A错误:

p->next->prev = p->next;  // 错误:让后继的前驱指向自己(p->next),破坏了链表结构

p->prev->next = p->prev;  // 错误:让前驱的后继指向自己(p->prev),链表断裂

题目详情
48 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 4.1 单链表

假设双向循环链表包含头尾哨兵结点(不存储实际内容),分别为 head 和 tail ,链表中每个结点有两个指针域 prev 和 next ,分别指向该结点的前驱及后继结点。

下面代码实现了一个空的双向循环链表,横线上应填的最佳代码是?( )

// 链表结点
template <typename T>
struct ListNode {
    T data;
    ListNode* prev;
    ListNode* next;
    // 构造函数
    explicit ListNode(const T& val = T())
        : data(val), prev(nullptr), next(nullptr) {}
};
struct LinkedList {
    ListNode<T>* head;
    ListNode<T>* tail;
};
void InitLinkedList(LinkedList* list) {
    list->head = new ListNode<T>;
    list->tail = new ListNode<T>;
    ________________________________ // 在此处填入代码
};
A
list->head->prev = list->head;list->tail->prev = list->head;
B
list->head->next = list->tail;list->tail->prev = list->head;
C
list->head->next = list->tail;list->tail->next = list->head;
D
list->head->next = list->tail;list->tail->next = nullptr;
答案与解析
正确答案:B

双向循环链表的结构:

头哨兵 head:

head->prev 应该指向链表的最后一个结点(即 tail)。

head->next 应该指向链表的第一个实际结点(如果链表为空,则指向 tail)。

尾哨兵 tail:

tail->prev 应该指向链表的最后一个实际结点(如果链表为空,则指向 head)。

tail->next 应该指向链表的第一个结点(即 head)。

由于链表为空,head 和 tail 应该互相指向对方:

head->next = tail

tail->prev = head

题目详情

用以下辗转相除法(欧几里得算法)求gcd(84, 60)的步骤中,第二步计算的数是?( )

int gcd(int a, int b) {
    int big = a > b ? a : b;
    int small = a < b ? a : b;
    if (big % small == 0) {
        return small;
    }
    return gcd(small, big % small);
}
A
84和60
B
60和24
C
24和12
D
12和0
答案与解析
正确答案:B

调用gcd(84, 60)函数中:

big=84,small=60,big % small不为零,递归调用:

gcd(60, 24)。

题目详情
50 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.4 质因数分解

根据唯一分解定理,下面整数的唯一分解是正确的?( )

A
18 = 3 × 6
B
28 = 4 × 7
C
36 = 2 × 3 × 6
D
30 = 2 × 3 × 5
答案与解析
正确答案:D

唯一分解定理指出:任何一个大于 1 的整数,要么本身是一个质数,要么可以唯一地分解为一系列质数的乘积。

需要检查每个选项的分解是否 全部是质数,只有选项D符合。

题目详情
51 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

下述代码实现素数表的线性筛法,筛选出所有小于等于 n 的素数,横线上应填的最佳代码是?( )

vector<int> sieve_linear(int n) {
    vector<bool> is_prime(n +1, true);
    vector<int> primes;
    if (n < 2) return primes;
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n/2; i++) {
        if (is_prime[i])
            primes.push_back(i);
        for (int j = 0; ___________________ ; j++) { // 在此处填入代码
            is_prime[ i * primes[j] ] = false;
            if (i % primes[j] == 0)
                break;
        }
    }
    for (int i = n/2 +1; i <= n; i++) {
        if (is_prime[i])
            primes.push_back(i);
    }
    return primes;
}
A
j < primes.size()
B
i * primes[j] <= n
C
j < primes.size() && i * primes[j] <= n
D
j <= n
答案与解析
正确答案:C

线性筛法的核心思想是 每个合数只被其最小质因数筛除一次,从而保证 O(n) 的时间复杂度。

内层循环的目的是 筛除 i×primes[j],因此需要满足:

j 不超过 primes 数组的大小(避免越界访问)。

i×primes[j]≤n(筛除的合数不能超过 n)。

本题答案为选项C。

题目详情
52 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 6.1 递归概念

在程序运行过程中,如果递归调用的层数过多,会因为( )引发错误?

A
系统分配的栈空间溢出
B
系统分配的堆空间溢出
C
系统分配的队列空间溢出
D
系统分配的链表空间溢出
答案与解析
正确答案:A

如果递归层数过深,栈空间会被耗尽,导致 栈溢出错误。

题目详情
53 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

对下面两个函数,说法【错误】的是?( )

int factorialA(int n) {
    if (n <= 1) return 1;
    return n * factorialA(n - 1);
}
int factorialB(int n) {
    if (n <= 1) return 1;
    int res = 1;
    for(int i=2; i<=n; i++)
        res *= i;
}
A
两个函数的实现的功能相同。
B
两个函数的时间复杂度均为 O(n)。
C
factorialA采用递归方式。
D
factorialB采用递归方式。
答案与解析
正确答案:D

两个计算阶乘的函数 factorialA 和 factorialB。

factorialA采用递归的方法,factorialB 采用循环方式实现,二者的时间复杂度均为O(n)。

题目详情
54 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

下算法中,( )是不稳定的排序?

A
选择排序
B
插入排序
C
归并排序
D
冒泡排序
答案与解析
正确答案:A

稳定排序 是指:如果两个相等的元素在排序前后的相对位置保持不变。

不稳定排序 是指:相等的元素在排序后可能交换位置。

对于选择排序,每次从未排序部分选择最小(或最大)元素,放到已排序部分的末尾。

例如:[5, 5, 2]进行排序,[5(1), 5(2), 2](用下标区分两个 5),找到最小值 2,交换 5(1)和 2,数组变为:[2, 5(2), 5(1)],两个5的相对顺序改变了。

题目详情
55 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

考虑以下C++代码实现的快速排序算法,将数据从小到大排序,则横线上应填的最佳代码是?( )

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 基准值
    int i = low - 1;
    for (int j = low; j < high; j++) {
        ____________________ // 在此处填入代码
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}
// 快速排序
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
A
if (arr[j] > pivot) {
    i++;
    swap(arr[i], arr[j]);
}
B
if (arr[j] < pivot) {
    i++;
    swap(arr[i], arr[j]);
}
C
if (arr[j] < pivot) {
    swap(arr[i], arr[j]);
    i++;
}
D
if (arr[j] == pivot) {
    i++;
    swap(arr[i], arr[j]);
}
答案与解析
正确答案:B

快速排序是一种分治算法,其基本步骤如下:

选择基准:从数组中选择一个元素作为基准(通常选择最后一个元素)。

分区:重新排列数组,使得所有比基准小的元素放在基准前面,所有比基准大的元素放在基准后面。分区完成后,基准就位于其最终排序后的正确位置。

递归排序:递归地对基准前后的子数组进行快速排序。

在分区过程中:

i初始化为low - 1,表示小于基准的区域最初为空。

j从low到high - 1遍历数组。

如果arr[j]小于pivot,则i增加1,并将arr[i]和arr[j]交换。这样,arr[i]现在是一个小于pivot的元素。

本题答案为选项B。

题目详情
56 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

若用二分法在[1, 100]内猜数,最多需要猜( )次?

A
100
B
10
C
7
D
5
答案与解析
正确答案:C

二分查找每次将搜索区间对半分,最坏情况下需要猜测的次数:

2^6<100(6 次不够),2^7>=100(7 次足够)。

题目详情
57 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 5.1 二分查找

下面代码实现了二分查找算法,在数组 arr 找到目标元素 target 的位置,则横线上能填写的最佳代码是?( )

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        _____________________ // 在此处填入代码
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}
A
int mid = left + (right - left) / 2;
B
int mid = left;
C
int mid = (left + right) / 2;
D
int mid = right;
答案与解析
正确答案:A

计算 mid 需要满足:

正确性:必须保证 mid 是当前区间的中间位置。

安全性:避免整数溢出(当 left 和 right 很大时,left + right 可能溢出)。

选项A:int mid = left + (right - left) / 2,数学等价于选项C,但是通过 right - left 避免直接计算 left + right,防止溢出。

题目详情
58 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 8.1 贪心思想

贪心算法的核心特征是?( )

A
总是选择当前最优解
B
回溯尝试所有可能
C
分阶段解决子问题
D
总能找到最优解
答案与解析
正确答案:A

贪心算法是一种在每一步选择中都采取当前状态下最优(局部最优)的决策,从而希望导致全局最优解的算法策略,但是贪心算法 不一定能得到全局最优解。

题目详情
59 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 综合练习

函数 int findMax(int arr[], int low, int high) 计算数组中最大元素,其中数组 arr 从索引low 到 high ,( )正确实现了分治逻辑?

A
if (low == high)
    return arr[low];
int mid = (low + high) / 2;
return arr[mid];
B
if (low >= high)
    return arr[low];
int mid = (low + high) / 2;
int leftMax = findMax(arr, low, mid - 1);
int rightMax = findMax(arr, mid, high);
return leftMax + rightMax;
C
if (low > high)
    return 0;
int mid = low + (high - low) / 2;
int leftMax = findMax(arr, low, mid);
int rightMax = findMax(arr, mid + 1, high);
return leftMax * rightMax;
D
if (low == high)
    return arr[low];
int mid = low + (high - low) / 2;
int leftMax = findMax(arr, low, mid);
int rightMax = findMax(arr, mid + 1, high);
return (leftMax > rightMax) ? leftMax : rightMax;
答案与解析
正确答案:D

分治法的核心思想是:分解,解决,合并。

对于 求数组最大值,分治法的具体实现是:

基准情况:如果 low == high,说明区间只有一个元素,直接返回 arr[low]。

分解:计算中间位置 mid。

递归求左半部分 [low, mid] 的最大值 leftMax。

递归求右半部分 [mid+1, high] 的最大值 rightMax。

合并:比较 leftMax 和 rightMax,返回较大者。

题目详情
60 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 3.1 高精度加法

小杨编写了一个如下的高精度乘法函数,则横线上应填写的代码为?( )

vector<int> multiply(vector<int>& a, vector<int>& b) {
    int m = a.size(), n = b.size();
    vector<int> c(m + n, 0);
    // 逐位相乘,逆序存储
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            c[i + j] += a[i] * b[j];
        }
    }
    // 处理进位
    int carry = 0;
    for (int k = 0; k < c.size(); ++k) {
        ______________________ // 在此处填入代码
        c[k] = temp % 10;
        carry = temp / 10;
    }
    while (c.size() > 1 && c.back() == 0)
        c.pop_back();
    return c;
}
A
int temp = c[k];
B
int temp = c[k] + carry;
C
int temp = c[k] - carry;
D
int temp = c[k] * carry;
答案与解析
正确答案:B

高精度乘法(大数乘法)通过 逐位相乘并处理进位 来实现。

选项B正确,temp 是当前位的值加上前一位的进位。

题目详情