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

在无向图中，顶点的度是什么？

1. A它在邻接表中的位置
2. B与它相连的边数
3. C图中顶点的个数
4. D从它出发的最长路径的长度

最大堆性质是什么？

1. A每个左子节点的键都大于或等于其右兄弟的键
2. B键从左到右排好序
3. C所有叶子都包含最大键
4. D每个父节点的键都大于或等于其子节点的键

数组的元素在内存中是如何存储的？

1. A在一整块连续的内存中，一个接一个地存放
2. B存放在由内存页组成的树中
3. C存放在由哈希选择的随机位置
4. D分散存放，通过指针相连

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

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

把键 50、30、70、20、40 按此顺序插入一棵空的二叉搜索树。30 的左子节点是什么？

1. A40
2. B70
3. C20
4. D50

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

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

在一棵根为 50、左子树为 30（子节点 20、40）、右子树为 70（子节点 60、80）的 BST 中，用中序后继删除根。哪个键成为新的根？

1. A40
2. B70
3. C80
4. D60

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

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