算法设计与分析期中笔试题(2015)(答案)

1/8北京大学信息科学技术学院考试试卷考试科目：算法设计与分析姓名：学号：考试时间：2015年4月27日大班教师:小班教师:以下以下为答题纸，共页答题要求：解答算法设计题目时，请先用一段话描述算法思想。若用动态规划算法，请写出递推方程、边界条件、标记函数等设计要素；贪心法需给出证明；回溯法需给出解向量、搜索树等、约束条件；各种算法需分析时间复杂度。阅卷时会根据算法的正确性和效率评分。题号一二三四五六七总分分数阅卷人北京大学考场纪律1、考生进入考场后，按照监考老师安排隔位就座，将学生证放在桌面上。无学生证者不能参加考试；迟到超过15分钟不得入场。在考试开始30分钟后方可交卷出场。2、除必要的文具和主考教师允许的工具书、参考书、计算器以外，其它所有物品（包括空白纸张、手机、或有存储、编程、查询功能的电子用品等）不得带入座位，已经带入考场的必须放在监考人员指定的位置。3、考试使用的试题、答卷、草稿纸由监考人员统一发放，考试结束时收回，一律不准带出考场。若有试题印制问题请向监考教师提出，不得向其他考生询问。提前答完试卷，应举手示意请监考人员收卷后方可离开；交卷后不得在考场内逗留或在附近高声交谈。未交卷擅自离开考场，不得重新进入考场答卷。考试结束时间到，考生立即停止答卷，在座位上等待监考人员收卷清点后，方可离场。4、考生要严格遵守考场规则，在规定时间内独立完成答卷。不准交头接耳，不准偷看、夹带、抄袭或者有意让他人抄袭答题内容，不准接传答案或者试卷等。凡有违纪作弊者，一经发现，当场取消其考试资格，并根据《北京大学本科考试工作与学术规范条例》及相关规定严肃处理。5、考生须确认自己填写的个人信息真实、准确，并承担信息填写错误带来的一切责任与后果。学校倡议所有考生以北京大学学生的荣誉与诚信答卷，共同维护北京大学的学术声誉。装订线内不要答题2/8得分一、（15分）按照阶递减的顺序排列下面的函数。如果函数f(n)与g(n)的阶相同，就表示成f(n)=(g(n))，本题只需要给出结果。答案：nnknnnnnnnnnnknnnnnnnloglog),(log12,2),(10log),log()!log(,),()(log,2,2,!1log2log3logloglog2得分二、（10分）求解下述递推方程，其中k是给定的正整数.要求给出求解过程.𝑇(𝑛)=4𝑇(𝑛2)+𝑛2log𝑘𝑛𝑇(1)=1解答：𝑇(𝑛)=𝑂(𝑛2log𝑘+1𝑛)或𝑇(𝑛)=𝛩(𝑛2log𝑘+1𝑛)nnnnnnnknnnnnnnnnnknn10log,,!,,loglog,log),!log(,2,2,)(log,2,1,log,2loglog3log2log1log23/8得分三、（15分）设A是n个实数的数组，考虑下面的递归算法：XYZ(A[1..n])1.ifn=1thenreturnA[1]2.elsetempXYZ(A[1..n1])3.iftempA[n]4.thenreturntemp5.elsereturnA[n]1.用简短的文字说明算法XYZ的输出是什么？2.以A中元素的比较作为基本运算，列出算法XYZ最坏情况下时间复杂度W(n)的递推方程，并解出W(n)。3.在求解这个问题的算法类中，算法XYZ最坏情况下是不是效率最高的算法？为什么？解答：1.A中的最小实数。2.W(n)=W(n1)+1W(1)=0W(n)=n13.是效率最高的算法，因为找最小问题至少需要比较n1次。4/8得分四、（15分）设A是n个数的序列，如果A中的元素x满足以下条件：小于x的数的个数n/4，且大于x的数的个数n/4，则称x为A的近似中值.设计算法求A的一个近似中值.说明算法的设计思想和最坏情况下的时间复杂度.答案算法1：1.用Select算法找第n/4小的数a和第3n/4小的数b2.ifa=breturn“无解”3.else用a和b划分数组A为A1,A2,A3,A4,A5，其中A1的数a，A2的数=a,A3的数a且小于b，A4的数=b.A5的数b.（当a=b时，无解）4.ifA3非空，则A3中的数为近似中值，否则无解.时间O(n).5/8得分五、（15分）在一组服务器S={𝑠1,𝑠2,…,𝑠𝑛}上放置文件副本,如果副本放置在𝑠𝑖上,则产生𝑐𝑖（正的整数值）的存储代价.当在𝑠𝑖上发生对该文件的访问时,如果文件副本在𝑠𝑖上,则无访问代价;如果不在𝑠𝑖上,则需要顺序查找𝑠𝑖+1,𝑠𝑖+2,…,𝑠𝑗，直到在𝑠𝑗上找到文件副本,这将产生𝑗−𝑖的访问代价.规定副本至少一定要放置在𝑠𝑛上,以便所有的访问均能成功.问当每个服务器上均发生对该文件的一次访问时,存储代价加访问代价之和最少是多少?设计一个算法计算之,说明算法的正确性,并分析算法的时间复杂度.参考答案一：𝐹𝑛[𝑘]={0𝑘=𝑛min{𝐹𝑛[𝑗]+𝑐𝑗+(𝑗−𝑘)(𝑗−𝑘−1)2|𝑘𝑗≤𝑛}0≤𝑘𝑛𝐹𝑛(𝑘)代表仅考虑在𝑠𝑘+1,𝑠𝑘+2,…,𝑠𝑛这些服务器上放置文件副本的最小总代价.求𝐹𝑛(0).递推式的含义为,枚举第一个副本放置的服务器编号,计算该副本承担的代价,加上该副本之后的服务器上最优副本放置方案的代价，取最小值为最优结果.𝐹𝑛[𝑙]={0𝑙=0min{𝐹𝑛[𝑡]+𝑐𝑛−𝑡+𝑡(𝑡−1)2|0≤𝑡𝑙}0𝑙≤𝑛𝐹𝑛[𝑙]表示只考虑后l个服务器上如何放置文件副本的子问题。求𝐹𝑛[𝑛]。参考答案二：关于副本放置问题，有一个比较简单的表示，只需要一个参数来界定子问题。令OPT[j]表示副本放在sj，从s1到sj的最小代价，那么原始问题求的是OPT[n]。假如在sj前面，离sj最近的放置副本的位置是si，那么OPT[j]=cj+min{OPT[i]+C(i+1,j)|0ij}其中C(i+1,j)=(j-i)(j-i-1)/2s1sisj6/8OPT[0]=0上式的C(i+1,j)代表si+1到sj-1这些服务器上的访问代价之和，其中sj-1的代价是1，sj-2的代价是2，…,si+1的代价是j-i-1.求和是1+2+…+(j-i)=(j-i)(j-i-1)/27/8得分六、（15分）一个公司需要购买n个密码软件的许可证，按规定每个月至多可得到一个软件许可证.每个许可证当前售价都是1000元，但是第i个许可证的售价将按照ri1的指数因子增长，i=1,2,…,n.例如，第i个许可证的售价在1个月后将是ri1000元，2个月后将是ri21000元，k个月后将是rik1000元.假设r1,r2,…,rn是给定正整数，试给出一个购买许可证的顺序，以使得花费的总钱数最少.设计一个算法求解这个问题，说明设计思想，证明其正确性并分析算法最坏情况下的时间复杂度.答案排序ri为递减次序，使得r1r2…rn，依次购买.设最优解为OPT(I)，假设在OPT(I)存在逆序，即rjri，但是j在i前面购买.一定有相邻的逆序,即存在i和j,使得j在i前面与i相邻.设j是第t个月购买，i是第t+1个月购买.那么交换i与j得到解S(I)，那么花费之差V(OPT(I))V(S(I))=(rit+11000+rjt1000)(rit1000+rjt+11000)=[rit(ri1)rjt(1rj)]1000由于rirj，于是ri1rj1且ritrjt，得到上式0.时间为O(nlogn).8/8得分七、（15分）某会展中心有m行n列会议室阵列，每间会议室为边长为10米的正方形，现在要在会议室中设置无线路由器，假设只能在会议室的中心位置放置路由器，每个路由器的信号覆盖范围是一个半径为25米的圆形，请问如何设计路由器的位置，使得所有的会议室的中心点都有信号并使得路由器个数最少。答案：解向量为mn维x_11,x_12,…,x_mn,x_ij=1表示会议室(i,j)放置路由器，x_ij=0表示不放。这样搜索树为mn层。初始令所有的会议室都放置路由器，算法从会议室（1,1）开始，左子树表示拿走（1，1）会议室的路由器，右子树表示保留。这样可证明满足多米诺性质。在进入左子树时要检查是否有会议室未被覆盖，若有则停止搜索该分支。检查涉及的会议室个数为常数个，每个涉及的会议室只需要寻找能否在25米之内找到路由器，这个也是常数时间。所以总的时间复杂度最坏情况为O(2^mn)。