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

什么是带权图？

1. A有些顶点因为边更多而比其他顶点更重的图
2. B边数多于顶点数的图
3. C存储在磁盘上的图
4. D每条边都有一个数值（如代价或距离）的图

静态数组与动态数组的主要区别是什么？

1. A动态数组可以通过移到更大的内存块来增长
2. B静态数组的下标访问更慢
3. C静态数组只能存储数字
4. D动态数组把元素存储在链接的节点中，因此可以一次增长一个

在树中，什么是兄弟节点？

1. A位于不同子树中同一深度的节点
2. B一个节点及其父节点
3. C没有子节点的节点
4. D拥有同一个父节点的节点

Dijkstra 算法使用哪种抽象数据类型来选择下一个要处理的顶点？

1. AFIFO 队列
2. B最小优先队列
3. C栈
4. D无序集合

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

1. A(i − 1) mod n
2. B2i + 1
3. C(i + 1) mod n
4. Di + 1

如何向二叉堆中插入一个新元素？

1. A从头重建整个堆
2. B通过把所有更大的元素右移一位，将它插入到有序位置
3. C把它放在数组末尾，只要它违反堆性质就将其上浮（sift up）
4. D把它放在根上，再将其下沉（sift down）

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

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

红黑树的规则对含 n 个键的树的高度给出了什么保证？

1. A高度恰好为 log₂ n
2. B高度至多为 log₂ n + 1
3. C高度至多为 2 log₂(n + 1)
4. D高度至多为 n / 2