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

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

1. 与数组相比，链表在（   ）操作上通常具有更高的效率。

{{ select(1) }}

• 随机访问元素
• 查找指定元素
• 在已知位置插入或删除节点
• 遍历所有元素

2. 下面C++代码实现双向链表。函数is_empty()判断链表是否为空，如链表为空返回true，否则返回false。横线处不能填写（  ）。

// 节点结构体
struct Node
{
    int data;
    Node *prev;
    Node *next;
};
// 双向链表结构体
struct DoubleLink
{
    Node *head;
    Node *tail;
    int size;
    DoubleLink()
    {
        head = nullptr;
        tail = nullptr;
        size = 0;
    }
    ~DoubleLink()
    {
        Node *curr = head;
        while (curr)
        {
            Node *next = curr->next;
            delete curr;
            curr = next;
        }
    }
    // 判断链表是否为空
    bool is_empty() const
    {
        _______________________
    }
};

{{ select(2) }}

• return head == nullptr;
• return tail == nullptr;
• return head.data == 0;
• return size == 0;

3. 基于上题代码正确的前提下，填入相应代码完善append()，用于在双向链表尾部增加新节点，横线上应填写（   ）。

void append(int data)
{
    Node *newNode = new Node{data, nullptr, nullptr};
    if (is_empty())
    {
        head = tail = newNode;
    }
    else
    {
        _______________________
    }
    ++size;
}

{{ select(3) }}

• tail->next = newNode;
• newNode->prev = tail;
tail = newNode;
• tail = newNode;
newNode->prev = tail;
tail->next = newNode;
• tail->next = newNode;
newNode->prev = tail;
tail = newNode;

4. 下列C++代码用循环链表解决约瑟夫问题，即假设n个人围成一圈，从第一个人开始数，每次数到第k 个的人就出圈，输出最后留下的那个人的编号。横线上应填写（   ）。

struct Node
{
    int data;
    Node *next;
};
Node *createCircularList(int n)
{
    Node *head = new Node{1, nullptr};
    Node *prev = head;
    for (int i = 2; i <= n; ++i)
    {
        Node *node = new Node{i, nullptr};
        prev->next = node;
        prev = node;
    }
    prev->next = head;
    return head;
}
int fingLastSurvival(int n, int k)
{
    Node *head = createCircularList(n);
    Node *p = head;
    Node *prev = nullptr;
    while (p->next != p)
    {
        for (int count = 1; count < k; ++count)
        {
            prev = p;
            p = p->next;
        }
        _______________________
    }
    cout << "最后留下的人编号是: " << p->data << endl;
    delete p;
    return 0;
}

{{ select(4) }}

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

5. 下列C++代码判断一个正整数是否是质数，说法正确的是(  )。

bool is_prime(int n)
{
    if (n <= 1)
        return false;
    if (n == 2 || n == 3 || n == 5)
        return true;
    if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0)
        return false;
    int i = 7;
    int step = 4;
    int finish_number = sqrt(n) + 1;
    while (i <= finish_number)
    {
        if (n % i == 0)
            return false;
        i += step;
        step = 6 - step;
    }
    return true;
}

{{ select(5) }}

• 代码存在错误，比如5是质数，但因为5 % 5余数是0返回了false
• finish_number的值应该是n / 2，当前写法将导致错误
• 当前while循环正确的前提是：所有大于3的质数都符合6k±1形式
• while循环修改如下，其执行效果和执行时间相同。
for (int i = 2; i < finish_number; i++)
{
if (n % i == 0)
return false;
}
return true;

6. 下列C++代码用两种方式求解两个正整数的最大公约数，说法错误的是(  )。

int gcd0(int big, int small)
{
    if (big < small)
    {
        swap(big, small);
    }
    if (big % small == 0)
    {
        return small;
    }
    return gcd0(small, big % small);
}
int gcd1(int big, int small)
{
    if (big < small)
    {
        swap(big, small);
    }
    for (int i = small; i >= 1; --i)
    {
        if (big % i == 0 && small % i == 0)
            return i;
    }
    return 1;
}

{{ select(6) }}

• gcd0()函数的时间复杂度为O(log n)
• gcd1()函数的时间复杂度为O(n)
• 一般说来，gcd0()的效率高于gcd1()
• gcd1()中的代码for (int i = small; i >= 1; --i)应该修改为for (int i = small; i > 1; --i)

7. 下面的代码用于判断整数 n 是否是质数，错误的说法是（ ）。

