数据结构练习卷（附答案）

二叉树的后序遍历按什么顺序访问节点？

1. A先节点，再左子树，最后右子树
2. B先左子树，再节点，最后右子树
3. C先左子树，再右子树，最后节点
4. D先右子树，再节点，最后左子树

哪种数据结构最适合实现文本编辑器中的"撤销"（undo）功能？

1. A栈
2. B哈希集合
3. C队列
4. D图

一棵有 n 个节点的树有多少条边？

1. An − 1
2. Bn + 1
3. Cn
4. D2n

在平衡二叉搜索树中查找一个键的时间复杂度是多少？

1. AO(n)
2. BO(n log n)
3. CO(1)
4. DO(log n)

在一个有 n 个元素的数组中间插入一个元素，代价是多少？

1. AO(n²)，因为每个元素要移动 n 次
2. BO(1)，因为下标已知
3. CO(log n)，因为使用二分查找
4. DO(n)，因为后面的元素必须移动

在二叉最小堆中，extract-min 是如何工作的？

1. A把最后一个元素移到根上，再将其下沉
2. B删除根，并把所有元素左移一位
3. C在所有叶子中查找新的最小值
4. D删除数组的最后一个元素

采用按秩合并（union by rank）和路径压缩（path compression）的并查集（union-find，不相交集合），每次操作的均摊代价为：

1. AO(n²)
2. B恰好 O(log n)
3. CO(α(n))，即反阿克曼函数，实际上可视为常数
4. DO(n)

与有序链表相比，跳表（skip list）的主要优势是什么？

1. A利用多层前向指针，实现期望 O(log n) 的查找
2. B它以无序方式存储键
3. C它不占用额外内存
4. D保证 O(1) 的查找，因为每个节点都存有指向其他所有节点的指针