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

向栈顶添加元素的栈操作叫什么？

1. APeek
2. BEnqueue
3. CPop
4. DPush

二叉最小堆中最小的元素在哪里？

1. A在数组的最后一个位置
2. B在某个叶子上，必须进行查找
3. C在最左边的叶子上
4. D在根上

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

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

一个道路网络有 100,000 个路口，每个路口大约与另外 4 个路口相连。哪种表示方法最合适？

1. A邻接表
2. B一个由边组成的二叉堆
3. C邻接矩阵
4. D一个有序的顶点数组

一棵高度为 h（以边数计）的满二叉树有多少个节点？

1. A2^h
2. Bh²
3. C2^h+1 − 1
4. D2h + 1

AVL 树和红黑树保证：

1. A键按插入顺序存储
2. B通过再平衡使高度为 O(log n)
3. C没有节点拥有两个子节点
4. D在任何情况下查找都是常数时间

为什么数据库常用 B+ 树而不是普通的 B 树来建立索引？

1. AB+ 树使用二叉内部节点，从而减少磁盘读取次数
2. BB+ 树只在根中存储数据
3. C所有记录都在相互链接的叶子中，使范围扫描很高效
4. DB+ 树不需要保持平衡

建立在 n 个数的数组上的树状数组（Fenwick tree，binary indexed tree）以 O(log n) 支持哪些操作？

1. A在任意位置插入元素
2. B对数组排序和二分查找
3. C以 O(1) 求中位数
4. D前缀和查询和单个元素更新