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

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

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

{{ select(1) }}

• 数组大小固定，链表大小可动态调整。
• 数组支持随机访问，链表只能顺序访问。
• 存储相同数目的整数，数组比链表所需的内存多。
• 数组插入和删除元素效率低，链表插入和删除元素效率高。

2. 通过（  ）操作，能完成在双向循环链表结点p之后插入结点s的功能（其中next域为结点的直接后继，prev域为结点的直接前驱）。

{{ select(2) }}

• p->next->prev = s; s->prev = p; p->next = s; s->next = p->next;
• p->next->prev = s; p->next = s; s->prev = p; s->next = p->next;
• s->prev = p; s->next = p->next; p->next = s; p->next->prev = s;
• s->next = p->next; p->next->prev = s; s->prev = p; p->next = s;

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

int sumA(int n)
{
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        res += i;
    }
    return res;
}
int sumB(int n)
{
    if (n == 1)
        return 1;
    int res = n + sumB(n - 1);
    return res;
}

{{ select(3) }}

• sumA体现了迭代的思想。
• SumB采用的是递归方式。
• SumB函数比SumA的时间效率更高。
• 两个函数的实现的功能相同。

4. 有如下函数fun，则fun(20, 12)的返回值为（ ）。

int fun(int a, int b)
{
    if (a % b == 0)
        return b;
    else
        return fun(b, a % b);
}

{{ select(4) }}

• 20
• 12
• 4
• 2

5. 下述代码实现素数表的埃拉托斯特尼筛法，筛选出所有小于等于n的素数，则横线上应填的最佳代码是( )。

void sieve_Eratosthenes(int n)
{
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;
    for (int i = 2; i * i <= n; i++)
    {
        if (is_prime[i])
        {
            primes.push_back(i);
            ________________________________
            {
                // 在此处填入代码
                is_prime[j] = false;
            }
        }
    }
    for (int i = sqrt(n) + 1; i <= n; i++)
    {
        if (is_prime[i])
        {
            primes.push_back(i);
        }
    }
    return primes;
}

{{ select(5) }}

• for (int j = i; j <= n; j++)
• for (int j = i * i; j <= n; j++)
• for (int j = i * i; j <= n; j += i)
• for (int j = i; j <= n; j += i)

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

vector<int> sieve_linear(int n)
{
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;
    for (int i = 2; i <= n / 2; i++)
    {
        if (is_prime[i])
            primes.push_back(i);
        ________________________________
        {
            // 在此处填入代码
            is_prime[i * primes[j]] = 0;
            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;
}

{{ select(6) }}

• for (int j = 0; j < primes.size() && i * primes[j] <= n; j++)
• for (int j = 1; j < primes.size() && i * j <= n; j++)
• for (int j = 2; j < primes.size() && i * primes[j] <= n; j++)
• 以上都不对

7. 下面函数可以将n的所有质因数找出来，其时间复杂度是（    ）。

#include <iostream>
#include <vector>
vector<int> get_prime_factors(int n)
{
    vector<int> factors;
    while (n % 2 == 0)
    {
        factors.push_back(2);
        n /= 2;
    }
    for (int i = 3; i * i <= n; i += 2)
    {
        while (n % i == 0)
        {
            factors.push_back(i);
            n /= i;
        }
    }
    if (n > 2)
    {
        factors.push_back(n);
    }
    return factors;
}

{{ select(7) }}

• O(n²)
• O(n log n)
• $O(\sqrt(n) log n)$
• O(n)

8. 现在用如下代码来计算xⁿ（n个x相乘），其时间复杂度为（ ）。

double quick_power(double x, unsigned n)
{
    if (n == 0)
        return 1;
    if (n == 1)
        return x;
    return quick_power(x, n / 2) * quick_power(x, n / 2) * ((n & 1) ? x : 1);
}

{{ select(8) }}

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

9. 假设快速排序算法的输入是一个长度为n的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。下面选项（ ）描述的是在这种情况下的快速排序行为。

{{ select(9) }}

• 快速排序对于此类输入的表现最好，因为数组已经排序。
• 快速排序对于此类输入的时间复杂度是O(n log n)。
• 快速排序对于此类输入的时间复杂度是O(n²)。
• 快速排序无法对此类数组进行排序，因为数组已经排序。

10. 考虑以下C++代码实现的归并排序算法：

void merge(int arr[], int left, int mid, int right)
{
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}
void merge_sort(int arr[], int left, int right)
{
    if (left < right)
    {
        int mid = left + (right - left) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

对长度为n的数组arr，调用函数merge_sort(a, 0, n-1)，在排序过程中merge函数的递归调用次数大约是（  ）。

{{ select(10) }}

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

11. 现在有n个人要过河，每只船最多载2人，船的承重为100kg。下列代码中，数组weight中保存有n个人的体重（单位为kg），已经按从小到大排好序，代码输出过河所需要的船的数目，采用的思想为（  ）。

int i, j;
int count = 0;
for (i = 0, j = n - 1; i < j; j--)
{
    if (weight[i] + weight[j] <= 100)
    {
        i++;
    }
    count++;
}
printf("过河的船数：%d\n", count);

{{ select(11) }}

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

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

{{ select(12) }}

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

13. 根据下述二分查找法，在排好序的数组1，3，6，9，17，31，39，52，61，79中查找数值31，循环while (left <= right)执行的次数为（  ）。

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

{{ select(13) }}

• 1
• 2
• 3
• 4

14. 以下关于高精度运算的说法错误的是( )。

{{ select(14) }}

• 高精度计算主要是用来处理大整数或需要保留多位小数的运算。
• 大整数除以小整数的处理的步骤可以是，将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商。
• 高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关。
• 高精度加法运算的关键在于逐位相加并处理进位。

15. 当n=7 时，下面函数的返回值为（  ）。

int fun(int n)
{
    if (n == 1)
        return 1;
    else if (n >= 5)
        return n * fun(n - 2);
    else
        return n * fun(n - 1);
}

{{ select(15) }}

• 105
• 840
• 210
• 420