GESP 五级 · 2025 真题

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

01// 循环单链表的结点
02struct Node {
03    int data;        // 数据域
04    Node* next;      // 指针域
05
06    Node(int d) : data(d), next(nullptr) {}
07};
08
09// 创建一个只有一个结点的循环单链表
10Node* createList(int value) {
11    Node* head = new Node(value);
12    head->next = head;
13    return head;
14}
15
16// 在循环单链表尾部插入新结点
17void insertTail(Node* head, int value) {
18    Node* p = head;
19    while (p->next != head) {
20        p = p->next;
21    }
22    Node* node = new Node(value);
23    node->next = head;
24    p->next = node;
25}
26
27// 遍历并输出循环单链表
28void printList(Node* head) {
29    if (head == nullptr) return;
30
31    Node* p = head;
32    ____________      // 在此处填入代码
33    cout << endl;
34}

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

01//区块（节点）
02struct Block {
03    int index;         // 区块编号（高度）
04    string data;       // 区块里保存的数据
05    Block* prev;       // 指向前一个区块
06
07    Block(int idx, const string& d, Block* p) : index(idx), data(d), prev(p) {}
08};
09
10// 区块链
11struct Blockchain {
12    Block* tail;
13
14    // 初始化
15    void init() {
16        tail = new Block(0, "Genesis Block", nullptr);
17    }
18
19    // 插入新区块
20    void addBlock(const string& data) {
21        ____________      // 在此处填入代码
22    }
23
24    // 释放内存
25    void clear() {
26        Block* cur = tail;
27        while (cur != nullptr) {
28            Block* p = cur->prev;
29            delete cur;
30            cur = p;
31        }
32        tail = nullptr;
33    }
34};

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

01struct DNode {
02    int data;
03    DNode* prev;
04    DNode* next;
05};
06
07// 在双链表中删除指定节点
08void deleteNode(DNode* node) {
09    if (node->prev) {
10        node->prev->next = node->next;
11    }
12    if (node->next) {
13        node->next->prev = node->prev;
14    }
15    delete node;
16}
17
18struct SNode {
19    int data;
20    SNode* next;
21};
22
23// 在单链表中删除指定节点
24void deleteSNode(SNode* head, SNode* node) {
25    SNode* prev = head;
26    while (prev->next != node) {
27        prev = prev->next;
28    }
29    prev->next = node->next;
30    delete node;
31}

假设我们有两个数 $a = 38$ 和 $b = 14$，它们对模 $m$ 同余，即 $a \equiv b \pmod{m}$。以下哪个值不可能是 $m$？

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

01int gcd1(int a, int b) {
02    return b == 0 ? a : gcd1(b, a % b);
03}
04
05int gcd2(int a, int b) {
06    while (b != 0) {
07        int temp = b;
08        b = a % b;
09        a = temp;
10    }
11    return a;
12}

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

下述代码实现素数表的线性筛法，筛选出所有小于等于 $n$ 的素数，则横线上应填的代码是（ ）。

01vector<int> linear_sieve(int n) {
02    vector<bool> is_prime(n +1, true);
03    vector<int> primes;
04
05    is_prime[0] = is_prime[1] = 0; //0和1两个数特殊处理
06    for (int i = 2; i <= n; ++i) {
07        if (is_prime[i]) {
08            primes.push_back(i);
09        }
10        ____________ {      // 在此处填入代码
11            is_prime[ i * primes[j] ] = 0;
12            if (i % primes[j] == 0)
13                break;
14        }
15    }
16
17    return primes;
18}

下列关于排序的说法，正确的是（ ）。

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

