GESP 2024年12月认证 C++ 5级真题

一、单选题（每题2分，共30分）

第1题

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

• A. 当数据数量不确定时，为了应对各种可能的情况，需要申请一个较大的数组，可能浪费空间；此时用链表比较合适，大小可动态调整。
• B. 在链表中访问节点的效率较低，时间复杂度为O(n)。

• C. 链表插入和删除元素效率较低，时间复杂度为O(n)。

• D. 链表的节点在内存中是分散存储的，通过指针连在一起。

第2题

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

• A. 当前节点

• B. nullptr

• C. 第一个节点

• D. 上一个节点

第3题

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

1 struct LinkedNode {  
2     int val;  
3     LinkedNode* next;  
4     LinkedNode(int val) : val(val), next(nullptr) {}  
5 };  
6  
7 void removeElements(LinkedNode* head, int val) {  
8     if (head == nullptr) {  
9         return;  
10     }  
11     LinkedNode* cur;  
12     LinkedNode* dummyHead = new LinkedNode(0); // 虚拟头节点  
13     // 在此处填入代码  
14  
15     while (cur->next != nullptr) {  
16         if (cur->next->val == val) {  
17             LinkedNode* tmp = cur->next;  
18             cur->next = cur->next->next;  
19             delete tmp;  
20             tmp = nullptr;  
21         } else {  
22             cur = cur->next;  
23         }  
24     }  
25     head = dummyHead->next;  
26     delete dummyHead;  
27     dummyHead = nullptr;  
28 }  

• A. dummyHead->next = head; cur = dummyHead;

• B. dummyHead->next = head->next; cur = dummyHead;

• C. dummyHead->next = head; cur = dummyHead->next;

• D. dummyHead->next = head->next; cur = dummyHead->next;

第4题

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

1 int fibA(int n) {  
2     if (n <= 1)  
3         return n;  
4     int f1 = 0, f2 = 1;  
5     for (int i = 2; i <= n; ++i) {  
6         int temp = f2;  
7         f2 = f1 + f2;  
8         f1 = temp;  
9     }  
10     return f2;  
11 }  
12  
13 int fibB(int n) {  
14     if (n <= 1)  
15         return n;  
16     return fibB(n - 1) + fibB(n - 2);  
17 }  

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

• B. fibA采用递推方式。

• C. fibB采用的是递归方式。

• D. fibA时间复杂度为O(n)，fibB的时间复杂度为O(n²)。

第5题

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

1 int gcd(int a, int b) {  
2     int big = a > b ? a : b;  
3     int small = a < b ? a : b;  
4     if (big % small == 0) {  
5         return small;  
6     }  
7     return gcd(small, big % small);  
8 }  

• A. gcd(24, 36)、gcd(24, 12)、gcd(12, 0)
• B. gcd(24, 36)、gcd(12, 24)、gcd(0, 12)
• C. gcd(24, 36)、gcd(24, 12)
• D. gcd(24, 36)、gcd(12, 24)

第6题

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

void primeFactors(int n) {  
    while (n % 2 == 0) {  
        cout << 2 << " ";  
        n /= 2;  
    }  
    // 在此处填入代码  
    for (int i = 3; ... ; ... ) {  
        while (n % i == 0) {  
            cout << i << " ";  
            n /= i;  
        }  
    }  
    if (n > 2)  
        cout << n << " ";  
}  

• A. for (int i = 3; i <= n; i++)

• B. for (int i = 3; i * i <= n; i++)

• C. for (int i = 3; i <= n; i += 2)

• D. for (int i = 3; i * i <= n; i += 2)

第7题

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

vector<bool> sieve_Eratosthenes(int n) {  
    vector<bool> isPrime(n + 1, true);  
    isPrime[0] = isPrime[1] = false;  
    for (int i = 2; i * i <= n; ++i) {  
        if (isPrime[i]) {  
            for (int j = i * i; j <= n; j += i) {  
                isPrime[j] = false;  
            }  
        }  
    }  
    return isPrime;  
}  

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

