Problem I: [CSP-S1][选择] 高级数据结构1

1. 以下哪种数据结构支持快速查找中位数？

A. 二叉搜索树

B. 堆

C. 平衡二叉搜索树（AVL树）

D. 哈希表

2. 在AVL树中插入一个结点后，若发现平衡因子为2，则需要进行（ ）。

A. 左旋

B. 右旋

C. 先左旋后右旋

D. 旋转类型取决于不平衡结点的位置

3. 红黑树中，从根到叶结点的最长路径长度不超过最短路径长度的（ ）。

A. 1倍

B. 2倍

C. log n 倍

D. 不确定

4. 以下关于并查集的说法正确的是（ ）。

A. 仅支持合并操作

B. 仅支持查询操作

C. 支持合并和查询操作

D. 不支持路径压缩

5. 在Trie树中插入一个长度为k的字符串，时间复杂度为（ ）。

A. O(k)

B. O(k log k)

C. O(k^2)

D. O(1)

6. 线段树主要用于处理（ ）。

A. 字符串匹配

B. 区间查询与更新

C. 最短路径

D. 最小生成树

7. 堆排序的时间复杂度是（ ）。

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

8. 树状数组（Fenwick Tree）支持的操作是（ ）。

A. 单点更新，区间查询

B. 区间更新，单点查询

C. 区间更新，区间查询

D. 单点更新，单点查询

9. 在红黑树中，新插入的结点初始颜色是（ ）。

A. 红色

B. 黑色

C. 由父结点决定

D. 随机

10. 并查集在最优情况下的查询时间复杂度是（ ）。

A. O(1)

B. O(log n)

C. O(n)

D. O(α(n))