2019清华912数据结构真题精华解析

在2019年的清华大学计算机科学专业考试912题的Data Structure部分，涉及了一系列关于数据结构和算法的判断题与简答题。以下是关键知识点的详细解析： 1. 判断题： - 复杂度关系：n^(log(log(log(n)))) 的时间复杂度等于 O(log(n!)) 是错误的（F），因为这是指数级增长，而 log(n!) 的对数增长较慢。 - 局部性与伸展树：如果访问顺序缺乏局部性，伸展树（一种数据结构，用于缓存局部访问）不能保证达到线性对数时间复杂度（O(log(n))) 的性能，这个说法是正确的（F）。 - 赫夫曼树编码：交换不同深度的子树可能导致编码成本增加，这同样是对的（F），因为不同的路径长度会影响编码效率。 - 逆序对：在交换序列中，任意一对逆序元素会导致逆序对数减少，这是一个基本的性质，表述正确（T）。 - KMP算法：未改进的 next 表在 KMP 算法中确实可以在线性时间内完成串匹配（T），因为它利用了部分匹配信息。 - 二叉树遍历：仅凭先序遍历和后序遍历无法唯一确定层序遍历，这个结论是正确的（T）。 - 基数排序稳定性：不稳定底层算法可能导致基数排序输出序列不正确，这说明稳定性在某些排序算法中很重要（T）。 - 树的辅助队列：对于层序遍历，辅助队列规模不会超过叶节点的数量，所以对于2018个叶节点的树，队列规模不会超过这个数（T）。 - 二叉树与括号表达式：2019个叶节点的真二叉树数目并不小于2018对括号构成的合法表达式的数量，这个判断错误（F）。 - 插入排序：在插入排序中，有序前缀增长不会改变循环节点的数量，正确（T）。 - 调用栈：同一函数的不同调用帧不一定按顺序排列，它们可能交错（F）。 - 堆的操作：完全二叉堆的平均插入操作时间在理想随机情况下是 O(1)，但最坏情况是 O(log(n))，这是正确的（T）。 2. 简答题： - 逆波兰式与常规表达式：逆波兰式效率高是因为无需处理优先级问题，转换成本虽然高，但长期重复计算时能节省比较操作，意义在于提高运算效率。 - DFS的边标记：前向边在访问新节点时标记，后向边在回溯到父节点时标记。 - 插入排序优势：除了稳定性和输入敏感性（最好情况复杂度低），插入排序在处理部分有序的数据时表现良好。 - Dijkstra与多叉堆：在稠密图中，多叉堆用于Dijkstra算法可以减少因边多导致的堆调整和I/O开销，堆的分叉数取决于边的数量。 - 封闭散列：优点包括本地操作无需维护额外的二维结构和冲突解决时I/O少，查找速度快。 - 败者树的优势：减少 I/O 和比较操作，只在必要时更新节点。 - 红黑树与AVL树：红黑树在插入结构调整和保持适度平衡方面优于AVL树，例如在插入导致不平衡时，红黑树的调整操作更灵活。 这些题目涵盖了数据结构、算法复杂度、排序方法、图算法优化、哈希表和搜索树的区别等多个重要知识点，展示了理论与实践中的考量。