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

什么是双端队列（deque）？

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

树的高度通常定义为：

1. A树中叶子的个数
2. B根的子节点个数
3. C树中节点的总数，包括根和每个叶子
4. D从根到叶子的最长路径上的边数

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

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

一个道路网络有 100,000 个路口，每个路口大约与另外 4 个路口相连。哪种表示方法最合适？

1. A一个有序的顶点数组
2. B邻接表
3. C一个由边组成的二叉堆
4. D邻接矩阵

如果按已排序的顺序插入键，含 n 个节点的二叉搜索树在最坏情况下的高度是多少？

1. An（退化为链表）
2. B√n
3. C1
4. Dlog₂ n

为什么二叉堆可以不用任何指针而存储在数组中？

1. A堆中所有的键都相等
2. B堆中的元素从不超过 100 个
3. C它是完全二叉树，因此位置遵循简单的下标公式
4. D数组会自动使键保持有序，因此不需要指针

在 Kruskal 最小生成树算法中，并查集结构用来做什么？

1. A检查一条边的两个端点是否已经连通
2. B在搜索过程中存储每个顶点到源点的当前距离
3. C选择起始顶点
4. D按权重对边排序

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

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