初赛模拟卷 A（7）

第 1 题（单选）

以下关于链表与数组的描述，正确的是（）。

{{ select(1) }}

• 链表支持随机访问，数组不支持
• 数组插入元素的时间复杂度总是O(1)
• 链表在头部插入元素的时间复杂度为O(1)
• 数组和链表都不需要预先分配连续内存

第 2 题（单选）

二分查找算法在有序数组中查找元素，最坏情况下的比较次数是（）。

{{ select(2) }}

• O(1)
• O(log n)
• O(n)
• O(n log n)

第 3 题（单选）

下列关于递归算法的说法，错误的是（）。

{{ select(3) }}

• 递归必须有终止条件
• 递归算法都可以用循环实现
• 递归算法一定比循环效率高
• 递归调用会消耗系统栈空间

第 4 题（单选）

用分治法求解最大子段和问题，合并步骤的时间复杂度为（）。

{{ select(4) }}

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

第 5 题（单选）

下面哪个是计算斐波那契数列第n项的递归式？

{{ select(5) }}

• F(n)=n*F(n-1)
• F(n)=F(n-1)+F(n-2)
• F(n)=F(n-1)+1
• F(n)=2*F(n/2)

第 6 题（单选）

一个算法的时间复杂度为O(2^n)，当n=20时，执行次数大约为（）。

{{ select(6) }}

• 100万
• 10亿
• 100
• 20

第 7 题（单选）

以下关于链表存储结构的描述，正确的有（）。

{{ select(7) }}

• 存储空间不一定是连续的
• 插入和删除操作不需要移动其他元素
• 可以随机存取任意元素
• 需要额外的空间存储指针

第 8 题（单选）

贪心算法通常需要满足的条件有（）。

{{ select(8) }}

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

第 9 题（单选）

以下哪些操作在单链表中时间复杂度为O(1)？

{{ select(9) }}

• 在已知结点后插入新结点
• 删除已知结点的后继结点
• 查找第i个结点
• 在表头插入结点

第 10 题（单选）

关于链表和数组，以下说法正确的有（）。

{{ select(10) }}

• 数组支持随机访问
• 链表插入删除不需要移动元素
• 数组在内存中连续存储
• 链表每个结点内存连续

第 11 题（单选）

在单链表中，要删除结点p（已知p不是尾结点），以下哪些操作正确？

{{ select(11) }}

• p.data = p.next.data; p.next = p.next.next
• 找到p的前驱q，然后q.next = p.next
• p = p.next; 然后删除原p
• 直接让p.next = p.next.next

第 12 题（单选）

关于贪心算法的特点，正确的有（）。

{{ select(12) }}

• 每一步都选择当前最优
• 可以得到全局最优解（某些问题）
• 不能回退
• 通常需要证明最优性

第 13 题（单选）

在双向链表中，下列哪些操作需要修改两个指针？

{{ select(13) }}

• 在p结点前插入
• 删除p结点
• 在表头插入
• 遍历链表

第 14 题（单选）

以下哪些操作在链表中的时间复杂度与位置有关？

{{ select(14) }}

• 查找
• 在指定位置插入
• 在头结点插入
• 删除尾结点（无尾指针）

第 15 题（单选）

以下哪些情况，使用二分查找比线性查找更优？

{{ select(15) }}

• 有序静态数组
• 无序链表
• 频繁查找但很少修改的有序数组
• 动态插入频繁的集合

第 16 题（单选）

关于贪心算法与动态规划的关系，正确的有（）。

{{ select(16) }}

• 贪心是动态规划的一种特例
• 动态规划可以考虑所有选择
• 贪心不需要保存子问题解
• 两者都需要最优子结构

第 17 题（单选）

链表插入和删除操作的时间复杂度均为O(1)。（）

{{ select(17) }}

• 正确
• 错误
• 以上说法不成立

第 18 题（判断）

贪心算法每一步都选择当前最优，因此总能得到全局最优解。（）

{{ select(18) }}

• 正确
• 错误

第 19 题（判断）

二分查找要求待查找序列有序。（）

{{ select(19) }}

• 正确
• 错误

第 20 题（单选）

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

{{ select(20) }}

• 正确
• 错误
• 以上说法不成立

第 21 题（单选）

如果一个问题的子问题有重叠，则分治法效率较低，应考虑动态规划。（）

{{ select(21) }}

• 正确
• 错误
• 以上说法不成立

第 22 题（单选）

循环链表是一种特殊的链表，其最后一个结点的指针指向头结点。（）

{{ select(22) }}

• 正确
• 错误
• 以上说法不成立

第 23 题（单选）

链表中每个结点占用的内存空间大小是固定的。（）

{{ select(23) }}

• 正确
• 错误
• 以上说法不成立

第 24 题（判断）

递归深度过大会导致程序崩溃，因为栈空间有限。（）

{{ select(24) }}

• 正确
• 错误

第 25 题（判断）

贪心算法不需要回退，因此它的实现通常很简单。（）

{{ select(25) }}

• 正确
• 错误

第 26 题（判断）

删除双向链表中的头结点需要修改头指针。（）

{{ select(26) }}

• 正确
• 错误