GESP 五级 · 2025 真题

与数组相比，链表在（ ）操作上通常具有更高的效率。

下面 C++ 代码实现双向链表。函数 is_empty() 判断链表是否为空，如果链表为空返回 true，否则返回 false。横线处不能填写（ ）。

01// 节点结构体
02struct Node {
03    int data;
04    Node* prev;
05    Node* next;
06};
07
08// 双向链表结构体
09struct DoubleLink {
10    Node* head;
11    Node* tail;
12    int size;
13
14    DoubleLink() {
15        head = nullptr;
16        tail = nullptr;
17        size = 0;
18    }
19
20    ~DoubleLink() {
21        Node* curr = head;
22        while (curr) {
23            Node* next = curr->next;
24            delete curr;
25            curr = next;
26        }
27    }
28
29    // 判断链表是否为空
30    bool is_empty() const {
31        ____________
32    }
33};

在双向链表尾部增加新节点的 append() 函数中，横线上应填写（ ）。

01void append(int data) {
02    Node* newNode = new Node(data, nullptr, nullptr);
03
04    if (is_empty()) {
05        head = tail = newNode;
06    } else {
07        ____________
08    }
09    ++size;
10}

下列 C++ 代码用循环链表解决约瑟夫问题，即假设 $n$ 个人围成一圈，从第一个人开始数，每次数到第 $k$ 个的人就出圈，输出最后留下的那个人的编号。横线上应填写（ ）。

01struct Node {
02    int data;
03    Node* next;
04};
05
06Node* createCircularList(int n) {
07    Node* head = new Node(1, nullptr);
08    Node* prev = head;
09    for (int i = 2; i <= n; ++i) {
10        Node* node = new Node(i, nullptr);
11        prev->next = node;
12        prev = node;
13    }
14    prev->next = head;
15    return head;
16}
17
18int fingLastSurvival(int n, int k) {
19    Node* head = createCircularList(n);
20    Node* p = head;
21    Node* prev = nullptr;
22
23    while (p->next != p) {
24        for (int count = 1; count < k; ++count) {
25            prev = p;
26            p = p->next;
27        }
28        ____________
29    }
30
31    cout << "最后留下的人编号是：" << p->data << endl;
32    delete p;
33
34    return 0;
35}

下列 C++ 代码判断一个正整数是否是质数，说法正确的是（ ）。

01bool is_prime(int n) {
02    if (n <= 1)
03        return false;
04    if (n == 2 || n == 3 || n == 5)
05        return true;
06    if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0)
07        return false;
08
09    int i = 7;
10    int step = 4;
11    int finish_number = sqrt(n) + 1;
12
13    while (i <= finish_number) {
14        if (n % i == 0)
15            return false;
16        i += step;
17        step = 6 - step;
18    }
19    return true;
20}

下列 C++ 代码用两种方式求解两个正整数的最大公约数，说法错误的是（ ）。

01int gcd0(int big, int small) {
02    if (big < small) {
03        swap(big, small);
04    }
05    if (big % small == 0) {
06        return small;
07    }
08    return gcd0(small, big % small);
09}
10
11int gcd1(int big, int small) {
12    if (big < small) {
13        swap(big, small);
14    }
15    for (int i = small; i >= 1; --i) {
16        if (big % i == 0 && small % i == 0)
17            return i;
18    }
19    return 1;
20}

下面的代码用于判断整数 $n$ 是否是质数，错误的说法是（ ）。

01bool is_prime(int n) {
02    if (n <= 1) return false;
03
04    int finish_number = static_cast<int>(sqrt(n)) + 1;
05    for (int i = 2; i < finish_number; ++i) {
06        if (n % i == 0)
07            return false;
08    }
09    return true;
10}

唯一分解定理描述了关于正整数的什么性质？

下面的 C++ 代码，用于求一系数据中的最大值。有关其算法说法错误的是（ ）。

