GESP 五级 · 2024 真题

下面 C++ 代码用于求斐波那契数列，该数列第 $1$、$2$ 项为 $1$，以后各项均是前两项之和。函数 fibo() 属于（ ）。

01int fibo(int n) {
02    if (n <= 0)
03        return 0;
04    if (n == 1 || n == 2)
05        return 1;
06
07    int a = 1, b = 1, next;
08    for (int i = 3; i <= n; i++) {
09        next = a + b;
10        a = b;
11        b = next;
12    }
13    return next;
14}

下面 C++ 代码用于将输入金额换成最少币种组合方案，其实现算法是（ ）。

01#include <iostream>
02using namespace std;
03
04#define N_COINS 7
05int coins[N_COINS] = {100, 50, 20, 10, 5, 2, 1}; //货币面值，单位相同
06int coins_used[N_COINS];
07
08void find_coins(int money) {
09    for (int i = 0; i < N_COINS; i++) {
10        coins_used[i] = money / coins[i];
11        money = money % coins[i];
12    }
13    return;
14}
15int main() {
16    int money;
17    cin >> money;    //输入要换算的金额
18
19    find_coins(money);
20    for (int i = 0; i < N_COINS; i++)
21        cout << coins_used[i] << endl;
22
23    return 0;
24}

小杨采用如下双链表结构保存他喜欢的歌曲列表：

01struct dl_node {
02    string song;
03    dl_node* next;
04    dl_node* prev;
05};

小杨想在头指针为 head 的双链表中查找他喜欢的某首歌曲，采用如下查询函数，该操作的时间复杂度为（ ）。

01dl_node* search(dl_node* head, string my_song) {
02    dl_node* temp = head;
03    while (temp != nullptr) {
04        if (temp->song == my_song)
05            return temp;
06        temp = temp->next;
07    }
08    return nullptr;
09}

在双向链表头部插入一个新节点，为了保持链表结构正确，横线上应填入的代码为（ ）。

01void insert(dl_node *head, string my_song) {
02    p = new dl_node;
03    p->song = my_song;
04    p->prev = nullptr;
05    p->next = head;
06
07    if (head != nullptr) {
08        ____________ // 在此处填入代码
09    }
10    head = p;
11}

下面是根据欧几里得算法编写的函数，它计算的是 a 与 b 的（ ）。

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

欧几里得算法还可以写成如下形式：下面有关说法，错误的是（ ）。

01int gcd(int a, int b) {
02    return b == 0 ? a : gcd(b, a % b);
03}

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

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

线性筛法（欧拉筛）求小于等于 n 的所有素数，其时间复杂度是（ ）。

为了正确实现快速排序，下面横线上的代码应为（ ）。

01void qsort(vector<int>& arr, int left, int right) {
02    int i, j, mid;
03    int pivot;
04
05    i = left;
06    j = right;
07    mid = (left + right) / 2; // 计算中间元素的索引
08    pivot = arr[mid]; // 选择中间元素作为基准值
09
10    do {
11        while (arr[i] < pivot) i++;
12        while (arr[j] > pivot) j--;
13        if (i <= j) {
14            swap(arr[i], arr[j]); // 交换两个元素
15            i++; j--;
16        }
17    } ____________; // 在此处填入代码
18    if (left < j) qsort(arr, left, j); // 对左子数组进行快速排序
19    if (i < right) qsort(arr, i, right); // 对右子数组进行快速排序
20}

关于分治算法，以下哪个说法正确？

根据下述二分查找法，在排好序的数组 $1, 3, 6, 9, 17, 31, 39, 52, 61, 79, 81, 90, 96$ 中查找数值 $82$，和 $82$ 比较的数组元素分别是（ ）。

01int binary_search(vector<int>& nums, int target) {
02    int left = 0;
03    int right = nums.size() - 1;
04    while (left <= right) {
05        int mid = (left + right) / 2;
06        if (nums[mid] == target) {
07            return mid;
08        } else if (nums[mid] < target) {
09            left = mid + 1;
10        } else {
11            right = mid - 1;
12        }
13    }
14    return -1; // 如果找不到目标元素，返回-1
15}

要实现一个高精度减法函数，则下面代码中加划线应该填写的代码为（ ）。

01//假设a和b均为正数，且a表示的数比b大
02vector<int> minus(vector<int> a, vector<int> b) {
03    vector<int> c;
04    int len1 = a.size();
05    int len2 = b.size();
06    int i, t;
07
08    for (i = 0; i < len2; i++) {
09        if (a[i] < b[i]) {   //借位
10            ____________    // 在此处填入代码
11            a[i] += 10;
12        }
13        t = a[i] - b[i];
14        c.push_back(t);
15    }
16
17    for (; i < len1; i++)
18        c.push_back(a[i]);
19
20    len3 = c.size();
21    while (c[len3 - 1] == 0) {//去除前导0
22        c.pop_back();
23        len3--;
24    }
25    return c;
26}

设 A 和 B 是两个长度为 n 的有序数组，现将 A 和 B 合并成一个有序数组，归并排序算法在最坏情况下至少要做（ ）次比较。

给定如下函数：

01int fun(int n) {
02    if (n == 1) return 1;
03    if (n == 2) return 2;
04    return fun(n - 2) - fun(n - 1);
05}

则当 $n = 7$ 时，函数返回值为（ ）。

给定如下递归函数（含输出打印）：

01int fun(int n) {
02    cout << n << " ";
03    if (n == 1) return 1;
04    if (n == 2) return 2;
05    return fun(n - 2) + fun(n - 1);
06}

则当 $n = 4$ 时，屏幕上输出序列为（ ）。

如果将双向链表的最后一个结点的下一项指针指向第一个结点，第一个结点的前一项指针指向最后一个结点，则该双向链表构成循环链表。

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

链表的存储空间物理上可以连续，也可以不连续。

找出自然数 n 以内的所有质数，常用算法有埃拉托斯特尼（埃氏）筛法和线性筛法，其中埃氏筛法效率更高。

唯一分解定理表明任何一个大于 $1$ 的整数都可以唯一地表示为一系列质数的乘积，即质因数分解是唯一的。

贪心算法通过每一步选择局部最优解来获得全局最优解，但并不一定能找到最优解。

归并排序和快速排序都采用递归实现，也都是不稳定排序。

插入排序有时比快速排序时间复杂度更低。

在进行全国人口普查时，将其分解为对每个省市县乡来进行普查和统计。这是典型的分治策略。

在下面 C++ 代码中，由于删除了变量 ptr，因此 ptr 所对应的数据也随之删除，故执行下述代码时，将报错。

01int* ptr = new int(10);
02cout << *ptr << endl;
03delete ptr;
04cout << ptr << endl;