算法分析与设计复习题

3. 快速排序算法是利用（ A ）实现的算法。

A. 分治策略 B. 动态规划法 C. 贪心法 D. 回溯法

4． 实现归并排序利用的算法是（ A ）。

A. 分治策略 B. 动态规划法 C. 贪心法 D. 回溯法 4． 实现棋盘覆盖算法利用的算法是（ A ）。

A. 分治法 B. 动态规划法 C. 贪心法 D. 回溯法

8. （ B ）是贪心算法与动态规划算法的共同点。

A. 重叠子问题 B. 构造最优解 C. 贪心选择性质 D. 最优子结构性质

9. 下面问题（ B ）不能使用贪心法解决

。 A. 单源最短路径问题 B. N

皇

后

问题 C. 最小花费生成树问题 D.

背

包

问

题

9. 下列算法中不能解决0/1背包问题的是（ A ） A. 贪心法 B. 动态规划 C. 回溯法 D. 分支限界法

10. 回溯法解旅行售货员问题时的解空间树是（ B ）。

A. 子集树 B. 排列树 C. 深度优先生成树 D. 广度优先生成树

12. 回溯法的效率不依赖于下列哪些因素（ D ）

A. 满足显约束的值的个数 B. 计算约束函数的时间 C. 计算限界函数的时间 D. 确定解空间的时间 14. 下面关于NP问题说法正确的是（ B ） A. NP问题都是不可能解决的问题 B. P类问题包含在NP类问题

中 C. NP完全问题是P类问题的子集 D. NP类问题包含在P类问题中

15. 下列哪些问题是典型的NP完全问题( C )

A． 排序问题 B． n-后问题 C． 0/1背包问题 D． 旅行商问题 15. 下面哪个问题不是NP完全问题（ D ）

A. 图着色问题 B. TSP问题

C. 哈密尔顿回路问题 D. 最小生成树问题

6、采用动态规划技术设计的算法都是递归算法。F

9、采用回溯法或分支限界求解问题首先必须先完整生成一颗解空间树，再在这颗树上遍历

搜索。F

9、回溯法每次只构造可能解的一部分。T

NP

10、回溯法就是一种有组织的系统化搜索技术T 10、分支限界法是一种有组织的系统化搜索技术T

13、NP完全问题是NP类问题的一个子集T 13、P类问题是NP类问题的子集T

1、考虑下面的每对函数f(n)和g(n)，如果他们的阶相等则使用记号?，否则使用O记号表示它们的关系。 (10?)

(1) f(n)?(n2?n)/2 ，g(n)?6n g(n) = O(f(n)) (2) f(n)?n?2n，g(n)?n2 f(n) = O(g(n)) (3) f(n)?n?nlogn，g(n)?nn f(n) = O(g(n)) (4) f(n)?2logn，g(n)?logn?1 g(n) = O(f(n))

1.05(5) f(n)?log(n!)，g(n)?n f(n) = O(g(n))

22、在下表中填上true或false。 (10?) f(n) 1 2 3 4 5 g(n) f(n)?O(g(n)) F T F T F f(n)??(g(n))f(n)??(g(n)) F T F F F T T T F T 2n?3n 50n?logn 50nlogn logn n! 3100n?2n?100 10n?loglogn 10nloglogn 2log2n 5n

针对以下问题，详细说明其所采用算法的思想和伪代码。 1、采用分治策略求第K小的元素的算法。 问题：选第k小。

输入：数组S，S的长度n，正整数k，其中k?[1,n].

输出：第k小的元素

思路一：使用快排（nlogn）. 思路二：使用分治O(n).主要思想是利用S中的某个元素m作为标准将S划分成2个子数组

S1和S2，其中S1中的元素都比m小，S2中的元素都比m大，设S1中的元素的数目为|S1|。如果k<=|S1|，则原问题就规约为在S1中找第k小的元素； 如果k = |S1| + 1，则m就是所要找的第k小的元素；

如果k > |S1| + 1，则原问题规约为在S2中找第p小的元素，其中p = k - |S1| -1. 以上算法的关键是确定这个划分的标准，即元素m：

