内部资料，转载请注明出处，谢谢合作。北京大学信息科学技术学院考试试卷考试科目：算法设计与分析姓名：学号：考试时间：2009年6月9日任课教师:考场纪律1．请持学生证入场考试，并按指定座位就座；除必要的文具和教师指定的用具用书外，其他所有物品包括手机、呼机、MP3、电子词典、书籍、笔记、纸张等严禁带入座位，必须放在指定位置。凡有试题印制问题请向监考教师提出，不得向其他考生询问。2．认真、诚实、独立并在规定时间内完成答卷，严禁任何形式的违纪作弊行为；否则，本答卷成绩以0分记，并根据《北京大学本科考试工作与学术规范条例》给予纪律处分。3．提前交卷的考生不要在考场逗留，不要在门口、窗外大声喧哗。考试结束时间到，请停止答卷，在座位等候监考教师收卷并清点完毕，方可离开考场；考题和试卷不得带出考场。以下为试题和答题纸，共9页。一、填空题(选做5道，10分)1．用矩阵幂的方法求斐波那契数，其运行时间为（）。2．对于一个可以用动态规划法求解的问题，要求问题既要满足（）的特性，又要具有大量的（）。题号一二三四五六七八总分分数阅卷人装订线内不要答题3．对于一个可以用贪心法求解的问题，不仅要求问题满足（）的特性，还应证明其贪心策略的（）。4．设有n个栈操作（PUSH、POP、MULTIPOP）的序列，作用于初始为空的栈S。不区分三种操作，则每个操作的最坏运行时间为（），平摊运行时间为（）。5．三种平摊分析的方法分别为（）、（）、（）。6．四后问题的搜索空间为（）树；0-1背包问题的搜索空间为（）树；巡回售货员问题的搜索空间为（）树。7．（）法的求解目标是找出解空间树中满足约束条件的所有解，而（）法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。8．回溯法一般以（）优先的方式搜索解空间树，而分支限界法则一般以（）优先或以最小耗费优先的方式搜索解空间树。二、单项选择题(10分)1．下列关于排序算法的叙述，不正确的是？（）A)堆排序的最差情形运行时间为Θ(nlgn)B)快速排序平均情形运行时间为Θ(nlgn)C)任何排序算法的最差情形运行时间都不可能比Ω(nlgn)更小D)插入排序在最好情形下的运行时间为Θ(n)2．对于课堂讲解的线性时间内找第i小的元素的算法，（）下列叙述中不正确的是？A)算法第一步中可以按每五个元素一组找中位数；B)算法第一步中可以按每七个元素一组找中位数；B)算法第一步中不能按每三个元素一组找中位数；D)如果要求的n个元素的中位数，则中位数一定是第一步中找到的中位数中的某一个。3．主方法可以求解满足形如下式的递推方程，（）则下列关于方程中的约束中不准确的是？A)对于系数a，必须满足a≥1B)对于系数b，必须满足b>1C)若对于常数ε>0，f(n)=O(nlogba-ε)，则T(n)=Θ(nlogba)D)若f(n)=O(nlogba)，则T(n)=Θ(nlogbalogn)4．下列哪些问题不能用贪心法求解？（）A)霍夫曼编码问题B)单源最短路径问题C)0-1背包问题D)最小生成树问题装订线内不要答题5．可合并堆上可以不包含下列哪个操作？（）A)DECREASE-KEY(H,x,k)B)UNION(H1,H2)C)INSERT(H,x)D)EXTRACT-MIN(H)6．不同堆上插入操作最差情形下的开销或平摊开销，（）对二叉堆、二项堆和斐波那契堆，下列选项中描述错误的是？A)二叉堆为Θ(lgn)B)二项堆为O(lgn)C)斐波那契堆为Θ(1)D)三种堆的开销都是Θ(lgn)7．关于网络流的割，下列选项中错误的是？（）割(S,T)是流网络G=(V,E)的一个划分，其中s∈S,t∈T。如果f是G上的流，那么流经割的净流量为f(S,T)，割(S,T)上的容量定义为c(S,T)。A)|f|≤c(S,T)B)f(S,T)=|f|C)f(s,V-s)=|f|D)f(S-s,V)=|f|8．下列随机算法一定有解但解不一定正确的是？（）A)SherwoodB)LasVegasC)MonteCarloD)三者都不是9．在快速排序算法中引入随机过程的主要目的是什么？（）A)改善确定性算法的平均运行时间B)保证算法总能在O(nlgn)时间内结束C)避免了算法最坏情况下的发生D)改善了确定性算法最坏情形下的平均运行时间10．用MonteCarlo方法估计四后问题回溯算法的效率。（）五次实验结果分别为<1,4,2>、<2,4,1,3>、<4,2>、<3,1,4,2>、<1,3>，则解空间中的结点数估计为？A)16B)16.2C...
