中南大学2014算法试卷及答案分析.doc

中南大学考试试卷
2013 -- 2014学年 下 学期 时间100分钟 2014 年6 月6日
算法分析与设计 课程 48 学时 3 学分 考试形式： 闭 卷
专业年级：12级计算机、信安、物联本科生，总分100分，占总评成绩70 %
注：此页不作答题纸，请将答案写在答题纸上
一、简答题（本题30分，每小题5分）
1、 陈述算法在最坏情况下的时间复杂度和平均时间复杂度；这两种评估算法复杂性的方法各自有什么实际意义？
1 最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。 意义：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长
2 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。 意义：在输入不同的情况下算法的运行时间复杂度可能会发生变化。平均时间复杂度给出了算法的期望运行时间，有助于算法好坏的评价以及在不同算法之间比较时有一个统一标准
2、 简单描述分治法的基本思想。
分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。
3、 何谓最优子结构性质？
如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
4、 何谓P、NP、NPC问题
P(Polynomial问题)：也即是多项式复杂程度的问题。
NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。
NPC(NP Complete)问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。
5、 试比较回溯法与分支限界法。
1、引言 
　　1.1回溯法 
　　回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。这种以深度优先方式系统搜索问题解的算法称为回溯法。 
　　1.2分支限界法 
　　分支限界法是以广度优先或以最小耗费优先的方式搜索解空间树，在每一个活结点处，计算一个函数值，并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解，这种方法称为分支限界法。 
　　2、回溯法的基本思想 
　　用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少应包含问题的一个解。之后还应将解空间很好的组织起来，使得能用回溯法方便的搜索整个解空间。在组织解空间时常用到两种典型的解空间树，即子集树和排列树。确定了解空间的组织结构后，回溯法从开始结点出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法以这种工作方式递归的在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。 
　　3、分支限界法的基本思想 
　　用分支限界法解问题时，同样也应明确定义问题的解空间。之后还应将解空间很好的组织起来。分支限界法也有两种组织解空间的方法，即队列式分支限界法和优先队列式分支限界法。两者的区别在于：队列式分支限界法按照队列先进先出的原则选取下一个节点为扩展节点，而优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。分支限界法常以广度优先或以最小耗费优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 
　　4、回溯法的设计原理 
　　在设计一个回溯算法时，通常按照以下步骤进行： 
　　（1）针对所给问题，定义问题的解空间； 
　　（2）确定易于搜索的解空间结构； 
　　（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 
　　在一般情况下用递归方法实现回溯法的基本框架如下： 
　　void backtrack （int t） 
　　{ 
　　if （t>n） output（x）； 
　　else 
　　for （int i=f（n，t）；i<=g（n，t）；i++） { 
　　x[t]=h（i）； 
　　if （constraint（t）&&bound（t）） backtrack（t+1）； 
　　} 
　　} 
　　其中：t表示递归深度，output（x）记录或输出得到的可行解x，f（n，t）和g（n，t）分别表示在当前扩展结点处未搜索过的子树的起始编号和终止编号，h（i）表示当前扩展结点处的第i个可选值，constraint（t）和bound（t）表示当前扩展结点的约束函数和限界函数。 
　　5、分支限界法的设计原理 
　　在设计一个分支限界算法时，通常按照以下步骤进行： 
　　（1）针对所给问题，定义问题的解空间； 
　　（2）确定易于搜索的解空间结构； 
　　（3）以广度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 
　　6、回溯法与分支限界法的差异及应用 
　　回溯法与分支定界法都是在问题的解空间上搜索问题解的算法。但是两者是有区别的： 
　　首先，求解目标不同： 
　　一般而言，回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是尽快地找出满足约束条件的一个解。 
　　其次，搜索方法不同： 
　　由于求解目标不同，导致分支限界法与回溯法对解空间的搜索方式也不同，回溯法采用深度优先方法搜索解空间，而分支限界法一般采用用广度优先或以最小耗费优先的方式搜索解空间。 
　　再次，对扩展结点的扩展方式不同： 
　　在搜索解空间书中两者的主要区别在于它们对当前扩展结点所采用的扩展方式不同。在回溯法中，如果当前的扩展结点不能够再向纵深方向移动，则当前扩展结点就成为死结点，此时应回溯到最近的一个活结点处，并使此活结点成为扩展结点。而在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。 
　　最后，存储空间的要求不同： 
　　分支限界法的存储空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。 
　　下面结合具体的实例来说明何种情况下比较适合采用回溯法，何种情况下比较适合采用分支限界法： 
　　适合采用回溯法的问题：最典型的代表如n后问题，即在n*n个格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。对于n后问题，解与解之间不存在优劣的区别。必须要搜索到叶节点时才能确定出一组解。这种情况下，我们采用回溯法来解决时，采用排列树的解空间结构，在最坏的情况下，其堆栈的深度不会超过n。而采用分支限界法时，由于解之间不存在优劣关系，故不可能用限界函数剪枝，需要较大的存储空间。 
　　适合采用分支限界法的问题：最典型的代表如布线问题，即印刷电路板将布线区域划分成n*m个方格阵列。要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线。为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。此问题，如果采用回溯法来解决时，为了找到最短路径，必须把整个区域的所有路径逐一搜索后才能得到最优解，这使得算法效率较低。而如果用分支限界法来解决，则可以保证找到的解是最短的布线方案，因为如果存在一条由a至b的更短的路径，b结点一定会更早地被加入到活结点队列中并得到处理。 
6、 贪心法是一种通过多步选择，试图获得最优解的方法。贪心法每次选择的原则是什么？请举例说明。
设计贪心算法的三个步骤
    将最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解（比较重要的一步）
    证明作出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的
    证明作出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构

