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

在二叉搜索树中，某节点左子树中的值：

1. A大于该节点的值
2. B顺序随机
3. C小于该节点的值
4. D等于该节点的值

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

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

作为抽象数据类型，集合（set）的定义性特征是什么？

1. A它按有序方式存储元素
2. B它只允许在一端访问
3. C它存储键值对
4. D它存储元素且没有重复

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

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

为什么二叉堆可以不用任何指针而存储在数组中？

1. A数组会自动使键保持有序，因此不需要指针
2. B堆中的元素从不超过 100 个
3. C堆中所有的键都相等
4. D它是完全二叉树，因此位置遵循简单的下标公式

Dijkstra 算法使用哪种抽象数据类型来选择下一个要处理的顶点？

1. A无序集合
2. B栈
3. CFIFO 队列
4. D最小优先队列

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

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

把键 5、3、8、1 按此顺序插入一个空的基于数组的二叉最小堆。最终的数组是什么？

1. A[1, 3, 5, 8]
2. B[1, 3, 8, 5]
3. C[3, 1, 8, 5]
4. D[1, 5, 8, 3]