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

对树进行层序遍历时使用哪种数据结构？

1. A哈希表
2. B队列
3. C优先队列
4. D栈

什么是带权图？

1. A存储在磁盘上的图
2. B每条边都有一个数值（如代价或距离）的图
3. C有些顶点因为边更多而比其他顶点更重的图
4. D边数多于顶点数的图

树中节点的深度是：

1. A该节点的子节点个数
2. B从根到该节点的边数
3. C其子树中的节点个数
4. D从该节点到最深叶子的边数

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

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

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

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

在用数组存储的二叉最小堆（索引从 0 开始）中，索引为 i 的节点的子节点位于：

1. Ai/2 和 i/2 + 1
2. B2i + 1 和 2i + 2
3. Ci + 1 和 i + 2
4. D2i 和 2i + 1

一个 AVL 节点失衡，原因是其左子节点的右子树变得过高（左右情况）。应采用哪种修正？

1. A在该节点处进行一次左旋
2. B在该节点处进行一次右旋
3. C先在左子节点处右旋，再在该节点处左旋
4. D先在左子节点处左旋，再在该节点处右旋

如何只用 O(1) 的额外内存检测一个单链表中是否有环？

1. A计数节点，直到计数超过链表的长度字段
2. B让一个指针每次走一步，另一个每次走两步，检查它们是否相遇
3. C把每个访问过的节点存入一个哈希集合
4. D对链表排序并寻找重复元素