初赛模拟卷 B（5）
初赛模拟卷 B（5）
第 1 题（单选）
下面的代码片段用于计算斐波那契数列。该代码的时间复杂度是 ( ) ?
[]int fibonacci(int n) { if (n 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(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 题（单选）
关于欧几里得算法（辗转相除法），正确的有（ ）。
{{ select(3) }}
- 用于求两个整数的最大公约数
- 时间复杂度为O(log min(a, b))
- 可以递归实现，也可以循环实现
- 只能用于正整数，不能用于负数
第 4 题（单选）
关于高精度加法，下列说法正确的有（ ）。
{{ select(4) }}
- 高精度加法需要按位相加并处理进位
- 存储数字时通常采用倒序存储（个位在前）以便进位
- 高精度加法的时间复杂度与两个数的位数之和成正比
- 高精度加法不能处理负数
第 5 题（单选）
关于高精度减法，正确的有（ ）。
{{ select(5) }}
- 需要借位处理
- 通常要求被减数不小于减数，否则需要特殊处理符号
- 结果前导零需要去除
- 时间复杂度与两个数的位数之积成正比
第 6 题（单选）
关于埃拉托斯特尼筛法，正确的有（ ）。
{{ select(6) }}
- 可以找出n以内的所有素数
- 时间复杂度为O(n log log n)
- 每个合数会被标记多次
- 空间复杂度为O(n)
第 7 题（单选）
关于线性筛法，正确的有（ ）。
{{ select(7) }}
- 每个合数只被标记一次
- 时间复杂度为O(n)
- 与埃氏筛法相比效率更高
- 实现比埃氏筛法更复杂
第 8 题（单选）
关于递归算法，下列说法正确的有（ ）。
{{ select(8) }}
- 递归算法必须有一个明确的终止条件，否则会导致无限递归
- 递归算法的执行效率通常高于对应的迭代算法
- 递归算法每次调用都会在栈上分配新的空间，可能引发栈溢出
- 任何递归算法都可以用循环加栈的方式模拟实现
第 9 题（单选）
以下关于分治算法的描述，正确的有（ ）。
{{ select(9) }}
- 分治算法将原问题分解为多个规模更小的子问题
- 分治算法通常需要合并子问题的解
- 二分查找是分治算法的一个典型应用
- 所有分治算法的时间复杂度都是O(n log n)
第 10 题（单选）
以下关于贪心算法的说法，正确的有（ ）。
{{ select(10) }}
- 贪心算法每一步选择当前最优解
- 贪心算法一定能得到全局最优解
- 贪心算法通常适用于具有最优子结构的问题
- 贪心算法不一定能找到最优解
第 11 题（单选）
关于链表，下列说法正确的有（ ）。
{{ select(11) }}
- 链表在头部插入元素的时间复杂度为O(1)
- 链表支持随机访问
- 双向链表可以方便地访问前驱和后继
- 链表的存储空间可以是连续的，也可以是不连续的
第 12 题（单选）
关于数组和链表的比较，正确的有（ ）。
{{ select(12) }}
- 数组大小固定，链表大小动态可调
- 数组插入和删除操作效率通常低于链表
- 数组支持随机访问，链表不支持
- 存储相同数量的元素，数组占用的内存一定比链表少
第 13 题（单选）
下列关于链表说法，正确的是（）。
{{ select(13) }}
- 不能用数组来实现链表。
- 在链表头部插入元素的时间复杂度是 。
- 循环链表使得任意一个结点都可以很方便地访问其前驱与后继。
- 从双向链表的任意一个节点出发，并不一定能够访问到所有其他节点。
第 14 题（单选）
近年来，线上授课变得普遍，很多有助于改善教学效果的设备也逐渐流行，其中包括比较常用的手写板，那么它属于哪类设备？（）。
{{ select(14) }}
- 输入
- 输出
- 控制
- 记录
第 15 题（单选）
通讯卫星在通信网络系统中主要起到（） 的作用。
{{ select(15) }}
- 信息过滤
- 信号中继
- 避免攻击
- 数据加密
第 16 题（单选）
小杨想编写一个判断任意输入的整数N是否为素数的程序，下面哪个方法不合适？ ( )
{{ select(16) }}
- 埃氏筛法
- 线性筛法 []
- 二分答案
- 枚举法
第 17 题（单选）
贪心算法的核心思想是 ( ) ?
{{ select(17) }}
- 在每一步选择中都做当前状态下的最优选择
- 在每一步选择中都选择局部最优解
- 在每一步选择中都选择全局最优解 []
- 以上都对
第 18 题（单选）
辗转相除法也被称为(）
{{ select(18) }}
- 高斯消元法
- 费马定理
- 欧几里德算法
- 牛顿迭代法
第 19 题（单选）
递归函数在调用自身时，必须满足（）， 以避免无限递归？
{{ select(19) }}
- 有终止条件
- 函数参数递减（或递增）
- 函数返回值固定
- 以上都对
第 20 题（单选）
关于分治算法， 以下哪个说法正确？
{{ select(20) }}
- 分治算法将问题分成子问题，然后分别解决子问题，最后合并结果。
- 归并排序不是分治算法的应用。
- 分治算法通常用于解决小规模问题。
- 分治算法的时间复杂度不一定总是优于 O(n log n)。
第 21 题（单选）
给定如下递归函数，当 n = 7 时，函数返回值为（ ）。
int fun(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return fun(n - 2) - fun(n - 1); }
{{ select(21) }}
- -11
- 11
- 7
- 3
第 22 题（单选）
下面关于链表和数组的描述，错误的是（）。
{{ select(22) }}
- 数组大小固定，链表大小可动态调整。
- 数组支持随机访问，链表只能顺序访问。
- 存储相同数目的整数，数组比链表所需的内存多。
- 数组插入和删除元素效率低，链表插入和删除元素效率高。