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

2021-09-24 18:05

华南农业大学期末考试试卷(A卷)

2012学年第1学期 考试科目: 算法设计与分析 考试类型:(闭卷)考试 考试时间: 120 分钟

学号 姓名 年级专业

题号

装

一(20)

二(25)

三(16)

四(24)

五(15)

总分

得分 评阅人

订

说明:

(1)请勿漏填学号姓名等信息。本试卷仅一份,请将答案直接填于试卷上,莫将试卷当草稿,想好了再写,若空白的位置不够,标注清楚后可以写反面;

(2)答题时,对算法的描述可以采用文字、公式、图、伪代码、实例说明等混合形式。请注意表达应条理清晰,思想简洁,勿长篇累述不得要领。

得分

线

一、填空题(1~3题每空1分,第4题每空2分,共20分,结果直接填于划线处) 1、化简下面f(n)函数的渐进上界表达式。(5分) f1(n) n2/2 3n, 则O(f1(n)) O(_____________) f2(n) 2n 3,

f3(n) logn3,

则O(f2(n)) O(_____________) 则O(f3(n)) O(_____________) 则O(f4(n)) O(_____________) 则O(f5(n)) O(_____________)

n

f4(n) 2logn,

f5(n) log3n,

2

参考解答:O(f1(n)) O(3);O(f2(n

)) O(2n);O(f

3(n)) O(logn);

O(f4(n)) O(n2);O(f5(n)) O(n)。

2、用大O符号和关于n的渐进函数来表征如下算法Loop1至Loop3的运行时间。(3分)

算法1:);

算法2:;

1

算法3:参考解答:算法1:O(n2);算法2:O(n3);算法3:O(n4)。

3、假设算法A的计算时间为T(n) 2n,现在一慢一快的两台计算机上测试算法A,为解决规模n的问题慢机运行算法A花费t秒,而另一台快机速度是慢机的256倍,则在快机上算法A同样运行t秒能解决n1规模,则n1和n的关系为:B的计算时间为T(n) n2,其余条件不变,则。(2分)

参考解答:对算法A,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过程为堆顶元素删除操作,该过程时间代价为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:TA(n) O(_______________); 算法B:TB(n) O(_______________); 算法C:TC(n) O(______________); 算法E:TE(n) O(______________)。

参考解答:算法A:

算法D:TD(n) O(_______________);

TA(n) O(i n); TB(n) O(nlogn i)或TB(n) O(nlogn)

TC(n) O(n ilogn),其中建立堆需要O(n),i次堆顶元素删除O(ilogn)。

2

装

订

线

TD(n) O(n ilogi),其中找第i大元素需要O(n),对i个元素排序需要O(ilogi)。

TE(n) O(i (n i)logi ilogi)或TE(n) O(nlogi),其中建立长度为i的最小堆需要O(i),

后续n-i个元素比较并判定是否逐个插入堆,最坏情况为O((n i)logi),最后对i个堆中元素逐个输出堆顶元素需要O(ilogi),合计后略去低阶项为O(nlogi)。

得分

二、简答题(共5小题,每题5分,共25分) 1、请将下列函数的阶按上升顺序排列。(5分)

n1/2,logn2,2n,log2n,nlogn,n2logn,210,2logn,22n

,2n2

参考解答:2

10

,logn2,log2n,n

1/2

,2

logn

,nlogn,n2logn,2n

,2n2,22n

提示:拿不准两个函数f(n)和g(n)时,考虑logf(n)和logg(n),或2^f(n)或2^g(n)。学生答题的排序后若有一个不在位,扣1分。

2、复数a+bi可以用数对(a, b)表示(其中i2 1)。描述一个方法,只需构造进行三次实数

乘法(可采用有限次实数加减),即可计算a+bi和c+di相乘的结果数对(e, f)。请写出采用了哪三次实数乘法?(5分)

参考解答:

(a,b)(c,d) ac (ad bc)i bd( 1) ac [(a b)(d c) ac bd]i bd

三次实数乘法分别是:ac,

(a b)(d c),bd

评分准则:此参考解答并非唯一解,只要能凑出ac, bd, (ad+bc)三部分的解皆可。

3、对于矩阵连乘所需最少数乘次数问题,其递推关系式为:

m[i,j]

0i j

min{i k jm[i,k] m[k 1,j] pi 1pkpj}i j

其中m[i,j]为计算矩阵连乘Ai…Aj所需的最少数乘次数,pi 1为矩阵Ai的行数,pi为矩阵Ai的列数。现有四个矩阵,其中各矩阵维数分别为:

A1 A2 A3 A4 10 100 100 5

5 50

50 10

p 0 p 1

p 1 p 2 p 2 p 3p 3 p 4请根据递推关系,计算出矩阵连乘积A1A2A3A4所需要的最少数乘次数。(5分)

参考解答:根据递推公式:

m[1][1] 0;m[2][2] 0;m[3][3] 0;m[4][4] 0;

m[1][2] p0p1p2 5000;m[2][3] p1p2p3 25000;m[3][4] p2p3p4 2500;

3

m[1][3] min{m[1][1] m[2][3] p0p1p3,m[1][2] m[3][3] p0p2p3} 7500;m[2][4] min{m[2][2] m[3][4] p1p2p4,m[2][3] m[4][4] p1p3p4} 5000;

m[1][1] m[2][4] p0p1p4 0 5000 10000 15000

算法设计与分析 期末试卷 A卷(完整含答案).doc 将本文的Word文档下载到电脑 下载失败或者文档不完整,请联系客服人员解决!

下一篇:新苏教版小学六年级 比例的基本性质下册数学教案

相关阅读
本类排行
× 注册会员免费下载(下载后可以自由复制和排版)

马上注册会员

注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: