发布时间 : 星期三 文章华中科技大学《算法设计与分析》复习参考题更新完毕开始阅读5f825ebb1a37f111f1855bf5
1．什么是算法？算法必须满足的五个特性是什么？
算法：一组有穷的规则，规定了解决某一特定类型问题的一系列运算。（有限指令的集合，遵循它可以完成一个特定的任务）.
必须满足的五个特性是(遵循以下五条准则)： 1．有穷（限）性 2．确定性
3．可（能）行性 4．输入（n≥0） 5．输出（n≥1） 2．对算法进行分析分哪两个阶段？各自完成什么任务（分别得到什么结果）？
对一个算法要作出全面的分析可分成两个阶段进行，即：事前分析和事后测试。
事前分析求出该算法的一个时间界限函数；
事后测试搜集此算法的执行时间和实际占用空间的统计资料。
3．证明：若f1(n)=O(g1(n))并且f2(n)= O(g2(n))，那么f1(n) +f2(n)= O(max{g1(n), g2(n)}
证明：
根据f1(n)=O(g1(n))可知，存在正常数C1，当n≥n0时，使得|f1(n)|≤C1|g1(n)|； 同理，根据f2(n)= O(g2(n))可知，存在正常数C2，当n≥n0时，使得|f2(n)|≤C2|g2(n)| 当n≥n0时，|f1(n)+f2(n)|≤|f1(n)|+|f2(n)|≤C1|g1(n)|+C2|g2(n)| ≤C1|gk(n)|+C2|gk(n)|
≤（C1+C2）|gk(n)|， 其中gk(n)=max{g1(n),g2(n)}，k={1,2}
当n≥n0时，取C=（C1+C2），据定义命题得证。
4．如果f1(n)= Θ(g1(n))并且f2(n)= Θ(g2(n))，下列说法是否正确？试说明之。
（a） f1(n) +f2(n)= Θ(g1(n)+ g2(n))
（b） f1(n) +f2(n)= Θ(min{g1(n), g2(n)}) （c） f1(n) +f2(n)= Θ(max{g1(n), g2(n)}) 答：（a）和（c）均正确，（b）错误。
（a）正确可以根据定义直接证得。
（b）错误可举反例。例：f1(n)= 2n，f2(n)=2 n2 下面证明（c）正确性.
根据上题已经证明f1(n)+f2(n)= O(max{g1(n),g2(n)})，下面只需证明f1(n)+f2(n)= Ω(max{g1(n), g2(n)})，即存在正常数C，使得|f1(n)+f2(n)|≥C(max{g1(n), g2(n)})
根据f1(n)= Θ(g1(n))并且f2(n)= Θ(g2(n)) 得到，当n≥n0时，存在正常数C1、C2 、C3、C4
C1|g1(n)|≤|f1(n)|≤C3|g1(n)|
C2|g2(n)|≤|f2(n)|≤C4|g2(n)|
不妨设max{g1(n), g2(n)}= g1(n)
由于|f1(n)+f2(n)|≥||f1(n)|-|f2(n)||≥|C1|g1(n)|-C3|g2(n)||
=C|max{g1(n), g2(n)}|
取C≥|C1-C3|的正常数，由定义得 f1(n)+f2(n) = Ω(max{g1(n), g2(n)}) 命题得证。
5．证明 |「log2n」|= O(n)
证明：对于任意的正整数n，
|「log2n」|≤|log2（n+1）|≤|n+1|≤2|n| 取n0=1，C=2，根据定义知命题成立。
6．证明 3n「log2n」= O(n2)
2
证明：对于任意的正整数n，|3n「log2n」|≤|3n「log2n」|≤3|n| 取n0=1，C=3，根据定义知命题成立。
n7．用数学归纳法证明：当n≥1时，?i?n(n?1)/2.
i?1n证明：当n=1时，?i?1，n(n+1)/2=1，命题成立；
i?1n 假设n=k-1时，?i?n(n?1)/2成立;（k≥2）
i?1nn 当n=k时，?i?n(n?1)/2=?i?k(k?1)/2?k=k(k+1)/2
i?1i?1综上可知，命题成立。
8．在下列情况下求解递归关系式
?g(n)n足够小 T(n)= ?
否则?2T(n/2)?f(n)
当①n=2k g(n)= O(1)和f(n)= O(n)；
k
②n=2g(n)= O(1)和f(n)= O(1)。
解: T(n)=T(2k)=2 T(2k-1)+f(2k)=2(2 T(2k-2)+f(2k-1)) +f(2k) =22T(2k-2)+21 f(2k-1)+ f(2k) =??
=2kT(1)+2k-1f(2)+2k-2f(22)+?+20f(2k) =2kg(n)+ 2k-1f(2)+2k-2f(22)+?+20f(2k) ①当g(n)= O(1)和f(n)= O(n)时，
不妨设g(n)=a，f(n)=bn，a，b为正常数。则
T(n)=T(2k)= 2ka+ 2k-1*2b+2k-2*22b+?+20*2kb =2ka+kb2k
=an+bnlog2n= O(nlog2n)
②当g(n)= O(1)和f(n)= O(1)时，
不妨设g(n)=c，f(n)=d，c，d为正常数。则 T(n)=T(2k)=c2k+ 2k-1d+2k-2d+?+20d=c2k+d(2k-1)
=(c+d)n-d= O(n)
9．求解递推关系式：
h(n)?2h(n?1)?1
解：构造生成函数
H(x)?h(1)x?h(2)x???2h(1)?1?h(k)x
kk?1?求解H(x)
H(x)?h(1)x?h(2)x???2xH(x)??2h(1)x?2h(2)x??232
x (1?2x)H(x)?x?x2?x3???H(x)?x(1?2x)(1?x)1?x (x?1)
分解H(x)成幂级数 令H(x)?
?H(x)??11?x?11?2x2A1?x?B1?2x 则A=-1 B=1
??(1?x?x??)?(1?2x?(2x)?(2x)??)2nn223
?(2?1)x?(2?1)x???(2?1)x??
???(2k?1k?1)xk
所以?h(n)?2n?1
?T1?110．求解递推关系式：?
T?2T?2n?1?n解：
Tn?2Tn?1?2?2(Tn?2?2)?2?2Tn?2?2?2?222n?1T1?(2n?1???2)?3*2n?1?2
?F1?1?11．求解递推关系式：?F2?1
?F?F?F(n?2)n?1n?2?n解：以Fn为系数，构成生成函数F(x)
F(x)?F1x?F2x??2 xF(x)?F1x?F2x???xF(x)?F1x?F2x??23423
(1?x?xF(x)?F1x?(F2?F1)x?(F3?F2?F1)x???xF(x)?x1?x?x22)23?(x??x1?25)(x?1?25)?x?A1?25?x?B1?25
A?12(?1?15) B?12(?1?15)
F(x)?15((???)x?(?222??)x??
其中??15151?2n5 ??1?25
Fn?(?n??)52
Fn?n??(1?
)n
12．分治法的三个步骤是什么？给出使用SPARKS语言描述的分治策略抽象化控制。
答:分治法的三个步骤是: ① 分解 ②解决 ③合并 用SPARKS语言描述的分治策略抽象化控制为:
Procedure DANDC(p,q)
Global n,A(1:n);integer m,p,q; If SMALL(p,q)
Then return(G(p,q)) Else m←DIVIDE(p,q)
Return(COMBINE(DANDC(p,m), DANDC(m+1,q)))
Endif End DANDC