2024年6月 GESP C++ 5级

下面 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;
}

下面 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;
}

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

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;
}

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

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;
}

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

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

欧几里得算法还可以写成如下形式：

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

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

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

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;
}

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

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

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); // 对右子数组进行快速排序
}

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

根据下述二分查找法，在排好序的数组 $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
}

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

// 假设 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;
}

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

给定如下函数：

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

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

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

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$ 时，屏幕上输出序列为（ ）。

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

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

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

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

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

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

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

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

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

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

int* ptr = new int(10);
cout << *ptr << endl;
delete ptr;
cout << ptr << endl;

试题名称：黑白格

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

题目描述

小杨有一个 $n$ 行 $m$ 列的网格图，其中每个格子要么是白色，要么是黑色。

小杨想知道至少包含 $k$ 个黑色格子的最小子矩形包含了多少个格子。

输入格式

第一行包含三个正整数 $n,m,k$，含义如题面所示。

之后 $n$ 行，每行⼀个长度为 $m$ 的 $\text{01}$ 串，代表网格图第 $i$ 行格子的颜色，如果为 $\text{0}$，则对应格子为白色，否则为黑色。

输出格式

输出一个整数，代表至少包含 $k$ 个黑色格子的最小子矩形包含格子的数量，如果不存在则输出 $0$。

样例输入 #1

4 5 5
00000
01111
00011
00011

样例输出 #1

6

说明/提示

样例解释

对于样例 $1$，假设 $(i,j)$ 代表第 $i$ 行第 $j$ 列，至少包含 $5$ 个黑色格子的最小子矩形的四个顶点为 $(2,4)$，$(2,5)$，$(4,4)$，$(4,5)$，共包含 $6$ 个格子。

数据范围

对于全部数据，保证有 $1\le n,m\le 100$，$1\le k\le n\times m$。

Update on 2024/7/9：添加了若干组 hack 数据，感谢 @cff_0102 的贡献。

试题名称：小杨的幸运数字

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

题目描述

小杨认为他的幸运数字应该恰好有两种不同的质因子，例如，$12=2\times 2\times 3$ 的质因子有 $2,3$，恰好为两种不同的质因子，因此 $12$ 是幸运数字，而 $30=2\times 3\times 5$ 的质因子有 $2,3,5$，不符合要求，不为幸运数字。

小杨现在有 $n$ 个正整数，他想知道每个正整数是否是他的幸运数字。

输入格式

第一行包含一个正整数 $n$，代表正整数个数。

之后 $n$ 行，每行一个正整数。

输出格式

输出 $n$ 行，对于每个正整数，如果是幸运数字，输出 $1$，否则输出 $0$。

样例输入 #1

3
7
12
30

样例输出 #1

0
1
0

说明/提示

样例解释

$7$ 的质因子有 $7$，只有一种。

$12$ 的质因子有 $2,3$，恰好有两种。

$30$ 的质因子有 $2,3,5$，有三种。

数据范围

对于全部数据，保证有 1≤n≤1041\leq n\leq 10^41≤n≤104，每个正整数 aia_iai​ 满足 2≤ai≤1062\leq a_i\leq 10^62≤ai​≤106。