### 25年秋DSA期末

一、签到题 ($5'$)

	1. 抄一遍加粗字体;
	1. 算一遍总分;

二、判断题 ($1' \times 20 = 20'$)

(记不住了)

三、大题 ($5' + 5' + 8' + 8' + 8' + 12' + 12' + 12' + 17' = 87'$)

(分数有点记不准了, 但总共应该是 $112$ 分)

1. $1-2n+1$ 个数, 从中抽三个数, 取中间数. 问中间数是中位数的概率. 若 $n=4$, 计算这个概率.

2. Linear Select. 问下一个递归范围最大为多少. 并给出构造.

3. $2025$个区间构建区间树. 问最大平衡因子; 并且给出对应构造.

4. 把一个节点插入红黑树成为根节点, 应该满足什么条件?

5. $2024$ 个 $\circ$和$1$个 $\times$, 做KMP算法, 问改进版next数组的最大和.

6. 某个大小的左式堆交换次数最大值.

7. 一个avl tree: 删除某个节点, 两个祖先没有被修改, 三个祖先被修改. 问最小树大小.

8. 给定一个pattern $P$ . 构造字符串 $T$, 使得BM算法的gs表 (???). (不会也没记住🥺)

9. $[0,1)$ 范围有 $n$ 个点.

   (1) 给定区间 $[a, a+\dfrac{1}{n})$, 问落在其中的点的个数的分布与期望; 问所有点都不在其中的概率, 以及当 $n \to \infty$时这个概率.

   (2) 设计一个算法: $O(n)$ 预处理, $\text{expected-} O(1)$查询据某个点 $p \in [0,1)$ 最近的点. (i) 算法设计与伪代码; (ii) 正确性; (iii) 复杂度证明.



***小结***

1. 大题基本都是构造题
2. 判断题和仓库关联没那么大