装订线
华南农业大学期末考试试卷（A卷） 2012学年第1学期 考试科目：算法设计与分析
考试类型：（闭卷）考试 考试时间：120 分钟
学号姓名年级专业
题号一(20) 二(25) 三(16) 四(24) 五(15) 总分
得分
评阅人
说明：
（1）请勿漏填学号姓名等信息。本试卷仅一份，请将答案直接填于试卷上，莫将试卷当草稿，想好了再写，若空白的位置不够，标注清楚后可以写反面；
（2）答题时，对算法的描述可以采用文字、公式、图、伪代码、实例说明等混合形式。请注意表达应条理清晰，思想简洁，勿长篇累述不得要领。
得分
一、填空题（1~3题每空1分，第4题每空2分，共20分，结果直接填于划线处）
1、化简下面f(n)函数的渐进上界表达式。（5分）
n
n
n
f3
2/
)
(2
1
，则____)
(_________
))
(
(
1
O
n
f
O
3
2
2
)
(
n
n
f，则____)
(_________
))
(
(
2
O
n
f
O
3
3
log
)
(n
n
f ，则____)
(_________
))
(
(
3
O
n
f
O
2
log
4
2
)
(n
n
f ，则____)
(_________
))
(
(
4
O
n
f
O
n
n
f3
log
)
(
5
，则____)
(_________
))
(
(
5
O
n
f
O
参考解答：)
3(
))
(
(
1
n
O
n
f
O ；)
2(
))
(
(
2
n
O
n
f
O ；)
(log
))
(
(
3
n
O
n
f
O ；
)
(
))
(
(2
4
n
O
n
f
O ；)
(
))
(
(
5
n
O
n
f
O 。
2、用大O符号和关于n的渐进函数来表征如下算法Loop1至Loop3的运行时间。（3分）
算法1：O( )；
算法2：O( )；
1
2
算法3：O( )
参考解答：算法1：)(2n O ；算法2：)(3n O ；算法3：)(4n O 。
3、假设算法A 的计算时间为n n T 2)( ，现在一慢一快的两台计算机上测试算法A ，为解决规模n 的问题慢机运行算法A 花费t 秒，而另一台快机速度是慢机的256倍，则在快机上算法A 同样运行t 秒能解决n1规模，则n1和n 的关系为：n1= ；若算法B 的计算时间为2)(n n T ，其余条件不变，则n1= 。（2分）
参考解答：对算法A ，81
n n ；对算法B ，n n 161 。
4、求最大的i 个数问题：给定n 个不同数的集合S 和正整数i （i<=n ），S 中元素无序，求S 中最大的i 个数且有序输出（按照升序或降序皆可）。有下述多种算法：（10分）
（1）算法A ：调用i 次顺序比较查找最大元素的算法findmax ，每调用一次删除此最大的数。 （2）算法B ：对S 排序，并输出S 中最大的i 个数。
（3）算法C ：对输入集合S 中的n 个数建立一个长度为n 的最大堆，接着反复调用i 次堆的extract_Max 过程。其中extract_Max 过程为堆顶元素删除操作，该过程时间代价为O(logn)，而建立一个n 个元素的最大堆过程需要O(n)。
（4）算法D ：利用O(n)线性时间的分治算法找第i 大元素x ，然后调用partition 过程对n 个数以x 进行划分，比x 大的i-1个元素被置于x 的右边（即后边），再对这i 个数进行排序。 （5）算法E ：先对集合S 的前i 个元素建立一个长度为i 的最小堆，利用extract_Min 过程可得最小堆的堆顶元素为x ，让集合S 的后续n-i 个元素（称当前元素y ）逐个去和堆顶元素x 比较，若y>x ，将y 插入堆中并重新整合成最小堆和形成新的堆顶元素x ；否则丢弃y 。当后续n-i 个元素全部比较完毕，则最小堆中的i 个元素即为原序列n 个数中最大的i 个数，最后对这堆中的i 个数调用i 次extract_Min 过程即可有序输出。
请分析A 、B 、C 、D 和E 这五个算法在最坏情况下的渐进时间复杂性（用n 和i 表示，但需化简，即忽略系数且略去低阶项）。
算法A ：______)(_________)(O n T A ； 算法B ：______)(_________)(O n T B ； 算法C ：_____)(_________)(O n T C ； 算法D ：______)(_________)(O n T D ；
算法E ：_____)(_________)(O n T E 。
参考解答：算法A ：
)()(n i O n T A ； )log ()(i n n O n T B 或)log ()(n n O n T B
)log ()(n i n O n T C ，其中建立堆需要)(n O ，i 次堆顶元素删除)log (n i O 。