先将S分组，5个元素一组，一共分成n / 5个组。在每组中找出一个中位数，然后将这5个中位数放到集合M中。最后在M中调用选择算法选出M的一个中位数，它就是我们要找的m。算法的伪码描述如下： Select(S,k) 输入：n个数的数组S，正整数k 输出：S中第k小的元素 1. 将S划分成5个一组，一共n / 5组； 2. 每组中找出一个中位数，把这些中位数放到集合M中； 3. m <-- Select(M,|M|/2); // 选M的中位数m，将S中的数划分成A,B,C,D四个集合 4. 把A和D中的每个元素与m进行比较，小的构成S1，大的构成S2； 5. S1 = S1 ? C，S2= S2 ? B； 6. if k = |S1| + 1 then 输出m 7. else if k <= |S1| then Select(S1,k); 8. else Select(S2,k - |S1| - 1) 1、采用分治策略求最大子段和问题的算法。

给定n个整数的序列A = ,求max{0,1??i??j??nk?imax?a}

kj我们可以在n/2的位置将A划分成A1和A2，于是A的最大子段和可能有3种情况：出现在A1、出现在A2、出现在A1和A2，前2种情况恰好是规模减半的子问题。第三种情况需要特殊处理。假设原问题的输入是A[1...n]，中间分点k = n /2,那么前半部分的子问题的输入是A[1...k],后半部分的输入是A[k+1,n]，在第三种情况设最大和是A[p...q]，那么p<=k,q>=k+1,从A[p]到A[k]的元素都在A1中，从A[k+1]到A[q]的元素都在A2中，我们只需要从A[k]和A[k+1]分别向前和向后求和即可。当2个方向扫描完成后S1+S2就是横跨中心的最大和，其边界从p到q。这3种情况都计算完成后通过比较就可以确定A的最大字段和。

伪码描述： MaxSubSum(A,left,right) 输入：数组A、left和right分别是A的左右边界 1 <= left <= right 输出：A的最大子段和sum及其子段的前后边界 1. if left = right then return max{A[left],0} 2. center <-- (left + right) / 2 3. leftsum <-- MaxSubSum(A,left,center) 4. rightsum <-- MaxSubSum(A,center + 1,right) 5. S1 <-- A1[center]

6. S2 <-- A2[center + 1] 7. sum <-- S1 + S2 8. if leftsum > sum then sum <-- leftsum 9. if rightsum > sum then sum <-- rightsum 2、求最小生成树的prim算法（贪心法）

设无向带权图G=，其中w(e) ?W是边e的的权。G的一棵生成树是包含了G的所有顶点的树。树中各边的权的和就是整棵树的权。具有最小权的树就是G的最小生成树。

设G是n阶连通图，T是G的n阶联通子图，那么： ? T是G的生成树iff T有n-1条边；

? 如果T是G的生成树，e?T，那么T?{e}包含一个回路

设G= ，其中V= {1,2,3...n}，这个算法的基本思想是将V划分成2个子集S和V-S。初始时S= {1}。算法每一步从联通S和V-S的边中挑选一条权值最小的边，然后将这条边所关联的顶点加到S中去，这条边也成了生成树T的边。至多经过n-1步就可以求得最小生成树。算法的伪码如下：

Prim(G,E,W) // G-连通图 E顶点集合 W权值集合 输入：连通图G 输出：G的最小生成树T 1. S <-- {1};T = ? 2. while V-S ≠ 空集 do 3. 从V-S中选择j使得j到S中顶点的边e的权最小： T = T ∪ {e} 4. S <-- S ∪ {j} 2、求单源最短路径的dijkstra算法

在一个带权有向网络G= (V,E,W)中每条边e = 的权w(e)为非负实数，表示从i到j的距离。网络中有源点s∈V，求从s出发到达其他各个节点的最短路径。

