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

精选优质文档-倾情为你奉上一、 单选题（每小题1分，共10分）1、下列函数中，渐近紧致界为的是（ C ）。A； B； C； D 。2、下列函数中，渐近非紧上界为的是（ D ）。A； B； C； D 。3、以下描述中，不正确的有（ A ）。A在渐进复杂性概念下，等式在时成立；B在渐进复杂性概念下，有成立； C在渐进复杂性概念下，与无法渐近比较； D对于任意函数， (为空集)。4、在快速排序中，以下描述不正确的是（ D ）。A在快速排序，最好时间复杂性和平均时间复杂性均为；B若精心挑选一个划分元，每次经过Partition算法后，分成两个子问题，从而使得 其 最坏时间复杂性为； C若随机挑选一个划分元，每次经过RandomizedPartition算法后，分成两个期望均长的子问题，从而使得其期望时间复杂性为； D不管是精心挑选还是随机挑选划分元，快速排序的最坏时间复杂性均为。 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、 在空格处填上合适的大函数使得下列关系，在渐进复杂性概念下成立。 _。2、 分治策略求解问题可以分为三步：分解；递归地解子问题；组合。有的问题分解难而组合容易，如_快速排序_，有的问题分解容易而组合难，如归并排序_。3、 活动安排问题既可以用动态规划算法求解也可以用贪心算法求解。其中用动态规划算法求解的时间复杂性为：_；用贪心算法求解的时间复杂性为：_（假定个活动已经按照结束时间单调有序）。4、 哈夫曼编码是用于_数据文件_压缩的一个十分有效的编码方法。其中算法Huffman Tree用最小堆来实现优先队列。而退出优先队列算法DeleteMin和进入优先队列算法Insert均需要_时间。三、 求以下递推式的渐近上界（每小题8分，共16分）1 （） （2分）迭代次后，将有 （4分）直到（）时 （6分） （） （） （8分）2nnnn总共 （4分）在将递归树各层的值加起来时，发现每一层的值都为。从根到叶的最长的一条路经是。因为当时，该树的高度为。因而，该递归式的解至多是。（8分）四、 简答题（每小题4分，共20分）1试论和的区别。2简述回溯法和分支限界法的异同。（1）相同点：都是用来求解组合难题的系统方法，需要在解空间按照某种策略搜索，但都不同于一般的穷举搜索方法。（1分）（2）不同点：搜索方式不同。回溯法按照深度优先搜索原则，而分支限界法按照广度优先或是最佳优先原则；（3分）所用的数据结构不同。栈和队列或优先队列。（4分）3分析以下程序，然后指出程序返回（return）的结果是多少，为什么？ Darts() ;for =1 to do uniform(0,1); /随机生成一个大于等于0小于1的实数 ; if () then ; return ; 五、 计算题（每小题7分，共14分）1计算题：请用动态规划算法找出矩阵连乘的最佳计算次序（即最佳完全加括号方式），其中，。列出计算过程。因为， （2分）所以，； （3分）= （4分）（5分）（6分）则最佳完全加括号方式为： （7分）。2在0-1背包问题中，有四种物品，其重量(价值)分别为：2kg(12$)，1kg(10$)，3kg(20$)，2kg(15$)。并且背包总容量。请用动态规划算法，找出一个最优解的装包情形及其装包的总价值。列出计算过程。解：设是背包容量为，可选物品为前个物品时，0-1背包问题的最优值，即能够装进承重量为的背包中前个物品最有价值子集的总价值。则有： （2分）初始条件：当时，当时，。计算过程见下表：i j012345000000010012121212201012222222401015253037（6分）故：第1、2、4物品装包其它不装，总价值为37$ （7分）六、 算法设计题（每小题10分，共30分）要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间复杂性。1某次选举中有个候选人，编号从到，有个选民参与了选举，每个选民只能选择一位候选人，当某个候选人获得超过一半的选票时，则认为该候选人获胜。试设计一个算法，在选举结束后，可在的时间内判断是否有某个候选人获胜。2在一个直线跑道上摆放着一行共堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将堆石子合并成一堆的最小得分。3假定我军计划炸毁敌方整个通信网络。敌方通信网络由各个驻点加上其间的通信线路组成（如下图3）。炸毁一个驻点，则该驻点与其它所有驻点间通信就中断。请设计算法，找出一种最佳轰炸策略，使得敌方整个通信网络瘫痪，即，使得所有驻点间都不能通信。ABFCDE图1：通信网络拓扑图（其中一部分）专心-专注-专业