版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、 1 装订线 华南农业大学期末考试试卷华南农业大学期末考试试卷(A 卷卷) 2012 学年第学年第 1 学期学期 考试科目考试科目: 算法设计与分析 考试类型考试类型: (闭卷闭卷)考试考试 考试时间考试时间: 120 分钟 学号 姓名 年级专业 题号题号 一一(20) 二二(25) 三三(16) 四四(24) 五五(15) 总分总分 得分得分 评阅人评阅人 说明: (1)请勿漏填学号姓名等信息。本试卷仅一份,请将答案直接填于试卷上,莫将试卷当草稿,想好了再 写,若空白的位置不够,标注清楚后可以写反面; (2)答题时,对算法的描述可以采用文字、公式、图、伪代码、实例说明等混合形式。请注意表达应
2、条 理清晰,思想简洁,勿长篇累述不得要领。 得分 一一、填空题填空题(13题题每空每空1分分,第第4题题每每空空2分分,共共20分分,结果直接填于划线处结果直接填于划线处) 1、化简下面f(n)函数的渐进上界表达式。 (5分) n nnf32/)( 2 1 , 则_)(_)( 1 OnfO 3 2 2)( n nf, 则_)(_)( 2 OnfO 3 3 log)(nnf, 则_)(_)( 3 OnfO 2 log 4 2)( n nf, 则_)(_)( 4 OnfO n nf3log)( 5 , 则_)(_)( 5 OnfO 参考解答参考解答:)3()( 1 n OnfO;)2()( 2 n
3、 OnfO;)(log)( 3 nOnfO; )()( 2 4 nOnfO;)()( 5 nOnfO。 2、用大O符号和关于n的渐进函数来表征如下算法Loop1至Loop3的运行时间。 (3分) 算法1:O( ); 算法2:O( ); 算法算法 2 Loop2(n) s=0; for(i=1;i=n2;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:)( 2 nO;算法 2:)( 3 nO;算法 3:)( 4 n
4、O。 3、假设算法A的计算时间为 n nT2)(,现在一慢一快的两台计算机上测试算法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(ix,将y插入堆中并重新整合成最小堆和形成新的堆顶元素x;否则丢弃y。当后续n-i个 元素全部比较完毕,则最小堆中的i个元素即为原序列n个数中最大的i个数,最
5、后对这堆中 的i个数调用i次extract_Min过程即可有序输出。 请分析A、B、C、D和E这五个算法在最坏情况下的渐进时间复杂性(用n和i表示,但 需化简,即忽略系数且略去低阶项) 。 算法A:_)(_)(OnTA; 算法B:_)(_)(OnTB; 算法C:_)(_)(OnTC; 算法D:_)(_)(OnTD; 算法E:_)(_)(OnTE。 参考解答参考解答:算法A: )()(niOnTA; )log()(innOnTB或)log()(nnOnTB )log()(ninOnTC,其中建立堆需要 )(nO,i 次堆顶元素删除)log(niO。 算法算法 3 Loop3(n) s=0; fo
6、r(i=1;i=n2;i+) for(j=1;j=i;j+) s=s+i*j; 3 装订线 )log()(iinOnTD,其中找第i大元素需要 )(nO,对i个元素排序需要)log(iiO。 )loglog)()(iiiiniOnTE或)log()(inOnTE,其中建立长度为i的最小堆需要 )(iO, 后续n-i个元素比较并判定是否逐个插入堆, 最坏情况为)log)(iinO, 最后对i个堆中元素逐个输出堆顶 元素需要)log(iiO,合计后略去低阶项为)log(inO。 得分 二二、简答题简答题(共共5小题小题,每题每题5分分,共共25分分) 1、请将下列函数的阶按上升顺序排列。 (5分)
7、 2/1 n, 2 logn , n 2 ,n 2 log,nnlog,nn log 2 , 10 2 , nlog 2, n 2 2, 2 2n 参考解答参考解答: 10 2, 2 logn,n 2 log, 2/1 n, nlog 2,nnlog,nn log 2 , n 2, 2 2n, n 2 2 提示:拿不准两个函数f(n)和g(n)时,考虑logf(n)和logg(n),或2f(n)或2g(n)。学生答题的排序后若有一个不在位,扣1分。 2、复数a+bi可以用数对(a, b)表示(其中1i2) 。描述一个方法,只需构造进行三次实数 乘法(可采用有限次实数加减) ,即可计算a+bi和
8、c+di相乘的结果数对(e, f)。请写出采用了 哪三次实数乘法?(5分) 参考解答参考解答: bdibdaccdbaac bdibcadacdcba )( ) 1()(),)(,( 三次实数乘法分别是:bdcdbaac),)(, 评分准则:此参考解答并非唯一解,只要能凑出ac, bd, (ad+bc)三部分的解皆可。 3、对于矩阵连乘所需最少数乘次数问题,其递推关系式为: 1 i k j 0 , min , 1, ikj ij m i j m i km kjpp pij 其中mi,j为计算矩阵连乘AiAj所需的最少数乘次数, 1i p为矩阵Ai的行数, i p 为矩阵 Ai的列数。现有四个矩
9、阵,其中各矩阵维数分别为: A1 A2 A3 A4 10 100 100 5 5 50 50 10 p 0 p 1 p 1 p 2 p 2 p 3 p 3 p 4 请根据递推关系,计算出矩阵连乘积A1A2A3A4所需要的最少数乘次数。 (5分) 参考解答参考解答:根据递推公式: ;250043;2500032;500021 ; 044; 033; 022; 0 11 432321210 pppmpppmpppm mmmm 4 ;50004432,4322min42 ;7500 3321 , 32 11 min 31 431421 320310 pppmmpppmmm pppmmpppmmm 1
10、25005000075004431 8000500250050004321 15000100005000042 11 min41 m 430 420 410 pppmm pppmm pppmm 因此:800041 m 4、操场上摆放一行共n堆石头,呈直线排列。n堆石子从左到右方向编号为1n,每堆石子 个数分别为a1,an,现在要将石子有次序的合并为一堆,规定每次只能选相邻的2堆合 并为新的一堆,并将新的一堆的石子数记为该次合并的得分,经过n-1次合并,最终合并为 一堆,总得分为n-1次合并得分之和。现要设计一个算法,计算出将一行的n堆石子合并为一 堆的最小得分。这里假设mi,j为合并石子AiA
11、j, 1ijn,所得到的最小得分。请写出 mi,j的递推公式。 (5分) 参考解答参考解答:设 n 堆石子从左到右方向编号为 1,2,n,每堆石子个数分别为 a1,an。n 堆石子的合并有许多不同 的方式,每种合并方式对应于 n 个矩阵连乘的一种完全加括弧方式。显然,这里合并是满足最优子结构性质的,用 A1An 来代表每堆的石子,则最后一次合并在 Ak 和 Ak+1 之间,则 A1An 的最优合并为(A1Ak)(Ak+1An),可以看出最优 解左边部分(A1Ak)和右边部分(Ak+1An)的合并也分别是最优的。 假设 mi,j为合并石子 AiAj, 1ijn,所得到的最小得分,若没有“合并”这
12、个动作,则为 0。原问题所求 的最优值即为 m1,n。 jitajkmkim ji j it jki , 1,min 0 jmi, 填充mi,j即可得到任意行状摆放的石子合并的最小得分。 5、有这样一类特殊0-1背包问题:可选物品重量越轻的物品价值越高。n=6,c=20,P=(4,8, 15,1,6,3),W=(5,3,2,10,4,8)。其中n为物品个数,c为背包载重量,P表示物品 的价值,W表示物品的重量。请问对于此特殊的0-1背包问题,为使放进背包的物品总价值 最大,应如何选择放进去的物品?此例能获得的最大总价值多少?(5分) 参考解答参考解答:因为该 01 背包问题比较特殊,恰好重量越
13、轻的物品价值越高,所以优先取重量轻的物品放进背包。最终可 以把重量分别为 2,3,4,5 的三个物品放进背包,得到的价值和为 15 + 8 + 6 + 4 = 33,为最大值。 得分 三三、画图画图题题(共共16分分,每每图图4分分) 1、字符ah出现的频率恰好是前八个Fibonacci数(数列最开始两个元素都为1,之后每个元 素都等于前两个元素之和) ,请画出ah这八个字符的Huffman编码树。 (4分) 参考解答参考解答:若字符 ah 出现的频率恰好是前 8 个 Fibonacci 数,它们的 Haffman 编码树如下图所示。 5 装订线 此图并非唯一解,但所做的编码树须满足Huffm
14、an树的构造方法,频率越低的在树的越深处。 2、对如下问题采用回溯的搜索算法,请画出搜索状态的解空间树。注意这题无需说明算法 或搜索过程,只画解空间树即可。 (8分:4分+4分) (1)作业分配问题:n个作业分配给n个人,将第i个作业分给第j个人所需费用代价为cij, 为每个作业分配给不同的人来完成,并使得所有工作的总费用和最小。以n=3为例,请画出 搜索的解空间树。 (2)图的m着色问题:给定n个顶点的无向连通图G和m种不同的颜色,用这m种颜色为图G 的各顶点着色,且G中邻接顶点(指有边相连的顶点)不能着同色,求所有不同的着色方法 数。以n=3,m=3为例,请画出搜索的解空间树。 参考解答参
15、考解答: (1) (1)n=3 的排列树 (2) (2)n=3,m=3 的 n 层完全 m 叉树) 3、折纸留痕:你喜欢折纸吗?给你一张很大的纸,对折以后再对折,再对折,每次对 折都是从右往左折(沿逆时针) ,因此折了很多次以后,原来的大纸就会变成窄窄的纸条。 现在把这个纸条沿着折纸的痕迹打开,把每个痕迹视为一个“直角” ,那么从纸的一端沿着 与纸面平行的方向看过去(即截面图) ,会看到一个曲线。例如,对折2次和3次,看到如下 曲线。请你画出对折4次的截面曲线。 (4分) 对折两次后形成的曲线 对折三次后形成的曲线 参考解答参考解答: 3 2 3 2 2 x3=1 x1=1 x2=1 3 3
16、1 2 2 1 3 2 2 1 3 3 1 3 1 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 c d e f g h a b 6 对折四次后形成的曲线 得分 四四、程序填空程序填空题题(共共12个空格个空格,每空每空2分分,共共24分分, 结果结果集中集中的的填于程序下方划线处填于程序下方划线处) 1、有重复元素的全排列:对n个元素集 R = r1, r2, , rn进行全排列,其中r1,r2,rn可能相 同,下面算法框架Permpp( )可以输出R的所有不同的排列,请补充完整。 void Permpp(char list, int k, int m) /产生 listkm的
17、所有排列 if(k=m) 输出 list 内的所有元素; return; for(int i=k; i=m; i+) if ( Findsame(list,k,i) )/判断第 i 个元素是否在 listk,i1中出现过 continue; Swap(listk, listi); (1) ; (2) ; int Findsame (int a, int k, int m)/判断第 m 个元素是否在 ak,m1中出现过 for (int j=k; jm; j+) if ( (3) ) return 1; return 0; (1) (2) (3) 参考解答参考解答: (1) Permpp(lis
18、t, k+1, m); (2) Swap(listk, listi); (3) am=aj 2、求二维数组的“最大子矩阵和”算法框架MaxSum2( )如下,请补充完整。 int MaxSum(int n, int *a) /求解一维整数序列的最大子段和 int sum=0,b=0; for (int i=0;i0) b+=ai; else b=ai; if(bsum) sum=b; return sum; 7 装订线 int MaxSum2(int m, int n, int *a) /求解二维整数数组的最大子矩阵和 int sum=0; int *b=new intn; for(int i
19、=0;im;i+) for(int k=0;kn;k+) /b 数组初始化 bk=0; for(int j=i;jm;j+) for(int k=0;ksum) sum = max; return sum; (4) (5) 参考解答参考解答: (4) bk+=ajk; (5) MaxSum(n,b); 3、 “子集和问题”是求解:n个元素的整数集合,是否能找到一个子集,使得子集元素之和 为c。其回溯搜索算法框架Backtrack( )如下,请补充完整。 void Backtrack(int i) /子集树的搜索算法,根节点,i=1 if(in) /搜索到子集树的叶子 if (cw = c) f
20、ound=1; /cw 为当前的子集之和,found 已被初始化为 false else found=0; /found 是一个寻找标志,找到则为 true,否则为 false return; if(found=0) /无条件左子树 xi = 1; cw += ai; Backtrack(i+1); (6) ; /搜索完左子树,无条件右子树 xi = 0; (7) ; (6) (7) 参考解答参考解答: (6) cw -= ai; (7) Backtrack(i+1); 4、 “n皇后问题”是求解:nn的棋盘上放置n个不同行不同列不同斜线的皇后,是否有放 置方案,有请输出可行的放置方案数。其算
21、法框架nQueen( )如下,请补充完整。 int nQueen() /假定 n,sum,x数组等都为全局变量,并在 nQueen 中初始化; 8 sum=0; for(int i=1; in) /搜索到 n 叉树的叶子 sum+; /sum 为可行放置方案个数的统计变量 /并输出 x解向量,此处略 else for(int i=1; i=n; i+) xt = i; if( Place(t) ) Backtrack(t+1); int Place(int k) for(int j=1;jk;j+) if( (8) | (9) ) return 0; /可使用 abs()库函数求绝对值 ret
22、urn 1; (8) (9) 参考解答参考解答: (8) abs(k-j)=abs(xk-xj) (9) xj=xk 5、大于1的正整数 n 都可以分解为 n = x1x2.xm,对于给定正整数n,计算n共有多 少种不同的分解式的solve( )过程如下。例如:当n=12时,共有8种不同的分解式: 12 = 12; 12 = 6*2; 12 = 4*3; 12 = 3*4;12 = 3*2*2;12 = 2*6; 12 = 2*3*2; 12 = 2*2*3 total=0; /全局变量 total void solve(int n) /递归实现对 n 的不同分解式的个数统计 if (n=1)
23、 total+; else for (int i=2; i=n; i+) if (n%i = 0) (10) ; (10) 参考解答参考解答: (10) solve(n/i); 或 if (n=1) total=1; else total=solve(i)*solve(n/i); 6、二维0-1背包问题:n种物品,每种物品仅1件,物品i的重量wi,体积bi,价值vi,背包容 量为c,容积为d。所有参数均为正整数,如何选择装入背包的物品子集,使得装入背包物 品的总价值最大?其动态规划算法Knapsack2( )算法如下,其中mixy含义:每种物品仅 1件,但可选物品1i,背包容量为x容积为y(1
24、in,0 xc,0yd) ,可获得装入 物品的最大价值和存于mixy中。 /全局变量有 n, w, b, v;含义如题说明。 /全局变量有 m数组;含义如题说明。 9 装订线 int Knapsack2() /动态规划法计算二维背包问题,填充 m 数组 int i,x,y; for(x=0;x=c;x+) /初始化 m1xy for(y=0;y=w1 else m1xy=0; for(i=2;i=n;i+) /递推填充 mixy,2=i=n for(x=0;x=c;x+) for(y=0;y=wi else mixy = (12) ; return mncd; (11) (12) 参考解答参考
25、解答: (11) mixy = mi-1 x-wi y-bi + vi; (12) mixy = mi-1xy; 得分 五五、算法设计算法设计题题(共共2小题小题,共共15分分) 此大题请写出算法设计的详细步骤,可用伪代码、文字、图表来描述。 1、 【、 【区间相交问题区间相交问题】 (7分) 给定数轴上n个区间。去掉尽可能少的区间,使剩下的区间都不相交。请给出删除区间的方 案。 (这里:两区间仅边界有交点不算相交) 参考解答参考解答:区间相交问题基本等同于活动安排问题。 1) 、将区间按照区间后端点排序(从小到大) 。 2) 、选择第一个区间 3) 、依次扫描后续区间,和第一个不相交的,拉入相容区间集合 4) 、总区间数减去相容区间集合得到的就是最少的需要去掉的区间数 评分准则: 1) 答到贪心算法,且贪心算法表述正确,本题即可得满分; 2) 说明用到贪心
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- GB/T 23149-2026洗衣机牵引器技术要求
- 老年慢性病的综合管理与康复治疗研究与实践
- 肝脏疾病防治策略与护理
- 茶树病虫害防治办法
- 2027年春季开学考试一年级科学模拟卷及答案解析
- 慢性疼痛治疗策略分析
- 2027年春季开学考试高三语文易错题卷电子版
- 高血压脑出血相关的护理常规课件
- 2027年寒假开学摸底考试二年级语文基础卷及答案解析
- 2027年云南省高考三模英语押题卷及答案解析
- 2026年餐饮管理专业知识结构评估试题及答案
- 非法营运案例课件
- 2026年土建主管考试题库及答案
- 理性上网辨别网络谣言 大学生网络文明课件
- GB/T 47549-2026塑料断裂韧性的测定J-R曲线法
- 安全防范系统专项施工方案(2026新版)
- 2026年学习教育偏差主要问题清单(对照检查四大方面16个问题共160条)两篇
- 机房值机员年终总结(3篇)
- 瓶装液化气配送制度规范
- EGFR 20外显子插入突变非小细胞肺癌中国专家共识(2025版)要点解读
- 教育学原理 第二版 课件 第10章 教育科学研究
评论
0/150
提交评论