2015武汉大学《算法设计与分析》期中试卷

武汉大学计算机学院 算法设计与分析 期中测试

姓名： 学号： 学院： 专业：

一、请用大“O(·)”记号求下列函数的渐进表达式：3n2 + 10n -1; n2/10 + 2n +1/n; 14 + 5/n + 1/n2 ; logn2?n; 20log3n（10分,每小题2分）

解答：

上述渐进表达式的时间复杂度分别为：

3n2 + 10n -1 =O(n2); n2/10 + 2n + 1/n =O(2n); 14 + 5/n + 1/n2=O(1);

logn2?n=O(logn); 20log3n =O(n)

二、 令{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为根结点的树。

解答：

(a)12345678(b)216346587UNION（1,2）;UNION（4,3）;UNION（5,6）;UNION（7,8）;(c)125UNION（2,6）;6(d)FIND（1）;5812(e)437681725UNION（3,8）;(f)43UNION（8,6）;6(g)3487125FIND（4）;6(h)3487125FIND（5）;

三、 设有n个小球，其中一个是劣质球，其特征是重量较轻，给你一个天平，设计一个分治算法，找出劣质球。（总分15分） （1) 写出算法的主要思路；（5分） （2) 试分析算法的时间复杂度；（5分） （3) 试分析n=9和10，即n分别为奇数和偶数，两种情形下的分治过程。（5分）

解法：（1）二对分算法思路：

①若小球个数≤2，则直接比较，找出假币。否则，转②。 ②若n%2=0，则将其分为个数相等的两部分，选择轻的部分保留，转①；否则转③。

③将a[0…n-2]分为相等的两部分：若两部分重量相等，则a[n-1]为劣质球，终止；若不等，则保留轻的部分，转①。

（2）以比较操作为基本运算，最好情况比较1次，最坏比较logn次，

（3）① 分成两部分：a[0…4]、a[5…9]，假定后者轻，保留a[5…9]

② 分成三部分：a[5…6]、a[7…8]、a[9]，若前两者一样重，故劣质球为a[9]。

四、 考试前，A老师给同学答疑，同一时间只能给一个同学答疑，有n个人等待答疑，已知每个人需要答疑的时间为ti（0

（1）请写出两种以上的贪心策略，比较它们，选出一种用于贪心算法；（5分） （2）写出贪心算法的主要思路；（5分）

（3）该算法一定能够保证排队时间总和最小？请简要说明理由。（5分）

解法：

（1）答疑时间短先安排；答疑时间长先安排。

（2）本题贪心算法：n个人时间从小到大排序，就是这n个人最佳排队方案。求部分和的和即为所求。

（3）反证法证明：假设有最优解序列：s1,s2…sn,如s1不是最小的Tmin，不妨设sk=Tmin,将s1与sk对调，显然，对sk之后的人无影响，对sk之前的人等待都减少了，(s1-sk)>0,从而新的序列比原最优

序列好，这与假设矛盾，故s1为最小时间，同理可证s2…sn依次最小。

五、 在一个操场上一排地摆放着Ｎ堆石子，N堆石子的编号为1，2，?，N。现要将石子有次序地合并成一堆。每堆石子包含的石子个数给定，规定每次只能选相邻的２堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。（总分20分）

（1) 假设要求计算出将Ｎ堆石子合并成一堆的最小得分值，已知该问题可以采用动态规划来进行求解，试写出你的动态规划算法的递归方程，并分析该递归方程能否采用递归程序来实现；（5分） （2) 试设计一个动态规划程序（伪代码即可），计算出将Ｎ堆石子合并成一堆的

最小得分值；（5分）

（3) 试分析第（2）问中你设计的动态规划算法的时间复杂度；（5分）

（4) 如果要得到取得最小得分的合并方案，将如何修改程序，使之能够输出最

优的合并方案，并分析该方法的空间复杂度（注意：最优合并方案的表示可以采用加括号的方式表示）。（5分）

参考答案：注意,本题会有多种解法,参考答案仅仅是一种,改卷子时一定要看清楚

（1） 设S(i)表示前i堆石子总的数量(也即价值之和)，f[i][j]

表示把第i堆到第j堆的石头合并成一堆的最优值。则递推方程为：

(f[i][k]?f[k?1][j]?s[j]?s[i])i?j??imin?k?jf[i]?j???

0i?j?? -----------------------得分3分

由于该递推方程递推下去包含有大量重叠子问题，所以不能直接采用递归算法来实现，递归的算法复杂度为：

1?2n?2?f(n)??f(k)f(n?k)??? n?1nk?1??n?1 -----------------------得分2分 （2） 算法分为初始值赋值和循环两个评分点，算法的伪代码为；

Algorithm dd（） {

for (i=1; i<=n; i++) f[i][i]=0; //可能超出int的范围 -----------------------得分2分 for (i=n-1; i>=1; i--) for (j=i+1; j<=n; j++) f[i][j]=INF；

for (k=i; k<=j-1; k++)

f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]); -----------------------得分3分 printf(\ return 0; }

（3） 算法复杂度为?(n3)。

-----------------------得分3分 （4） 输出最优解的程序（和矩阵链相乘一样）

Algorithm dd(p) ｛