2015武汉大学《算法设计与分析》期中试卷(共10页).doc

精选优质文档-倾情为你奉上武汉大学计算机学院算法设计与分析 期中测试姓名： 学号： 学院： 专业： 一、请用大“O()”记号求下列函数的渐进表达式：3n2 + 10n -1; n2/10 + 2n +1/n; 14 + 5/n + 1/n2 ; ; 20log3n（10分,每小题2分）解答：上述渐进表达式的时间复杂度分别为：3n2 + 10n -1 =O(n2); n2/10 + 2n + 1/n =O(2n); 14 + 5/n + 1/n2=O(1); =O(logn); 20log3n =O(n)二、 令1,2,3,8是n个单元素集合，每个集合由一棵仅有一个结点的树表示。请用按秩合并和路径压缩措施的UNION-FIND算法来执行以下操作序列，并画出每一步操作完成后的树表示。（总分20分）合并和查找操作序列如下所示：UNION（1,2）；UNION（4,3）；UNION