安徽大学2010-2011学年第1学期《算法分析与设计》
期末试题
押宝
（内部交流，非考试试题，学生自发交流创作，版权归作者*******************所有）
一、选择题(单选)(10*2’=20’)
1. 选择正确的组合对于
2112n +=( ) ①2()o n ② 2()O n ③2()n θ ④2()n Ω ⑤ 2()n ω
A. ①③④
B. ②③④
C.③④⑤
D. ①⑤
2. ①21()()n i i O n O n ==∑ ②2()()nO n O n = ③(log )()O n O n ⊆ ④ 2.99993()n
O n =
⑤2/log ()n n n ω=其中正确的有（ ）
A ．5组 B.4组 C.3组 D.没有正确的
3. 2/102n n +=（ ）
A. 2()O n
B.(2)n O
C.2(2)n n O +
D.2
()o n 4. 211/n += ( )（我认为是比较不错的一道题，考试可能会出现相同的方法，用极限定义来做，最后一节课老师也讲过类似的方法）
A. ()O n
B.()o n
C.()n Ω
D.(1)O
5. 310log n = ( )
A.(log )O n n
B. (log )O n
C. 3()O n
D. log ()n O n
6. 认真完成课后习题P5面的算法分析题1-6，里面也有我不会做的，可是有谁愿意讨论？
如果能够把以上的题目都能做对，应该就是掌握了。

给自己一个奖励吧！答案(如有问题，联系我吧)：1-5：BBBDB 6.做出来对对答案吧。

二、填空题
1.()2(/2)T n T n n =+⎢⎥⎣⎦的一个渐进上界为 （答案：(log )O n n ，用迭代法）
2.()(/3)(2/3)()T n T n T n O n =++的一个渐进上界为 （答案：(log )O n n ，用递归树求解，不会的赶快看）
3.()9(/3)T n T n n =+的一个渐进紧致界为 （答案：2
()n θ，采用迭代法或者采用主方法，不会的赶快看）
4.送分题，给你两个串，求他们的最长公共子序列
5.送分题，给你一个数字序列，求最大字段和，直接写出结果
6.大家自己都可以补充了
如果能把上面三题完全独立做出来，第一章应该可以过了，以上题目均来源于算法导论教师手册上的原题，题题经典。

三、计算题和简答题
1.给你一个具体的排序算法，让你分析他的时间复杂性（1-2种排序结合）
2.给你一个具体的0-1背包，让你写那个过程表
3.给你一个贪心活动安排实例，让你写出同课本P104面表中的过程。

4.Dijikstra算法计算过程，最小生成树计算过程一定要会，考试再翻书来不及时间
5.那个都知道的回溯法与分枝限界法的异同点必考的，就算把书上P191面的都抄上也不
过得一半的分。

上课谁听课了，把老师讲的都答上来才能得满分。

6.一些概念性的题目，书上可以找到答案的
四、算法题
1.猜中了，就算有课后习题答案的同学把课后习题答案抄上去不过得个辛苦分，大头分还
是拿不到，建议把贪心或者动态规划的例题证明认真看看吧。

2.还有一题，有些人知道，有些人不知道，自然是来上课的人知道，不来上课的人不知道
了。

不过题海茫茫，记不得了。

就算不知道，把课本动态规划和贪心算法的例题及证明认认真真看懂，也就能拿个差不多了。

周末之前务必做完以上准备工作。

欢迎大家有新的想法交流，我还是比较喜欢复杂度分析那些题目，那些题目可是我看一些参考书总结出来的。

！！！！！！！！！！！！！！！！！！！！！！！！！！！。