1、武汉大学计算机学院算法设计与分析 期中测试姓名： 学号： 学院： 专业： 一、请用大“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-F
2、IND算法来执行以下操作序列，并画出每一步操作完成后的树表示。（总分20分）合并和查找操作序列如下所示：UNION（1,2）；UNION（4,3）；UNION（5,6）；UNION（7,8）；UNION（2,6）；FIND（1）；UNION（3,8）；UNION（8,6）；FIND（4）；FIND（5）。要求：UNION操作在同秩情况下，以后一个结点作为根结点。如UNION（1，2），生成以2为根结点的树。解答：三、 设有n个小球，其中一个是劣质球，其特征是重量较轻，给你一个天平，设计一个分治算法，找出劣质球。（总分15分）（1) 写出算法的主要思路；（5分）（2) 试分析算法的时间复杂度；（
3、5分）（3) 试分析n=9和10，即n分别为奇数和偶数，两种情形下的分治过程。（5分）解法：（1）二对分算法思路：若小球个数2，则直接比较，找出假币。否则，转。若n%2=0，则将其分为个数相等的两部分，选择轻的部分保留，转；否则转。将a0n-2分为相等的两部分：若两部分重量相等，则an-1为劣质球，终止；若不等，则保留轻的部分，转。 （2）以比较操作为基本运算，最好情况比较1次，最坏比较logn次， （3） 分成两部分：a04、a59，假定后者轻，保留a59 分成三部分：a56、a78、a9，若前两者一样重，故劣质球为a9。四、 考试前，A老师给同学答疑，同一时间只能给一个同学答疑，有n个人等
4、待答疑，已知每个人需要答疑的时间为ti（0i0,从而新的序列比原最优序列好，这与假设矛盾，故s1为最小时间，同理可证s2sn依次最小。五、 在一个操场上一排地摆放着堆石子，N堆石子的编号为1，2，N。现要将石子有次序地合并成一堆。每堆石子包含的石子个数给定，规定每次只能选相邻的堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。（总分20分）（1) 假设要求计算出将堆石子合并成一堆的最小得分值，已知该问题可以采用动态规划来进行求解，试写出你的动态规划算法的递归方程，并分析该递归方程能否采用递归程序来实现；（5分）（2) 试设计一个动态规划程序（伪代码即可），计算出将堆石子合并成一堆的最
5、小得分值；（5分）（3) 试分析第（2）问中你设计的动态规划算法的时间复杂度；（5分）（4) 如果要得到取得最小得分的合并方案，将如何修改程序，使之能够输出最优的合并方案，并分析该方法的空间复杂度（注意：最优合并方案的表示可以采用加括号的方式表示）。（5分）参考答案：注意,本题会有多种解法,参考答案仅仅是一种,改卷子时一定要看清楚（1） 设S(i)表示前i堆石子总的数量(也即价值之和)，fij表示把第i堆到第j堆的石头合并成一堆的最优值。则递推方程为： -得分3分由于该递推方程递推下去包含有大量重叠子问题，所以不能直接采用递归算法来实现，递归的算法复杂度为： -得分2分（2） 算法分为初始值赋
6、值和循环两个评分点，算法的伪代码为；Algorithm dd（） for (i=1; i=1; i-) for (j=i+1; j=n; j+) fij=INF； for (k=i; k=j-1; k+) fij=min(fij,fik+fk+1j+sj-si-1); -得分3分 printf(%dn,f1n); return 0;（3） 算法复杂度为Q(n3)。 -得分3分（4） 输出最优解的程序（和矩阵链相乘一样）Algorithm dd(p) n lengthp - 1 for i 1 to nmi, i 0 end for for l 2 to n for i 1 to n (l 1)
7、j i + (l 1)mi, j for k i to j - 1q mi, k + mk + 1, j + pi-1 pkpjif q mcl then mcl = r, y=x endif4. else if r+l macl then maxcl(k+1,r,l-1)5. endif6. x(k) =17. if 节点k与前面取值为1的节点均有边相连 then8. if k=n then 9. if rmcl then mcl = r, y=x endif10. else maxcl(k+1,r+1,l-1)11. endif7. end if -得分10分（2） 解向量采用等长的二进制编码（x1,x2,xn），其中n为图中顶点的个数。 -得分2分时间复杂度为O(n2n)。 -得分3分（3）求解过程如下图所示（由于先选取x(k)=0的节点先生成，本实例造成的树太大，所以我们先生成x(k)=1的节点，不管那种做法，答案都算对），其中红色无字方框是不满足要求的中间节点，红色有字方框为被限界的中间节点，红色圆形为不满足要求的解，灰色圆形为满足要求的解。 -得分5分
