题目描述

本链接包含多道客观题，目前在线评测系统可以支持判断题、单选题、多选题、填空题。

其中，判断题将以单选题的形式部署，填空题将只部署输入形式简单的题目（例如只输入一个整数）。

本提交链接的内容由 提供，包含《数据结构》01 至 04 章的知识点，感谢他的支持！该用户将会长期针对《数据结构》的各章节自创课后习题，欢迎感兴趣的同学们持续关注。

客观题内容

1. 根据主定理扩展形式，若 $T(n)=aT(\frac{n}{b})+O(g(n))$，且 $g(n)=\Theta(n^{\log_ba}\times\log^k n)$（其中 $k$ 为任意整数），则一定有 $T(n)=\Theta(n^{\log_ba}\times \log^{k+1}n)$。（ {{ select(1) }} ）

• 正确
• 错误

判断题

2. 若某序列冒泡排序时，所有元素都需要参与 $n-1$ 次交换，则必为完全逆序的序列。（ {{ select(2) }} ）

• 正确
• 错误

判断题

3. 下列算法属于就地算法的是（ {{ select(3) }} ）。

• 采用记忆化策略计算 $fib(n)$
• 采用二分递归进行数组内所有元素求和
• 采用减治策略求序列的最大子段和
• 采样动态规划求解最长公共子序列

单选题

4. 若采用对数代价准则，则 $fib(n)$ 的计算至少需要 $\Omega(n)$ 的时间。（ {{ select(4) }} ）

• 正确
• 错误

判断题

5. $\lfloor \lg\lg n\rfloor !=O((\lg n)^{\lg \lg \lg n})$。（ {{ select(5) }} ）

• 正确
• 错误

判断题

6. 所有排序算法的复杂度下界均为 $\Omega(n\log n)$。（ {{ select(6) }} ）

• 正确
• 错误

判断题

7. 对于一个 $n\times m$ 的整数矩阵，若先对每一列分别排序，再对每一行分别排序，其中的各列仍然是有序的。（ {{ select(7) }} ）

• 正确
• 错误

判断题

8. 向量在归并排序的过程中，参与递归分解的子向量不一定是无序向量，参与逐层合并的子向量一定是有序向量。（ {{ select(8) }} ）

• 正确
• 错误

判断题

9. 某有序向量的长度为 $n=fib(2026)-1$，则该向量运用斐波那契查找时，最大失败查找长度为 {{ input(9) }}。

填空题

需要注意的是，输入时请输入 1 个无前导零的十进制整数，开头/末尾/中间均不要出现空白或其他字符。

10. 对长度为 $n$ 的列表进行折半插入排序，其最坏时间复杂度为 $O(n\log n)$。（ {{ select(10) }} ）

• 正确
• 错误

判断题

11. 在对序列进行插入排序的过程中，每迭代一轮，某些逆序对的间距可能会增大。（ {{ select(11) }} ）

• 正确
• 错误

判断题

12. 在序列中交换一对相邻逆序元素，整个序列的相邻逆序对数可能不变。（ {{ select(12) }} ）

• 正确
• 错误

判断题

13. 有序列表的查找效率比无序列表要高。（ {{ select(13) }} ）

• 正确
• 错误

判断题

14. 对于起泡排序而言，交换操作的次数与序列中的逆序对总数相等。（ {{ select(14) }} ）

• 正确
• 错误

判断题

15. 递归函数的空间复杂度主要取决于递归实例总数。（ {{ select(15) }} ）

• 正确
• 错误

判断题

16. 在采用双栈当队时，若连续入队 $n$ 个元素后再让所有的 $n$ 个元素出队，则均摊时间复杂度为 $O(1)$。（ {{ select(16) }} ）

• 正确
• 错误

判断题

17. 基于列表实现的栈结构，无论是将列表首/末节点作为栈顶/底，或者作为栈底/顶，其入栈和出栈的时间复杂度均为 $O(1)$。（ {{ select(17) }} ）

• 正确
• 错误

判断题

18. RPN 当中各运算符的执行次序和各操作数的相对次序，与原中缀表达式完全一致。（ {{ select(18) }} ）

• 正确
• 错误

判断题

19. 在存在双目运算符和单目运算符的 RPN 当中，运算符的数量一定不会超过操作数的数量。（ {{ select(19) }} ）

• 正确
• 错误

判断题

20. 下列排序算法属于稳定算法的是（ {{ multiselect(20) }} ）。

• 起泡排序
• 归并排序
• 基数排序
• 以上皆非

多选题