两个关键因素
1. 贪心选择性质：可以通过做出局部最优（贪心）选择来构造全局最优解；即每个步骤做出贪心选择能生成全局最优解【视不同具体问题进行证明，没有普遍适用的方法】
2. 最优子结构：一个问题的最优解包含其子问题的最优解

经典最优化问题的两个变形
0-1背包问题：一个正在抢劫的小偷发现了n个商品，第i个商品价值vi美元，重wi磅，vi和wi都是整数；小偷想尽可能拿走价值更多的商品，但是他的背包最多能容纳W磅的商品，W是一个整数【对每个商品，不能拿走一部分，要么完整拿走，要么留下）
分数背包问题：条件和0-1背包问题一样，但对每个商品，小偷可以拿走一部分

两个问题都有最优子结构，很相似，但是
贪心算法可以求解分数背包问题，而不能求解0-1背包问题
    分数背包问题：计算每个商品的每磅价值vi/wi，每次选择每磅价值最高的商品即可
    0-1背包问题：因为小偷无法装满背包，空闲空间降低了方案的有效每磅价值；当我们考虑一个商品食肉装入背包，需要比较包含此商品的子问题的解和不包含它的子问题的解，然后才能做出选择

当然，由于两个问题都有最优子结构，所以能用动态规划算法进行求解。

////////////////////////////拓展////////////////////////////////////////////////////////////////////////////////////////////////////////
二、简答题（本题25分，每小题5分）
1、 简单描述分治法的基本思想。
2、 简述动态规划方法所运用的最优化原理。
3、 何谓最优子结构性质？
4、 简单描述回溯法基本思想。
5、 何谓P、NP、NPC问题
二、简答题（本题25分，每小题5分）
1、 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同；对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止；将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
2、 “最优化原理”用数学化的语言来描述：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 < k < n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，…，Dn也是最优的。
3、 某个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。
4、 回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。
5、 P(Polynomial问题)：也即是多项式复杂程度的问题。
NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。
NPC(NP Complete)问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。
//////////////////////////////////////////////////////////////////////////////

二、选择题（14分，每题2分）
1. 下述表达不正确的是 。
A．n2/2 + 2n的渐进表达式上界函数是O(2n) B．n2/2 + 2n的渐进表达式下界函数是Ω(2n)
C．logn3的渐进表达式上界函数是O(logn) D．logn3的渐进表达式下界函数是Ω(n3)
logn3的渐进表达式下界函数是O(logn)
2. 下列算法中通常以自底向上的方式求解最优解的是
A．动态规划法 B．贪心法 C．回溯法
3. 下面关于NP问题说法正确的是
A. NP问题都是不可能解决的问题 B. P类问题包含在NP类问题中
B. NP完全问题是P类问题的子集 D. NP类问题包含在P类问题中
首先这些p和np都是用来描述解决一个问题需要的时间和它输入规模之间的关系...

P问题：
一个问题可以在多项式（O(n^k)）的时间复杂度内解决
例如：n个数的排序（不超过O(n^2)）
NP问题：
一个问题的解可以在多项式的时间内被证实或证伪
例如：典型的子集求和问题,给定一个整数集合求是否存在一个非空子集它的和为零。如给定集合s={-1,3,2,-5,6}，很明显子集{3,2,-5}能满足问题，并且验证该解只需要线性时间复杂度就能被证实。
NP-hard问题：
任意np问题都可以在多项式时间内归约为该问题。归约的意思是为了解决问题A，先将问题A归约为另一个问题B，解决问题B同时也间接解决了问题A。
例如，停机问题。
NPC问题：
既是NP问题，也是NP-hard问题。
例如，SAT问题（第一个NPC问题）。该问题的基本意思是，给定一系列布尔变量以及它的约束集，是否存在一个解使得它的输出为真。
相互关系：
显然，所有P问题都是NP问题，反之则不一定。npc问题是np问题的子集，也是p问题和np问题的差异所在。如果找到一个多项式内能被解决的npc问题的解决方法，那么P=NP。
>

