期末试题
押宝
（内部交流，非考试试题，学生自发交流创作，版权归作者*******************所有）
一、选择题(单选)(10*2’=20’)
1. 选择正确的组合对于
① ② ③ ④ ⑤
A. ①③④ B. ②③④ C.③④⑤ D. ①⑤
2. ① ② ③ ④
⑤其中正确的有（ ）
A．5组 B.4组 C.3组 D.没有正确的
3. =（ ）
A. B. C. D.
4. ( )（我认为是比较不错的一道题，考试可能会出现相同的方法，用极限定义来做，最后一节课老师也讲过类似的方法）
A. B. C. D.
5. ( )
A. B. C. D.
6. 认真完成课后习题P5面的算法分析题1-6，里面也有我不会做的，可是有谁愿意讨论？
如果能够把以上的题目都能做对，应该就是掌握了。给自己一个奖励吧！答案(如有问题，联系我吧)：1-5：BBBDB 6.做出来对对答案吧。
二、填空题
1.的一个渐进上界为 （答案：，用迭代法）
2.的一个渐进上界为 （答案：，用递归树求解，不会的赶快看）
3.的一个渐进紧致界为 （答案：，采用迭代法或者采用主方法，不会的赶快看）
4.送分题，给你两个串，求他们的最长公共子序列
5.送分题，给你一个数字序列，求最大字段和，直接写出结果
6.大家自己都可以补充了
如果能把上面三题完全做出来，第一章应该可以过了，以上题目均来源于算法导论教师手册上的原题，题题经典。
三、计算题和简答题
1.给你一个具体的排序算法，让你分析他的时间复杂性（1-2种排序结合）
2.给你一个具体的0-1背包，让你写那个过程表
3.给你一个贪心活动安排实例，让你写出同课本P104面表中的过程。
4.Dijikstra算法计算过程，最小生成树计算过程一定要会，考试再翻书来不及时间
5.那个都知道的回溯法与分枝限界法的异同点必考的，就算把书上P191面的都抄上也不过得一半的分。上课谁听课了，把老师讲的都答上来才能得满分。
6.一些概念性的题目，书上可以找到答案的
四、算法题
1.猜中了，就算有课后习题答案的同学把课后习题答案抄上去不过得个辛苦分，大头分还是拿不到，建议把贪心或者动态规划的例题证明认真看看吧。
2.还有一题，有些人知道，有些人不知道，自然是来上课的人知道，不来上课的人不知道了。不过题海茫茫，记不得了。就算不知道，把课本动态规划和贪心算法的例题及证明认认真真看懂，也就能拿个差不多了。
周末之前务必做完以上准备工作。欢迎大家有新的想法交流，我还是比较喜欢复杂度分析那些题目，那些题目可是我看一些参考书总结出来的。下载本文
