2024年12月 GESP C++ 5级

下面关于链表和数组的描述，错误的是（ ）。

在循环单链表中，节点的 next 指针指向下一个节点，最后一个节点的 next 指针指向（ ）。

为了方便链表的增删操作，一些算法生成一个虚拟头节点，方便统一删除头节点和其他节点。下面代码实现了删除链表中值为 $val$ 的节点，横线上应填的最佳代码是( )。

struct LinkedNode {
    int val;
    LinkedNode* next;
    LinkedNode(int val):val(val), next(nullptr){}
};
void removeElements(LinkedNode* head, int val) {
    if (head == nullptr) {
        return;
    }
    LinkedNode* cur;
    LinkedNode* dummyHead = new LinkedNode(0); //虚拟头节点
    ________________________________ // 在此处填入代码
    while(cur ->next != nullptr) {
        if(cur->next->val == val) {
            LinkedNode* tmp = cur->next;
            cur->next = cur->next->next;
            delete tmp;
            tmp = nullptr;
        }
        else {
            cur = cur ->next;
        }
    }
    head = dummyHead->next;
    delete dummyHead;
    dummyHead = nullptr;
}

对下面两个函数，说法错误的是（ ）。

int fibA(int n) {
    if (n <= 1) return n;
    int f1 = 0, f2 = 1;
    for (int i = 2; i <= n; ++i) {
        int temp = f2;
        f2 = f1 + f2;
        f1 = temp;
    }
    return f2;
}
int fibB(int n) {
    if (n <= 1) return n;
    return fibB(n - 1) + fibB(n - 2);
}

两块长方形土地的长宽分别为 $24$ 和 $36$ 米，要将它们分成正方形的小块，使得正方形的尺寸尽可能大。小杨采用如下的辗转相除函数 gcd(24, 36) 来求正方形分块的边长，则函数 gcd 调用顺序为（ ）。

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);
}

唯一分解定理表明，每个大于 $1$ 的自然数可以唯一地写成若干个质数的乘积。下面函数将自然数的所有质因数找出来，横线上能填写的最佳代码是（ ）。

#include <vector>
vector<int> get_prime_factors(int n) {
    vector<int> factors;
    if (n <= 1) {
        cout << "输入的数必须是大于1的正整数" << endl;
        return;
    }
    while (n % 2 == 0) {
        factors.push_back(2);
        n /= 2;
    }
    ________________________________ { // 在此处填入代码
        while (n % i == 0) {
            factors.push_back(i);
            n /= i;
        }
    }
    if (n > 2) {
        factors.push_back(n);
    }
    return factors;
}

下述代码实现素数表的埃拉托色尼（埃氏）筛法，筛选出所有小于等于 $n$ 的素数。

vector<int> sieve_Eratosthenes(int n) {
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    for (int i = sqrt(n) + 1; i <= n; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

下面说法，正确的是（ ）。

下述代码实现素数表的线性筛法，筛选出所有小于等于 $n$ 的素数。下面说法正确的是( )。

vector<int> sieve_linear(int n) {
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;
    for (int i = 2; i <= n / 2; i++) {
        if (is_prime[i])
            primes.push_back(i);
        for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
            is_prime[i * primes[j]] = 0;
            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;
}

考虑以下 C++ 代码实现的快速排序算法：

int partition(vector<int>& arr, int left, int right) {
    int pivot = arr[right]; // 基准值
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[right]);
    return i + 1;
}
// 快速排序
void quickSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int pi = partition(arr, left, right);
        quickSort(arr, left, pi - 1);
        quickSort(arr, pi + 1, right);
    }
}

以下关于快速排序的说法，正确的是（ ）。

下面关于归并排序，描述正确的是（ ）。

给定一个长度为 $n$ 的有序数组 nums，其中所有元素都是唯一的。下面的函数返回数组中元素 target 的索引。

int binarySearch(vector<int> &nums, int target, int left, int right) {
    if (left > right) {
        return -1;
    }
    int middle = left + ((right - left) / 2);
    if (nums[middle] == target) {
        return middle;
    }
    else if (nums[middle] < target) {
        return binarySearch(nums, target, middle + 1, right);
    }
    else
        return binarySearch(nums, target, left, middle - 1);
}
int Find(vector<int> &nums, int target) {
    int n = nums.size();
    return binarySearch(nums, target, 0, n - 1);
}

关于上述函数，描述不正确的是（ ）。

给定一个长度为 $n$ 的有序数组 nums，其中可能包含重复元素。下面的函数返回数组中某个元素 target 的左边界，若数组中不包含该元素，则返回 $-1$。例如在数组 nums = [5,7,7,8,8,10] 中查找 target=8，函数返回在数组中的左边界的索引为 $3$。则横线上应填写的代码为（ ）。

int getLeftBoundary(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while (left < right) {
        int middle = left + ((right - left) / 2);
        if (target <= nums[middle])
            ________________________________ // 在此处填入代码
        else
            left = middle+1;
    }
    return nums[left]==target?left:-1;
}

假设有多个孩子，数组 $g$ 保存所有孩子的胃口值。有多块饼干，数组 $s$ 保存所有饼干的尺寸。小杨给孩子们发饼干，每个孩子最多只能给一块饼干。饼干的尺寸大于等于孩子的胃口时，孩子才能得到满足。小杨的目标是尽可能满足越多数量的孩子，因此打算采用贪心算法来找出能满足的孩子的数目，则横线上应填写的代码为（ ）。

