2024年3月 GESP C++ 5级

唯一分解定理描述的内容是（ ）？

贪心算法的核心思想是（ ）？

下面的 C++ 代码片段用于计算阶乘。请在横线处填入（ ），实现正确的阶乘计算。

int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        _________________________________ // 在此处填入代码
    }
}

下面的代码片段用于在双向链表中删除一个节点。请在横线处填入（ ），使其能正确实现相应功能。

void deleteNode(DoublyListNode*& head, int value) {
    DoublyListNode* current = head;
    while (current != nullptr && current->val != value) {
        current = current->next;
    }
    if (current != nullptr) {
        if (current->prev != nullptr) {
            ____________________________________ // 在此处填入代码
        } else {
            head = current->next;
        }
        if (current->next != nullptr) {
            current->next->prev = current->prev;
        }
        delete current;
    }
}

辗转相除法也被称为（ ）

下面的代码片段用于计算斐波那契数列。该代码的时间复杂度是（ ）？

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

下面的代码片段用于将两个高精度整数进行相加。请在横线处填入（ ），使其能正确实现相应功能。

string add(string num1, string num2) {
    string result;
    int carry = 0;
    int i = num1.size() - 1, j = num2.size() - 1;
    while (i >= 0 || j >= 0 || carry) {
        int x = (i >= 0) ? num1[i--] - '0' : 0;
        int y = (j >= 0) ? num2[j--] - '0' : 0;
        int sum = x + y + carry;
        carry = sum / 10;
        _______________________________________
    }
    return result;
}

给定序列：$1$，$3$，$6$，$9$，$17$，$31$，$39$，$52$，$61$，$79$，$81$，$90$，$96$。使用以下代码进行二分查找查找元素 $82$ 时，需要循环多少次，即最后输出的 times 值为（ ）。

int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    int times = 0;
    while (left <= right) {
        times++;
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            cout << times << endl;
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    cout << times << endl;
    return -1;
}

下面的代码片段用于判断一个正整数是否为素数。请对以下代码进行修改，使其能正确实现相应功能。（ ）

bool isPrime(int num) {
    if (num < 2) {
        return false;
    }
    for (int i = 2; i * i < num; ++i) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

在埃拉托斯特尼筛法中，要筛选出不大于 $n$ 的所有素数，最外层循环应该遍历什么范围（ ）？

vector<int> sieveOfEratosthenes(int n) {
    std::vector<bool> isPrime(n + 1, true);
    std::vector<int> primes;
    _______________________ {
        if (isPrime[i]) {
            primes.push_back(i);
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    for (int i = sqrt(n) + 1; i <= n; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

素数的线性筛法时间复杂度为（ ）。

归并排序的基本思想是（ ）。

在快速排序中，选择的主元素（pivot）会影响算法的（ ）。

递归函数在调用自身时，必须满足（ ），以避免无限递归？

假设给定链表为: ，若调用 searchValue(head, 5)，函数返回值为（ ）。

int searchValue(ListNode* head, int target) {
    while (head != nullptr) {
        if (head->val == target) {
            return 1;
        }
        head = head->next;
    }
    return 0;
}

辗转相除法用于求两个整数的最大公约数。

插入排序的时间复杂度是 O(n2)O(n^2)O(n2)。

二分查找要求被搜索的序列是有序的，否则无法保证正确性。

使用贪心算法解决问题时，每一步的局部最优解一定会导致全局最优解。

分治算法的核心思想是将一个大问题分解成多个相同或相似的子问题进行解决，最后合并得到原问题的解。

分治算法的典型应用之一是归并排序，其时间复杂度为 $O(n\log n)$。

素数表的埃氏筛法和线性筛法的时间复杂度都是 $O(n)$。

贪心算法是一种可以应用于所有问题的通用解决方案。

单链表和双链表都可以在常数时间内实现在链表头部插入或删除节点的操作。

在 C 语言中，递归的实现方式通常会占用更多的栈空间，可能导致栈溢出。

试题名称：成绩排序

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

有 $n$ 名同学，每名同学有语文、数学、英语三科成绩，你需要按照如下规则对所有同学的成绩从高到低排序：

1. 比较总分，高者靠前；
2. 如果总分相同，则比较语文和数学两科的总分，高者靠前；
3. 如果仍相同，则比较语文和数学两科的最高分，高者靠前；
4. 如果仍相同，则二人并列。

你需要输出每位同学的排名，如遇 $x$ 人并列，则他们排名相同，并留空后面的 $x-1$ 个名次。例如，有 $3$ 名同学并列第 $1$，则后一名同学自动成为第 $4$ 名。

输入格式

第一行一个整数 $N$，表示同学的人数。
接下来 $N$ 行，每行三个非负整数 ci,mi,eic_i, m_i, e_ici​,mi​,ei​ 分别表示该名同学的语文、数学、英语成绩。

输出格式

输出 $N$ 行，按输入同学的顺序，输出他们的排名。
注意：请不要按排名输出同学的序号，而是按同学的顺序输出他们各自的排名。

样例输入 #1

6
140 140 150
140 149 140
148 141 140
141 148 140
145 145 139
0 0 0

样例输出 #1

1
3
4
4
2
6

说明/提示

• 对 $30\%$ 的数据，$N\le 100$，且所有同学总分各不相同。
• 对全部的测试数据，保证 2≤N≤1042 \leq N \leq 10^42≤N≤104，0≤ci,mi,ei≤1500 \leq c_i, m_i, e_i \leq 1500≤ci​,mi​,ei​≤150。

试题名称：B-smooth 数

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

小杨同学想寻找一种名为 $B$-smooth 数的正整数。

如果一个正整数的最大质因子不超过 $B$，则该正整数为 $B$-smooth 数。小杨同学想知道，对于给定的 $n$ 和 $B$，有多少个不超过 $n$ 的 $B$-smooth 数。

输入格式

第一行包含两个正整数 $n$ 和 $B$，含义如题面所示。

输出格式

输出一个非负整数，表示不超过 $n$ 的 $B$-smooth 数的数量。

样例输入 #1

10 3

样例输出 #1

7

说明/提示

样例解释

在不超过 $10$ 的正整数中，$3$-smooth 数有 $1,2,3,4,6,8,9$，共 $7$ 个。

数据规模与约定

对全部的测试数据，保证 1≤n,B≤1061 \leq n, B \leq 10^61≤n,B≤106。