算法设计与分析-期末试卷-A卷(完整含答案)

1装订线华南农业大学期末考试试卷（A卷）2012学年第1学期考试科目：算法设计与分析考试类型：（闭卷）考试考试时间：120分钟学号姓名年级专业题号一(20)二(25)三(16)四(24)五(15)总分得分评阅人说明：（1）请勿漏填学号姓名等信息。本试卷仅一份，请将答案直接填于试卷上，莫将试卷当草稿，想好了再写，若空白的位置不够，标注清楚后可以写反面；（2）答题时，对算法的描述可以采用文字、公式、图、伪代码、实例说明等混合形式。请注意表达应条理清晰，思想简洁，勿长篇累述不得要领。得分一、填空题（1~3题每空1分，第4题每空2分，共20分，结果直接填于划线处）1、化简下面f(n)函数的渐进上界表达式。（5分）nnnf32/)(21，则____)(_________))((1OnfO322)(nnf，则____)(_________))((2OnfO33log)(nnf，则____)(_________))((3OnfO2log42)(nnf，则____)(_________))((4OnfOnnf3log)(5，则____)(_________))((5OnfO参考解答：)3())((1nOnfO；)2())((2nOnfO；)(log))((3nOnfO；)())((24nOnfO；)())((5nOnfO。2、用大O符号和关于n的渐进函数来表征如下算法Loop1至Loop3的运行时间。（3分）算法1：O()；算法2：O()；算法2Loop2(n)s=0;for(i=1;i=n2;i++)for(j=1;j=n;j++)s=s+i*j;算法1Loop1(n)s=0;for(i=1;i=n;i++)for(j=1;j=i;j++)s=s+i*j;2算法3：O()参考解答：算法1：)(2nO；算法2：)(3nO；算法3：)(4nO。3、假设算法A的计算时间为nnT2)(，现在一慢一快的两台计算机上测试算法A，为解决规模n的问题慢机运行算法A花费t秒，而另一台快机速度是慢机的256倍，则在快机上算法A同样运行t秒能解决n1规模，则n1和n的关系为：n1=；若算法B的计算时间为2)(nnT，其余条件不变，则n1=。（2分）参考解答：对算法A，81nn；对算法B，nn161。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比较，若yx，将y插入堆中并重新整合成最小堆和形成新的堆顶元素x；否则丢弃y。当后续n-i个元素全部比较完毕，则最小堆中的i个元素即为原序列n个数中最大的i个数，最后对这堆中的i个数调用i次extract_Min过程即可有序输出。请分析A、B、C、D和E这五个算法在最坏情况下的渐进时间复杂性（用n和i表示，但需化简，即忽略系数且略去低阶项）。算法A：______)(_________)(OnTA；算法B：______)(_________)(OnTB；算法C：_____)(_________)(OnTC；算法D：______)(_________)(OnTD；算法E：_____)(_________)(OnTE。参考解答：算法A：)()(niOnTA；)log()(innOnTB或)log()(nnOnTB)log()(ninOnTC，其中建立堆需要)(nO，i次堆顶元素删除)log(niO。算法3Loop3(n)s=0;for(i=1;i=n2;i++)for(j=1;j=i;j++)s=s+i*j;3装订线)log()(iinOnTD，其中找第i大元素需要)(nO，对i个元素排序需要)log(iiO。)loglog)(()(iiiiniOnTE或)log()(inOnTE，其中建立长度为i的最小堆需要)(iO，后续n-i个元素比较并判定是否逐个插入堆，最坏情况为)log)((iinO，最后对i个堆中元素逐个输出堆顶元素需要)log(iiO，合计后略去低阶项为)log(inO。得分二、简答题（共5小题，每题5分，共25分）1、请将下列函数的阶按上升顺序排列。（5分）2/1n，2logn，n2，n2log，nnlog，nnlog2，102，nlog2，n22，22n参考解答：102，2logn，n2log，2/1n，nlog2，nnlog，nnlog2，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、对于矩阵连乘所需最少数乘次数问题，其递推关系式为：1ikj0[,]min{[,][1,]}ikjijmijmikmkjpppij其中m[i，j]为计算矩阵连乘Ai…Aj所需的最少数乘次数，1ip为矩阵Ai的行数，ip为矩阵Ai的列数。现有四个矩阵，其中各矩阵维数分别为：A1A2A3A41010010055505010p0p1p1p2p2p3p3p4请根据递推关系，计算出矩阵连乘积A1A2A3A4所需要的最少数乘次数。（5分）参考解答：根据递推公式：;2500]4][3[;25000]3][2[;5000]2][1[;0]4][4[;0]3][3[;0]2][2[;0]1][1[432321210pppmpppmpppmmmmm4;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pppmmpppmmmpppmmpppmmm12500500007500]4][4[]3][1[800050025005000]4][3[]2][1[150001000050000]4][2[]1][1[min]4][1[m430420410pppmmpppmmpppmm因此：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]。jitajkmkimjijitjki][]},1[],[{min0j]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装订线此图并非唯一解，但所做的编码树须满足Huffman树的构造方法，频率越低的在树的越深处。2、对如下问题采用回溯的搜索算法，请画出搜索状态的解空间树。注意这题无需说明算法或搜索过程，只画解空间树即可。（8分：4分+4分）（1）作业分配问题：n个作业分配给n个人，将第i个作业分给第j个人所需费用代价为c[i][j]，为每个作业分配给不同的人来完成，并使得所有工作的总费用和最小。以n=3为例，请画出搜索的解空间树。（2）图的m着色问题：给定n个顶点的无向连通图G和m种不同的颜色，用这m种颜色为图G的各顶点着色，且G中邻接顶点（指有边相连的顶点）不能着同色，求所有不同的着色方法数。以n=3，m=3为例，请画出搜索的解空间树。参考解答：（1）（1）n=3的排列树（2）（2）n=3,m=3的n层完全m叉树）3、折纸留痕：你喜欢折纸吗？给你一张很大的纸，对折以后再对折，再对折……，每次对折都是从右往左折（沿逆时针），因此折了很多次以后，原来的大纸就会变成窄窄的纸条。现在把这个纸条沿着折纸的痕迹打开，把每个痕迹视为一个“直角”，那么从纸的一端沿着与纸面平行的方向看过去（即截面图），会看到一个曲线。例如，对折2次和3次，看到如下曲线。请你画出对折4次的截面曲线。（4分）对折两次后形成的曲线对折三次后形成的曲线参考解答：32322x[3]=1x[1]=1x[2]=1331221322133131201010101010101cdefghab6对折四次后形成的曲线得分四、程序填空题（共12个空格，每空2分，共24分,结果集中的填于程序下方划线处）1、有重复元素的全排列：对n个元素集R={r1,r2,…,rn}进行全排列，其中r1,r2,…,rn可能相同，下面算法框架Permpp()可以输出R的所有不同的排列，请补充完整。voidPermpp(cha