算法分析与设计期末考试模拟试题一

第 1 页 （共 4 页） 算法分析与设计期末考试模拟试题一

课程名称：__ 算法分析与设计 考试形式： 闭 卷

学习中心：_________ 考试时间： 90分钟

姓 名：_____________ 学 号：

一、填空题（每小题4分，共计40分）

1. 通常只考虑三种情况下的时间复杂度，即 情况、

情况和 情况下的时间复杂度，分别记为T max (N)、T min

(N) 和T avg (N)，实践表明可操作性最好且最有实际价值的是 情况下的时间复杂度。

2. n n 1032 的渐近表达式是 ，

)log(3n 的渐近表达式是 。

3. 根据符号O 的定义易知O(1)=O(2)，用O(1)和O(2)表示同一个方法

时，差别仅在于其中的 。

4. 递归算法是指 的算法，递归函数

是指 的

函数。

5. 贪心算法总是做出在当前看来_____________的选择，也就是说，贪

心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的

________________。

6. 如果某问题具有________________________和

___________________________两个重要性质，该问题可以用贪心算

法求解。

7. 单源最短路径问题适合用_______________算法来求解、0-1背包问

题适合用_____________算法来求解。