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

哈希表中的哈希函数做什么？

1. A把键映射到表中的一个下标
2. B统计存储了多少个键
3. C对表中的键排序
4. D对表中的值加密

双向链表中的每个节点包含什么？

1. A两份数据和一个指针
2. B数据、指向下一个节点的指针和指向前一个节点的指针
3. C只有数据和指向下一个节点的指针
4. D数据和两个指针，一个指向下一个节点，一个指向再下一个节点

在树中，什么是兄弟节点？

1. A一个节点及其父节点
2. B位于不同子树中同一深度的节点
3. C没有子节点的节点
4. D拥有同一个父节点的节点

在从下标 0 开始存储于数组中的二叉堆里，下标为 i 的节点的父节点在哪里？

1. A下标 ⌊i / 2⌋ + 1
2. B下标 2i + 1
3. C下标 i − 1
4. D下标 ⌊(i − 1) / 2⌋

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

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

AVL 树在每个节点上维持什么平衡条件？

1. A每个节点的两棵子树包含完全相同数量的节点
2. B左右子树的高度之差至多为 1
3. C每个节点都被着成红色或黑色
4. D所有叶子都恰好位于同一深度

布隆过滤器（Bloom filter）回答"该元素是否在集合中？"时：

1. A可能出现假阴性，但不会出现假阳性
2. B只能回答数字的情况
3. C可能出现假阳性，但不会出现假阴性
4. D总是给出精确答案

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

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