01void merge(vector<int>& arr, vector<int>& temp, int l, int mid, int r) {
02    int i = l, j = mid + 1, k = l;
03    while (i <= mid && j <= r) {
04        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
05        else temp[k++] = arr[j++];
06    }
07    while (i <= mid) temp[k++] = arr[i++];
08    while (j <= r)  temp[k++] = arr[j++];
09    for (int p = l; p <= r; p++) arr[p] = temp[p];
10}
11
12void mergeSort(vector<int>& arr, vector<int>& temp, int l, int r) {
13    if (l >= r) return;
14    int mid = l + (r - l) / 2;
15    mergeSort(arr, temp, l, mid);
16    mergeSort(arr, temp, mid + 1, r);
17    merge(arr, temp, l, mid, r);
18}

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

01int partition(vector<int>& arr, int low, int high) {
02    int i = low, j = high;
03    int pivot = arr[low];             // 以首元素为基准
04    while (i < j) {
05        while (i < j && arr[j] >= pivot) j--;
06        while (i < j && arr[i] <= pivot) i++;
07        if (i < j) swap(arr[i], arr[j]);
08    }
09    swap(arr[i], arr[low]);
10    return i;
11}
12
13void quickSort(vector<int>& arr, int low, int high) {
14    if (low >= high) return;
15    int p = partition(arr, low, high);
16    quickSort(arr, low, p - 1);
17    quickSort(arr, p + 1, high);
18}

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

01int lower_bound(vector<int>& arr, int x) {
02    int l = 0, r = arr.size();
03    while(l < r) {
04        int mid = l + (r - l) / 2;
05        if(arr[mid] >= x) r = mid;
06        else l = mid + 1;
07    }
08    return l;
09}

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

01// 判断：在不超过 K 次切割内，是否能让每段长度 <= x
02bool check(int L, int K, int x) {
03    int cuts = (L - 1) / x;
04    return cuts <= K;
05}
06
07// 二分查找最小可行的 x
08int binary_cut(int L, int K) {
09    int l = 1, r = L;
10    while (l < r) {
11        int mid = l + (r - l) / 2;
12        ____________      // 在此处填入代码
13    }
14    return l;
15}
16
17int main() {
18    int L = 10;   // 木头长度
19    int K = 2;    // 最多切 K 刀
20
21    cout << binary_cut(L, K) << endl;
22    return 0;
23}

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

01int factorial1(int n) {
02    if (n <= 1) return 1;
03    return n * factorial1(n - 1);
04}
05
06int factorial2(int n) {
07    int acc = 1;
08    while (n > 1) {
09        acc = n * acc;
10        n = n - 1;
11    }
12    return acc;
13}

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

01struct Task {
02    int deadline;    //截止时间
03    int profit;      //利润
04};
05
06void sortByProfit(vector<Task>& tasks) {
07    sort(tasks.begin(), tasks.end(),
08        [](const Task& a, const Task& b) {
09            return a.profit > b.profit;
10        });
11}
12
13int maxProfit(vector<Task>& tasks) {
14    sortByProfit(tasks);
15
16    int maxTime = 0;
17    for (auto& t : tasks) {
18        maxTime = max(maxTime, t.deadline);
19    }
20
21    vector<bool> slot(maxTime + 1, false);
22    int totalProfit = 0;
23
24    for (auto& task : tasks) {
25        for (int t = task.deadline; t >= 1; t--) {
26            if (!slot[t]) {
27                ____________      // 在此处填入代码
28                break;
29            }
30        }
31    }
32
33    return totalProfit;
34}

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

01vector<int> add(vector<int> a, vector<int> b) {
02    vector<int> c;
03    int carry = 0;
04
05    for (int i = 0; i < a.size() || i < b.size(); i++) {
06        if (i < a.size()) carry += a[i];
07        if (i < b.size()) carry += b[i];
08        ____________      // 在此处填入代码
09    }
10    if (carry) c.push_back(carry);
11
12    return c;
13}

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

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

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

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

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

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

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

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

以下 fib 函数计算第 $n$ 项斐波那契数（fib(0)=0，fib(1)=1），其时间复杂度为 $O(n)$。

01int fib(int n) {
02    if (n <= 1) return n;
03    return fib(n-1) + fib(n-2);
04}

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

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