武汉大学《算法设计与分析》期中试卷课案.pdf

武汉大学计算机学院武汉大学计算机学院算法设计与分析算法设计与分析 期中测试期中测试姓名：姓名：学号：学号：学院：学院：专业：专业：一、请用大“O()”记号求下列函数的渐进表达式：3n2+10n-1;n2/10+2n+1/n;14+5/n+1/n2;20log3n（10 分,每小题 2 分）nn 2log解答：上述渐进表达式的时间复杂度分别为：3n2+10n-1=O(n2);n2/10+2n +1/n=O(2n);14+5/n+1/n2=O(1);=O(logn);20log3n=O(n)nn 2log二、令1,2,3,8是 n 个单元素集合，每个集合由一棵仅有一个结点的树表示。请用按秩合并和路径压缩措施的 UNION-FIND 算法来执行以下操作序列，并画出每一步操作完成后的树表示。（总分 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 为根结点的树。解答：(b)21(a)2134563465UNION（1,2）;UNION（4,3）;UNION（5,6）;UNION（7,8）;(c)6251UNION（2,6）;(d)6251FIND（1）;(e)UNION（3,8）;(g)FIND（4）;(h)FIND（5）;78878374(f)UNION（8,6）;837462518374625183746251三、设有 n 个小球，其中一个是劣质球，其特征是重量较轻，给你一个天平，设计一个分治算法，找出劣质球。（总分 15 分）（1)写出算法的主要思路；（5 分）（2)试分析算法的时间复杂度；（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 个人等待答疑，已知每个人需要答疑的时间为 ti（0i0,从而新的序列比原最优序列好，这与假设矛盾，故 s1 为最小时间，同理可证 s2sn 依次最小。五、在一个操场上一排地摆放着堆石子，N 堆石子的编号为 1，2，N。现要将石子有次序地合并成一堆。每堆石子包含的石子个数给定，规定每次只能选相邻的堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。（总分 20 分）（1)假设要求计算出将堆石子合并成一堆的最小得分值，已知该问题可以采用动态规划来进行求解，试写出你的动态规划算法的递归方程，并分析该递归方程能否采用递归程序来实现；（5 分）（2)试设计一个动态规划程序（伪代码即可），计算出将堆石子合并成一堆的最小得分值；（5 分）（3)试分析第（2）问中你设计的动态规划算法的时间复杂度；（5 分）（4)如果要得到取得最小得分的合并方案，将如何修改程序，使之能够输出最优的合并方案，并分析该方法的空间复杂度（注意：最优合并方案的表示可以采用加括号的方式表示）。（5 分）参考答案：参考答案：注意,本题会有多种解法,参考答案仅仅是一种,改卷子时一定要看清楚（1）设 S(i)表示前 i 堆石子总的数量(也即价值之和)，fij表示把第 i 堆到第 j 堆的石头合并成一堆的最优值。则递推方程为：1 s s(0)i kjmin f i kf kjjiijf ijij -得分 3 分由于该递推方程递推下去包含有大量重叠子问题，所以不能直接采用递归算法来实现，递归的算法复杂度为：11221()()(n)1nknf nf k fknn -得分 2 分（2）算法分为初始值赋值和循环两个评分点，算法的伪代码为；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）算法复杂度为(n3)。-得分 3 分（4）输出最优解的程序（和矩阵链相乘一样）Algorithm dd(p)n lengthp-1 for for i 1 to to nmi,i 0 end for for for l 2 to to n for for i 1 to to n (l 1)j i+(l 1)mi,j for for k i to to j-1q mi,k+mk+1,j+pi-1 pkpjif if 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 的节点，不管那种做法，答案都算对），其中红色无字方框是不满足要求的中间节点，红色有字方框为被限界的中间节点，红色圆形为不满足要求的解，灰色圆形为满足要求的解。(1,0,5)(2,1,4)(2,0,4)(3,1,3)(4,2,2)(4,1,2)(5,3,1)(5,1,1)mcl=3X(1)=1X(2)=1X(2)=0X(3)=1X(4)=1X(5)=1X(4)=0X(1)=0(3,1,3)X(2)=1X(3)=1X(3)=0(4,1,2)X(3)=0(3,0,3)X(2)=0X(5)=0 -得分 5 分