电子科大算法试卷-答案

一、列式计算与算法设计：（20分）1.给定6个表示算法增长阶的函数：(1)n5+10n4,(2)n2+3n,(3)210000n,(4)logn+(2logn)3,(5)2n+n!+5en,(6)3log2n+5logn.a)用O给出它们的渐近表达式。(6分)b)使用“”或“=”将这些表达式连接起来。(4分)a)(1)n5+10n4=O(n5)（1分，非最简表达式扣0.5分，写成或不符合题意，不给分）(2)n2+3n=O(3n)（1分，标准同上）(3)210000n=O(n)（1分，标准同上）(4)logn+(2logn)3=O((logn)3)（1分，标准同上）(5)2n+n!+5en=O(n!)（1分，标准同上）(6)3log2n+5logn=O(n)（1分，标准同上）b)O((logn)3)O(n)=O(n)O(n4)O(3n)O(n!)（4分，每个错误位置扣1分，扣完为止。符号错误每次扣0.5分。）2设输入规模和处理器数目都为n,试写出洗牌-交换网络上的同步并行求和算法，分析该算法的运行长度(Depth)和时间开销(Cost).（10分）AlgorithmSUM-SEfori=1tologndoforallPj(0=jn)doinparallelshuffle(xj);(3分)tj=xj;exchange(xj);xj=xj+tj;(3分)Depth为：Θ(logn)(2分)Cost为:Θ(nlogn)(2分)二、问答题（每题10分，共20分）1.请列举5种算法设计技术并简述其设计思想。答：分治法：将一个规模为n的问题分解为k个规模较小的问题，这些子问题相互独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。(2分，未解释得1分)回溯法：深度优先，若遇到可行解是当前最优解，则记录；若本结点的所有结点已为死结点，则回溯到上层结点。(2分，未解释得1分)分支限界法：在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。(2分，未解释得1分)贪心法：贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义下的局部最优选择。(2分，未解释得1分)动态规划：在每一判定步骤，列出各种可能的局部解，然后抛弃那些不能扩展成全局最优解的局部解，再继续下一步的判定。(2分，未解释得1分)2.简述什么是P类问题，什么是NP类和NP完全类问题，以及如何证明一个问题属于NP完全类。答：在确定型图灵机上多项式时间内可解的问题称为P类问题。(2分)在非确定型图灵机上多项式时间内可计算的判定问题所组成的集合称为NP类问题。(2分)称L0∈NP是NP完全问题，如果对一切L∈NP都存在一台确定型图灵机M，它可以在多项式时间内将L转换为L0。(2分)证明方法：（1）直接变换法。对一个判定问题∏∈NP，要证明∏是NP完全问题，只需将一个已知的NP完全问题∏’经多项式时间变换为∏。(2分)（2）限制法。证明∏∈NP且包含一个已知的NP完全问题∏’作为它的一种特殊情况。限制法的核心在于对∏的实例规定一些附加线之后使所得到的问题与∏’等价。(2分)三、计算题（每题10分，共20分）1.求下面的级数和.0()mmiimiabbn解：a=b时，0011mmmiimmiiabamamn（＋）（＋）2（分）ab时，000111131312immmmiimiimiiimmmmmbabaabaabaabaababnabab（分）（分）（分）2.解递归方程T(n2)=nT(n)+n2,(T(2)=2)解：设kn22，则nkloglog（1分，假设）T(n)=T(k22)=122k*T(122k)+k2226340=122k*(222k*T(222k)+122k)+k22=122k*(222k*(322k*T(322k)+k22)+122k)+k22（4分，递推过程）=……=122223212kkk*T(2)+k22*k（2分，中间结果）=k22+k22*k=n+nnloglog（2分，结果）四、根据下面的图回答（40分）1）从顶点A开始按宽度优先和深度优先的顺序进行遍历，画出相应的周游顺序和BFS/DFS树。（10分）2）按照Prim算法的次序给出以顶点A为根的最小生成树（MST）。（10分）3）按照Dijkstra算法的次序依次找出从顶点A到其余各顶点的最短路径。（20分）1）从顶点A开始按宽度优先和深度优先的顺序进行遍历，画出相应的周游顺序和BFS/DFS树。（10分）宽度优先遍历：顺序为：A—B—C—F—D—E(3分，错一个扣0.5分，直至扣完)BFS树如下：(2分，错一个分枝扣0.5分，直至扣完)11112595205ABCEFDABCEFD6深度优先遍历：顺序为：A—B—C—D—E—F(3分，错一个扣0.5分，直至扣完)DFS如下：(2分，错一个分枝扣0.5分，直至扣完)2）按照Prim算法的次序给出以顶点A为根的最小生成树（MST）。（10分）最小生成树如下：（错一条分枝扣2分，直至扣完；没有顺序，只有结果扣4分）(a)(b)(c)(d)(e)11ABCEFD5AB5ABF25ABCF2511D5ABCF2511D5ABCF25E3）按照Dijkstra算法的次序依次找出从顶点A到其余各顶点的最短路径。（10分）ABCDEF初始0∞∞∞∞∞A0520∞∞9AB051045∞7ABF051018327ABFC051018327ABFCD051018247ABFCDE051018247（10分）错一行（每行中数字有两个错了就算错），扣2分；扣完为止顶点A到B的最短路径为：A—B，长度为5；顶点A到C的最短路径为：A—B—C，长度为10；顶点A到D的最短路径为：A—B—F—D，长度为18；顶点A到E的最短路径为：A—B—F—D—E，长度为24；顶点A到F的最短路径为：A—B—F，长度为7；（10分）错1个扣2分，扣完为止。