初赛模拟卷 A（5）

第 1 题（单选）

下面函数可以将 n 的所有质因数找出来，其时间复杂度是（）。

[]
vector get_prime_factors(int n) { vector factors;
while (n % 2 == 0) {
factors.push_back(2); n /= 2;
}
for (int i = 3; i * i  2) {
factors.push_back(n); }
return factors; }

{{ select(1) }}

• O(n²)
• O(nlog n) []
• O(√n)
• O(n)

第 2 题（单选）

用以下辗转相除法（欧几里得算法）求gcd(84, 60)的步骤中，第二步计算的数是（）。 6 7 8

int gcd(int a, int b) {
int big = a > b ? a : b; int small = a & nums, int target) {
|
2 | int left = 0;
|
3 | int right = nums.size() - 1;
|
4 | while (left  b ? a : b; int small = a  get_prime_factors(int n) { vector factors;
while (n % 2 == 0) {
factors.push_back(2); n /= 2;
}
for (int i = 3; i * i  2) {
factors.push_back(n); }
return factors; }

{{ select(2) }}

• O(n²)
• O(nlog n) []
• O(√n)
• O(n)

第 3 题（单选）

用以下辗转相除法（欧几里得算法）求gcd(84, 60)的步骤中，第二步计算的数是（）。 6 7 8

int gcd(int a, int b) {
int big = a > b ? a : b; int small = a & nums, int target) {
|
2 | int left = 0;
|
3 | int right = nums.size() - 1;
|
4 | while (left  b ? a : b; int small = a < b ? a : b; if (big % small ==
0) {
return small; }
return gcd(small, big % small); }

{{ select(3) }}

• gcd(24, 36)、gcd(24, 12)、gcd(12, 0)
• gcd(24, 36)、gcd(12, 24)、gcd(0, 12) []
• gcd(24, 36)、gcd(24, 12)
• gcd(24, 36)、gcd(12, 24)

第 4 题（单选）

关于栈和递归，正确的有（　）。

{{ select(4) }}

• 递归调用过程中，系统使用栈保存返回地址和局部变量
• 递归深度过大可能导致栈溢出
• 可以通过尾递归优化来减少栈空间使用
• C++编译器总是会自动优化尾递归

第 5 题（单选）

关于高精度乘法，正确的有（　）。

{{ select(5) }}

• 采用模拟竖式乘法的方法
• 结果位数最多为两个乘数位数之和
• 需要处理进位
• 时间复杂度为O(n²)（n为位数）

第 6 题（单选）

关于递归算法的时间复杂度分析，正确的有（　）。

{{ select(6) }}

• 可以通过递推关系式求解
• 主定理可以应用于某些递推式
• 斐波那契数列的递归实现时间复杂度为O(2ⁿ)
• 递归树法可以用于求解复杂度

第 7 题（单选）

关于空间复杂度，正确的有（　）。

{{ select(7) }}

• 递归算法的空间复杂度通常包括栈空间
• 归并排序的空间复杂度为O(n)
• 快速排序的空间复杂度为O(log n)（递归栈）
• 原地算法空间复杂度为O(1)

第 8 题（单选）

关于动态规划与贪心的区别，正确的有（　）。

{{ select(8) }}

• 贪心只考虑当前局部最优，动态规划考虑全局最优
• 动态规划通常需要记录子问题的解
• 贪心算法不需要重复计算子问题
• 动态规划比贪心更复杂，但适用范围更广

第 9 题（单选）

关于二分查找的变体，正确的有（　）。

{{ select(9) }}

• 可以查找第一个等于目标的位置
• 可以查找最后一个等于目标的位置
• 可以查找大于等于目标的第一个位置
• 可以用于数组和链表

第 10 题（单选）

关于二分查找的递归实现，正确的有（　）。

{{ select(10) }}

• 每次递归调用问题规模减半
• 递归深度为O(log n)
• 递归实现可能导致栈溢出
• 循环实现比递归实现更节省空间

第 11 题（单选）

以下哪些排序算法在平均情况下的时间复杂度为O(n log n)？（　）

{{ select(11) }}

• 冒泡排序
• 快速排序
• 归并排序
• 插入排序

第 12 题（单选）

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

{{ select(12) }}

• 快速排序是一种不稳定的排序算法
• 快速排序的平均时间复杂度为O(n log n)
• 快速排序在最坏情况下的时间复杂度为O(n²)
• 快速排序是稳定的排序算法

第 13 题（单选）

关于归并排序，下列说法正确的有（　）。

{{ select(13) }}

• 归并排序是稳定的排序算法
• 归并排序的时间复杂度在任何情况下均为O(n log n)
• 归并排序需要额外的O(n)辅助空间
• 归并排序通常采用迭代方式实现，而非递归

第 14 题（单选）

下列关于链表说法，正确的是（）。

{{ select(14) }}

• 不能用数组来实现链表。
• 在链表头部插入元素的时间复杂度是 $O(1)$。
• 循环链表使得任意一个结点都可以很方便地访问其前驱与后继。
• 从双向链表的任意一个节点出发，并不一定能够访问到所有其他节点。

第 15 题（单选）

近年来，线上授课变得普遍，很多有助于改善教学效果的设备也逐渐流行，其中包括比较常用的手写板，那么它属于哪类设备？（）。

{{ select(15) }}

• 输入
• 输出
• 控制
• 记录

第 16 题（单选）

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

{{ select(16) }}

• 信息过滤
• 信号中继
• 避免攻击
• 数据加密

第 17 题（单选）

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

{{ select(17) }}

• 埃氏筛法
• 线性筛法 []
• 二分答案
• 枚举法

第 18 题（单选）

贪心算法的核心思想是 ( ) ?

{{ select(18) }}

• 在每一步选择中都做当前状态下的最优选择
• 在每一步选择中都选择局部最优解
• 在每一步选择中都选择全局最优解 []
• 以上都对

第 19 题（单选）

辗转相除法也被称为(）

{{ select(19) }}

• 高斯消元法
• 费马定理
• 欧几里德算法
• 牛顿迭代法

第 20 题（单选）

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

{{ select(20) }}

• 有终止条件
• 函数参数递减（或递增）
• 函数返回值固定
• 以上都对

第 21 题（单选）

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

{{ select(21) }}

• 分治算法将问题分成子问题，然后分别解决子问题，最后合并结果。
• 归并排序不是分治算法的应用。
• 分治算法通常用于解决小规模问题。
• 分治算法的时间复杂度不一定总是优于 O(n log n)。

第 22 题（单选）

给定如下递归函数，当 n = 7 时，函数返回值为（ ）。

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

{{ select(22) }}

• -11
• 11
• 7
• 3

第 23 题（单选）

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

{{ select(23) }}

• 数组大小固定，链表大小可动态调整。
• 数组支持随机访问，链表只能顺序访问。
• 存储相同数目的整数，数组比链表所需的内存多。
• 数组插入和删除元素效率低，链表插入和删除元素效率高。