2023年12月 GESP C++ 5级

下面 C++ 代码用于求斐波那契数列，该数列第 $1$、$2$ 项为 $1$，以后各项均是前两项之和。下面有关说法错误的是( )。

下面 C++ 代码以递归方式实现合并排序，并假设 merge(int T[], int R[], int s, int m, int t) 函数将有序（同样排序规则）的 T[s..m] 和 T[m+1..t] 归并到 R[s..t] 中。横线处应填上代码是( )。

阅读下面的 C++ 代码，执行后其输出是( )。

下面的 C++ 用于对 lstA 排序，使得偶数在前奇数在后，横线处应填入( )。

下面的 C++ 代码用于将字符串保存到带头节点的双向链表中，并对重复的串计数，然后将最新访问的串的节点放在链头便于查找。横线处应填入代码是（ ）。

有关下面 C++ 代码说法正确的是（ ）。

下面的 C++ 代码实现对 list 的快速排序，有关说法，错误的是（ ）。

下面 C++ 代码中的 isPrimeA() 和 isPrimeB() 都用于判断参数 $N$ 是否素数，有关其时间复杂度的正确说法是（ ）。

下面 C++ 代码用于有序 list 的二分查找，有关说法错误的是（ ）。

在上题的 _binarySearch 算法中，如果 lst 中有 $N$ 个元素，其时间复杂度是（ ）。

下面的 C++ 代码使用数组模拟整数加法，可以处理超出大整数范围的加法运算。横线处应填入代码是（ ）。

有关下面 C++ 代码的说法正确的是（ ）。

通讯卫星在通信网络系统中主要起到（）的作用。

小杨想编写一个判断任意输入的整数 $N$ 是否为素数的程序，下面哪个方法不合适？（ ）

下面的排序算法都要处理多趟数据，哪种排序算法不能保证在下一趟处理时从待处理数据中选出最大或最小的数据？（ ）

归并排序的时间复杂度是 $O(n\log n)$。( )

小杨在生日聚会时拿一块 $H\times W$ 的巧克力招待来的 $K$ 个小朋友，保证每位小朋友至少能获得一块相同大小的巧克力。那么小杨想分出来最大边长的巧克力可以使用二分法。（ ）

以下 C++ 代码能以递归方式实现斐波那契数列，该数列第 1、2 项为 $1$，以后各项均是前两项之和。( )

贪心算法可以达到局部最优，但可能不是全局最优解。( )

小杨设计了一个拆数程序，它能够将任意的非质数自然数 $N$ 转换成若干个质数的乘积，这个程序是可以设计出来的。（ ）

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

下面的 C++ 代码能实现十进制正整数 $N$ 转换为八进制并输出。（ ）

对数组 int arr[] = {2, 6, 3, 5, 4, 8, 1, 0, 9, 10} 执行 sort(arr, arr+10)，则执行后 arr 中的数据调整为 {0, 1, 2, 3, 4, 5, 6, 8, 9, 10}。（ ）

小杨想写一个程序来算出正整数 $N$ 有多少个因数，经过思考他写出了一个重复没有超过 $N/2$ 次的循环就能够算出来了。（ ）

同样的整数序列分别保存在单链表和双向链中，这两种链表上的简单冒泡排序的复杂度相同。（ ）

试题名称：小杨的幸运数

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

题目描述

小杨认为，所有大于等于 $a$ 的完全平方数都是他的超级幸运数。

小杨还认为，所有超级幸运数的倍数都是他的幸运数。自然地，小杨的所有超级幸运数也都是幸运数。

对于一个非幸运数，小杨规定，可以将它一直 $+1$，直到它变成一个幸运数。我们把这个过程叫做幸运化。例如，如果 $a=4$，那么 $4$ 是最小的幸运数，而 $1$ 不是，但我们可以连续对 $1$ 做 $3$ 次 $+1$ 操作，使其变为 $4$，所以我们可以说， $1$ 幸运化后的结果是 $4$。

现在，小杨给出 $N$ 个数，请你首先判断它们是不是幸运数；接着，对于非幸运数，请你将它们幸运化。

输入格式

第一行 $2$ 个正整数 $a,N$。

接下来 $N$ 行，每行一个正整数 $x$ ，表示需要判断（幸运化）的数。

输出格式

输出 $N$ 行，对于每个给定的 $x$ ，如果它是幸运数，请输出 lucky，否则请输出将其幸运化后的结果。

样例输入 #1

2 4 
1 
4 
5 
9

样例输出 #1

4 
lucky 
8 
lucky

样例输入 #2

16 11 
1 
2 
4 
8 
16 
32 
64 
128 
256 
512
1024

样例输出 #2

16 
16 
16 
16 
lucky 
lucky 
lucky 
lucky 
lucky 
lucky 
lucky

说明/提示

样例解释 1

$1$ 虽然是完全平方数，但它小于 $a$，因此它并不是超级幸运数，也不是幸运数。将其进行 $3$ 次 $+1$ 操作后，最终得到幸运数 $4$。

$4$ 是幸运数，因此直接输出 lucky。

$5$ 不是幸运数，将其进行 $3$ 次 $+1$ 操作后，最终得到幸运数 $8$。

$9$ 是幸运数，因此直接输出 lucky。

数据规模

对于 $30\%$ 的测试点，保证 $a,x\le 100,N\le 100$。

对于 $60\%$ 的测试点，保证 a,x≤106a,x \le 10^6a,x≤106。

对于所有测试点，保证 $a\le 1,000,000$；保证 N≤2×105N \le 2 \times 10^5N≤2×105；保证 $1\le x\le 1,000,001$。

试题名称：烹饪问题

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

题目描述

有 $N$ 种食材，编号从 $1$ 至 $N$，其中第 $i$ 种食材的美味度为 aia_iai​。

不同食材之间的组合可能产生奇妙的化学反应。具体来说，如果两种食材的美味度分别为 $x$ 和 $y$ ，那么它们的契合度为 $x\text{and}y$。

其中，$\text{and}$ 运算为按位与运算，需要先将两个运算数转换为二进制，然后在高位补足 ，再逐位进行与运算。例如，$12$ 与 $6$ 的二进制表示分别为 $1100$ 和 $0110$ ，将它们逐位进行与运算，得到 $0100$ ，转换为十进制得到 4，因此 $12\text{and}6=4$。在 C++ 或 Python 中，可以直接使用 & 运算符表示与运算。

现在，请你找到契合度最高的两种食材，并输出它们的契合度。

输入格式

第一行一个整数 $N$，表示食材的种数。

接下来一行 $N$ 个用空格隔开的整数，依次为 a1,⋯ ,aNa_1,\cdots,a_Na1​,⋯,aN​，表示各种食材的美味度。

输出格式

输出一行一个整数，表示最高的契合度。

样例输入 #1

3
1 2 3

样例输出 #1

2

样例输入 #2

5
5 6 2 10 13

样例输出 #2

8

说明/提示

样例解释 1

可以编号为 $2,3$ 的食材之间的契合度为 $2\text{and}3=2$，是所有食材两两之间最高的契合度。

样例解释 2

可以编号为 $3,4$ 的食材之间的契合度为 $10\text{and}13=8$，是所有食材两两之间最高的契合度。

数据范围

对于 $40\%$ 的测试点，保证 $N\le 1,000$；

对于所有测试点，保证 N≤106N \le 10^6N≤106，0≤ai≤2,147,483,6470\le a_i \le 2,147,483,6470≤ai​≤2,147,483,647。