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

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

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

通常用哪种结构来实现优先队列？

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下标 2i + 1
2. B下标 i − 1
3. C下标 ⌊(i − 1) / 2⌋
4. D下标 ⌊i / 2⌋ + 1

如果按已排序的顺序插入键，含 n 个节点的二叉搜索树在最坏情况下的高度是多少？

1. An（退化为链表）
2. B1
3. Clog₂ n
4. D√n

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

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

在二叉堆中（已知元素位置），decrease-key 操作的时间复杂度是：

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