资源描述：
《算法分析与设计模拟试题.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、《算法设计与分析》复习题参考答案1．什么是算法？算法必须满足的五个特性是什么？算法：一组有穷的规则，规定了解决某一特定类型问题的一系列运算。（有限指令的集合，遵循它可以完成一个特定的任务）.必须满足的五个特性是(遵循以下五条准则)：1．有穷（限）性2．确定性3．可（能）行性4．输入（n≥0）5．输出（n≥1）2．对算法进行分析分哪两个阶段？各自完成什么任务（分别得到什么结果）？对一个算法要作出全面的分析可分成两个阶段进行，即：事前分析和事后测试。事前分析求出该算法的一个时间界限函数；事后测试搜集此算法的执行时间和实际占用空间的统计资料。3．证明：
2、若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时，使得
3、f1(n)
4、≤C1
5、g1(n)
6、；同理，根据f2(n)=O(g2(n))可知，存在正常数C2，当n≥n0时，使得
7、f2(n)
8、≤C2
9、g2(n)
10、当n≥n0时，
11、f1(n)+f2(n)
12、≤
13、f1(n)
14、+
15、f2(n)
16、≤C1
17、g1(n)
18、+C2
19、g2(n)
20、≤C1
21、gk(n)
22、+C2
23、gk(n)
24、≤（C1+C2）
25、gk(n)
26、，其中gk(n)
27、=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)=2n2下面证明（c）正确性.根据上
28、题已经证明f1(n)+f2(n)=O(max{g1(n),g2(n)})，下面只需证明f1(n)+f2(n)=Ω(max{g1(n),g2(n)})，即存在正常数C，使得
29、f1(n)+f2(n)
30、≥C(max{g1(n),g2(n)})根据f1(n)=Θ(g1(n))并且f2(n)=Θ(g2(n))得到，当n≥n0时，存在正常数C1、C2、C3、C4C1
31、g1(n)
32、≤
33、f1(n)
34、≤C3
35、g1(n)
36、C2
37、g2(n)
38、≤
39、f2(n)
40、≤C4
41、g2(n)
42、不妨设max{g1(n),g2(n)}=g1(n)由于
43、f1(n)+f2(n)
44、≥
45、
46、f1(
47、n)
48、-
49、f2(n)
50、
51、≥
52、C1
53、g1(n)
54、-C3
55、g2(n)
56、
57、=C
58、max{g1(n),g2(n)}
59、取C≥
60、C1-C3
61、的正常数，由定义得f1(n)+f2(n)=Ω(max{g1(n),g2(n)})命题得证。5．证明
62、「log2n」
63、=O(n)证明：对于任意的正整数n，
64、「log2n」
65、≤
66、log2（n+1）
67、≤
68、n+1
69、≤2
70、n
71、取n0=1，C=2，根据定义知命题成立。6．证明3n「log2n」=O(n2)证明：对于任意的正整数n，
72、3n「log2n」
73、≤
74、3n「log2n」
75、≤3
76、n2
77、取n0=1，C=3，根据定义知命题成立。7．用
78、数学归纳法证明：当n≥1时，.证明：当n=1时，，n(n+1)/2=1，命题成立；假设n=k-1时，成立;（k≥2）当n=k时，==k(k+1)/2综上可知，命题成立。8．在下列情况下求解递归关系式T(n)=当①n=2kg(n)=O(1)和f(n)=O(n)；②n=2kg(n)=O(1)和f(n)=O(1)。解:T(n)=T(2k)=2T(2k-1)+f(2k)=2(2T(2k-2)+f(2k-1))+f(2k)=22T(2k-2)+21f(2k-1)+f(2k)=……=2kT(1)+2k-1f(2)+2k-2f(22)+…+20f(2k)=2k
79、g(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．求解递推关系式：解：构造生成
80、函数求解分解成幂级数令则A=-1B=1所以10．求解递推关系式：解：11．求解递推关系式：解：以为系数，构成生成函数其中12．分治法的三