• A. 代码的时间复杂度是 ( O(n\sqrt{n}) )。

• B. 在标记非素数时，代码从 ( i^2 ) 开始，可以减少重复标记。

• C. 代码会输出所有小于等于n的奇数。

• D. 调用函数 sieve_Eratosthenes(10)，函数返回值的数组中包含的元素有：2, 3, 5, 7, 9。

第8题

下述代码实现素数表的线性筛法，筛选出所有小于等于n的素数。

vector<int> linearSieve(int n) {  
    vector<int> primes;  
    vector<bool> isComposite(n + 1, false);  
    for (int i = 2; i <= n; ++i) {  
        if (!isComposite[i]) {  
            primes.push_back(i);  
        }  
        for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {  
            isComposite[i * primes[j]] = true;  
            if (i % primes[j] == 0) {  
                break;  
            }  
        }  
    }  
    return primes;  
}  

下面说法正确的是（）。

• A. 线性筛的时间复杂度是O(n)。

• B. 每个合数会被其所有的质因子标记一次。

• C. 线性筛和埃拉托色尼筛的实现思路完全相同。

• D. 以上都不对。

第9题

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

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

• A. 快速排序通过递归对子问题进行求解。

• B. 快速排序的最坏时间复杂度是O(n log n)。

• C. 快速排序是一个稳定的排序算法。

• D. 在最优情况下，快速排序的时间复杂度是O(n)。

第10题

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

• A. 归并排序是一个不稳定的排序算法。

• B. 归并排序的时间复杂度在最优、最差和平均情况下都是 ( O(n \log n) )。

• C. 归并排序需要额外的O(1)空间。

• D. 对于输入数组{12,11,13,5,6,7}，代码输出结果为：7 6 5 13 12 11。

第11题

给定一个长度为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);  
}  

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

• A. 函数采用二分查找，每次计算搜索当前搜索区间的中点，然后根据中点的元素值排除一半搜索区间。

• B. 函数采用递归求解，每次问题的规模减小一半。

• C. 递归的终止条件是中间元素的值等于target，若数组中不包含该元素，递归不会终止。

• D. 算法的复杂度为O(log n)。

第12题

给定一个长度为n的有序数组nums，其中可能包含重复元素。下面的函数返回数组中某个元素target的左边界，若数组中不包含该元素，则返回-1。例如在数组nums = [5,7,7,8,8,10]中查找target = 8，函数返回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;  
}  

• A. right = middle - 1;

• B. right = middle;

• C. right = middle + 1;

• D. 以上都不对。

第13题

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

int cookieForChildren(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;  
}  

• A. result++; index--;

• B. result--; index--;

• C. result--; index++;

• D. result++; index++;

第14题

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

• A. 分治算法将问题分成子问题，然后分别解决子问题，最后合并结果。

• B. 归并排序采用了分治思想。

• C. 快速排序采用了分治思想。

• D. 冒泡排序采用了分治思想。

第15题

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

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

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

• A. 如果数组a表示的整数小于b表示的整数，代码会正确返回二者的差为负数。

• B. 代码假设输入数字是以倒序存储的，例如500存储为{0, 0, 5}。

• C. 代码的时间复杂度为O(a.size() + b.size())。

• D. 当减法结果为0时，结果数组仍然会存储很多个元素0。

二、判断题（每题2分，共20分）

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

   • □ 正确

   • □ 错误

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

   • □ 正确
   • □ 错误

3. 任何一个大于1的自然数都可以分解成若干个不同的质数的乘积，且分解方式是唯一的。
   • □ 正确
   • □ 错误

4. 贪心算法通过每一步选择当前最优解，从而一定能获得全局最优解。
   • □ 正确
   • □ 错误

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

6. 快速排序和归并排序的平均时间复杂度均为 ( O(n \log n) )，且都是稳定排序。
   • □ 正确
   • □ 错误

