章节自测题

使用说明

• 每章先不看答案，自己口述或手写。
• 如果 30 秒内答不出，就说明这一块还不稳。

第1章 绪论

1. 什么是数据结构三要素？
2. 时间复杂度为什么只保留最高阶？
3. 算法的五个特性分别是什么？

第2章 线性表

1. 为什么顺序表按位查找是 O(1)，单链表不是？
2. 删除单链表结点时，为什么通常要找前驱？
3. 快慢指针能解决哪几类经典问题？

第3章 栈与队列

1. 循环队列如何判满、判空、求长度？
2. 为什么 BFS 要用队列？
3. 表达式求值时，操作符优先级如何体现？

第4章 串

1. KMP 为什么能做到主串指针不回退？
2. next 数组表示什么？
3. 什么时候朴素匹配会退化得很厉害？

第5章 树与二叉树

1. 满二叉树和完全二叉树的区别是什么？
2. WPL 为什么只算叶结点？
3. BST 判断为什么不能只比较父子大小？

第6章 图

1. 邻接矩阵和邻接表各适合什么图？
2. 拓扑排序的前提是什么？
3. 欧拉图、半欧拉图的判定条件是什么？

第7章 查找

1. 折半查找为什么不能直接用于链表？
2. AVL 相比 BST 的优势是什么？
3. 散列表查找性能和什么因素关系最大？

第8章 排序

1. 稳定排序有哪些？不稳定排序有哪些？
2. 快速排序为什么最坏会退化到 O(n^2)？
3. 归并排序和堆排序分别有什么优缺点？

答案速看

点击展开参考答案

第1章

• 三要素：逻辑结构、存储结构、数据运算。
• 复杂度分析关注规模增长趋势。
• 五性：有穷性、确定性、可行性、输入、输出。

第2章

• 顺序表支持随机访问，链表不支持。
• 单链表删除需要修改前驱的 next。
• 倒数第 k 个、找中点、找环入口、重排链表。

第3章

• 判空 front == rear，判满 (rear + 1) % MaxSize == front。
• BFS 要按层推进，队列天然满足 FIFO。
• 栈顶运算符与当前运算符比较优先级。

第4章

• 因为 next 记录了失配后的最长可复用前缀信息。
• next[i] 反映模式串前缀/后缀重合情况。
• 主串和模式串高度重复时，朴素算法易退化。

第5章

• 满二叉树每层都满；完全二叉树只要求最后一层尽量靠左。
• 因为 WPL 定义就是叶结点权值与路径长度之积求和。
• 因为某个结点可能违反祖先范围约束，但不违反父子大小关系。

第6章

• 邻接矩阵适合稠密图，邻接表适合稀疏图。
• 图必须是 DAG。
• 奇度顶点 0 个是欧拉回路，2 个是欧拉路径。

第7章

• 折半查找依赖随机访问。
• AVL 能保证最坏查找仍是 O(log n)。
• 装填因子和冲突处理方式。

第8章

• 稳定：插入、冒泡、归并、基数。
• 快排若每次划分极不平衡会退化。
• 归并稳定但耗空间；堆排序原地但不稳定。