发布时间 : 2024/6/1 11:55:29 星期六 文章算法分析与设计复习题更新完毕开始阅读b930ec3b69dc5022abea0050

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的节点