算法设计与分析(博士考试)

一、单选题（每小题1分，共10分）1、下列函数中，渐近紧致界为)(2n的是（C）。A．2logn；B．n3；C．24100nn；D．nn210/2。2、下列函数中，渐近非紧上界为)(2no的是（D）。A．nn2/1；B．34log10nn；C．nn22；D．2110n。3、以下描述中，不正确的有（A）。A．在渐进复杂性概念下，等等式式)(42/1nOn在在16n时时成成立立；；B．在渐进复杂性概念下，有)2(21nnO成立；C．在渐进复杂性概念下，n与nnsin1无法渐近比较；D．对于任意函数0)(ng，))(())((ngwngoΦ(Φ为空集)。4、在快速排序中，以下描述不正确的是（D）。A．在快速排序，最好时间复杂性和平均时间复杂性均为)log(nnO；B．若精心挑选一个划分元，每次经过Partition算法后，分成两个子问题，从而使得其最坏时间复杂性为)log(nnO；C．若随机挑选一个划分元，每次经过RandomizedPartition算法后，分成两个期望均长的子问题，从而使得其期望时间复杂性为)log(nnO；D．不管是精心挑选还是随机挑选划分元，快速排序的最坏时间复杂性均为)(2nO。6、Dijkstra算法是解单源最短路径问题的一个贪心算法，工作过程与Prim算法是一样的，不同点在于它比较的是路径的长度而不是边的长度。以下哪种权重的图，Dijkstra算法总是能够产生一个正确的解。（D）A．自然数；B．整数；C．实数；D．非负实数。8、分支限界法与回溯法都是在问题的解空间树T上搜索问题的解，二者（B）。A．求解目标不同，搜索方式相同；B．求解目标不同，搜索方式也不同；C．求解目标相同，搜索方式不同；D．求解目标相同，搜索方式也相同。9、回溯法在解空间树T上的搜索方式是（A）。A．深度优先；B．广度优先；C．最小耗费优先；D．活结点优先。10、在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为扩展结点的是（B）。A．回溯法；B．分支限界法；C．回溯法和分支限界法；D．回溯法求解子集树问题。二、填空题（每空1分，共10分）1、在空格处填上合适的大O函数使得下列关系，在渐进复杂性概念下成立。)1(O_____)(lgnO__)(nO_)lg(nnO________)2()(2nOnO。2、分治策略求解问题可以分为三步：分解；递归地解子问题；组合。有的问题分解难而组合容易，如_快速排序_，有的问题分解容易而组合难，如归并排序_。3、活动安排问题既可以用动态规划算法求解也可以用贪心算法求解。其中用动态规划算法求解的时间复杂性为：____)(3nO______；用贪心算法求解的时间复杂性为：_)(nO_____（假定n个活动已经按照结束时间单调有序）。4、哈夫曼编码是用于___数据文件___压缩的一个十分有效的编码方法。其中算法HuffmanTree用最小堆来实现优先队列。而退出优先队列算法DeleteMin和进入优先队列算法Insert均需要____)(lgnO____时间。三、求以下递推式的渐近上界（每小题8分，共16分）1．nnTnT)4/(3)(nnTnT)4/(3)()4/4/(34/(3nTnn)))4/4/4/(34/4/(34/(3nTnnn（abnban///）)))4/(34/(34/(332nTnnn（2分）迭代i次后，将有))...)))4/(34/(3...4/(34/(34/(3)(132iinTnnnnnnT（4分）直到04/1in（ni4log）时))...)))0(34/(3...4/(34/(34/(3)(32TnnnnnnTi))...)))0(34/(3...4/(34/(34/(32Tnnnnni)0(3)43(...)43()43(43132Tnnnnnii)0(341Tni（6分）)0(34)(3log4TnnnT（3log1log144333nni）)()(nOnT（)1()0(OT）（8分）2．nnTnTnT)3/2()3/()(n3nn32nn9n92n92n94nn…………总共)lg(nnOn2/3log（4分）在将递归树各层的值加起来时，发现每一层的值都为n。从根到叶的最长的一条路经是1)3/2()3/2(2nnn。因为当nk2/3log时，1)3/2(nk，该树的高度为nnnlg)2/3lg/1(2/3lg/lglog2/3。因而，该递归式的解至多是)lg(log2/3nnOnn。（8分）四、简答题（每小题4分，共20分）1．试论)1(O和)2(O的区别。2．简述回溯法和分支限界法的异同。（1）相同点：都是用来求解组合难题的系统方法，需要在解空间按照某种策略搜索，但都不同于一般的穷举搜索方法。（1分）（2）不同点：搜索方式不同。回溯法按照深度优先搜索原则，而分支限界法按照广度优先或是最佳优先原则；（3分）所用的数据结构不同。栈和队列或优先队列。（4分）3．分析以下程序，然后指出程序返回（return）的结果是多少，为什么？Darts(n){0k;fori=1tondo{xuniform(0,1);//随机生成一个大于等于0小于1的实数xy;if(122yx)thenk;}returnnk/4;}五、计算题（每小题7分，共14分）1．计算题：请用动态规划算法找出矩阵连乘4321AAAA的最佳计算次序（即最佳完全加括号方式），其中4035)1(1)(ijaA，2040)2(2)(ijaA，1020)3(3)(ijaA，1510)4(4)(ijaA。列出计算过程。因为，jipppmmjimjkijkikjkiij}{min011（2分）所以，2800020403512m；800010204023m；300015102034m（3分）}104035,102035min{231213mmm=}140008000,700028000min{22000（4分）14000}120003000,60008000min{}152040,151040min{342324mmm（5分）}151035,152035,154035min{1334122414mmmmm}525022000,10500300028000,2100014000min{27250}27250,41500,35000min{（6分）则最佳完全加括号方式为：)))(((4321AAAA（7分）。2．在0-1背包问题中，有四种物品，其重量(价值)分别为：2kg(12$)，1kg(10$)，3kg(20$)，2kg(15$)。并且背包总容量5C。请用动态规划算法，找出一个最优解的装包情形及其装包的总价值。列出计算过程。解：设],[jiV是背包容量为j，可选物品为前i个物品时，0-1背包问题的最优值，即能够装进承重量为j的背包中前i个物品最有价值子集的总价值。则有：iiiiwjwjjiVwjiVvjiVjiV如果如果],1[]},1[],,1[max{],[（2分）初始条件：当0j时，0],0[jV，当0i时，0]0,[iV。计算过程见下表：ij012345000000010012121212201012222222401015253037（6分）故：第1、2、4物品装包其它不装，总价值为37$（7分）六、算法设计题（每小题10分，共30分）要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间复杂性。1．某次选举中有k个候选人，编号从1到k，有n个选民参与了选举，每个选民只能选择一位候选人，当某个候选人获得超过一半的选票时，则认为该候选人获胜。试设计一个算法，在选举结束后，可在)(nO的时间内判断是否有某个候选人获胜。2．在一个直线跑道上摆放着一行共n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分。3．假定我军计划炸毁敌方整个通信网络。敌方通信网络由各个驻点加上其间的通信线路组成（如下图3）。炸毁一个驻点，则该驻点与其它所有驻点间通信就中断。请设计算法，找出一种最佳轰炸策略，使得敌方整个通信网络瘫痪，即，使得所有驻点间都不能通信。图1：通信网络拓扑图（其中一部分）ABFCDE