7. 快速排序的时间复杂度总比插入排序的时间复杂度低。
   • □ 正确
   • □ 错误

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

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

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

3 编程题（每题25分，共50分）

3.1 编程题1：奇妙数字

试题名称：奇妙数字
时间限制：1.0 s
内存限制：512.0 MB

题面描述
小杨认为一个数字 ( x ) 是奇妙数字当且仅当 ( x = p^a )，其中 ( p ) 为任意数且 ( a ) 为正整数。例如，8 = 2(^3)，所以8是奇妙数字，而6不是。

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

1. 集合中不包含相同的数字。
2. ( x_1 \times x_2 \times \ldots \times x_m ) 是 ( n ) 的因子。

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

输入格式
第一行包含一个正整数 ( n )。

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

样例
输入：

128  

输出：

3  

样例解释
符合题意的一个包含3个奇妙数字的集合是 {2, 4, 8}。其乘积为64，是128的因子。

参考程序

#include <bits/stdc++.h>  
using namespace std;  
#define ll long long  
const int N = 1e5+10;  

ll calc(ll x) {  
    int ans = 0;  
    ll tmp = 1;  
    while (x >= tmp) {  
        ans++;  
        x -= tmp;  
        tmp++;  
    }  
    return ans;  
}  

int main() {  
    ll n;  
    cin >> n;  
    ll ans = 0;  
    for (ll i = 2; i * i <= n; i++) {  
        if (n % i == 0) {  
            int cnt = 0;  
            while (n % i == 0) {  
                cnt++;  
                n /= i;  
            }  
            ans += calc(cnt);  
        }  
    }  
    if (n != 1) {  
        ans += calc(1);  
    }  
    cout << ans << "\n";  
}  

3.2 编程题2：武器强化

试题名称：武器强化
时间限制：1.0 s
内存限制：512.0 MB

题面描述
小杨有 ( n ) 种武器和 ( m ) 种强化材料。第 ( i ) 种强化材料会适配第 ( p_i ) 种武器，小杨可以花费 ( c_i ) 金币将该材料对应的适配武器修改为任意武器。

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

输入格式
第一行包含两个正整数 ( n, m )。
之后 ( m ) 行，每行包含两个正整数 ( p_i, c_i )，表示第 ( i ) 种材料的适配武器和修改花费。

输出格式
输出一个整数，表示最少需要的金币。

样例
输入：

3 3  
1 5  
2 3  
3 1  

输出：

1  

样例解释
将第三种材料的适配武器从3改为1后，武器1有2种适配材料，武器2和3各有1种，满足条件。

参考程序

#include <bits/stdc++.h>  
using namespace std;  
#define ll long long  
int n, m;  
int cnt[1010];  
vector<int> cs[1010];  

ll calc(int aim) {  
    int cur_cnt = cnt[1];  
    ll res = 0;  
    vector<int> tmp;  
    for (int i = 2; i <= n; i++) {  
        int buy = max((int)cs[i].size() - aim + 1, 0);  
        for (int j = 0; j < buy; j++) {  
            res += cs[i][j];  
        }  
        cur_cnt += buy;  
        for (int j = buy; j < cs[i].size(); j++) {  
            tmp.push_back(cs[i][j]);  
        }  
    }  
    sort(tmp.begin(), tmp.end());  
    for (int i = 0; i < aim - cur_cnt; i++) {  
        res += tmp[i];  
    }  
    return res;  
}  

signed main() {  
    cin >> n >> m;  
    for (int i = 1; i <= m; i++) {  
        int p, c;  
        cin >> p >> c;  
        cnt[p]++;  
        cs[p].push_back(c);  
    }  
    for (int i = 1; i <= n; i++) {  
        sort(cs[i].begin(), cs[i].end());  
    }  
    ll ans = 1e18;  
    for (int i = max(cnt[1], 1); i <= m; i++) {  
        ans = min(ans, calc(i));  
    }  
    cout << ans << "\n";  
}