01int find_max_recursive(const vector<int>& nums, int left, int right) {
02    if (left == right)
03        return nums[left];
04
05    int mid = left + (right - left) / 2;
06    int left_max = find_max_recursive(nums, left, mid);
07    int right_max = find_max_recursive(nums, mid + 1, right);
08
09    return max(left_max, right_max);
10}
11
12int find_max(const vector<int>& nums) {
13    if (nums.empty()) {
14        throw invalid_argument("输入数组不能为空");
15    }
16    return find_max_recursive(nums, 0, nums.size() - 1);
17}

下面的 C++ 代码，用于求一系数据中的最大值。有关其算法说法错误的是（ ）。

01int find_max(const vector<int>& nums) {
02    if (nums.empty()) {
03        throw invalid_argument("输入数组不能为空");
04    }
05
06    int max_value = nums[0];
07    for (int num : nums) {
08        if (num > max_value) {
09            max_value = num;
10        }
11    }
12    return max_value;
13}

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

01int binary_search_last_occurrence(const vector<int>& lst, int target) {
02    if (lst.empty()) return -1;
03
04    int low = 0, high = lst.size() - 1;
05
06    while (low < high) {
07        int mid = (low + high + 1) / 2;
08        if (lst[mid] <= target) {
09            low = mid;
10        } else {
11            high = mid - 1;
12        }
13    }
14
15    if (lst[low] == target)
16        return low;
17    else
18        return -1;
19}

有关下面 C++ 代码的说法，错误的是（ ）。

01double sqrt_binary(long long n, double epsilon = 1e-10) {
02    if (n < 0) {
03        throw invalid_argument("输入必须为非负整数");
04    }
05
06    if (n == 0 || n == 1) return n;
07
08    // 阶段 1
09    long long low = 1, high = n;
10    long long k = 0;
11
12    while (low <= high) {
13        long long mid = (low + high) / 2;
14        long long mid_sq = mid * mid;
15
16        if (mid_sq == n) {
17            return mid;
18        } else if (mid_sq < n) {
19            k = mid;
20            low = mid + 1;
21        } else {
22            high = mid - 1;
23        }
24    }
25
26    long long next_k = k + 1;
27    if (next_k * next_k == n) {
28        return next_k;
29    }
30
31    // 阶段 2
32    double low_d = (double)k;
33    double high_d = (double)(k + 1);
34    double mid;
35
36    while (high_d - low_d >= epsilon) {
37        mid = (low_d + high_d) / 2;
38        double mid_sq = mid * mid;
39
40        if (mid_sq < n) {
41            low_d = mid;
42        } else {
43            high_d = mid;
44        }
45    }
46
47    double result = (low_d + high_d) / 2;
48    long long check_int = (long long)(result + 0.5);
49    if (check_int * check_int == n) {
50        return check_int;
51    }
52
53    return result;
54}

硬币找零问题中要求找给客户最少的硬币。coins 存储可用硬币规格，单位为角，假设规格都小于 $10$ 角，且一定有 $1$ 角规格。amount 为要找零的金额，约定必须为 $1$ 角的整数倍。输出为每种规格及其数量，按规格从大到小输出，如果某种规格不必要，则输出为 $0$。下面是其实现代码，相关说法正确的是（ ）。

01const int MAX_COINS = 10;
02int result[MAX_COINS] = {0};  // 假设最多10种面额
03
04int find_coins(const vector<int>& coins, int amount) {
05    sort(coins.begin(), coins.end(), greater<int>());
06
07    int n = coins.size();
08
09    for (int i = 0; i < n; ++i) {
10        int coin = coins[i];
11        int num = amount / coin;
12        result[i] = num;
13        amount -= num * coin;
14        if (amount == 0) break;
15    }
16
17    cout << "找零方案如下：" << endl;
18    for (int i = 0; i < n; ++i) {
19        cout << sorted_coins[i] << "角需要" << result[i] << "枚" << endl;
20    }
21
22    return 0;
23}

关于下述 C++ 代码的快速排序算法，说法错误的是（ ）。

