2006-2007学年第二学期《算法设计与分析》 a卷

《2006-2007学年第二学期《算法设计与分析》 a卷》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、姓名学号学院专业座位号(密封线内不答题)……………………………………………………密………………………………………………封………………………………………线……………………………………线………………………………………_____________________…诚信应考,考试作弊将带来严重后果！华南理工大学期末考试《算法设计与分析》试卷A注意事项：1.考前请将密封线内填写清楚；2.所有答案请直接答在试卷上；3．考试形式：闭卷；4.本试卷共七大题，满分100分，考试时间120分钟。题号一二三四五六七总分得分评卷人一、给出O，W，Q的定义（10分）。《算法设计与

2、分析》第7页共7页一、对于下列各组函数，确定f(n)=O(g(n))，或者f(n)=Ω(g(n))，或f(n)＝Q(g(n))。（15分）1.f(n)=logn2,g(n)=logn+52.f(n)=logn2,g(n)=3.f(n)=n,g(n)=log2n4.f(n)=nlogn+n,g(n)=logn二、给定如下矩阵连乘问题，用动态规划算法计算最优计算次序及最优值（15分）。A1A2A3A4A5A620×1010×3535×1515×4040×2525×30《算法设计与分析》第7页共7页《算法设计与分析》第7页共7页一、对于数组a[0:n-1]，

3、给定段合并排序算法如下，建立其计算复杂性递归表达式并求解（15分）。Publicstaticvoidmergesort(int[]a,intleft,intright){if(left1){for(inti=0;i

4、设计与分析》第7页共7页一、给定图如下，求出最小生成树以及以顶点1为源的单源最短路径。（15分）1256734506020305010307020502060898101050201010030《算法设计与分析》第7页共7页一、证明求最大公约数的欧几里得算法的正确性，并分析其算法复杂性。（15分）intgcd(inta,intb){if(b==0)returna;returngcd(b,a%b);}其中%为求模运算。《算法设计与分析》第7页共7页一、给定分别有n个元素的两个集合S和T，试设计一个判定S和T是否相等的蒙特卡罗算法，并分别就相等和不相等（有

5、一个元素不同）两种情形分析算法正确的概率。(15分)《算法设计与分析》第7页共7页