2025年3月 GESP C++ 5级

链表不具备的特点是( )。

双向链表中每个结点有两个指针域 prev 和 next ，分别指向该结点的前驱及后继结点。设 $p$ 指向链表中的一个结点，它的前驱结点和后继结点均非空。要删除结点 $p$ ，则下述语句中错误的是（ ）。

假设双向循环链表包含头尾哨兵结点(不存储实际内容)，分别为 $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>;
    ________________________________ // 在此处填入代码
};

用以下辗转相除法（欧几里得算法）求 $\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);
}

根据唯一分解定理，下面整数的唯一分解是正确的（ ）。

下述代码实现素数表的线性筛法，筛选出所有小于等于 $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;
}

在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。

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

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

下算法中，（ ）是不稳定的排序。

考虑以下 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);
    }
}

若用二分法在 $[1,100]$ 内猜数，最多需要猜（ ）次。

下面代码实现了二分查找算法，在数组 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;
}

贪心算法的核心特征是（ ）。

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

小杨编写了一个如下的高精度乘法函数，则横线上应填写的代码为（ ）。

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

要删除单链表中某个结点 p (非尾结点)，但不知道头结点，可行的操作是将 p->next 的数据拷贝到 p 的数据部分，将 p->next 设置为 p->next->next，然后删除 p->next。

链表存储线性表时要求内存中可用存储单元地址是连续的。

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

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

递归函数必须具有一个终止条件，以防止无限递归。

快速排序算法的时间复杂度与输入是否有序无关，始终稳定为 $O(n\log n)$。

归并排序算法的时间复杂度与输入是否有序无关，始终稳定为 $O(n\log n)$。

二分查找适用于对无序数组和有序数组的查找。

小杨有 $100$ 元去超市买东西，每个商品有各自的价格，每种商品只能买 $1$ 个，小杨的目标是买到最多数量的商品。小杨采用的策略是每次挑价格最低的商品买，这体现了分治思想。

归并排序算法体现了分治算法，每次将大的待排序数组分成大小大致相等的两个小数组，然后分别对两个小数组进行排序，最后对排好序的两个小数组合并成有序数组。

试题名称：平均分配

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

题目描述

小 A 有 $2n$ 件物品，小 B 和小 C 想从小 A 手上买走这些物品。对于第 $i$ 件物品，小 B 会以 bib_ibi​ 的价格购买，而小 C 会以 cic_ici​ 的价格购买。为了平均分配这 $2n$ 件物品，小 A 决定小 B 和小 C 各自只能买走恰好 $n$ 件物品。你能帮小 A 求出他卖出这 $2n$ 件物品所能获得的最大收入吗？

输入格式

第一行，一个正整数 $n$。

第二行，$2n$ 个整数 b1,b2,…,b2nb_1,b_2,\dots,b_{2n}b1​,b2​,…,b2n​。

第三行，$2n$ 个整数 c1,c2,…,c2nc_1,c_2,\dots,c_{2n}c1​,c2​,…,c2n​。

输出格式

一行，一个整数，表示答案。

样例输入 #1

3
1 3 5 6 8 10
2 4 6 7 9 11

样例输出 #1

36

样例输入 #2

2
6 7 9 9
1 2 10 12

样例输出 #2

35

说明/提示

数据范围

对于 $20\%$ 的测试点，保证 $1\le n\le 8$。

对于另外 $20\%$ 的测试点，保证 0≤bi≤10\le b_i\le10≤bi​≤1，0≤ci≤10\le c_i\le10≤ci​≤1。

对于所有测试点，保证 1≤n≤1051\le n\le10^51≤n≤105，0≤bi≤1090\le b_i\le10^90≤bi​≤109，0≤ci≤1090\le c_i\le10^90≤ci​≤109。

试题名称：原根判断

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

题目描述

小 A 知道，对于质数 $p$ 而言，$p$ 的原根 $g$ 是满足以下条件的正整数：

• $1<g<p$；
• gp−1 mod p=1g^{p-1}\bmod{p}=1gp−1modp=1；
• 对于任意 $1\le i<p-1$ 均有 gi mod p≠1g^i\bmod{p}\neq1gimodp=1。

其中 $a\mathrm{mod}p$ 表示 $a$ 除以 $p$ 的余数。

小 A 现在有一个整数 $a$，请你帮他判断 $a$ 是不是 $p$ 的原根。

输入格式

第一行，一个正整数 $T$，表示测试数据组数。

每组测试数据包含一行，两个正整数 $a,p$。

输出格式

对于每组测试数据，输出一行，如果 $a$ 是 $p$ 的原根则输出 Yes，否则输出 No。

样例输入 #1

3
3 998244353
5 998244353
7 998244353

样例输出 #1

Yes
Yes
No

说明/提示

数据范围

对于 $40\%$ 的测试点，保证 3≤p≤1033\le p\le10^33≤p≤103。

对于所有测试点，保证 $1\le T\le 20$，3≤p≤1093\le p\le10^93≤p≤109，$1<a<p$，$p$ 为质数。