2. (卷 1)已知 f1(n)=Θ(g1(n))，f2(n)=Θ(g2(n))，请问是否有 f1(n)+ f2(n)= Θ( max( g1(n),g2(n) ) )?
解：存在������1(n) + ������2(������) = ������(max(������1(������), ������2(������) 证明： ������1(������) = ������(������1(n)) 则存在 a1>0，a2>0, n1>0 使得 n>n1 时有 ������1 ∗ ������1(n) < ������1(������) < ������2 ∗ ������1(n) ������2(������) = ������(������2(n)) 则存在 b1>0，b2>0, n2>0 使得 n>n2 时有 ������1 ∗ ������2(n) < ������2(������) < ������2 ∗ ������2(n) 取 c1=min(a1,b1) >0, c2=2*max(a2,b2) >0, n0=max(n1,n2)>0 当 n>n0 时，有 ������1(n) + ������2(������) > ������1 ∗ ������1(n) + ������1 ∗ ������2(n)
= ������2(������������ − 5 ������������������������) − 2������ > 2������3 − 2������ > 2������0(������02 − 1) =12 即当 c=7, n0=2 时，对 n>n0, 5������2������������������������ + 2������ < ������������3恒成立， 5������2������������������������ + 2������ = ������(������3)
������������������������������ = ������������������23 < 2
则存在0 < ε < 2 − ������������������������������,有f(n) = Ω(������������������������������������+������)
(1)
T(n-1)=3T(n-2)+(n-2)2
T(n)-T(n-1) = 3T(n-1)+(n-1)2 -3T(n-2)-(n-2)2 = 3T(n-1)-3T(n-2)+2n-3
T(n)-T(n-1)+n = 3(T(n-1)-2T(n-2)+n-1)
令 c(n)= T(n)-T(n-1)+n，则有 c(n)=3c(n-1)。
4
6
4
6
13
17
21
24
13
17
21
2
19
83
27 29 14 2
12
4
6
13
17
14
2
19 8 3
27 29 12
14 24
4
6
13
3
14
2
19
83
27 29 21 24
19 8 17 27 29 21 24
12
4
6
8
3
14
2
19 13 17 27 29 21 24 12
3
2
8
4
14
6
19 13 17 27 29 21 24
解：没有 f1(n)+ f2(n)= Θ( min( g1(n),g2(n) ) ) 反例： 令 g1(n)=3n2+n, f1(n)=n2。 g2(n)=3n3+n, f2(n)=n3。 min(g1(n), g2(n))= g1(n), Θ( min( g1(n),g2(n) ) )= n2。 f1(n)+f2(n)= n3+ n2 显然 f1(n)+f2(n) ≠ Θ( min( g1(n),g2(n) ) )。
af
n (b)
=
3 4
∗
������2
−
21 2
∗
������
+
5
取 c=7/8 <1,n0=2,当 n>n0 时，有
n c ∗ f(n) − af (b)
=
(������
−
3 4)
∗
������2
+
21
− 14������ 2
∗
������
+
5(������
−
1)
21 − 14������ > 2 ∗ ������ − 5
由于 T(1)=1,则 T(2)=4，c(2)=T(2)-T(1)+2=5
则 c(n)=5*3n-2，
T(n)-T(n-1)+n=5*3n-2
(2)
将(1)式和(2)式联合求解可得
T(n)=(5*3n-1-n2-n-1)/2
(卷 2)求解递归方程 T(n)=2T(n-1)+ n2-2n+1。
解：
T(n)=2T(n-1)+(n-1)2
Min-堆的过程。
解：调整过程如下，带
的节点表示正在调整以该节点为根的堆为小根堆。
12
4
16
3
7
21
22
15 8 5
28 20 9 11
12
4
16
3
7
9
11
12
4
16
3
7
21
11
15
85
28 20 9 22
12
4
16
3
5
9
11
15
85
28 20 21 22
12
4
16
3
5
9
11
15
87
28 20 21 22
> 2������ − 5
> 2������0 − 5 = 1
即af
(n)
b
≤
������������(������),满足主定理第三条
综上，T(n) = Θ(f(n)) = Θ(������2)
(卷 2)求解递归方程 T(n)=3T(n/2)+n2-7n+5。
解：
采用主方法
a = 3, b=2, f(n) = ������2 − 7������ + 5
12
4
2
8
3
14
6
19 13 17 27 29 21 24 2
3
12
8
4
14
6
19 13 17 27 29 21 24
2
3
6
8
4
14
12
2
3
6
8
4
14
12
19 13 17 27 29 21 24
19 13 17 27 29 21 24
2、 (卷 1) 请在图 1 所示的红黑树中先插入关键字为 23 的结点，在插入关键字为 21 的结 点，给出具体的变化过程。
af
n (b)
=
4 9
∗
������2
−
28 3
∗
������
+
5
取 c=5/9 < 1,n0=3,当 n>n0 时，有
c
∗
f(n)
−
af
n (b)
=
(������
−
4 9)
∗
������2
+
28
− 21������ 3
∗
������
+
5(������
−
1)
28 − 21������ > 3 ∗ ������ − 5
题目分卷 1 和卷 2，不分说明两卷相同。
一、基本题 1. (卷 1)请证明������������������������������������������ + ������������ = ������(������������)。
证明：取 c=7, n0=2,对 n>n0 有 c������3 − 5������2������������������������ − 2������
A
4
图1 解：第一幅图为在图 1 中插入结点 23
插入结点 23
改变颜色 左旋
右旋
插入结点 21
(卷 2)请在图 1 所示的红黑树中先插入关键字为 37 的结点，再插入关键字为 32 的结点， 给出具体变化过程。
图1 解答：从原图基础上开始画变化过程下
插入结点 37
左旋 右旋 插入结点 32
改变颜色
3. (卷 1)求解递归方程 T(n)=4T(n/3)+n2-7n+5。
解：
采用主方法 a = 4, b=3, f(n) = ������2 − 7������ + 5
������������������������������ = ������������������34 < 2 则存在0 < ε < 2 − ������������������������������,有f(n) = Ω(������������������������������������+������)
综上，������1(n) + ������2(������) = ������(max(������1(������), ������2(������) (卷 2)已知 f1(n)=Θ(g1(n))，f2(n)=Θ(g2(n))，请问是否有 f1(n)+ f2(n)= Θ( min( g1(n),g2(n) ) )?