### 一. 判断题(12x2=24分):

1. 对合法的表达式, 左括号一定等到自己的右括号才弹出
2. 总和最大区段, 如果存在两个最大 $2025$, 那么不重叠
3. Hopcraft一定满足 `T[F[k]]=k`
4. one-pass, 直方图的元素单调, 则最大栈是 $O(\log n)$
5. $\log \prod k^2 = O(n\log^2n)$
6. 插入排序不导致轮换减少
7. `list::merge_sort`是inplace的
8. 某个栈混洗是否合法
9. bubble排序中, 所有元素一定会朝着自己最终的位置移动
10. 多个括号匹配, 用计数算法, 能把正确的判断为错的
11. 调用栈里, 同一个函数的栈帧必然相邻
12. 总共12个, 但是想不起来了, 顺序不做任何保证

### 二. 填空(6x4=24分):

1. $T(n) = \sum 64^k T(n/2^k) + O(\sqrt[2025] \sum_{k=6}^{25} n^{k^3})$

2. 手动模拟带压缩的最大队列, 求`queue.pop_rear`的所有元素
3. 版本C的二分查找, 如果查找长度最小为 $5$, 求最少元素个数
4. $100$ 个元素, 有 $4560$ 个逆序对, $[10, 80)$ 区段最少逆序对个数
5. 列表 `2025, 2024, ... , 1`, 进行交换式的插入排序, 求冗余次数
6. 对频数`2025, 1013, 507, 254, x`做哈夫曼算法, 形成重复, $x$可以是多少?

### 三. 大题(6+10+16+20=52分):

1. (6分) 扩容`expand()`按照$\{1^2, ... , n^2\}$进行, insert $n$次, 求消耗时间.

2. (5+5=10分) 有一个由 $2025$ 个二元运算符构成的表达式 $s$, 有表达式树$et(s)$, 逆波兰表达式 $rpn(s)$, 表达式树满足对任意节点`v` `size(lc(v)) >= size(rc(v)) - 2 `, 求rpn计算过程中的最大栈容量. 并说明什么时候能够取到, 并画出树的图.

3. (2+2+2+10=16分) 

   ```cpp
   void fn(int* A, int n){
     for(int k=0;k<n;){
       for(int i=0;A[i]!=A[k];++k);
       if(i!=k){
         while(++k<n){
           a[i-1] = a[i];
         }
         --n;
       } else{
         ++k;
       }
     }
   }
   ```

   1. 函数作用;
   2. 给定`2 0 2 5 1 1 0 9` , `CMP`和`MOV`各多少次?
   3. 给定`忘了` , `CMP`和`MOV`各多少次?
   4. 证明`CMP`次数和`MOV`次数之和只和`n`有关.

4. (4+4+8+4=20分) 后缀+层次重建多叉树

   1. 给定一颗多叉树的层次遍历和后序遍历, 进行重建;
   2. 给出层次遍历和后序遍历构造先序遍历的算法思路和原理, 要求时间复杂度$O(n)$, 辅助空间复杂度$O(n)$;
   3. 给出伪代码;
   4. 证明算法复杂度满足要求.