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

栈的 peek（或 top）操作做什么？

1. A返回栈底元素
2. B删除栈中所有元素
3. C删除栈顶元素并返回它
4. D返回栈顶元素但不删除它

在图的邻接表表示中，每个顶点存储什么？

1. A一行 V 个布尔值
2. B到其他每个顶点的最短路径
3. C图中边的总数
4. D其相邻顶点的列表

哈希表的负载因子是什么？

1. A迄今为止的冲突次数
2. B从磁盘加载表所需的时间
3. C已存储元素的个数除以桶的个数
4. D桶的个数除以所存储键的平均长度

在字母表固定的字典树中查找一个长度为 L 的单词需要多长时间？

1. AO(n)，其中 n 是单词个数
2. BO(log n)，其中 n 是单词个数
3. CO(L)，与存储了多少个单词无关
4. DO(L × n)

一棵二叉树的根为 1，左子节点为 2，右子节点为 3；节点 2 的子节点为 4（左）和 5（右）。前序遍历的结果是什么？

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C1 2 3 4 5
4. D4 5 2 3 1

在存储于容量为 n 的数组中的循环队列里，下标 i 之后的下一个位置如何计算？

1. A2i + 1
2. Bi + 1
3. C(i + 1) mod n
4. D(i − 1) mod n

在简单均匀哈希假设下，在含 n 个键、m 个桶的拉链法哈希表中查找的期望时间是多少？

1. AO(log n)
2. BO(n)
3. CO(m)
4. DO(1 + α)，其中 α = n / m

对以邻接矩阵存储的、有 V 个顶点的图进行广度优先搜索，运行时间是多少？

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