2025年3月GESP 5级C++真题_含答案与解析

一单选题

共 15 道每题 2 分共计 30 分

第 1 题

链表不具备的特点是（）。

A

可随机访问任何一个元素

B

插入、删除操作不需要移动元素

C

无需事先估计存储空间大小

D

所需存储空间与存储元素个数成正比

第 2 题

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

A

p->next->prev = p->next;
p->prev->next = p->prev;
delete p;

B

p->prev->next = p->next;
p->next->prev = p->prev;
delete p;

C

p->next->prev = p->prev;
p->next->prev->next = p->next;
delete p;

D

p->prev->next = p->next;
p->prev->next->prev = p->prev;
delete p;

第 3 题

假设双向循环链表包含头尾哨兵结点（不存储实际内容），分别为 head 和 tail，链表中每个结点有两个指针域 prev 和 next，分别指向该结点的前驱及后继结点。下面代码实现了一个空的双向循环链表，横线上应填的最佳代码是（）。

// 链表结点
template <typename T>
struct ListNode {
    T data;
    ListNode<T>* prev;
    ListNode<T>* 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>();     
    // 在此处填入代码
}

A

list->head->prev = list->head;
list->tail->prev = list->head;

B

list->head->next = list->tail;
list->tail->prev = list->head;

C

list->head->next = list->tail;
list->tail->next = list->head;

D

list->head->next = list->tail;
list->tail->next = nullptr;

第 4 题

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

A

84 和 60

B

60 和 24

C

24 和 12

D

12 和 0

第 5 题

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

A

$18 = 3 \times 6$

B

$28 = 4 \times 7$

C

$36 = 2 \times 3 \times 6$

D

$30 = 2 \times 3 \times 5$

第 6 题

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

A

j < primes.size()

B

i * primes[j] <= n

C

j < primes.size() && i * primes[j] <= n

D

j <= n

第 7 题

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

A

系统分配的栈空间溢出

B

系统分配的堆空间溢出

C

系统分配的队列空间溢出

D

系统分配的链表空间溢出

第 8 题

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

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

A

两个函数的实现的功能相同。

B

两个函数的时间复杂度均为 $O(n)$。

C

factorialA 采用递归方式。

D

factorialB 采用递归方式。

第 9 题

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

A

选择排序

B

插入排序

C

归并排序

D

冒泡排序

第 10 题

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

A

if (arr[j] > pivot) {
    i++;
    swap(arr[i], arr[j]);
}

B

if (arr[j] < pivot) {
    i++;
    swap(arr[i], arr[j]);
}

C

if (arr[j] < pivot) {
    swap(arr[i], arr[j]);
    i++;
}

D

if (arr[j] == pivot) {
    i++;
    swap(arr[i], arr[j]);
}

第 11 题

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

A

100

B

10

C

7

D

5

第 12 题

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

A

int mid = left + (right - left) / 2;

B

int mid = left;

C

int mid = (left + right) / 2;

D

int mid = right;

第 13 题

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

A

总是选择当前最优解

B

回溯尝试所有可能

C

分阶段解决子问题

D

总能找到最优解

第 14 题

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

A

if (low == high)
    return arr[low];
int mid = (low + high) / 2;
return arr[mid];

B

if (low >= high)
    return arr[low];
int mid = (low + high) / 2;
int leftMax = findMax(arr, low, mid - 1);
int rightMax = findMax(arr, mid, high);
return leftMax + rightMax;

C

if (low > high)
    return 0;
int mid = low + (high - low) / 2;
int leftMax = findMax(arr, low, mid);
int rightMax = findMax(arr, mid + 1, high);
return leftMax * rightMax;

D

if (low == high)
    return arr[low];
int mid = low + (high - low) / 2;
int leftMax = findMax(arr, low, mid);
int rightMax = findMax(arr, mid + 1, high);
return (leftMax > rightMax) ? leftMax : rightMax;

第 15 题

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

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

A

int temp = c[k];

B

int temp = c[k] + carry;

C

int temp = c[k] - carry;

D

int temp = c[k] * carry;

CCF GESP 2025年3月认证 C++ 5级