第1题

题目： 下面关于链表和数组的描述，错误的是（ ）。

A. 当数据数量不确定时，为了应对各种可能的情况，需要申请一个较大的数组，可能浪费空间；此时用链表比较合适，大小可动态调整。
B. 在链表中访问节点的效率较低，时间复杂度为O(n)。
C. 链表插入和删除元素效率较低，时间复杂度为O(n)。
D. 链表的节点在内存中是分散存储的，通过指针连在一起。

解析：

• A. 正确，链表的大小可以动态调整，适合数据数量不确定的情况。
• B. 正确，链表访问节点的效率较低，时间复杂度为O(n)。
• C. 错误，链表插入和删除元素的效率较高，时间复杂度为O(1)（在已知节点的情况下）。
• D. 正确，链表的节点在内存中是分散存储的，通过指针连在一起。

答案： C

第2题

题目： 在循环单链表中，节点的 next 指针指向下一个节点，最后一个节点的 next 指针指向（ ）。

A. 当前节点
B. nullptr
C. 第一个节点
D. 上一个节点

解析：

• 在循环单链表中，最后一个节点的指针指向第一个节点，形成一个环。

答案： C

第3题

题目： 为了方便链表的增删操作，一些算法生成一个虚拟头节点，方便统一删除头节点和其他节点。下面代码实现了删除链表中值为 val 的节点，横线上应填的最佳代码是( )。

A. dummyHead->next = head; cur = dummyHead;
B. dummyHead->next = head->next; cur = dummyHead;
C. dummyHead->next = head; cur = dummyHead->next;
D. dummyHead->next = head->next; cur = dummyHead->next;

解析：

• 虚拟头节点的指针应该指向原链表的头节点，指针应该从虚拟头节点开始遍历。

答案： A

第4题

题目： 对下面两个函数，说法错误的是（ ）。

A. 两个函数的实现的功能相同。
B. fibA采用递推方式。
C. fibB采用的是递归方式。
D. fibA时间复杂度为O(n)，fibB的时间复杂度为O(n^2)。

解析：

• A. 正确，两个函数都计算斐波那契数列的第n项。
• B. 正确，采用递推方式。
• C. 正确，采用递归方式。
• D. 错误，的时间复杂度为O(2^{n)，而不是O(n}2)。

答案： D

第5题

题目： 两块长方形土地的长宽分别为24和36米，要将它们分成正方形的小块，使得正方形的大尺寸可能大。小杨采用如下的辗转相除函数gcd(24, 36)来求正方形分块的边长，则函数gcd调用顺序为（ ）。

A. gcd(24, 36), gcd(24, 12), gcd(12, 0)
B. gcd(24, 36), gcd(12, 24), gcd(0, 12)
C. gcd(24, 36), gcd(24, 12)
D. gcd(24, 36), gcd(12, 24)

解析：

• 辗转相除法的调用顺序为：gcd(24, 36), gcd(24, 12)。

答案： C

第6题

题目： 唯一分解定理表明，每个大于1的自然数可以唯一地写成若干个质数的乘积。下面函数将自然数的所有因数素找出来，横线上能填写的最佳代码是（ ）。

A. for (int i = 3; i <= n; i++)
B. for (int i = 3; i * i <= n; i++)
C. for (int i = 3; i <= n; i += 2)
D. for (int i = 3; i * i <= n; i += 2)

解析：

• 为了提高效率，应该从3开始，每次增加2，并且只需要检查到。

答案： D

第7题

题目： 下述代码实现素数表的块拉托色尼(埃氏)筛法，筛选出所有小于等于n的素数。

下面说法，正确的是（ ）。

A. 代码的时间复杂度是 ( O(nsqrt{n}) )。
B. 在标记非素数时，代码从 ( i^2 ) 开始，可以减少重复标记。
C. 代码会输出所有小于等于 ( n ) 的奇数。
D. 调用函数 sieve_Eratosthenes(10)，函数返回值的数组中包含的元素有：2, 3, 5, 7, 9。

解析：

• A. 错误，时间复杂度为 ( O(nloglog n) )。
• B. 正确，从 ( i^2 ) 开始标记可以减少重复标记。
• C. 错误，代码会输出所有小于等于 ( n ) 的素数。
• D. 错误，返回的数组中不包含9，因为9不是素数。

答案： B

第8题

题目： 下述代码实现素数表的线性筛选、筛选出所有小于等于n的素数。下面说法正确的是()。

A. 线性筛的时间复杂度是 ( O(n) )。
B. 每个合数其所有的质因子标记一次。
C. 线性筛和块拉托尼筛的实现思路完全相同。
D. 以上都不对

解析：

• A. 正确，线性筛的时间复杂度是 ( O(n) )。
• B. 正确，每个合数只会被它的最小质因子标记一次。
• C. 错误，线性筛和块拉托尼筛的实现思路不同。
• D. 错误，A和B都是正确的。

答案： A

