《09博士-算法设计与分析(答案).doc》由会员分享，可在线阅读，更多相关《09博士-算法设计与分析(答案).doc（5页珍藏版）》请在金锄头文库上搜索。
1、一、 单选题（每小题1分，共10分）1. C； 2. D； 3. A； 4. D ；5. B ；6. D ；7. C ；8. B ；9. A ；10. B二、 填空题（每空1分，共10分）1，（答案可以不唯一，根据具体答题给分）2快速排序，归并排序（答案可以不唯一，根据具体答题给分）3，4数据文件，57063三、 求以下递推式的渐近上界（每小题8分，共16分）1解（用迭代方法求解） （） （2分）迭代次后，将有 （4分）直到（）时 （6分） （） （） （8分）（方法不唯一，根据实际解题过程给分）2解（用递归树求解）nnnn总共 （4分）在将递归树各层的值加起来时，发现每一层的值都为。从根到叶
2、的最长的一条路经是。因为当时，该树的高度为。因而，该递归式的解至多是。（8分）（方法不唯一，根据实际解题过程给分）四、 简答题（每小题4分，共20分）1答根据符号的定义易知。用或表示同一个函数时，差别仅在于其中的常数因子。（4分）2答：（1）相同点：都是用来求解组合难题的系统方法，需要在解空间按照某种策略搜索，但都不同于一般的穷举搜索方法。（1分）（2）不同点：搜索方式不同。回溯法按照深度优先搜索原则，而分支限界法按照广度优先或是最佳优先原则；（3分）所用的数据结构不同。栈和队列或优先队列。（4分）3返回值为：。（2分）因为：根据题意有 即。（4分）BxO4（1）相同点：三种算法都是概率算法，
3、其基本特征是对所有求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。（1分）（2）差异：舍伍德算法总能求得问题的一个解，且所求得的解总是正确的，当一算法在最坏与平均情况下复杂性有较大差别时，可用次算法消除或减少问题的好坏实例间的这种差别。拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。但有时用拉斯维加斯算法会找不到解，找到正确解的概率随着计算时间的增加而提高。对于所求问题的任一实例，用同一拉斯维加斯算法反复求解足够多次，可使求解失败的概率任意小。蒙特卡罗算法常用于求问题的准确解。它能求得问题的一个解，但这个解未必正确，求得正确解的概率依赖于
4、算法所用的时间，所用时间越多得到正确解的概率越高。（4分）5复杂度类P包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题，P代表Polynomial（多项式）；类NP由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成，或者等效的说，那些解可以在非确定图灵机上在多项式时间内找出的问题的集合。缩写NP代表“Non-deterministic（非确定性）Polynomial（多项式）”而不是代表“Non-Polynomial（非多项式）。（2分）要解决P=NP问题，NP完全的概念非常有用。不严格的讲，NP完全问题是NP类中“最难”的问题，也就是说它们是最可能不属于P类的。
5、NP完全事实上表求NP中判定问题的一个子类。这类问题也是很有趣的，即如果它们中的一个被证明是多项式时间内确定性算法可解，那么所有属于这一类的其它问题也是多项式时间内确定性算法可解。（4分）五、 计算题（每小题7分，共14分）1. 解：因为， （2分）所以，； （3分）= （4分）（5分）（6分）则最佳完全加括号方式为： （7分）。2解：设是背包容量为，可选物品为前个物品时，0-1背包问题的最优值，即能够装进承重量为的背包中前个物品最有价值子集的总价值。则有： （2分）初始条件：当时，当时，。计算过程见下表：i j01234500000001001212121220101222222240101
6、5253037（6分）故：第1、2、4物品装包其它不装，总价值为37$ （7分）六、 算法设计题（每小题10分，共30分）1设计思想：原问题相当于在某一组元中找主元素问题。用最坏时间为线性的Select算法求解中值元。（4分）算法描述： Input A1.n, a array of n keysOutput A中主原数x，否则返回fasleSearch(A1.n) /在数组A中找主原数 xselect(A,1,n,); s0;for i=1 to n do if Ai=x then ss+1; if s then return x else return false;（8分）算法分析：时间复杂
7、性： (10分)2用动态规划算法求解（2分）：该问题实际上是矩阵连乘积问题的变形。设n堆石子从左到右编号为1，2, n，每堆石子的石子数分别为。n堆石子的合并可以有许多不同的方式，每一种合并方式都对应于的一种完全加括号方式。因此该问题转化为的最优加括号方式问题。由于我们的问题是要求合并的最小得分，因此这里的最优的含义就是要求使得分达到最小的完全加括号方式。这与矩阵连乘积的最优性含义完全相同，不同之处在于各自的最优值计算公式。1) 最优子结构性质：对于的一个最优合并方式，设其在和之间断开，则其合并方式为，容易看出，此时和的合并方式也是最优的，即该问题具有最优子结构性质（4分）。2) 递归关系：设
8、合并，所得到的最小得分为，则原问题的最优值为。由最优子结构性质可知：（6分）3) 自底向上计算，同时还确定了合并的断开位置，可将记录在中，便于在计算出最优值后，根据中记录的断开位置构造出最优解(程序略)（8分）。算法的时间复杂性:（10分）。3用贪心算法求解（2分）贪心选择：驻点度数大的优先轰炸（4分）。具备最优子结构性质：反证法证明，略（5分）。计算步骤：1）用最坏时间为线性的选择算法,选取度数最大的驻点实施轰炸。2）更新各结点的度数；3）转1）递归求解直到所有驻点度数为0。（7分）形式实现（略）（8分）复杂性分析：选择算法最坏需要炸掉所有结点故总的时间（10分）（注：主观命题，答案不固定，根据实际解题过程给分）