01int randomPartition(std::vector<int>& arr, int low, int high) {
02    int random = low + rand() % (high - low + 1);
03    std::swap(arr[random], arr[high]);
04
05    int pivot = arr[high];
06    int i = low - 1;
07
08    for (int j = low; j < high; j++) {
09        if (arr[j] <= pivot) {
10            i++;
11            std::swap(arr[i], arr[j]);
12        }
13    }
14    std::swap(arr[i + 1], arr[high]);
15    return i + 1;
16}
17
18void quickSort(std::vector<int>& arr, int low, int high) {
19    if (low < high) {
20        int pi = randomPartition(arr, low, high);
21
22        quickSort(arr, low, pi - 1);
23        quickSort(arr, pi + 1, high);
24    }
25}

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

01const int MAXN = 1005; // 最大位数
02struct BigInt {
03    int d[MAXN]; // 存储数字，d[0]是个位，d[1]是十位，...
04    int len;     // 数字长度
05
06    BigInt() {
07        memset(d, 0, sizeof(d));
08        len = 0;
09    }
10};
11
12// 比较两个高精度数的大小
13int compare(BigInt a, BigInt b) {
14    if(a.len != b.len) return a.len > b.len ? 1 : -1;
15    for(int i = a.len - 1; i >= 0; i--) {
16        if(a.d[i] != b.d[i]) return a.d[i] > b.d[i] ? 1 : -1;
17    }
18    return 0;
19}
20
21// 高精度减法
22BigInt sub(BigInt a, BigInt b) {
23    BigInt c;
24    for(int i = 0; i < a.len; i++) {
25        c.d[i] += a.d[i] - b.d[i];
26        if(c.d[i] < 0) {
27            c.d[i] += 10;
28            c.d[i+1]--;
29        }
30    }
31    c.len = a.len;
32    while(c.len > 1 && c.d[c.len-1] == 0) c.len--;
33    return c;
34}
35
36// 高精度除法 (a/b, 返回商和余数)
37pair<BigInt, BigInt> div(BigInt a, BigInt b) {
38    BigInt q, r; // q是商，r是余数
39
40    if(compare(a, b) < 0) { // 如果a<b，商为0，余数为a
41        q.len = 1;
42        q.d[0] = 0;
43        r = a;
44        return make_pair(q, r);
45    }
46
47    // 初始化余数r为a的前b.len位
48    r.len = b.len;
49    for(int i = a.len - 1; i >= a.len - b.len; i--) {
50        r.d[i - (a.len - b.len)] = a.d[i];
51    }
52
53    // 逐位计算商
54    for(int i = a.len - b.len; i >= 0; i--) {
55        // 把下一位加入余数
56        if(r.len > 1 || r.d[0] != 0) {
57            for(int j = r.len; j > 0; j--) {
58                r.d[j] = r.d[j-1];
59            }
60            ____________
61        } else {
62            r.d[0] = a.d[i];
63            r.len = 1;
64        }
65
66        // 计算当前位的商
67        while(compare(r, b) >= 0) {
68            r = sub(r, b);
69            q.d[i]++;
70        }
71    }
72
73    // 确定商的长度
74    q.len = a.len - b.len + 1;
75    while(q.len > 1 && q.d[q.len-1] == 0) q.len--;
76
77    // 处理余数前导零
78    while(r.len > 1 && r.d[r.len-1] == 0) r.len--;
79
80    return make_pair(q, r);
81}

下面 C++ 代码是用欧几里得算法（辗转相除法）求两个正整数的最大公约数，a 大于 b 还是小于 b 都适用。

01int gcd(int a, int b) {
02    while (b) {
03        int temp = b;
04        b = a % b;
05        a = temp;
06    }
07    return a;
08}

假设函数 gcd() 函数能正确求两个正整数的最大公约数，则下面的 lcm() 函数能求相应两数的最小公倍数。

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

