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

图由什么组成？

1. A只有根和叶子
2. B只有键和哈希值
3. C由边（edge）连接的顶点（vertex，即节点）
4. D行和列

什么是带权图？

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

作为抽象数据类型，集合（set）的定义性特征是什么？

1. A它只允许在一端访问
2. B它按有序方式存储元素
3. C它存储键值对
4. D它存储元素且没有重复

检查 "{[()]}" 中的括号是否匹配，使用哪种数据结构？

1. A二叉搜索树
2. B栈
3. C哈希表
4. D队列

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

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

用两个栈实现一个队列：入队时压入 "in" 栈，出队时从 "out" 栈弹出，"out" 栈为空时从 "in" 栈重新填充。每次操作的均摊代价是多少？

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

红黑树必须满足哪条性质？

1. A从任一节点到其所有后代叶子的每条路径上，黑色节点的数量都相同
2. B根节点必须是红色
3. C每个节点都必须是红色
4. D每个红色节点的子节点必须是红色，因此红色节点总是沿着通向叶子的路径连成不间断的链

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

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