GESP C++ 五 级 2024年6月真题（180 分钟，总分 100 分）

单选题（共 15 题，每题 2 分，共 30 分）

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

int fibo(int n)
{
    if (n <= 0)
        return 0;
    if (n == 1 || n == 2)
        return 1;
    int a = 1，b = 1, next;
    for (int i = 3; i <= n; i++)
    {
        next = a + b;
        a = b;
        b = next;
    }
    return next;
}

{{ select(1) }}

• 枚举算法
• 贪心算法
• 迭代算法
• 递归算法

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

#include <iostream>
using namespace std;
#define N_COINS 7
int coins[N_COINS] = {100, 50, 20, 10, 5, 2, 1}; // 货币面值，单位相同
int coins_used[N_COINS];
void find_coins(int money)
{
    for (int i = 0; i < N_COINS; i++)
    {
        coins_used[i] = money / coins[i];
        money = money % coins[i];
    }
    return;
}
int main()
{
    int money;
    cin >> money;
    // 输入要换算的金额
    find_coins(money);
    for (int i = 0; i < N_COINS; i++)
        cout << coins_used[i] << endl;
    return 0;
}

{{ select(2) }}

• 枚举算法
• 贪心算法
• 迭代算法
• 递归算法

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

struct dl_node
{
    string song;
    dl_node *next;
    dl_node *prev;
};

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

dl_node *search(dl_node *head, string my_song)
{
    dl_node *temp = head;
    while (temp != nullptr)
    {
        if (temp->song == my_song)
            return temp;
        temp = temp->next;
    }
    return nullptr;
}

{{ select(3) }}

• O(1)
• O(n)
• O(log n)
• O(n²)

4. 小杨想在如上题所述的双向链表中加入一首新歌曲。为了能快速找到该歌曲，他将其作为链表的第一首歌曲，则下面横线上应填入的代码为（  ）。

void insert(dl_node *head, string my_song)
{
    p = new dl_node;
    p->song = my_song;
    p->prev = nullptr;
    p->next = head;
    if (head != nullptr)
    {
        ________________________________ // 在此处填入代码
    }
    head = p;
}

{{ select(4) }}

• head->next->prev = p;
• head->next = p;
• head->prev = p;
• 触发异常，不能对空指针进行操作。

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

int gcd(int a, int b)
{
    while (b != 0)
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

{{ select(5) }}

• 最小公倍数
• 最大公共质因子
• 最大公约数
• 最小公共质因子

6. 欧几里得算法还可以写成如下形式:

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

下面有关说法，错误的是（  ）。

{{ select(6) }}

• 本题的gcd()实现为递归方式。
• 本题的gcd()代码量少，更容易理解其辗转相除的思想。
• 当 a 较大时，本题的gcd()实现会多次调用自身，需要较多额外的辅助空间。
• 当 a 较大时，相比上题中的gcd()的实现，本题的gcd()执行效率更高。

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

vector<int> linear_sieve(int n)
{
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;
    is_prime[0] = is_prime[1] = 0; // 0和1两个数特殊处理
    for (int i = 2; i <= n; ++i)
    {
        if (is_prime[i])
        {
            primes.push_back(i);
        }
        ________________________________
        {
            // 在此处填入代码
            is_prime[i * primes[j]] = 0;
            if (i % primes[j] == 0)
                break;
        }
    }
    return primes;
}

{{ select(7) }}

• for (int j = 0;  j < primes.size() && i * primes[j] <= n;  j++)
• for (int j = 0;  j <= sqrt(n) && i * primes[j] <= n;  j++)
• for (int j = 0;  j <= n;  j++)
• for (int j = 1;  j <= sqrt(n);  j++)

8. 上题代码的时间复杂度是（  ）。

{{ select(8) }}

• O( n² )
• O(n log n)
• O(n log log n)
• O(n)

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

void qsort(vector<int> &arr, int left, int right)
{
    int i, j, mid;
    int pivot;
    i = left;
    j = right;
    mid = (left + right) / 2; // 计算中间元素的索引
    pivot = arr[mid];         // 选择中间元素作为基准值
    do
    {
        while (arr[i] < pivot)
            i++;
        while (arr[j] > pivot)
            j--;
        if (i <= j)
        {
            swap(arr[i], arr[j]); // 交换两个元素
            i++;
            j--;
        }
    }
    ________________________________; // 在此处填入代码
    if (left < j)
        qsort(arr, left, j);
    // 对左子数组进行快速排序
    if (i < right)
        qsort(arr, i, right); // 对右子数组进行快速排序
}

{{ select(9) }}

• while (i <= mid)
• while (i < mid)
• while (i < j)
• while (i <= j)

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

{{ select(10) }}

• 分治算法将问题分成子问题，然后分别解决子问题，最后合并结果。
• 归并排序不是分治算法的应用。
• 分治算法通常用于解决小规模问题。
• 分治算法的时间复杂度总是优于 O(n log(n))。

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

int binary_search(vector<int> &nums, int target)
{
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (nums[mid] == target)
        {
            return mid;
        }
        else if (nums[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    return -1; // 如果找不到目标元素，返回-1
}

{{ select(11) }}

• 52, 61, 81, 90
• 52, 79, 90, 81
• 39, 79, 90, 81
• 39, 79, 90

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

// 假设a和b均为正数，且a表示的数比b大
vector<int> minus(vector<int> a, vector<int> b)
{
    vector<int> c； int len1 = a.size();
    int len2 = b.size();
    int i, t;
    for (i = 0; i < len2; i++)
    {
        if (a[i] < b[i])
        { // 借位
            _____________
            // 在此处填入代码
            a[i] += 10;
        }
        t = a[i] - b[i];
        c.push_back(t);
    }
    for (; i < len1; i++)
        c.push_back(a[i]);
    len3 = c.size();
    while (c[len3 - 1] == 0)
    { // 去除前导0
        c.pop_back();
        len3--;
    }
    return c;
}

{{ select(12) }}

• a[i + 1]--;
• a[i]--;
• b[i + 1]--;
• b[i]--;

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

{{ select(13) }}

• n²
• n log n
• 2n-1
• n

14. 给定如下函数：

int fun(int n)
{
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;
    return fun(n - 2) - fun(n - 1);
}

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

{{ select(14) }}

• 0
• 1
• 21
• -11

15. 给定如下函数（函数功能同上题，增加输出打印）：

int fun(int n)
{
    cout << n << " ";
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;
    return fun(n - 2) - fun(n - 1);
}

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

{{ select(15) }}

• 4 3 2 1
• 1 2 3 4
• 4 2 3 1 2
• 4 2 3 2 1