第9题

题目： 考虑以下C++代码实现的快速排序算法：

以下关于快速排序的说法，正确的是（ ）。

A. 快速排序通过递归对于问题进行求解。
B. 快速排序的最坏时间复杂度是 ( O(nlog n) )。
C. 快速排序是一个稳定的排序算法。
D. 在最优情况下，快速排序的时间复杂度是 ( O(n) )。

解析：

• A. 正确，快速排序通过递归对于问题进行求解。
• B. 错误，快速排序的最坏时间复杂度是 ( O(n^2) )。
• C. 错误，快速排序是一个不稳定的排序算法。
• D. 错误，在最优情况下，快速排序的时间复杂度是 ( O(nlog n) )。

答案： A

第10题

题目： 下面关于归并排序，描述正确的是（ ）。

A. 归并排序是一个不稳定的排序算法。
B. 归并排序的时间复杂度在最优、最差和平均情况下都是 ( O(nlog n) )。
C. 归并排序需要额外的 ( O(1) ) 空间。
D. 对于输入数组 ({12, 11, 13, 5, 6, 7})，代码输出结果为：(7 imes 6 imes 13 imes 12 imes 11)。

解析：

• A. 错误，归并排序是一个稳定的排序算法。
• B. 正确，归并排序的时间复杂度在最优、最差和平均情况下都是 ( O(nlog n) )。
• C. 错误，归并排序需要额外的 ( O(n) ) 空间。
• D. 错误，归并排序的输出结果是排序后的数组。

答案： B

第11题

题目： 给定一个长度为 ( n ) 的有序数组 ( nums )，其中所有元素都是唯一的。下面的函数返回数组中元素 target 的索引。

关于上述函数，描述不正确的是（ ）。

A. 函数采用二分查找，每次计算搜索当前搜索区间的中点，然后根据中点的元素值排除一半搜索区间。
B. 函数采用递归求解，每次问题的规模减小一半。
C. 递归的终止条件是中间元素的值等于target，若数组中不包含该元素，递归不会终止。
D. 算法的复杂度为 ( O(log n) )。

解析：

• A. 正确，函数采用二分查找。
• B. 正确，函数采用递归求解。
• C. 错误，递归的终止条件是，若数组中不包含该元素，递归会终止并返回-1。
• D. 正确，算法的复杂度为 ( O(log n) )。

答案： C

第12题

题目： 给定一个长度为n的有序数组nums，其中可能包含重复元素。下面的函数返回数组中某个元素target的左边界，若数组中不包含该元素，则返回-1。例如在数组nums = [5,7,7,8,8,10]中查找target=8，函数返回8在数组中的左边界的索引为3。则横线上应填写的代码为（ ）。

A. right = middle - 1;
B. right = middle;
C. right = middle + 1;
D. 以上都不对

解析：

• 当时，应该将更新为，以继续向左搜索。

答案： B

第13题

题目： 假设有多个孩子，数组g保存所有孩子的胃口值。有多块饼干，数组s保存所有饼干的尺寸。小杨给孩子们发饼干，每个孩子最多只能给一块饼干。饼干的尺寸大于等于孩子的胃口时，孩子才能得到满足。小杨的目标是尽可能满足越多数量的孩子，因此打算采用贪心算法来找出能满足的孩子的数目，则横线上应填写的代码为（ ）。

A. result++; index–;
B. result–; index–;
C. result–; index++;
D. result++; index++;

解析：

• 当饼干尺寸大于等于孩子的胃口时，孩子得到满足，结果加1，饼干数组下标减1。

答案： A

第14题

题目： 关于分治算法，以下说法中不正确的是（ ）。

A. 分治算法将问题分成子问题，然后分别解决子问题，最后合并结果。
B. 归并排序采用了分治思想。
C. 快速排序采用了分治思想。
D. 冒泡排序采用了分治思想。

解析：

• A. 正确，分治算法将问题分成子问题。
• B. 正确，归并排序采用了分治思想。
• C. 正确，快速排序采用了分治思想。
• D. 错误，冒泡排序没有采用分治思想。

答案： D

第15题

题目： 小杨编写了一个如下的高精度减法函数：

下面说法，正确的是（ ）。

A. 如果数组a表示的整数小于b表示的整数，代码会正确返回二者的差为负数。
B. 代码假设输入数字是以倒序存储的，例如500存储为 {0, 0, 5}。
C. 代码的时间复杂度为 ( O(a.size() + b.size()) )
D. 当减法结果为0时，结果数组仍然会存储很多个元素0。

解析：

• A. 错误，代码没有处理a小于b的情况。
• B. 正确，代码假设输入数字是以倒序存储的。
• C. 正确，代码的时间复杂度为 ( O(a.size() + b.size()) )。
• D. 错误，代码会去除结果数组中的前导零。

答案： B

第1题

题目： 单链表只支持在表头进行插入和删除操作。

解析：

