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

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

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

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

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

二叉树的后序遍历按什么顺序访问节点？

1. A先右子树，再节点，最后左子树
2. B先左子树，再节点，最后右子树
3. C先左子树，再右子树，最后节点
4. D先节点，再左子树，最后右子树

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

1. A1
2. B没有最大值
3. C2
4. D0.5

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

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

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

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

采用按秩合并（union by rank）和路径压缩（path compression）的并查集（union-find，不相交集合），每次操作的均摊代价为：

1. AO(n)
2. BO(n²)
3. C恰好 O(log n)
4. DO(α(n))，即反阿克曼函数，实际上可视为常数

哪种结构能以总共 O(n) 的时间求出数组中每个大小为 k 的窗口的最大值？

1. A通过移动元素来更新的有序数组
2. B一个按值递减顺序保存下标的双端队列
3. C由窗口元素组成的单链表
4. D为每个窗口重建的最小堆