int cooki4children(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    int index = s.size() - 1; // 饼干数组下标
    int result = 0;
    for (int i = g.size() - 1; i >= 0; i--) {
        if (index >= 0 && s[index] >= g[i]) {
            ________________________________ // 在此处填入代码
        }
    }
    return result;
}

关于分治算法，以下说法中不正确的是（ ）。

小杨编写了一个如下的高精度减法函数：

vector<int> highPrecisionSubtract(vector<int> a, vector<int> b) {
    vector<int> result;
    int borrow = 0;
    for (int i = 0; i < a.size(); ++i) {
        int digitA = a[i];
        int digitB = i < b.size() ? b[i] : 0;
        int diff = digitA - digitB - borrow;
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        }
        else {
            borrow = 0;
        }
        result.push_back(diff);
    }
    while (result.size() > 1 && result.back() == 0) {
        result.pop_back();
    }
    return result;
}

下面说法，正确的是（ ）。

单链表只支持在表头进行插入和删除操作。

线性筛相对于埃拉托斯特尼筛法，每个合数只会被它的最小质因数筛去一次，因此效率更高。

任何一个大于 $1$ 的自然数都可以分解成若干个不同的质数的乘积，且分解方式是唯一的。

贪心算法通过每一步选择当前最优解，从而一定能获得全局最优解。

递归算法必须有一个明确的结束条件，否则会导致无限递归并可能引发栈溢出。

快速排序和归并排序的平均时间复杂度均为 $O(n\log n)$，且都是稳定排序。

快速排序的时间复杂度总比插入排序的时间复杂度低。

二分查找仅适用于数组而不适合链表，因为二分查找需要跳跃式访问元素，链表中执行跳跃式访问的效率低。

对有序数组 {$5$, $13$, $19$, $21$, $37$, $56$, $64$, $75$, $88$, $92$, $100$} 进行二分查找，成功查找元素 $19$ 的比较次数是 $2$。

递归函数每次调用自身时，系统都会为新开启的函数分配内存，以存储局部变量、调用地址和其他信息等，导致递归通常比迭代更加耗费内存空间。

试题名称：奇妙数字

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

小杨认为一个数字 $x$ 是奇妙数字当且仅当 x=pax=p^ax=pa，其中 $p$ 为任意质数且 $a$ 为正整数。例如，8=238=2^38=23，所以 $8$ 是奇妙的，而 $6$ 不是。

对于一个正整数 $n$，小杨想要构建一个包含 $m$ 个奇妙数字的集合 {x1,x2,⋯ ,xm}\{x_1,x_2,\cdots,x_m\}{x1​,x2​,⋯,xm​}，使其满足以下条件：

• 集合中不包含相同的数字。
• x1×x2×⋯×xmx_1\times x_2\times \cdots\times x_mx1​×x2​×⋯×xm​ 是 $n$ 的因子（即 x1,x2,⋯ ,xmx_1,x_2,\cdots,x_mx1​,x2​,⋯,xm​ 这 $m$ 个数字的乘积是 $n$ 的因子）。

小杨希望集合包含的奇妙数字尽可能多，请你帮他计算出满足条件的集合最多包含多少个奇妙数字。

输入格式

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

输出格式

输出一个正整数，代表满足条件的集合最多包含的奇妙数字个数。

样例输入 #1

128

样例输出 #1

3

说明/提示

样例解释

关于本样例，符合题意的一个包含 $3$ 个奇妙数字的集合是 $\{2,4,8\}$。首先，因为 2=212=2^12=21，4=224=2^24=22，8=238=2^38=23，所以 $2,4,8$ 均为奇妙数字。同时，$2\times 4\times 8=64$ 是 $128$ 的的因子。

由于无法找到符合题意且同时包含 $4$ 个奇妙数字的集合，因此本样例的答案为 $3$。

数据范围

对于 $100\%$ 的数据，保证 2≤n≤10122\le n\le 10^{12}2≤n≤1012。

试题名称：武器强化

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

小杨有 $n$ 种武器和 $m$ 种强化材料。第 $i$ 种强化材料会适配第 pip_ipi​ 种武器，小杨可以花费 cic_ici​ 金币将该材料对应的适配武器修改为任意武器。

小杨最喜欢第 $1$ 种武器，因此他希望适配该武器的强化材料种类数严格大于其他的武器，请你帮小杨计算为了满足该条件最少需要花费多少金币。

输入格式

第一行包含两个正整数 $n,m$，含义如题面所示。

之后 $m$ 行，每行包含两个正整数 pi,cip_i,c_ipi​,ci​，代表第 $i$ 种强化材料的适配武器和修改花费。

输出格式

输出一个整数，代表能够使适配第 $1$ 种武器的强化材料种类数严格大于其他的武器最少需要花费的金币。

样例输入 #1

4 4
1 1
2 1
3 1
3 2

样例输出 #1

1

说明/提示

样例解释

花费 $1$，将第三种强化材料的适配武器由 $3$ 改为 $1$。此时，武器 $1$ 有 $2$ 种强化材料适配，武器 $2$ 和武器 $3$ 都各有 $1$ 种强化材料适配，满足适配第 $1$ 种武器的强化材料种类数严格大于其他的武器。

数据范围

对于 $100\%$ 的数据，保证 $1\le n,m\le 1000$，1≤pi≤n1\le p_i\le n1≤pi​≤n，1≤ci≤1091\le c_i\le 10^91≤ci​≤109。