2022-2023-2期中卷

一、简答题(本题15分，每题各5分)

1. 循环不变式有三个性质：初始化、保持和终止。请问分别是什么含义?

2. 动态规划和分治策略是两种典型的算法设计思想。Strassen 算法是一种采用分治策略的矩阵相乘算法。这个算法设计是否也符合动态规划思想?请说明理由。

3. 关于插入排序算法的最坏复杂度，有 \(O(n^3), O(n^2), \Theta(n^2), \Omega(n^2), \Omega(n)\) 等多种说法。哪些说法是正确的，哪些说法是不正确的?

二、算法复杂度分析(本题20分，第1小题5分，第2小题15分)

1. 对于规模为 \(n\) 的输入，算法A运行 \(128n\) 步，算法B运行 \(4n \lg n\) 步。当满足什么条件时，A算法优于B算法?

2. 对于下列每个递归式，给出 \(T(n)\) 的渐近上界和下界。假定 \(n \le 2\) 时，\(T(n)\) 是常数。给出尽量紧确的界，并验证其正确性。(每个式子3分)

​ \(T(n)=3T(n/3)+n^3\)

​ \(T(n)=27T(n/3)+n^3\)

​ \(T(n)=T(n-2)+n^2\)

​ \(T(n)=7T(n/5)+n^2\)

​ \(T(n)=T(n-1)+n\)

三、算法基础(本题10分，每题各5分)

1. 设计算法，仅使用三次实数乘法即可完成复数 \(a+bi\) 和 \(c+di\) 相乘。算法需要接收a、b、c和d为输入，分别生成实部 \(ac-bd\) 和虚部 \(ad+bc\)。

2. 假设 \(f(n)\) 和 \(g(n)\) 都是渐进非负函数，\(100f(n)+1000g(n)=\Theta(\max(f(n),g(n)))\) 是否正确?请说明理由。

四、排序与顺序统计量(本题15分，每题各5分)

1. 给定几个数，已知这些数是在 \(0-n^2\) 之间的正整数。如果想要对这些数进行排序，比较堆排序和计数排序，哪个算法运行速度快?哪个算法具有稳定性，为什么?

2. 说明在数组 \(A = \langle 1, 11, 25, 44, 7, 5, 38, 28, 9 \rangle\) 上执行 PARTITION 操作的过程，画出数组的变化情况。

3. 假设用 RANDOMIZED-SELECT 去选择数组 \(A = \langle 1, 11, 25, 44, 7, 5, 38, 28, 9 \rangle\) 的最大元素。请给出导致最坏情况发生的一个划分序列。

五、数据结构(本题25分，每题各5分)

1. 令 \(A = \langle 1, 11, 25 \rangle\) 和 \(\langle 44, 7, 5, 38 \rangle\) 是两个序列，请用多数组方式(长度为10)画出合法的存储方式，需要注明自由表和两个链表。

2. 用开放寻址法将关键字 11, 25, 44, 7, 5, 38 插入到一个长度为9的散列表中。辅助散列函数为 \(h(k)=k \bmod 9\)。请用线性探查方法进行操作。

3. 将关键字 1, 11, 25, 44, 7, 5, 38 连续地插入一棵初始为空的红黑树之后，试画出该红黑树(每插入一个数，画一张图)。

4. 以图中的红黑树为基础，插入元素，请画出新的红黑树。 (1) 仅插入6； (2) 仅插入24。

1. 假设一棵二叉搜索树中的结点在1到1000之间。现在想要查找数值为363的结点。下面序列中哪个不是查找过的序列。 (1) 2, 252, 401, 398, 330, 344, 397, 363 (2) 924, 220, 911, 244, 898, 258, 362, 263 (3) 925, 202, 911, 240, 912, 245, 363

六、动态规划(本题15分，每题各5分)

1. 对矩阵规模序列 \(\langle 2, 3, 4, 5, 2 \rangle\)，求矩阵链最优括号化方案

2. 假设某个运动员在爬楼梯时可以一次性爬一级台阶、二级台阶和四级台阶。则他从平地爬到第10级楼梯时，总共有几种方法? （只写答案得2分；写出步骤再得3分）

3. 钢条价格表如下所示。现在假设每次切割都需要有额外开销1。请设计动态规划方法来求解最优切割方案。

长度	1	2	3	4	5	6	7	8	9	10
价格	1	3	4	6	8	10	11	15	20	22