下面的 C++ 代码用于输出每个数对应的质因数表，输出形如：{5: [5], 6: [2, 3], 7: [7], 8: [2, 2, 2]}。

01int main() {
02    int n, m;
03    cin >> n >> m;
04    if (n > m) swap(n, m);
05
06    map<int, vector<int>> prime_factor;
07
08    for (int i = n; i <= m; ++i) {
09        int j = 2, k = i;
10        while (k != 1) {
11            if (k % j == 0) {
12                prime_factor[i] = prime_factor[i] + j;
13                k /= j;
14            } else {
15                ++j;
16            }
17        }
18    }
19
20    for (auto& p : prime_factor) {
21        cout << p.first << ": ";
22        for (int v : p.second)
23            cout << v << " ";
24        cout << endl;
25    }
26
27    return 0;
28}

下面的 C++ 代码实现归并排序。代码在执行时，将输出一次 HERE 字符串，因为 merge() 函数仅被调用一次。

01void merge(std::vector<int>& arr, int left, int mid, int right) {
02    std::vector<int> temp(right - left + 1);
03
04    int i = left;
05    int j = mid + 1;
06    int k = 0;
07
08    while (i <= mid && j <= right) {
09        if (arr[i] <= arr[j]) {
10            temp[k++] = arr[i++];
11        } else {
12            temp[k++] = arr[j++];
13        }
14    }
15
16    while (i <= mid) {
17        temp[k++] = arr[i++];
18    }
19
20    while (j <= right) {
21        temp[k++] = arr[j++];
22    }
23
24    for (int p = 0; p < k; ++p) {
25        arr[left + p] = temp[p];
26    }
27}
28
29void mergeSort(std::vector<int>& arr, int left, int right) {
30    if (left >= right) {
31        return;
32    }
33
34    int mid = left + (right - left) / 2;
35
36    mergeSort(arr, left, mid);
37    mergeSort(arr, mid + 1, right);
38
39    std::cout << "HERE";
40    merge(arr, left, mid, right);
41}

归并排序的最好、最坏和平均时间复杂度均为 $O(n \log n)$。

查字典这个小学生必备技能，可以把字典视为一个已排序的数组。假设小杨要查找一个音首字母为 g 的单词，他首先翻到字典约一半的页数，发现该页的首字母是 m ，由于字母表中 g 位于 m 之前，所以排除字典后半部分，查找范围缩小到前半部分；不断重复上述步骤，直至找到首字母为 g 的页码。这种查字典的一系列操作可看作二分查找。

求解下图中 $A$ 点到 $D$ 点最短路径，其中 $A$ 到 $B$ 之间的 $12$ 可以理解为距离。求解这样的问题常用 Dijkstra 算法，其思路是通过逐步选择当前距离起点最近的节点来求解非负权重图（如距离不能为负值）单源最短路径的算法。从该算法的描述可以看出，Dijkstra 算法是贪心算法。

分治算法将原问题可以分解成规模更小的子问题，使得解决问题的难度降低。但由于分治算法需要将问题进行分解，并且需要将多个子问题的解合并为原问题的解，所以分治算法的效率通常比直接求解原问题的效率低。

函数 puzzle 定义如下，则调用 puzzle(7) 程序会无限递归。

01int puzzle(int n) {
02    if (n == 1) return 1;
03    if (n % 2 == 0) return puzzle(n / 2);
04    return puzzle(3 * n + 1);
05}

如下为线性筛法，用于高效生成素数表，其核心思想是每个合数只被它的最小质因数筛掉一次，时间复杂度为 $O(n)$。

01vector<int> linearSieve(int n) {
02    vector<bool> is_prime(n + 1, true);
03    vector<int> primes;
04
05    for (int i = 2; i <= n; ++i) {
06        if (is_prime[i]) {
07            primes.push_back(i);
08        }
09
10        for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
11            is_prime[i * primes[j]] = false;
12            if (i % primes[j] == 0) {
13                break;
14            }
15        }
16    }
17    return primes;
18}