算法设计与分析期末笔试题(2011)

《算法设计与分析期末笔试题(2011)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京大学信息科学技术学院考试试卷考试科目：算法设计与分析姓名：学号：考试时间：2011年6月13日任课教师:汪小林/蒋婷婷/肖臻题号一二三四五六七总分分数装订阅卷人线北京大学考场纪律内1、考生进入考场后，按照监考老师安排隔位就座，将学生证放在桌面上。无学生证者不能参加考试；迟到超过15分钟不得入场。在考试开始30分钟后方可交卷出场。2、除必要的文具和主考教师允许的工具书、参考书、计算器以外，其它所有物品（包括空白纸张、手机、或有存储、编程、查询功能的电子用品等）不得带入座位，已经带入考场的必须放在监考人员指定的位

2、置。3、考试使用的试题、答卷、草稿纸由监考人员统一发放，考试结束时收以下以下为答题纸，共页回，一律不准带出考场。若有试题印制问题请向监考教师提出，不得向其他考不生询问。提前答完试卷，应举手示意请监考人员收卷后方可离开；交卷后不得要在考场内逗留或在附近高声交谈。未交卷擅自离开考场，不得重新进入考场答卷。考试结束时间到，考生立即停止答卷，在座位上等待监考人员收卷清点后，答方可离场。题4、考生要严格遵守考场规则，在规定时间内独立完成答卷。不准交头接耳，不准偷看、夹带、抄袭或者有意让他人抄袭答题内容，不准接传答案或者试卷

3、等。凡有违纪作弊者，一经发现，当场取消其考试资格，并根据《北京大学本科考试工作与学术规范条例》及相关规定严肃处理。5、考生须确认自己填写的个人信息真实、准确，并承担信息填写错误带来的一切责任与后果。学校倡议所有考生以北京大学学生的荣誉与诚信答卷，共同维护北京大学的学术声誉。以下为试题和答题纸，共15页。1/16得分一、填空题（每空1分，共20分）lgn222lgn1．请将下列5个关于n的函数(2),n,lgn,(lgn)!,2按渐进增长的关系排序，使得?1=Ω?2,?2=Ω?3,…,?4=Ω?5。________

4、____、____________、____________、____________和____________。2.对于n个元素的数组，插入排序、归并排序和快速排序的最坏情形运行时间分别是_______________、_______________和_______________。3．对于某种快速排序算法，如果每两次连续选取的划分元素，一次会把数组划分为基本等长的两个部分，另一次则会划分为长度为1和n-2的两个部分（n表示当前数组长度）。则该快速排序算法的时间复杂度是___________________。4

5、．对在1~k之间的n个数用计数排序法排序，时间复杂度为____________，如果k>>n时，可以采用基于计数排序法的____________排序法提高排序效率。5．线性时间选择算法SELECT首先从每_______个数中选取中位数，用算法______________递归求这些中位数的______________作为分治划分的参照元素。6．如果图G=(V,E)中的每条边的长度均为1，则求给定起点的单源最短路径问题的时间复杂性为_______________。7．货郎问题（TSP）在_______________

6、______________________的条件下有多项式时间的2-近似算法。8．MAX-3-CNF可满足问题的随机近似算法是____-近似算法。（填近似比例）9．用势能法分析动态表（T），其插入操作的平摊代价是____________，其势函数Φ(T)=_________________________________________。（注：Φ(T)是num[T]和size[T]的函数，其中num[T]是动态表中当前数据量，size[T]是动态表当前长度。）10．平面上有三个点P1=(x1,y1)、P2=(x

7、2,y2)、P3=(x2,y3)，判断线段P1P3在P1P2逆时针方向的条件是_____________________________________________________。2/16得分二、单选题.（每小题1分，共10分）1.下列说法正确的是：[]（a）求n个数中的最大数至少需要比较n-1次（b）求n个数中的次大数最少只需要比较⌊logn⌋次（c）在n个数中找某个数x，可以采用二分法，只需比较O(logn)次（d）不可能用少于7次的比较对5个数排序2.下列哪个问题的回溯算法不能基于对称性优化：[]（a

8、）图的m着色问题（b）最大团问题（c）旅行商问题（TSP）（d）圆排列问题3.关于在线算法，下列说法中错误的是：[]（a）一个在线问题的最优在线算法具有最小的竞争比（b）没有比k竞争比更优的页面调度算法了（c）LRU和FIFO都是k竞争比页面调度在线算法（d）在实际应用中，LRU和FIFO都是最优的页面调度算法4.用Edmonds-Karp算法计算最大流，时间复杂度是：[