Dijkstra算法的设计思想：将V划分成集合S与V - S.初始S= {s}，算法的每一步都是把一个节点加入到S，直到S= V。算法对每一个i∈V-S，计算从s出发中间只经过S中节点并且最终到达i的最短路径，称为从s到i相对于S的最短路径，路径长度dist[i]（注意：如果此刻s到i不可达，则令dist[i] = ∞）。通过比较，从所有dist[i]（i∈V-S）中选出最小值，例如dist[j]最小，那么节点j就是在这一步加入到S中的节点。算法的伪码描述如下（其中w(i,j)表示有向边的权） Dijkstra 输入：带权有向图G = ，源点s∈ V 输出：数组L，对所有j ∈ V - {s},L[j]表示s到j的最短路径上j前一个节点的标号 1. S <-- {s} 2. dist[s] <-- 0 3. for i ∈ V - {s} do 4. dist[i] <-- w(s,i) 5. while V - S ≠ ? do 6. 从V - S中选出具有相对S最短路径的节点j，k是该路径上连接j的节点

7. S <-- S ∪ {j};L[j] <-- k 8. for i ∈ V - S do 9. if dist[j] + w(j,i) < dist[i] 10 then dist[i] <-- dist[j] + w(j,i)

关于NP完全性：

1 什么是P问题？

这里的P代表Polynomial。P问题就是可以有一个确定型图灵机在多项式时间内解决的问题。即目前那些存在O(n), O(nk), O(nlogn)等多项式时间复杂度解法的问题。比如排序问题、最小生成树、单源最短路径。直观的讲，我们将P问题视为可以较快解决的问题。 2 什么是NP问题？

那些可以在非确定型图灵机上在多项式时间内解决的问题。（在确定型图灵机（我们在使用的计算机吗?）上可以在多项式时间内验证解是否正确，但不能在多项式时间内找出最优解的问题）。非确定型图灵机：可以理解为无限个确定型图灵机的集合。应该是说的一种强大的目前还不存在的，也与目前的计算机无法比较的一种计算机吧。也许它具备跳跃思维、能联想能学习能推理……

NP是目前为止还未找到多项式解法的问题。对于这些问题，我们目前也不知道是否存在多项式的解法。所以叫非确定多项式问题。

NP代表“Non-deterministic（非确定性）Polynomial（多项式）”而不是代表“Non-Polynomial（非多项式）。

典型的NP问题是旅行商问题(TSP)。

P与NP问题的关系？

NP问题如果找到了多项式解法就是P问题了。NP问题是目前为止我们还未找到多项式解法的问题。我们也不能证明它一定存在或不存在多项式解法。调查显示有的人持肯定态度，认为NP问题一定存在多项式解法，即P=NP。有的坚信NP问题不存在多项式解法。当然也有的人持不确定态度。

3 什么是NPC问题？

NPC问题是NP中目前看起来最不可能存在多项式解法的问题，是NP中“最难”的问题，也就是说它们是最不可能属于P类的。一中观点是NP问题包含P问题和NPC问题。也有观点认为NP=NPC。

因为任何NP中的问题可以在多项式时间内变换成为任何特定NP完全问题的一个特例，所以若任何一个NP完全的问题在P内，则可以推出P = NP。不幸的是，很多重要的问题被证明为NP完全，但没有一个有已知快速的算法。

迄今为止，人们已经发现了成千上万的NP-complete 问题，它们都具有容易被检查的性质，包括前面介绍的推销员旅行问题。当然更重要的是，它们是否也容易被求解，这就是著名的 P vs NP 的问题。

4 什么是NPH问题？

比NPC还难的题。NPH类：若问题A不属于NP类，已知某一NPC问题可在多项式时间之内转化为问题A，则称A为NP难题。例如，“TSP”是NPH问题。

5 NP问题意味什么?

面对一个问题，如果较劲脑子也没有思路，那么它也许是个NP问题。你可以转而证明它是个NP问题。也意味者要找到一个有效的解法是不可能的，至少也是相当困难。明智的做法是寻求一个找到有效解的近似算法。

6 如何证明一个问题是NP问题

通常证明一个问题 A 是 NP-complete 需要两步，第一先证明 A 是 NP 的，即满足容易被检查这个性质; 第二步是构造一个从某个已知的 NP-complete 问题 B 到 A 的多项式变换，使得如果 B 能够被容易地求解，A 也能被容易地解决。这样一来，我们至少需要知道一个 NP-complete 问题。

7 新千年的七大难题之一：

P=NP？就是说，是否能找到一个多项式解法去解决TSP、包装、舞会等问题。找到这样的解法或证明不存在这样的解法、或证明存在这样的解法。

本文来源：https://www.bwwdw.com/article/2922.html