初赛模拟卷 B（7）

第 1 题（单选）

设有递归函数 f(n) = f(n-1) + f(n-2) 且 f(0)=f(1)=1，计算 f(5) 的过程中，f(2) 被调用了多少次？

{{ select(1) }}

• 2
• 3
• 4
• 5

第 2 题（单选）

用贪心算法求解“找零问题”，若要保证得到最优解，硬币面额通常需要满足（）。

{{ select(2) }}

• 任意面额都是1的倍数
• 面额按倍数递增
• 面额为1,5,10,25等标准货币
• 任何面额组合都适用

第 3 题（单选）

在双向链表中删除p指向的结点（非头尾），需要修改的指针数量是（）。

{{ select(3) }}

• 1
• 2
• 3
• 4

第 4 题（单选）

已知一个链表的头结点指针为L，每个结点包含data和next，若要输出链表中所有元素，应使用（）。

{{ select(4) }}

• 递归遍历
• 迭代遍历
• 随机访问
• 二分查找

第 5 题（单选）

关于算法的空间复杂度，下列说法正确的是（）。

{{ select(5) }}

• 空间复杂度与输入规模无关
• 递归算法空间复杂度一定高
• 原地算法空间复杂度为O(1)
• 空间复杂度无法优化

第 6 题（单选）

以下哪个问题不适合用贪心算法求解？

{{ select(6) }}

• 活动选择问题
• 最小生成树
• 0-1背包问题
• 哈夫曼编码

第 7 题（单选）

分治法解决问题的三个步骤是（）。

{{ select(7) }}

• 分解、解决、合并
• 分解、递归、回溯
• 分治、贪心、动态规划
• 分拆、排序、合并

第 8 题（单选）

以下时间复杂度最低的算法是（）。

{{ select(8) }}

• 冒泡排序
• 归并排序
• 线性查找
• 二分查找（有序）

第 9 题（单选）

链表结点通过（）链接在一起。

{{ select(9) }}

• 索引
• 指针
• 数组下标
• 哈希值

第 10 题（单选）

在单向链表中，头指针的作用是（）。

{{ select(10) }}

• 标识链表第一个结点
• 存储链表长度
• 指向链表最后一个结点
• 存储结点数据

第 11 题（单选）

将递归算法转换成非递归算法，通常需要使用（）。

{{ select(11) }}

• 队列
• 栈
• 树
• 图

第 12 题（单选）

以下关于分治法与递归的关系，正确的是（）。

{{ select(12) }}

• 分治法必须用递归实现
• 递归实现的分治法一定比非递归高效
• 分治法通常用递归实现，但也可用迭代
• 分治法不能用递归

第 13 题（单选）

下列代码的时间复杂度是（）。 python for i in range(n): for j in range(i, n): print(i,j)

{{ select(13) }}

• O(n)
• O(n log n)
• O(n^2)
• O(n^3)

第 14 题（单选）

在Python中，递归深度默认限制大约是（）。

{{ select(14) }}

• 10
• 100
• 1000
• 10000

第 15 题（单选）

一个链表结点的定义如下：class Node: def __init__(self,data): self.next=None。若要创建三个结点的链表，包含1,2,3，正确的顺序是（）。

self.data=data;

{{ select(15) }}

• 先创建头结点，然后依次链接
• 先创建尾结点，然后逆向链接
• 两者均可
• 必须使用数组

第 16 题（单选）

以下哪个是典型的“减治”算法？

{{ select(16) }}

• 快速排序
• 归并排序
• 二分查找
• 冒泡排序

第 17 题（单选）

链表相对于数组的最大优势是（）。

{{ select(17) }}

• 随机访问速度快
• 内存连续
• 插入删除不需要移动元素
• 占用内存少

第 18 题（单选）

将递归转化为非递归时，通常需要用户自己管理（）。

{{ select(18) }}

• 堆
• 栈
• 队列
• 数组

第 19 题（单选）

贪心算法与动态规划都要求问题具有（）。

{{ select(19) }}

• 重叠子问题
• 最优子结构
• 无后效性
• 贪心选择性

第 20 题（单选）

在单向链表中，已知头指针head，要删除第i个结点，需要找到（）。

{{ select(20) }}

• 第i个结点
• 第i-1个结点
• 第i+1个结点
• 尾结点

第 21 题（单选）

链表中的“头结点”通常是指（）。

{{ select(21) }}

• 第一个数据结点
• 额外附加的结点，不存储数据
• 尾结点
• 指向链表的指针

第 22 题（单选）

关于递归中的“重复计算”问题，可以采用（）优化。

{{ select(22) }}

• 尾递归
• 记忆化搜索
• 循环替代
• 增加递归深度

第 23 题（单选）

链式存储结构相比顺序存储结构的优点是（）。

{{ select(23) }}

• 查找速度快
• 节省存储空间
• 插入删除操作不需要移动大量元素
• 访问任意元素速度快

第 24 题（单选）

对于递归算法，若递归深度过大，可能导致（）。

{{ select(24) }}

• 栈溢出
• 堆溢出
• 内存泄漏
• 死循环

第 25 题（单选）

以下哪个问题是典型的贪心算法应用？

{{ select(25) }}

• 最长公共子序列
• 最小生成树Prim
• Floyd最短路径
• 矩阵链乘

第 26 题（单选）

二分查找算法中，如果查找区间为空，表示（）。

{{ select(26) }}

• 查找失败
• 查找成功
• 继续查找
• 程序错误

第 27 题（单选）

一个问题使用分治法的条件是（）。

{{ select(27) }}

• 子问题规模必须相等
• 子问题必须相互独立
• 子问题必须重叠
• 子问题必须为原问题的子集

第 28 题（单选）

在单向链表中查找值为x的结点，时间复杂度是（）。

{{ select(28) }}

• O(1)
• O(n)
• O(log n)
• O(n^2)

第 29 题（单选）

已知递归函数 def gcd(a,b): return a if b==0 else gcd(b, a%b)，该函数的功能是（）。

{{ select(29) }}

• 求最小公倍数
• 求最大公约数
• 求模运算
• 求幂