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

树的高度通常定义为：

1. A树中叶子的个数
2. B根的子节点个数
3. C从根到叶子的最长路径上的边数
4. D树中节点的总数，包括根和每个叶子

删除队首元素的队列操作叫什么？

1. AEnqueue
2. BPush
3. CInsert
4. DDequeue

在单链表中，每个节点包含：

1. A数据和指向所有其他节点的引用
2. B只有数据
3. C数据和一个索引
4. D数据和指向下一个节点的引用

在使用开放寻址法的哈希表中，可能的最大负载因子是多少？

1. A0.5
2. B2
3. C1
4. D没有最大值

深度优先搜索（迭代版本）使用哪种数据结构？

1. A仅哈希表
2. B栈
3. C队列
4. D堆

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

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

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

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

你必须用 O(k) 的内存从 n 个数的数据流中保留最小的 k 个值。哪种方法能在 O(n log k) 时间内完成？

1. A一个包含全部 n 个值的有序数组
2. B一个保存全部 n 个值的最小堆，最后从中弹出 k 个最小值
3. C一个保存最后 k 个值的 FIFO 队列
4. D一个大小为 k 的最大堆，当出现更小的值时替换其根