• 错误，单链表可以在任意位置进行插入和删除操作。

答案： ×

第2题

题目： 线性筛相对于块拉杆排序后筛选，每个合数只会被它的最小质因数筛去一次，因此效率更高。

解析：

• 正确，线性筛的效率更高。

答案： √

第3题

题目： 任何一个大于1的自然数都可以分解成若干个不同的质数的乘积，且分解方式是唯一的。

解析：

• 错误，分解方式可以包含相同的质数。

答案： ×

第4题

题目： 贪心算法通过一步选择当前最优解，从而一定能获得全局最优解。

解析：

• 错误，贪心算法不一定能获得全局最优解。

答案： ×

第5题

题目： 递归算法必须有一个明确的结束条件，否则会导致无限递归并可能引发栈溢出。

解析：

• 正确，递归算法必须有明确的结束条件。

答案： √

第6题

题目： 快速排序和归并排序的平均时间复杂度均为 ( O(nlog n) )，且都是稳定排序。

解析：

• 错误，快速排序是不稳定的排序算法。

答案： ×

第7题

题目： 快速排序的时间复杂度总比插入排序的时间复杂度低。

解析：

• 错误，快速排序的最坏时间复杂度为 ( O(n^2) )，而插入排序的最坏时间复杂度也为 ( O(n^2) )。

答案： ×

第8题

题目： 二分查找仅适用于数组而不适合链表，因为二分查找需要跳跃式访问元素，链表中执行跳跃式访问的效率低。

解析：

• 正确，二分查找需要随机访问，链表不支持。

答案： √

第9题

题目： 对有序数组{5,13,19,21,37,56,64,75,88,92,100}进行二分查找，成功查找元素19的比较次数是2。

解析：

• 正确，查找19的比较次数是2。

答案： √

第10题

题目： 递归函数每次调用自身时，系统都会为新开点的函数分配内存，以存储局部变量、调用地址和其他信息等，导致递归通常比迭代更加耗费内存空间。

解析：

• 正确，递归调用会占用更多的内存空间。

答案： √

3. 编程题（每题25分，共50分）

3.1 编程题 1

题目： 奇妙数字

时间限制： 1.0 s

内存限制： 512.0 MB

3.1.1 题面描述

小杨认为一个数字 ( x ) 是奇妙数字当且仅当，其中 ( p ) 为任意质数且 ( a ) 为正整数。例如，，所以 ( 8 ) 是奇妙数字，而 ( 6 ) 不是。

对于一个正整数 ( n )，小杨想要构建一个包含 ( m ) 个奇妙数字的集合，使其满足以下条件：

• 集合中不包含相同的数字。
• 是 ( n ) 的因子（即 这 ( m ) 个数字的乘积是 ( n ) 的因子）。

小杨希望集合包含的奇妙数字尽可能多，请你帮他计算出满足条件的集合最多包含多少个奇妙数字。

3.1.2 输入格式

第一行包含一个正整数 ( n )，含义如题面所示。

3.1.3 输出格式

输出一个正整数，代表满足条件的集合最多包含的奇妙数字个数。

3.1.4 样例

输入样例1：

输出样例1：

输入样例2：

输出样例2：

3.1.5 样例解释

关于本样例，符合题意的一个包含 3 个奇妙数字的集合是 ( 2, 4, 8 )。首先，因为 ，，，所以 ( 2, 4, 8 ) 均为奇妙数字。同时， 是 128 的因子。

由于无法找到符合题意且同时包含 4 个奇妙数字的集合，因此本样例的答案为 3。

3.1.6 数据范围

对于全部数据，保证有 。

3.1.7 参考程序

3.2 编程题 2

题目： 武器强化

时间限制： 1.0 s

内存限制： 512.0 MB

3.2.1 题面描述

小杨有 ( m ) 种武器和 ( m ) 种强化材料。第 ( i ) 种强化材料会适配第 ( p_i ) 种武器，小杨可以花费 ( c_i ) 金币将该材料对应的适配武器修改为任意武器。

小杨最喜欢第 ( i ) 种武器，因此他希望适配该武器的强化材料种类数严格大于其他的武器，请你帮小杨计算为了满足该条件最少需要花费多少金币。

3.2.2 输入格式

第一行包含两个正整数 ( n, m )，含义如题面所示。

之后 ( m ) 行，每行包含两个正整数 ，代表第 ( i ) 种强化材料的适配武器和修改花费。

3.2.3 输出格式

输出一个整数，代表能够使适配第 ( i ) 种武器的强化材料种类数严格大于其他的武器最少需要花费的金币。

3.2.4 样例

输入样例：

输出样例：

3.2.5 样例解释

花费1，将第三种强化材料的适配武器由3改为1。此时，武器1有2种强化材料适配，武器2和武器3都有1种强化材料适配。满足适配第1种武器的强化材料种类数严格大于其他的武器。

3.2.6 数据范围

对于全部数据，保证有 。

3.2.7 参考程序