2021-2022-1期中卷¶
2020级
一、简答题(本题15分，每题各5分)¶
-
循环不变式有三个性质：初始化、保持和终止。请问分别是什么含义?
-
什么是动态规划?有两种具体实现方式，各是什么?
-
什么是平衡二叉树?红黑树是一种二叉平衡树，请介绍红黑树的5个特点。
二、算法复杂度分析(本题15分，每题各5分)¶
-
对于规模为n的输入，算法A运行 \(4n^2\) 步，算法B运行 \(128n \lg n\) 步。当n满足什么条件时，A算法优于B算法?
-
对于下列每个递归式，给出 \(T(n)\) 的渐近上界和下界。假定 \(n \le 2\) 时，\(T(n)\) 是常数。给出尽量紧确的界，并验证其正确性。
\(T(n)=2T(n/2)+n^4\)
\(T(n)=16T(n/4)+n^2\)
\(T(n)=T(n-2)+n^2\)
\(T(n)=7T(n/2)+n^2\)
\(T(n)=T(n-1)+n\)
-
证明：考虑函数 \(f(n)\)，如果 \(f(n) \in o(g(n))\)，则 \(f(n) \notin \omega(g(n))\)。(注：\(\notin\) 表示不属于)
三、算法基础(本题15分，每题各5分)¶
-
已知算法以概率 \(p\) 输出1，以概率 \(1-p\) 输出0，且 \(0 < p < 1\)。现拟基于算法A设计算法B，能以概率 \(1/2\) 返回0，以概率 \(1/2\) 返回1。请描述算法B，并分析其期望运行时间。
-
令a、b、c和d表示4个实数，如何仅用3次乘法计算出 \(ac-bd\) 和 \(ad+bc\)。
-
证明或者反驳以下猜测。 (1) \(f(n)+g(n)=\Theta(\max(f(n),g(n)))\) (2) \(f(n)=O(g(n))\) 蕴含 \(g(n)=\Omega(f(n))\)
四、排序与顺序统计量(本题20分，每题各5分)¶
-
描述一个运行时间为 \(O(n \lg n)\) 的算法，给定 \(n\) 个整数的集合 \(S\) 和另一个整数 \(x\)，该算法能确定 \(S\) 中是否存在两个其和刚好为 \(x\) 的元素。
-
快速排序法的 PARTITION 函数使用了循环不变式。请解释初始化、保持和终止各是什么?
-
说明在数组 \(A = \langle 13, 19, 3, 6, 4, 8, 11, 18, 9 \rangle\) 上执行 PARTITION 操作的过程，画出数组的变化情况。
-
算法 SELECT 将输入元素每5个元素分为一组，从而在线性时间内可解。如果分成每组3个元素，还是线性时间吗?为什么?
五、树(本题20分，每题各5分)¶
-
将关键字 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 连续地插入一棵初始为空的红黑树之后，试画出该红黑树。
-
以图中的红黑树为基础，插入元素，请画出新的红黑树。 (1) 仅插入2； (2) 仅插入20。
-
假设一棵二叉搜索树中的结点在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 (4) 2, 399, 387, 219, 266, 382, 381, 278, 363 (5) 935, 278, 347, 621, 299, 392, 358, 363
-
考虑一棵二叉搜索树 \(T\)，其关键字互不相同。如果 \(T\) 中的一个结点 \(x\) 的右子树为空，且 \(x\) 有一个后继 \(y\)。请结合树的结构，说明节点 \(y\) 和 \(x\) 之间的关系 (提示：可以说明 \(y\) 和 \(x\) 之间的祖先/子孙关系和左/右节点关系)。
六、动态规划(本题15分，每题各5分)¶
-
对矩阵规模序列 \(\langle 5, 15, 12, 5, 5 \rangle\)，求矩阵链最优括号化方案。
-
对输入链长度为 \(n\) 的矩阵链乘法问题，描述其子问题图包含多少个顶点?多少条边?这些边分别连接哪些顶点?
-
钢条价格表如下所示。现在假设每次切割都需要有额外开销2。请设计动态规划方法来求解最优切割方案。
| 长度 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 价格 | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30 |