202512 GESP认证 C++编程五级真题试卷

单选题共 15 题

对如下定义的C++循环单链表，横线处填写（）。

while (p != nullptr){
    cout << p->data << " ";
    p = p->next;
}

while (p->next != nullptr){
    cout << p->data << " ";
    p = p->next;
}

do {
    cout << p->data << " ";
    p = p->next;
} while (p != head);

for(; p; p=p->next){
    cout << p->data << " ";
}

区块链技术是比特币的基础。在区块链中，每个区块指向前一个区块，构成链式列表，新区块只能接在链尾，不允许在中间插入或删除。下面C++代码实现插入区块添加函数，则横线处填写（）。

Block* newBlock = new Block(tail->index + 1, data, tail);
tail = newBlock->prev;

Block* newBlock = new Block(tail->index + 1, data, tail);
tail = newBlock;

Block* newBlock = new Block(tail->index + 1, data, tail->prev);
tail = newBlock;

Block* newBlock = new Block(tail->index + 1, data, tail->prev);
tail = newBlock->prev;

下面关于单链表和双链表的描述中，正确的是（）。

A 双链表删除指定节点是 O(1)，单链表是 O(1) B

双链表删除指定节点是 O(n) ，单链表是 O(1)

双链表删除指定节点是O(1) ，单链表是O(n)

双链表删除指定节点是 O(n) ，单链表是O(n)

假设我们有两个数 a=38 和 b=14，它们对模 m 同余，即 a=b(mod m)。以下哪个值不可能是 m？

下面C++代码实现了欧几里得算法。下面有关说法，错误的是（）。

A gcd1() 实现为递归方式。 B gcd2() 实现为迭代方式。 C 当 a 较大时， gcd1() 实现会多次调用自身，需要较多额外的辅助空间。 D 当 a 较大时， gcd1() 的实现比 gcd2() 执行效率更高。

唯一分解定理描述的内容是（）。

A 任何正整数都可以表示为两个素数的和。 B 任何大于1的合数都可以唯一分解为有限个质数的乘积。 C 两个正整数的最大公约数总是等于它们的最小公倍数除以它们的乘积。 D 所有素数都是奇数。

下述c++代码实现素数表的线性筛法，筛选出所有小于等于的素数，则横线上应填的代码是( )。

A for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) B for(int j = sqrt(n); j <= n && i * primes[j] <= n; j++) C for (int j = 1; j <= sqrt(n); j++) D for(int j = 1; j < n && i * primes[j] <= n; j++)

下列关于排序的说法，正确的是( )。

A 快速排序是稳定排序 B 归并排序通常是稳定的 C 插入排序是不稳定排序 D 冒泡排序不是原地排序

下面c++代码实现了归并排序。下述关于归并排序的说法中，不正确的是（）。

A 归并排序的平均复杂度是 O(n log n) 。 B 归并排序需要 O(n) 的额外空间。 C 归并排序在最坏情况的时间复杂度是 O(n²)。 D 归并排序适合大规模数据。

10.

下述C++代码实现了快速排序算法，最坏情况的时间复杂度是（）。

O(n)

O(log n)

O(n²)

O(n log n)

11.

下面C++代码尝试在有序数组中查找第一个大于等于 x 的元素位置。如果没有大于等于 x 的元素，返回 arr.size() 。以下说法正确的是（）。

