中南大学204算法试卷及答案分析报告

1、中南大学考试试卷2013 - 2014 学年 下 学期 时间100分钟2014 年6月6日算法分析与设计 课程48学时丄学分 考试形式：闭 卷专业年级：12级计算机、信安、物联本科生，总分 100分，占总评成绩70 %注：此页不作答题纸，请将答案写在答题纸上一、简答题（本题30分，每小题5分）1、陈述算法在最坏情况下的时间复杂度和平均时间复杂度；这两种评估算法复杂性的方 法各自有什么实际意义？1 最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。意义：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何

2、更长2 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。意义：在输入不同的情况下算法的运行时间复杂度可能会发生变化。平均时间复杂度给出了算法的期望运行时间，有助于算法好坏的评价以及在不同算法 之间比较时有一个统一标准2、简单描述分治法的基本思想。分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问 题的解。3、何谓最优子结构性质？如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题

3、提供了重要线索。4、何谓P、NR NPC问题P（Polynomial问题）：也即是多项式复杂程度的问题。NP就是Non-deterministicPolynomial的问题，也即是多项式复杂程度的非确定性问题。NPQNP Complete）问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出 答案，这样的问题是 NP里面最难的问题，这种问题就是NPC问题。5、试比较回溯法与分支限界法。1、引言1.1回溯法回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则 跳过对该结点为根的子树的搜索，逐层向

4、其祖先结点回溯；否则，进入该子树，继续按 深度优先策略搜索。这种以深度优先方式系统搜索问题解的算法称为回溯法。1.2分支限界法分支限界法是以广度优先或以最小耗费优先的方式搜索解空间树，在每一个活结点处，计算一个函数值，并根据函数值，从当前活结点表中选择一个最有利的结点作为扩 展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解，这种 方法称为分支限界法。2、回溯法的基本思想用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少应包含问题的一 个解。之后还应将解空间很好的组织起来，使得能用回溯法方便的搜索整个解空间。在 组织解空间时常用到两种典型的解空间树，即子集树和排列树

5、。确定了解空间的组织结 构后，回溯法从开始结点出发，以深度优先方式搜索整个解空间。这个开始结点成为活 结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新 结点。这个新结点就成为新的活结点，并成为当前扩展结点。如果在当前的扩展结点处 不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动至最近的一 个活结点处，并使这个活结点成为当前的扩展结点。回溯法以这种工作方式递归的在解 空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。3、分支限界法的基本思想用分支限界法解问题时，同样也应明确定义问题的解空间。之后还应将解空间很好 的组织起来。分支限界法也有两种

6、组织解空间的方法，即队列式分支限界法和优先队列 式分支限界法。两者的区别在于：队列式分支限界法按照队列先进先出的原则选取下一 个节点为扩展节点，而优先队列式分支限界法按照优先队列中规定的优先级选取优先级 最高的节点成为当前扩展节点。分支限界法常以广度优先或以最小耗费优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点 一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解 或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点 表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找 到所需的

