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

哈希表以什么形式存储数据？

1. A通过哈希函数定位的键值对
2. B定长字符串
3. C仅为有序列表
4. D键有序的树

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

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

哪种操作对数组是 O(1)，对单链表却是 O(n)？

1. A访问下标为 i 的元素
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(log n)
3. CO(1)
4. DO(n²)

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

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

在循环缓冲区中，front == rear 既可能表示空，也可能表示满。区分它们的一种常见方法是什么？

1. A另外保存一个元素计数，或者始终留一个槽位不用
2. B使缓冲区大小为 2 的幂
3. C每当 front 等于 rear 时就始终清空缓冲区，使其状态为空
4. D把 front 和 rear 存储在同一个变量中