bool is_prime(int n)
{
    if (n <= 1)
        return false;
    int finish_number = static_cast<int>(sqrt(n)) + 1;
    for (int i = 2; i < finish_number; ++i)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

{{ select(7) }}

• 埃氏筛算法相对于上面的代码效率更高
• 线性筛算法相对于上面的代码效率更高
• 上面的代码有很多重复计算，因为不是判断单个数是否为质数，故而导致筛选出连续数中质数的效率不高
• 相对而言，埃氏筛算法比上面代码以及线性筛算法效率都高

8. 唯一分解定理描述了关于正整数的什么性质？

{{ select(8) }}

• 任何正整数都可以表示为两个素数的和。
• 任何大于1的合数都可以唯一分解为有限个质数的乘积。
• 两个正整数的最大公约数总是等于它们的最小公倍数除以它们的乘积。
• 所有素数都是奇数。

9. 下面的C++代码，用于求一系列数据中的最大值。有关其算法说法错误的是（    ）。

int find_max_recursive(const vector<int> &nums, int left, int right)
{
    if (left == right)
        return nums[left];
    int mid = left + (right - left) / 2;
    int left_max = find_max_recursive(nums, left, mid);
    int right_max = find_max_recursive(nums, mid + 1, right);
    return max(left_max, right_max);
}
int find_max(const vector<int> &nums)
{
    if (nums.empty())
    {
        throw invalid_argument("输入数组不能为空");
    }
    return find_max_recursive(nums, 0, nums.size() - 1);
}

{{ select(9) }}

• 该算法采用分治算法
• 该算法是递归实现
• 该算法采用贪心算法
• 该算法不是递推算法

10. 下面的C++代码，用于求一系列数据中的最大值。有关其算法说法错误的是（    ）。

int find_max(const vector<int> &nums)
{
    if (nums.empty())
    {
        throw invalid_argument("输入数组不能为空");
    }
    int max_value = nums[0];
    for (int num : nums)
    {
        if (num > max_value)
        {
            max_value = num;
        }
    }
    return max_value;
}

{{ select(10) }}

• 本题find_max()函数采用的是迭代算法
• 本题find_max()函数的时间复杂度为O(n)
• 本题find_max()函数没有使用递归，因此不会因为递归调用层数过多而导致栈溢出。
• 本题find_max()函数和上一题的find_max()空间复杂度相同

11. 下面的 C++ 代码用于在升序数组lst中查找目标值target最后一次出现的位置。相关说法，正确的是（    ）。

int binary_search_last_occurrence(const vector<int> &lst, int target)
{
    if (lst.empty())
        return -1;
    int low = 0, high = lst.size() - 1;
    while (low < high)
    {
        int mid = (low + high + 1) / 2;
        if (lst[mid] <= target)
        {
            low = mid;
        }
        else
        {
            high = mid - 1;
        }
    }
    if (lst[low] == target)
        return low;
    else
        return -1;
}

{{ select(11) }}

• 当lst中存在重复的target时，该函数总能返回最后一个target的位置，即便lst全由相同元素组成
• 当target小于lst中所有元素时，该函数会返回0
• 循环条件改为while (low <= high)程序执行效果相同，且能提高准确性
• 将代码中(low + high + 1) / 2修改为(low + high) / 2效果相同

12. 有关下面C++代码的说法，错误的是（    ）。

double sqrt_binary(long long n, double epsilon = 1e-10)
{
    if (n < 0)
    {
        throw invalid_argument("输入必须为非负整数");
    }
    if (n == 0 || n == 1)
        return n;
    // 阶段 1
    long long low = 1, high = n;
    long long k = 0;
    while (low <= high)
    {
        long long mid = (low + high) / 2;
        long long mid_sq = mid * mid;
        if (mid_sq == n)
        {
            return mid;
        }
        else if (mid_sq < n)
        {
            k = mid;
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    long long next_k = k + 1;
    if (next_k * next_k == n)
    {
        return next_k;
    }
    // 阶段 2
    double low_d = (double)k;
    double high_d = (double)(k + 1);
    double mid;
    while (high_d - low_d >= epsilon)
    {
        mid = (low_d + high_d) / 2;
        double mid_sq = mid * mid;
        if (mid_sq < n)
        {
            low_d = mid;
        }
        else
        {
            high_d = mid;
        }
    }
    double result = (low_d + high_d) / 2;
    long long check_int = (long long)(result + 0.5);
    if (check_int * check_int == n)
    {
        return check_int;
    }
    return result;
}

{{ select(12) }}

• “阶段1”的目标是寻找正整数n可能的正完全平方根
• “阶段2”的目标是如果正整数n没有正完全平方根，则在可能产生完全平方根附近寻找带小数点的平方根
• 代码check_int = (long long)(result + 0.5)是检查因浮点误差是否为正完全平方根
• 阶段2的二分法中 high_d - low_d >= epsilon 不能用于浮点数比较，会进入死循环

13. 硬币找零问题中要求找给客户最少的硬币。coins 存储可用硬币规格，单位为角，假设规格都小于10角，且一定有1角规格。amount为要找零的金额，约定必须为1角的整数倍。输出为每种规格及其数量，按规格从大到小输出，如果某种规格不必要，则输出为0。下面是其实现代码，相关说法正确的是（    ）。

const int MAX_COINS = 10;
int result[MAX_COINS] = {0}; // 假设最多10种面额
int find_coins(const vector<int> &coins, int amount)
{
    sort(coins.begin(), coins.end(), greater<int>());
    int n = coins.size();
    for (int i = 0; i < n; ++i)
    {
        int coin = coins[i];
        int num = amount / coin;
        result[i] = num;
        amount -= num * coin;
        if (amount == 0)
            break;
    }
    cout << "找零方案如下：" << endl;
    for (int i = 0; i < n; ++i)
    {
        cout << sorted_coins[i] << "角需要" << result[i] << "枚" << endl;
    }
    return 0;
}

{{ select(13) }}

• 上述代码采用贪心算法实现
• 针对本题具体要求，上述代码总能找到最优解
• 上述代码采用枚举算法
• 上述代码采用分治算法

14. 关于下述C++代码的快速排序算法，说法错误的是（   ）。

int randomPartition(std::vector<int> &arr, int low, int high)
{
    int random = low + rand() % (high - low + 1);
    std::swap(arr[random], arr[high]);
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++)
    {
        if (arr[j] <= pivot)
        {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}
void quickSort(std::vector<int> &arr, int low, int high)
{
    if (low < high)
    {
        int pi = randomPartition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

{{ select(14) }}

• 在randomPartition函数中，变量i的作用是记录大于基准值的元素的边界
• randomPartition函数随机选择基准值，可以避免输入数据特定模式导致的最坏情况下时间复杂度O(n²)
• 快速排序平均时间复杂度是O(n log n)
• 快速排序是稳定排序算法

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

const int MAXN = 1005; // 最大位数
struct BigInt
{
    int d[MAXN]; // 存储数字，d[0]是个位，d[1]是十位，...
    int len;
    // 数字长度
    BigInt()
    {
        memset(d, 0, sizeof(d));
        len = 0;
    }
};
// 比较两个高精度数的大小
int compare(BigInt a, BigInt b)
{
    if (a.len != b.len)
        return a.len > b.len ? 1 : -1;
    for (int i = a.len - 1; i >= 0; i--)
    {
        if (a.d[i] != b.d[i])
            return a.d[i] > b.d[i] ? 1 : -1;
    }
    return 0;
}
// 高精度减法
BigInt sub(BigInt a, BigInt b)
{
    BigInt c;
    for (int i = 0; i < a.len; i++)
    {
        c.d[i] += a.d[i] - b.d[i];
        if (c.d[i] < 0)
        {
            c.d[i] += 10;
            c.d[i + 1]--;
        }
    }
    c.len = a.len;
    while (c.len > 1 && c.d[c.len - 1] == 0)
        c.len--;
    return c;
}
// 高精度除法（a/b，返回商和余数）
pair<BigInt, BigInt> div(BigInt a, BigInt b)
{
    BigInt q, r; // q是商，r是余数
    if (compare(a, b) < 0)
    { // 如果a<b，商为0，余数为a
        q.len = 1;
        q.d[0] = 0;
        r = a;
        return make_pair(q, r);
    }
    // 初始化余数r为a的前b.len位
    r.len = b.len;
    for (int i = a.len - 1; i >= a.len - b.len; i--)
    {
        r.d[i - (a.len - b.len)] = a.d[i];
    }
    // 逐位计算商
    for (int i = a.len - b.len; i >= 0; i--)
    {
        // 把下一位加入余数
        if (r.len > 1 || r.d[0] != 0)
        {
            for (int j = r.len; j > 0; j--)
            {
                r.d[j] = r.d[j - 1];
            }
            _______________________
        }
        else
        {
            r.d[0] = a.d[i];
            r.len = 1;
        }
        // 计算当前位的商
        while (compare(r, b) >= 0)
        {
            r = sub(r, b);
            q.d[i]++;
        }
    }
    // 确定商的长度
    q.len = a.len - b.len + 1;
    while (q.len > 1 && q.d[q.len - 1] == 0)
        q.len--;
    // 处理余数前导零
    while (r.len > 1 && r.d[r.len - 1] == 0)
        r.len--;
    return make_pair(q, r);
}

{{ select(15) }}

• r.d[0] = a.d[i];
r.len++;
• r.d[i] = a.d[i];
r.len++;
• r.d[i] = a.d[i];
r.len = 1;
• r.d[0] = a.d[i];
r.len = 1;