int lower_bound(vector<int>& arr, int x) {
    int l = 0, r = arr.size();
    while(l < r) {
        int mid = l + (r - l) / 2;
        if(arr[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

A 上述代码逻辑正确 B 上述代码逻辑错误， while 循环条件应该用 l <= r C 上述代码逻辑错误， mid 计算错误 D 上述代码逻辑错误，边界条件不对

12.

小杨要把一根长度为 L 的木头切成 K 段，使得每段长度小于等于 x 。已知每切一刀只能把一段木头分成两段，他用二分法找到满足条件的最小 x （ x 为正整数），则横线处应填写（）。

if (check(L, K, mid))
    r = mid;
else
    l = mid + 1;

if (check(L, K, mid))
    r = mid+1;
else
    l = mid + 1;

if (check(L, K, mid))
    r = mid + 1;
else
    l = mid - 1;

if (check(L, K, mid))
    r = mid + 1;
else
    l = mid;

13.

下面给出了阶乘计算的两种方式。以下说法正确的是（）。

A 上面两种实现方式的时间复杂度相同，都为O(n) B 上面两种实现方式的空间复杂度相同，都为O(n) C 上面两种实现方式的空间复杂度相同，都为O(1) D 函数 factorial1() 的时间复杂度为 O(2ⁿ)，函数 factorial2() 的时间复杂度为O(n)

14.

给定有 n 个任务，每个任务有截止时间和利润，每个任务耗时 1 个时间单位、必须在截止时间前完成，且每个时间槽最多做 1 个任务。为了在规定时间内获得最大利润，可以采用贪心策略，即按利润从高到低排序，尽量安排，则横线处应填写（）。

slot[t] = true;

totalProfit += task.profit;

slot[t] = false;

totalProfit += task.profit;

slot[t] = true;

totalProfit = task.profit;

slot[t] = false;

totalProfit = task.profit

15.

下面C++代码实现了对两个数组表示的正整数的高精度加法（数组低位在前），则横线上应填写（）。

c.push_back(carry / 10);

carry %= 10;

c.push_back(carry % 10);

carry /= 10;

C c.push_back(carry % 10); D

c.push_back(carry);

carry /= 10;

判断题共 10 题

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

A 正确 B 错误

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

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

A 正确 B 错误

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

A 正确 B 错误

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

A 正确 B 错误

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

A 正确 B 错误

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

A 正确 B 错误

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

A 正确 B 错误

以下 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 错误

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

A 正确 B 错误

10.

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

A 正确 B 错误

问答题共 2 题

试题名称：数字移动

时间限制：1.0 s

内存限制：512.0 MB

3.1.1 题目描述

小 A 有一个包含 N 个正整数的序列，序列 A 恰好包含 N/2对不同的正整数。形式化地，对于任意 1<=i<=N，存在唯一一个 j 满足

小 A 希望每对相同的数字在序列中相邻，为了实现这一目的，小 A 每次操作会选择任意 i ( 1<=i<=N)，将当前序列的第 i 个数字移动到任意位置，并花费对应数字的体力。

例如，假设序列 A={1,2,1,3,2,3.}，小 A 可以选择 i=2 ，将 A₂=2移动到 A₃=1的后面，此时序列变为{1,1,2,3,2,3.}，耗费 2 点体力。小 A 也可以选择 i=3，将 A₃=1移动到A₂=2 的前面，此时序列变为{1,1,2,3,2,3.}，花费 1 点体力。

小 A 可以执行任意次操作，但他希望自己每次花费的体力尽可能小。小 A 希望你能帮他计算出一个最小的 x ，使得他能够在每次花费的体力均不超过 x 的情况下令每对相同的数字在序列中相邻。

3.1.2 输入格式

第一行一个正整数 N ，代表序列长度，保证 N 为偶数。

数据保证小 A 至少需要执行一次操作。

3.1.3 输出格式

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

3.1.4 样例

3.1.4.1 输入样例

6
1 2 1 3 2 3

3.1.4.2 输出样例

3.1.5 数据范围

试题名称：相等序列

时间限制：1.0 s

内存限制：512.0 MB

3.2.1 题目描述

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

选择序列中一个正整数 A_i（1<=i<=N ），将 A_i变为 A_i*P， P为任意质数；

选择序列中一个正整数 A_i（1<=i<=N ），将 A_i变为 A_i/P， p为任意质数，要求 A_i能整除 P。

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

3.2.2 输入格式

第一行一个正整数 N，含义如题面所示。

第二行包含N 个正整数 A₁,A₂,...AN，代表序列 A。

3.2.3 输出格式

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

3.2.4 样例

3.2.4.1 输入样例

5
10 6 35 105 42

3.2.4.2 输出样例

3.2.5 数据范围

提交试卷

退出练习

正在提交