4. 下列算法中不能解决0/1背包问题的是
A． 贪心法 B. 动态规划 C. 回溯法 D. 分支限界法
5. 是贪心算法与动态规划算法的共同点。
A． 重叠子问题 B．构造最优解 C．贪心选择性质 D．最优子结构性质
贪心算法的基本要素
贪心算法通过一系列的选择得到问题的解。它所做出的每 一选择都是当前状态下局部最好选择，即贪心选择。可以用贪心算法求解的问题一般具有两个重要性质：
（１）贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解能通过一系列局部最优的选择（即贪心选择）来达到。
（２）最优子结构性质。与动态规划算法相同，最优子结构性质是一个问题可用贪心算法求解的关键特征。
6. 以下关于判定问题难易处理的叙述中正确的是 。
A.可以由多项式时间算法求解的问题是难处理的
B.需要超过多项式时间算法求解的问题是易处理的
C.可以由多项式时间算法求解的问题是易处理的
D.需要超过多项式时间算法求解的问题是不能处理的
7. n个同学拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒定。如下 说法不正确？
A．让水桶大的人先打水，可以使得每个人排队时间之和最小
B．让水桶小的人先打水，可以使得每个人排队时间之和最小
C．让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水
D．若要在尽可能短的时间内，n个人都打完水，按照什么顺序其实都一样
三、解答题（30分）
1. 用贪心法求下图的最大生成树(5分)

贪心算法——最小生成树
设G = (V,E)是无向连通带权图，即一个网络。E中的每一条边（v,w）的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。构造最小生成树的两种方法：Prim算法和Kruskal算法。
一、最小生成树的性质
设G = (V,E)是连通带权图，U是V的真子集。如果(u,v)∈E,且u∈U,v∈V-U,且在所有这样的边中，(u,v)的权c[u][v]最小，那么一定存在G的一棵最小生成树，它意(u,v)为其中一条边。这个性质有时也称为MST性质。
二、Prim算法
设G = (V,E)是连通带权图，V = {1,2,…,n}。构造G的最小生成树Prim算法的基本思想是：首先置S = {1}，然后，只要S是V的真子集，就进行如下的贪心选择：选取满足条件i ∈S,j ∈V – S,且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S = V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。
如下带权图：

生成过程：
1 -> 3 : 1
3 -> 6 : 4
6 -> 4: 2
3 -> 2 : 5
2 -> 5 : 3
实现：
三、Kruskal算法
当图的边数为e时，Kruskal算法所需的时间是O(eloge)。当e = Ω(n^2)时，Kruskal算法比Prim算法差；但当e = o(n^2)时，Kruskal算法比Prim算法好得多。
给定无向连同带权图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 : 1
4 -> 6 : 2
2 -> 5 : 3
3 -> 4 : 4
2 -> 3 : 5
两种算法代码见教材
2. 对数组A={15，29，135，18，32，1，27，25，5}，写出用快速排序算法（按升序排序）的第一趟快速排序结果（5分）。
解：（1）第一步：15 29 135 18 32 1 27 25 5
第二步：29 135 18 32 27 25 15 1 5
第三步：135 32 29 18 27 25 15 5 1
第四步：135 32 29 27 25 18 15 5 1
3．(20分)用动态规划方法求解下列系列0/1背包问题；请给出利用分支限界技术求得最优解的具体过程，上界函数：ub=V+(M-w)(vi+1/wi+1)
0/1背包数据如下: 4件物品，物品重量分别为W={1，2，3，2}，物品价值V={10，15，30，12}，背包承重量M=5。求：能够放入背包的最有价值的物品集合及最大价值。
如设： V(i, j) —— 前 i个物品中能够装入承重量 j 的背包中的最大总价值。请将如下递推式填写完整：
V(0, j) = 0（0个物品），V(i, 0) = 0（承重量0）
V(i, j) = V(i-1, j) 第i个物品不能装入，j < wi 超重）
V(i, j) = max { V(i-1,j-w(i))+vi ， V(i-1,j) } j > wi （不超重）(5分)
V
j=0
1
2
3
4
5
i=0
0
0
0
0
0
0
1
0
10
15
35
40
45
2
0
0
15
30
30
45
3
0
0
12
30
30
42
4
0
0
12
12
12
12
i在最优子集中 i不在最优子集中
自底向上：按行或列填写下表。（8分）
V
j=0
1
2
3
4
5
i=0
0
0
0
0
0
0
1
0

2
0

3
0

4
0

V
j=0
1
2
3
4
5
i=0
0
0
0
0
0
0
1
0

2
0

3
0

4
0

用分支限界法求解的状态空间树的搜索图(7分)
四．算法复杂度分析 (10分)
请根据递归树分析快速排序算法的最好时间复杂性及最坏时间复杂性。
五．算法设计题 （16分, 每小题8分）
1. 对于给定的无向图G=(V,E), 设计深度优先算法判断图是否为连通图。
2. 改写二分查找算法，并分析其时间复杂度：
设a[1…n]是一个已经排好序的数组，改写二分查找算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i，和大于x的最小元素位置j；当搜索元素x在数组中时，i和j相同，均为x在数组中的位置。