1 装订线 华 南 农 业 大 学 期 末 考 试 试 卷 （ A 卷 ） 2012 学年第 1 学期 考试科目： 算法设计与分析 考试类型：（闭卷）考试 考试时间： 120 分钟 学号 姓名 年级专业 题号 一(20) 二(25) 三(16) 四(24) 五(15) 总分 得分 评阅人 说明： （1）请勿漏填学号姓名等信息。本试卷仅一份，请将答案直接填于试卷上，莫将试卷当草稿，想好了再写，若空白的位置不够，标注清楚后可以写反面； （2）答题时，对算法的描述可以采用文字、公式、图、伪代码、实例说明等混合形式。请注意表达应条理清晰，思想简洁，勿长篇累述不得要领。 得 分 一、填空题（1~3题每空1分，第4题每空2分，共20分，结果直接填于划线处） 1、化简下面f(n )函数的渐进上界表达式。（5分） nnnf32/)(21， 则____)(_________))((1OnfO 322)(nnf， 则____)(_________))((2OnfO 33lo g)(nnf， 则____)(_________))((3OnfO 2lo g42)(nnf， 则____)(_________))((4OnfO nnf3lo g)(5， 则____)(_________))((5OnfO 参考解答：)3())((1nOnfO；)2())((2nOnfO；)(lo g))((3nOnfO； )())((24nOnfO；)())((5nOnfO。 2、用大O符号和关于n 的渐进函数来表征如下算法Lo o p 1至Lo o p 3的运行时间。（3分） 算法1：O( )； 算法2：O( )； 算法 2 Loop2( n) s=0; for(i=1;i<=n 2;i++) for(j=1;j<=n;j++) s=s+i*j; 算法 1 Loop1 ( n) s=0; for(i=1;i<=n;i++) for(j=1;j<=i;j++) s=s+i*j; 2 算法3：O( ) 参考解答：算法 1：)(2nO；算法 2：)(3nO；算法 3：)(4nO。 3、假设算法A的计算时间为nnT2)(，现在一慢一快的两台计算机上测试算法A，为解决规模n的问题慢机运行算法A花费t秒，而另一台快机速度是慢机的256倍，则在快机上算法A同样运行t秒能解决n1规模，则n1和n的关系为：n1= ；若算法B的计算时间为2)(nnT，其余条件不变，则n1= 。（2分） 参考解答：对算法A，81 nn；对算法B，nn161。 4、求最大的i个数问题：给定n个不同数的集合S和正整数i（i<=n），S中元素无序，求S中最大的i个数且有序输出（按照升序或降序皆可）。有下述多种算法：（10分） （1）算法A：调用i次顺序比较查找最大元素的算法findmax ，每调用一次删除此最大的数。 （2）算法B：对S排序，并输出S中最大的i个数。 （3）算法C：对输入集合S中的n个数建立一个长...
