装订线华南农业大学期末考试试卷（A卷） 2012学年第1学期 考试科目：算法设计与分析考试类型：（闭卷）考试 考试时间：120 分钟学号姓名年级专业题号一(20) 二(25) 三(16) 四(24) 五(15) 总分得分评阅人说明：（1）请勿漏填学号姓名等信息。
本试卷仅一份，请将答案直接填于试卷上，莫将试卷当草稿，想好了再写，若空白的位置不够，标注清楚后可以写反面；（2）答题时，对算法的描述可以采用文字、公式、图、伪代码、实例说明等混合形式。
请注意表达应条理清晰，思想简洁，勿长篇累述不得要领。
得分一、填空题（1~3题每空1分，第4题每空2分，共20分，结果直接填于划线处）1、化简下面f(n)函数的渐进上界表达式。
（5分）nnnf32/)(21，则____)(_________))((1OnfO322)(nnf，则____)(_________))((2OnfO33log)(nnf ，则____)(_________))((3OnfO2log42)(nnf ，则____)(_________))((4OnfOnnf3log)(5，则____)(_________))((5OnfO参考解答：)3())((1nOnfO ；)2())((2nOnfO ；)(log))((3nOnfO ；)())((24nOnfO ；)())((5nOnfO 。
2、用大O符号和关于n的渐进函数来表征如下算法Loop1至Loop3的运行时间。
（3分）算法1：O( )；算法2：O( )；12算法3：O( )参考解答：算法1：)(2n O ；算法2：)(3n O ；算法3：)(4n O 。
3、假设算法A 的计算时间为n n T 2)( ，现在一慢一快的两台计算机上测试算法A ，为解决规模n 的问题慢机运行算法A 花费t 秒，而另一台快机速度是慢机的256倍，则在快机上算法A 同样运行t 秒能解决n1规模，则n1和n 的关系为：n1= ；若算法B 的计算时间为2)(n n T ，其余条件不变，则n1= 。
（2分）参考解答：对算法A ，81n n ；对算法B ，n n 161 。
4、求最大的i 个数问题：给定n 个不同数的集合S 和正整数i （i<=n ），S 中元素无序，求S 中最大的i 个数且有序输出（按照升序或降序皆可）。
有下述多种算法：（10分）（1）算法A ：调用i 次顺序比较查找最大元素的算法findmax ，每调用一次删除此最大的数。
（2）算法B ：对S 排序，并输出S 中最大的i 个数。
（3）算法C ：对输入集合S 中的n 个数建立一个长度为n 的最大堆，接着反复调用i 次堆的extract_Max 过程。
其中extract_Max 过程为堆顶元素删除操作，该过程时间代价为O(logn)，而建立一个n 个元素的最大堆过程需要O(n)。
（4）算法D ：利用O(n)线性时间的分治算法找第i 大元素x ，然后调用partition 过程对n 个数以x 进行划分，比x 大的i-1个元素被置于x 的右边（即后边），再对这i 个数进行排序。
（5）算法E ：先对集合S 的前i 个元素建立一个长度为i 的最小堆，利用extract_Min 过程可得最小堆的堆顶元素为x ，让集合S 的后续n-i 个元素（称当前元素y ）逐个去和堆顶元素x 比较，若y>x ，将y 插入堆中并重新整合成最小堆和形成新的堆顶元素x ；否则丢弃y 。
当后续n-i 个元素全部比较完毕，则最小堆中的i 个元素即为原序列n 个数中最大的i 个数，最后对这堆中的i 个数调用i 次extract_Min 过程即可有序输出。
请分析A 、B 、C 、D 和E 这五个算法在最坏情况下的渐进时间复杂性（用n 和i 表示，但需化简，即忽略系数且略去低阶项）。
算法A ：______)(_________)(O n T A ； 算法B ：______)(_________)(O n T B ； 算法C ：_____)(_________)(O n T C ； 算法D ：______)(_________)(O n T D ；算法E ：_____)(_________)(O n T E 。
参考解答：算法A ：)()(n i O n T A ； )log ()(i n n O n T B 或)log ()(n n O n T B)log ()(n i n O n T C ，其中建立堆需要)(n O ，i 次堆顶元素删除)log (n i O 。
装订线)log()(iinOnTD，其中找第i大元素需要)(nO，对i个元素排序需要)log(iiO。
)loglog)(()(iiiiniOnTE或)log()(inOnTE，其中建立长度为i的最小堆需要)(i O，后续n-i个元素比较并判定是否逐个插入堆，最坏情况为)log)((iinO ，最后对i个堆中元素逐个输出堆顶元素需要)log(iiO，合计后略去低阶项为)log(inO。
得分二、简答题（共5小题，每题5分，共25分）1、请将下列函数的阶按上升顺序排列。
（5分）2/1n，2log n，n2，n2log，nn log，nn log2，102，nlog2，n22，22n参考解答：102，2log n，n2log，2/1n，nlog2，nn log，nn log2，n2，22n，n22提示：拿不准两个函数f(n)和g(n)时，考虑logf(n)和logg(n)，或2^f(n)或2^g(n)。
学生答题的排序后若有一个不在位，扣1分。
2、复数a+bi可以用数对(a, b)表示（其中1i2）。
描述一个方法，只需构造进行三次实数乘法（可采用有限次实数加减），即可计算a+bi和c+di相乘的结果数对(e, f)。
请写出采用了哪三次实数乘法？（5分）参考解答：bdibdaccdbaacbdibcadacdcba]))([()1()(),)(,(三次实数乘法分别是：bdcdbaac),)((,评分准则：此参考解答并非唯一解，只要能凑出ac, bd, (ad+bc)三部分的解皆可。
3、对于矩阵连乘所需最少数乘次数问题，其递推关系式为：1i k j[,]min{[,][1,]}i k ji jm i j m i k m k j p p p i j其中m[i，j]为计算矩阵连乘Ai…Aj所需的最少数乘次数，1 ip为矩阵Ai的行数，ip为矩阵Ai的列数。
现有四个矩阵，其中各矩阵维数分别为：A1A2A3A410 100100 55 5050 10p 0 p 1 p 1 p 2p 2 p 3p 3 p 4请根据递推关系，计算出矩阵连乘积A1A2A3A4所需要的最少数乘次数。
（5分）参考解答：根据递推公式：;2500]4][3[;25000]3][2[;5000]2][1[;0]4][4[;0]3][3[;0]2][2[;0]1][1[43232121pppmpppmpppmmmmm34;5000}]4][4[]3][2[,]4][3[]2][2[min{]4][2[;7500}]3][3[]2][1[,]3][2[]1][1[min{]3][1[431421320310 p p p m m p p p m m m p p p m m p p p m m m12500500007500]4][4[]3][1[800050025005000]4][3[]2][1[150001000050000]4][2[]1][1[min ]4][1[m 430420410p p p m m p p p m m p p p m m因此：8000]4][1[ m4、操场上摆放一行共n 堆石头，呈直线排列。
n 堆石子从左到右方向编号为1~n ，每堆石子个数分别为a[1],…,a[n]，现在要将石子有次序的合并为一堆，规定每次只能选相邻的2堆合并为新的一堆，并将新的一堆的石子数记为该次合并的得分，经过n-1次合并，最终合并为一堆，总得分为n-1次合并得分之和。
现要设计一个算法，计算出将一行的n 堆石子合并为一堆的最小得分。
这里假设m[i,j]为合并石子Ai…Aj, 1≤i ≤j ≤n ，所得到的最小得分。
请写出m[i,j]的递推公式。
（5分）参考解答：设n 堆石子从左到右方向编号为1,2,…,n，每堆石子个数分别为a[1],…,a[n]。
n 堆石子的合并有许多不同的方式，每种合并方式对应于n 个矩阵连乘的一种完全加括弧方式。
显然，这里合并是满足最优子结构性质的，用A1…An 来代表每堆的石子，则最后一次合并在Ak 和Ak+1之间，则A1…An 的最优合并为((A1…Ak)(Ak+1…An))，可以看出最优解左边部分(A1…Ak)和右边部分(Ak+1…An)的合并也分别是最优的。
假设m[i,j]为合并石子Ai…Aj, 1≤i≤j≤n，所得到的最小得分，若没有“合并”这个动作，则为0。
原问题所求的最优值即为m[1,n]。
j i t a j k m k i m j i ji t jk i ][]},1[],[{min 0j]m[i,填充m[i,j]即可得到任意行状摆放的石子合并的最小得分。
5、有这样一类特殊0-1背包问题：可选物品重量越轻的物品价值越高。
n=6，c=20，P=(4，8，15，1，6，3)，W=(5，3，2，10，4，8)。
其中n 为物品个数，c 为背包载重量，P 表示物品的价值，W 表示物品的重量。
请问对于此特殊的0-1背包问题，为使放进背包的物品总价值最大，应如何选择放进去的物品？此例能获得的最大总价值多少？（5分）参考解答：因为该0－1背包问题比较特殊，恰好重量越轻的物品价值越高，所以优先取重量轻的物品放进背包。
最终可以把重量分别为2，3，4，5的三个物品放进背包，得到的价值和为15 + 8 + 6 + 4 = 33，为最大值。
得分三、画图题（共16分，每图4分）1、字符a~h 出现的频率恰好是前八个Fibonacci 数（数列最开始两个元素都为1，之后每个元素都等于前两个元素之和），请画出a~h 这八个字符的Huffman 编码树。
（4分）参考解答：若字符a~h 出现的频率恰好是前8个Fibonacci 数，它们的Haffman 编码树如下图所示。
5装订线2、对如下问题采用回溯的搜索算法，请画出搜索状态的解空间树。
注意这题无需说明算法或搜索过程，只画解空间树即可。
（8分：4分+4分）（1）作业分配问题：n 个作业分配给n 个人，将第i 个作业分给第j 个人所需费用代价为c[i][j]，为每个作业分配给不同的人来完成，并使得所有工作的总费用和最小。
以n=3为例，请画出搜索的解空间树。
（2）图的m 着色问题：给定n 个顶点的无向连通图G 和m 种不同的颜色，用这m 种颜色为图G 的各顶点着色，且G 中邻接顶点（指有边相连的顶点）不能着同色，求所有不同的着色方法数。
