算法设计与分析 期末试卷 A卷(完整含答案).pdf

《算法设计与分析 期末试卷 A卷(完整含答案).pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、华南农业大学期末考试试卷（A卷）2012学年第1学期考试科目：算法设计与分析考试类型：（闭卷）考试考试时间：120分钟学号姓名年级专业线订装题号一(20)二(25)三(16)四(24)五(15)总分得分评阅人说明：（1）请勿漏填学号姓名等信息。本试卷仅一份，请将答案直接填于试卷上，莫将试卷当草稿，想好了再写，若空白的位置不够，标注清楚后可以写反面；（2）答题时，对算法的描述可以采用文字、公式、图、伪代码、实例说明等混合形式。请注意表达应条理清晰，思想简洁，勿长篇累述不得要领。得分一、填空题（1~3题每

2、空1分，第4题每空2分，共20分，结果直接填于划线处）1、化简下面f(n)函数的渐进上界表达式。（5分）2nf(n)n/23，则O(f(n))O(_____________)11n3f(n)2，则O(f(n))O(_____________)223f(n)logn，则O(f(n))O(_____________)332lognf(n)2，则O(f(n))O(_____________)44nf(n)log3，则O(f(n))O(_____________)55nn参考解答：O(

3、f(n))O(3)；O(f(n))O(2)；O(f(n))O(logn)；1232O(f(n))O(n)；O(f(n))O(n)。452、用大O符号和关于n的渐进函数来表征如下算法Loop1至Loop3的运行时间。（3分）算法1Loop1(n)s=0;for(i=1;i<=n;i++)for(j=1;j<=i;j++)s=s+i*j;算法1：O()；算法2Loop2(n)s=0;2for(i=1;i<=n;i++)for(j=1;j<=n;j++)s=s+i*j;算法2：O()；1算法3Lo

4、op3(n)s=0;2for(i=1;i<=n;i++)for(j=1;j<=i;j++)s=s+i*j;算法3：O()234参考解答：算法1：O(n)；算法2：O(n)；算法3：O(n)。n3、假设算法A的计算时间为T(n)2，现在一慢一快的两台计算机上测试算法A，为解决规模n的问题慢机运行算法A花费t秒，而另一台快机速度是慢机的256倍，则在快机上算法A同样运行t秒能解决n1规模，则n1和n的关系为：n1=；若算法B的计算时间2为T(n)n，其余条件不变，则n1=。（2分）参考解答：对算法A，

5、n1n8；对算法B，n116n。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过程为堆顶元素删除操作，该过程时

6、间代价为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。

7、当后续n-i个元素全部比较完毕，则最小堆中的i个元素即为原序列n个数中最大的i个数，最后对这堆中的i个数调用i次extract_Min过程即可有序输出。请分析A、B、C、D和E这五个算法在最坏情况下的渐进时间复杂性（用n和i表示，但需化简，即忽略系数且略去低阶项）。算法A：TA(n)O(_______________)；算法B：TB(n)O(_______________)；算法C：TC(n)O(______________)；算法D：TD(n)O(_______________)；算法E：T

8、E(n)O(______________)。参考解答：算法A：T(n)O(in)；T(n)O(nlogni)或T(n)O(nlogn)ABBT(n)O(nilogn)，其中建立堆需要O(n)，i次堆顶元素删除O(ilogn)。C2T(n)O(nilogi)，其中找第i大元素需要O(n)，对i个元素排序需要O(ilogi)。DT(n)O(i(ni)logiilogi)或T(n)O(nlogi)，其中建立长度为i的最小堆需要O(