7、解或活结点表为空时为止。4、回溯法的设计原理在设计一个回溯算法时，通常按照以下步骤进行：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。在一般情况下用递归方法实现回溯法的基本框架如下：void backtrack （ int t ）if （ t>n ） output （ x）；elsefor （int i=f （n, t）； i<=g （ n, t）； i+） xt=h （i）；if(constraint(t) &&bound (t) backtrack (t+1 );其中：

8、t表示递归深度，output (x)记录或输出得到的可行解x, f (n, t )和g(n，t)分别表示在当前扩展结点处未搜索过的子树的起始编号和终止编号，h (i )表示当前扩展结点处的第i个可选值，constraint(t )和bound (t)表示当前扩展结点的约束函数和限界函数。5、分支限界法的设计原理在设计一个分支限界算法时，通常按照以下步骤进行：(1) 针对所给问题，定义问题的解空间；(2) 确定易于搜索的解空间结构；(3) 以广度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。6、回溯法与分支限界法的差异及应用回溯法与分支定界法都是在问题的解空间上搜索问题解的算法。但是

9、两者是有区别的：首先，求解目标不同：一般而言，回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是尽快地找出满足约束条件的一个解。其次，搜索方法不同：由于求解目标不同，导致分支限界法与回溯法对解空间的搜索方式也不同，回溯法 采用深度优先方法搜索解空间，而分支限界法一般采用用广度优先或以最小耗费优先的方式搜索解空间。再次，对扩展结点的扩展方式不同：在搜索解空间书中两者的主要区别在于它们对当前扩展结点所采用的扩展方式不同。在回溯法中，如果当前的扩展结点不能够再向纵深方向移动，则当前扩展结点就成 为死结点，此时应回溯到最近的一个活结点处，并使此活结点成为扩展结点。而在分支

10、 限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一 次性产生其所有儿子结点。最后，存储空间的要求不同：分支限界法的存储空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。下面结合具体的实例来说明何种情况下比较适合采用回溯法，何种情况下比较适合采用分支限界法：适合采用回溯法的问题：最典型的代表如n后问题，即在n*n个格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列 或同一斜线上的棋子。对于n后问题，解与解之间不存在优劣的区别。必须要搜索到叶节点时才能确定出一组解。这种情况下，我们采用回溯法来解决时，采用排列树的

11、解空 间结构，在最坏的情况下，其堆栈的深度不会超过n。而采用分支限界法时，由于解之间不存在优劣关系，故不可能用限界函数剪枝，需要较大的存储空间。适合采用分支限界法的问题：最典型的代表如布线问题，即印刷电路板将布线区域戈U分成n*m个方格阵列。要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线。为了避免线路相交，已布了线的方格做了封锁 标记，其他线路不允许穿过被封锁的方格。此问题，如果采用回溯法来解决时，为了找 到最短路径，必须把整个区域的所有路径逐一搜索后才能得到最优解，这使得算法效率 较低。而如果用分支限界法来解决，则可以保证找到的解是最短的布线方案，因

12、为如果 存在一条由a至b的更短的路径，b结点一定会更早地被加入到活结点队列中并得到处 理。6、贪心法是一种通过多步选择，试图获得最优解的方法。贪心法每次选择的原则是什么？ 请举例说明。设计贪心算法的三个步骤将最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解（比较重要的一步）证明作出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的证明作出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得 到原问题的最优解，这样就得到了最优子结构两个关键因素1. 贪心选择性质：可以通过做出局部最优（贪心）选择来构造全局最优解；即每个步骤做出贪心选择能生成全局最优解【视不同

13、具体问题进行证明，没有普遍适用的方法】2. 最优子结构：一个问题的最优解包含其子问题的最优解经典最优化问题的两个变形0-1背包问题：一个正在抢劫的小偷发现了n个商品，第i个商品价值vi美元，重wi磅，vi和wi都是整数；小偷想尽可能拿走价值更多的商品，但是他的背包最多能容纳W磅的商品，W是一个整数【对每个商品，不能拿走一部分，要么完整拿走，要么留下） 分数背包问题：条件和0-1背包问题一样，但对每个商品，小偷可以拿走一部分两个问题都有最优子结构，很相似，但是贪心算法可以求解分数背包问题，而不能求解0-1背包问题分数背包问题：计算每个商品的每磅价值vi/wi，每次选择每磅价值最高的商品即可0-1

14、背包问题：因为小偷无法装满背包，空闲空间降低了方案的有效每磅价值； 当我们考虑一个商品食肉装入背包，需要比较包含此商品的子问题的解和不包含它的子问题的解，然后才能做出选择当然，由于两个问题都有最优子结构，所以能用动态规划算法进行求解。/拓展/二、简答题(本题 25分，每小题5分)1、简单描述分治法的基本思想。2、简述动态规划方法所运用的最优化原理。3、何谓最优子结构性质？4、简单描述回溯法基本思想。5、何谓P、NP NPC'可题二、简答题(本题 25分，每小题5分)1、分治法的基本思想 是将一个规模为n的问题分解为k个规模较小的子问题， 这些子 问题互相独立且与原问题相同；对这 k个子

15、问题分别求解。如果子问题的规模仍然 不够小，则再划分为 k个子问题，如此递归的进行下去，直到问题规模足够小，很 容易求出其解为止；将求出的小规模的问题的解合并为一个更大规模的问题的解， 自底向上逐步求出原来问题的解。2、“最优化原理”用数学化的语言来描述：假设为了解决某一优化问题，需要依次作出n个决策D1, D2,，Dn,如若这个决策序列是最优的，对于任何一个整数k, 1 < k<n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当 前状态，即以后的决策 Dk+1, Dk+2,，Dn也是最优的。3、 某个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构

16、性质。4、回溯法的基本思想 是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到 上层父结点，继续下一步深度优先搜索过程。在回溯法中，并不是先构造出整棵状态 空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。5、P(Polynomial问题)：也即是多项式复杂程度的问题。NP就是Non-deterministicPolynomial的问题，也即是多项式复杂程度的非确定性问题。NPC(NP Complete)问题，这种

17、问题只有把解域里面的所有可能都穷举了之后才能得出 答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。/二、选择题(14分，每题2分)1. 下述表达不正确的是 。A. n2/2 + 2 n的渐进表达式上界函数是0(2)B . n2/2 + 2 n的渐进表达式下界函数是Q(2 n)C. logn3的渐进表达式上界函数是O(logn) D . logn3的渐进表达式下界函数是Q(n 3)logn 3的渐进表达式下界函数是O（logn）2. 下列算法中通常以自底向上的方式求解最优解的是 A.动态规划法B.贪心法C.回溯法3. 下面关于NP问题说法正确的是A. NP问题都是不可能解决的问题B

18、. P类问题包含在 NP类问题中B. NP完全问题是P类问题的子集D. NP 类问题包含在 P类问题中首先这些p和 叩都是用来描述解决一个问题需要的时间和它输入规模之间的关系P问题：一个问题可以在多项式（0（门你）的时间复杂度内解决例如：n个数的排序（不超过 0（nA2）NP问题：一个问题的解可以在多项式的时间内被证实或证伪例如：典型的子集求和问题，给定一个整数集合求是否存在一个非空子集它的和为零。 如给定集合s=-1,3,2,-5,6，很明显子集32-5能满足问题，并且验证该解只需要 线性时间复杂度就能被证实。NP-hard 问题：任意np问题都可以在多项式时间内归约为该问题。归约的意思是为

19、了解决问题 A,先将问题A归约为另一个问题B,解决问题B同时也间接解决了问题 A。例如，停机问题。NPC'可题：既是NP问题，也是 NP-hard问题。例如，SAT问题（第一个NPC问题）。该问题的基本意思是，给定一系列布尔变量以及 它的约束集，是否存在一个解使得它的输出为真。相互关系：显然，所有P问题都是NP问题，反之则不一定。npc问题是np问题的子集，也是p问 题和np问题的差异所在。如果找到一个多项式内能被解决的npc问题的解决方法，那么 P=NP4. 下列算法中不能解决 0/1背包问题的是A.贪心法B.动态规划C.回溯法D.分支限界法5. 是贪心算法与动态规划算法的共同点。A

20、.重叠子问题 B .构造最优解 C .贪心选择性质D.最优子结构性质贪心算法的基本要素贪心算法通过一系列的选择得到问题的解。它所做出的每一选择都是当前状态下局部最好选择，即贪心选择。可以用贪心算法求解的问题一般具有两个重要性质：(1) 贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解能通过一系列局部 最优的选择(即贪心选择)来达到。(2) 最优子结构性质。与动态规划算法相同，最优子结构性质是一个问题可用贪心算法求解的关键特征。6. 以下关于判定问题难易处理的叙述中正确的是 。A. 可以由多项式时间算法求解的问题是难处理的B. 需要超过多项式时间算法求解的问题是易处理的C可以由多项式时间算

21、法求解的问题是易处理的D.需要超过多项式时间算法求解的问题是不能处理的7. n个同学拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒定。如下说法不正确？A. 让水桶大的人先打水，可以使得每个人排队时间之和最小B. 让水桶小的人先打水，可以使得每个人排队时间之和最小C. 让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水D. 若要在尽可能短的时间内，n个人都打完水，按照什么顺序其实都一样三、解答题(30分)1. 用贪心法求下图的最大生成树 (5分)8贪心算法最小生成树设G = (V,E)是无向连通带权图，即一个网络。E中的每一条边(v,w)的权为cvw。如果

22、G的子图G'是一棵包含 G的所有顶点的树，则称G为G的生成树。生成树上各边权的总和称为生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。构造最小生成树的两种方法：Prim算法和Kruskal算法。、最小生成树的性质设G =(V,E)是连通带权图，这样的边中，(u,v)的权cuv 中一条边。这个性质有时也称为U是V的真子集。如果(u,v) E,且u U,v V-U,且在所有 最小，那么一定存在 G的一棵最小生成树，它意(u,v)为其MST性质。二、Prim算法设G = (V,E)是连通带权图，V = 1,2,n。构造G的最小生成树Prim算法的基本 思想是：首先置S

23、= 1，然后，只要S是V的真子集，就进行如下的贪心选择：选取满 足条件i S,j V - S,且cij 最小的边，将顶点j添加到S中。这个过程一直 进行到S = V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。如下带权图：生成过程：1 -> 3 : 13 -> 6 : 46 -> 4: 23 -> 2 : 52 -> 5 : 3实现：三、Kruskal算法当图的边数为 e时，Kruskal算法所需的时间是 O(eloge)。当e = Q (nA2)时，Kruskal 算法比Prim算法差；但当 e =0(门人2)时，Kruskal算法比Prim算法

24、好得多。给定无向连同带权图G = (V,E),V= 1,2,.,n 。Kruskal算法构造G的最小生成树的基本思想是：(1)首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小大排序。(2 )从第一条边开始，依边权递增的顺序检查每一条边。并按照下述方法连接两个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前两个不同的连通分支T1和T2的端点是，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看k+1条边。这个过程一个进行到只剩下一个连通分支时为止。此时，已构成G的一棵最小生成树。Kruskal算法的选边过程：1 -> 3:14 -> 6:22 -> 5:33 -> 4:42 -> 3:5两种算法代码见教材2. 对数组A=15 , 29, 135,18, 32, 1 , 27, 25, 5，写出用快速排序算法（按升序排序） 的第一