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

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

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

哪种操作在数组中很慢，但在链表头部却很快？

1. A通过索引读取最后一个元素
2. B求定长数组的长度
3. C访问第 5 个元素
4. D在开头插入元素

什么是双端队列（deque）？

1. A按优先级排序的队列
2. B只允许在尾部删除的队列
3. C共享一个数组的两个独立队列
4. D允许在两端插入和删除的结构

含 V 个顶点的图的邻接矩阵占用多少内存？

1. AO(E)
2. BO(log V)
3. CO(V + E)
4. DO(V²)

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

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

一个大小为 7 的哈希表使用 h(k) = k mod 7 和线性探测。插入 10 之后，17 存放在哪里？

1. A下标 4
2. B下标 6
3. C下标 0
4. D下标 3

线段树（segment tree）通常用于：

1. A存储图的边
2. B在 O(log n) 时间内处理区间查询（如区间求和）和更新
3. C通过把每个前缀存储在单独的树节点中，按字母顺序对字符串排序
4. D实现栈

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

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