算法设计与分析考点精讲串烧Word格式.docx
《算法设计与分析考点精讲串烧Word格式.docx》由会员分享，可在线阅读，更多相关《算法设计与分析考点精讲串烧Word格式.docx（15页珍藏版）》请在冰点文库上搜索。
如果选择了wi，则xi=1。
此解空间的空间树上有个叶结点，共有个结点。
2n,2n+1-1。
4．已知将两个分别包含n个和m个记录的已分类文件归并在一起得到一个分类文件需作n+m次记录移动。
现有五个已分类文件F1,F2,F3,F4,F5，它们的记录个数分别为25,40,15,10,40，将这五个文件归并成一个分类文件需作次记录移动。
注：
每次只能归并两个文件。
285。
5．两个序列A=“xyxxzxyzxy”和B=“zxzyyzxxyxxz”的最长的公共子序列的长度为________。
其中一个最长公共子序列为。
6,xzyzxy。
三、问答题（每小题5分，共20分）
1.快速排序算法是根据分治策略来设计的，简述其基本思想。
答：
快速分类算法是根据分治策略设计出来的算法。
其关键步骤就是“划分”：
根据某个元素v为标准，将序列中的元素重新整理，使得整理后的序列中v之前的元素都不大于v，而v之后的元素都不小于v。
此时，元素v即找到了其最终的位置。
要得到序列的排序结果，再只需对v之前的元素和v之后的元素分别排序即可，这可通过递归处理来完成。
2．简述蒙特卡罗算法的特点及提高蒙特卡罗算法得到的为正确的概率的措施？
在某些实际应用中经常会遇到一些问题，不论采用确定性算法还是概率算法都无法保证每次得到正确的解。
蒙特卡罗算法在一般情况下，可以保证对问题的所有实例都以高概率给出正确解，但是通常无法判定一个具体解是否正确。
使用蒙特卡罗算法肯定能得到问题的一个解，但是这个解未必是正确的。
可以通过重复调用同一个蒙特卡洛算法多次来提高获得正确解的概率。
3．简述回溯法的基本思想。
回溯法的基本思想是：
深度优先搜索+剪枝。
从根结点开始，以深度优先的方式进行搜索，搜索的过程中，每搜索到一个结点，检查是否满足约束函数和限界函数，如果满足，则更深一层的搜索，如果不满足，则剪枝，搜索过程直到找到问题的解或所有活结点变成死结点为止。
回溯法用来求问题的多个解。
4．简述最小生成树的Kruskal算法的基本思想。
按照图中边权由大到小的次序依次考虑每条边是否加入最小生成树中。
当考虑到某条边时，如果该边与已经加入到最小生成树中的边不形成回路，则将该边加入进去。
四、求解题
1．（5分）设f（N）、g（N）是定义在正数集上的正函数。
如果存在正的常数C和自然数N0，使得当N≥N0时有f（N）≤Cg（N），则成函数f（N）当N充分大时上有界，且g（N）是它的一个上界，记为f（N）=O（g（N））。
证明：
O（f（N））+O（g（N））=O（max{f（N），g（N）}）。
解：
对于任意f1（n）O（f（n）），存在正常数c1和自然数n1，使得对所有nn1，有f1（n）c1f（n）。
类似地，对于任意g1（n）O（g（n）），存在正常数c2和自然数n2，使得对所有nn2，有g1（n）c2g（n）。
令c3=max{c1,c2}，n3=max{n1,n2}，h（n）=max{f（n）,g（n）}。
则对所有的nn3，有
f1（n）+g1（n）c1f（n）+c2g（n）
c3f（n）+c3g（n）=c3（f（n）+g（n））
c32max{f（n）,g（n）}
=2c3h（n）=O（max{f（n）,g（n）}）.
拓展：
证明O（f）+O（g）=O（f+g）
令F[N]=O[f],则存在自然数N1,C1,使得对任意的自然数N>
=N1，有：
F（N）<
=C1f[N];
同理令：
G[N]=O[g],则存在自然数N2,C2,使得对任意的自然数N>
=N2，有：
G（N）<
=C2g[N];
令C3=max{C1,C2},N3=max{N1,N2},则对所有的N>
=N3,有
F[N]<
=C1f（N）<
=C3f（N）;
G[N]<
=C2f（N）<
=C3g（N）;
故有：
O（f）+O（g）=F（N）+G（N）<
=C3f（N）+C3g（N）=C3（f（N）+g（N））=O（f+g）;
因此有：
O（f）+O（g）=O（f+g）
2．（8分）用动态规划解决0-1背包问题的改进算法求解如下实例：
n=4，c=12，v=（18，15，8，12），w=（10，2，3，4）。
（要求：
先写出计算公式，再写具体的求解过程，指出最优值和最优解）
p[n+1]={（0,0）}
p[i]=p[i+1]∪p[i+1]
（wi,vi）去掉受控点。
P[5]={（0,0）}
P[4]={（0,0）,（4,12）}
P[3]={（0,0）,（3,8）,（4,12）,（7,20）}
P[2]={（0,0）,（2,15）,（5,23）,（6,27）,（9,35）}
P[1]={（0,0）,（2,15）,（5,23）,（6,27）,（9,35）}
最优值为35，最优解为（0,1,1,1）
3.（10分）用单纯性算法求解下面线性规划问题：
maxz=-x2+3x3-2x4
s.t.x1+3x2-x3+2x4=7
-4x2+3x3+8x4≤10
2x2-4x3≥-12
xi≥0（i=1,2,3,4）
要求：
（1）步骤描述
（2）写清每一迭代步的选择，单纯形表，可行解及可行解对应的目标函数的值。
线性规划的约束标准型为：
x5-4x2+3x3+8x4=10
x6-2x2+4x3=12
xi≥0（i=1,2,3,4,5,6）
初始单纯形表
C
x2
x3
x4
z
-1
3
-2
x1
7
2
x5
10
-4
8
x6
12
4
z=0,x=（7,0,0,0,10,12）
第一步迭代
（1）选入基变量x3
（2）选离基变量x6
（3）转轴变换
9
1/2
-3/4
5/2
1/4
1
-5/2
-1/2
z=9,x=（10,0,3,0,1,0）
第二步迭代
（1）选入基变量x2
（2）选离基变量x1
11
-1/5
-4/5
-12/5
2/5
1/10
4/5
5
1/5
3/10
Z行非基变量的系数全部为负，迭代结束，最大值为11，最优解为（0,4,5,0,11,0）
4.（10分）单源最短路径问题：
在下图实例上指定源点为1，目标点为6，应用优先队列式分支限界法找出1到6的最短路径。
（要求写明优先级，画出搜索树，标出最短路径）
优先级：
当前结点所代表的最短路径长度，长度越小，优先级越高
搜索树：
五、算法设计（共13分）：
说明：
任意选择所使用的算法策略。
说明所使用的算法策略；
写出算法实现的主要步骤；
题目：
n后问题
策略1：
回溯法（定义解的结构，确定解空间树，确定约束函数，深度优先方式搜索，判断当前是否到叶子节点，若到了叶子节点，则找到了一种着色方案，将其方案输出，并将方案个数加1，若是中间节点，判断是否满足约束条件，若满足，则深一步搜索，否则剪枝。
）
策略2：
分支限界法（定义解的结构，确定解空间树，确定约束函数，以广度优先方式搜索，判断当前是否到叶子节点，若到了叶子节点，则找到了一种放置方案，方案个数累加1，并且输出对应的方案，若是中间节点，判断有没有合适的放置位置，若有，则扩展该节点，将其可行的孩子节点加入到活节点表中，若没有，则从活节点表中取下一个活节点）
简答题：
1操作系统是算法吗？
请说说算法和程序的区别。
不是。
算法是满足下述性质的指令序列：
（1）输入：
有零个或多个外部量作为算法的输入。
（2）输出：
算法产生至少一个量作为输出。
（3）确定性：
组成算法的每条指令清晰、无歧义。
（4）有限性：
算法中每条指令的执行次数有限，执行每条指令的时间也有限
程序是算法用某种程序设计语言的具体实现。
程序可以不满足算法的性质（4）即有限性。
2、插入排序、合并排序和快速排序这三种算法，哪几种使用了分治策略？
请简述之。
合并排序和快速排序使用了分治的策略。
合并排序：
对要排序的数组A[low…high]，令mid=[（low+high）/2]，用A[mid]把原数组A[low…high]分成两个子数组，然后对两个子数组进行排序，在合并两个已牌子徐的子数组，产生排序数组。
快速排序：
对要排序的数组A[low…high]，先使用算法SPLIT重新排列元素，使得原先在A[low]中的祝愿占据其正确的位置A[w]，并且所有小于或等于A[w]的元素所处的位置为A[low…w-1]，而所有大于A[w]的元素所处的位置是A[w+1…high]。
在对子数组A[low…w-1]和A[w+1…high]递归地排序，产生整个排序数组。
归并排序要好于插入排序，插入排序要好于冒泡排序。
3、分治法适合求解的问题一般具有那些特征？
分治法可分为哪三个主要步骤？
适合分治法求解的问题一般具有以下特征：
（1）问题的规模缩小到一定程度就可以容易地解决
（2）问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
（3）基于子问题的解可以合并为原问题的解
（4）问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
分治法可分为以下三个步骤：
分解（Divide）：
将原问题分解为子问题
解决（Conquer）：
求解子问题
合并（Combine）：
组合子问题的解得到原问题的解。
4.贪心算法的基本思想是什么？
贪心算法适合求解的问题具有哪些特征？
贪心算法求解的问题一定可以获得最优解码？
贪心算法的基本思想：
适用于求解最优化问题的算法往往包含一系列步骤，每一步都有一组选择。
贪心算法总是作出在当前看来是最好的选。
择贪心算法并不从整体最优上加以考虑，它所作出的选择只是在某种意义上的局部最优选择。
贪心算法适合求解的问题具有的特征：
1）最优子结构性质：
整体最优一定包括子问题最优
2）贪心选择性质：
所求问题的整体最优解可以通过一系列局部最优的选择获得
贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。
在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
5.合并排序算法是根据分治策略来设计的，简述其基本思想。
将待排序元素分成大小大致相同的两个子集合，分别对两个子集合进行排序，最终将排好序的子集合合并成所要求的排好序的集合。
算法复杂度为：
O（nlogn）
6．简述拉斯韦加斯算法的算法特点及提高拉斯韦加斯算法得到解得概率的方法？
（1）绝不返回错误的解，一旦找到一个解，那么这个解一定是正确的，也可能找不到解。
（2）由于得到正确解的概率岁算法执行时间的增加而提高。
对于所求解的问题的任一实例，只要用同一拉斯韦加斯算法对该实例反复求解足够多得次数，可使求解失效的概率任意小。
7．简述分枝限界法的基本思想。
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。
活结点一旦成为扩展结点，就一次性产生其所有儿子结点。
在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。
这个过程一直持续到找到所需的解或活结点表为空时为止。
补充：
分支限界法与回溯法
（1）求解目标：
回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
（2）搜索方式的不同：
回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
（3）当前节点的扩展方式不同：
回溯法每个活结点有可能多次成为扩展结点，而分支限界法的每一个活结点最多只有一次机会变成扩展结点。
8．简述最小生成树的Prim算法的基本思想
设G=（V,E）是连通带权图，V={1,2,…,n}。
构造G的最小生成树的Prim算法的基本思想是：
（1）置S={1}
（2）只要S是V的真子集，就作如下的贪心选择
选取满足条件i∈S，j∈V-S，且c[i][j]最小的边，将顶点j添加到S中。
一直到S=V时为止。
（3）选取到的所有边恰好构成G的一棵最小生成树。
9.简单描述分治法的基本思想。
将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同；
对这k个子问题分别求解。
如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止；
将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
10.简述动态规划方法所运用的最优化原理。
“最优化原理”用数学化的语言来描述：
假设为了解决某一优化问题，需要依次作出n个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任何一个整数k，1<
k<
n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，…，Dn也是最优的。
11.何谓最优子结构性质？
某个问题的最优解包含着其子问题的最优解。
这种性质称为最优子结构性质。
13.何谓P、NP、NPC问题
14.简述二分检索（折半查找）算法的基本过程。
设输入是一个按非降次序排列的元素表A[i：
j]和x，选取A[（i+j）/2]与x比较，如果A[（i+j）/2]=x，则返回（i+j）/2，如果A[（i+j）/2]<
x，则A[i：
（i+j）/2-1]找x，否则在A[（i+j）/2+1：
j]找x。
上述过程被反复递归调用。
15.什么是算法？
算法的特征有哪些？
算法是解决某类问题的一系列运算的集合【2分】。
具有有穷行、可行性、确定性、0个或者多个输入、1个或者多个输出【8分】。
16.什么是P类问题？
什么是NP类问题？
什么是NPC问题?
请描述集合覆盖问题的近似算法的基本思想。
用确定的图灵机可以在多项式实践内可解的判定问题称为P类问题【2分】。
用不确定的图灵机在多项式实践内可解的判定问题称为NP类问题。
【2分】只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。
集合覆盖问题的近似算法采用贪心思想：
对于问题<
X,F>
，每次选择F中覆盖了尽可能多的未被覆盖元素的子集S，然后将U中被S覆盖的元素删除，并将S加入C中，最后得到的C就是近似最优解。
【6分】
补充算法思想
1.贪心法：
基本思想：
贪心算法的基本要素：
2）贪心选择性质：
2.单源最短路径问题
算法的思想：
先求出长度最短的一条路径，再参照它求出长度次短的一条路径，以此类推，直到从源点到其他各个定点的最短路径全部求出为止，该算法俗称Dijkstra算法。
3.动态规划：
实质是分治思想和解决冗余。
将待求解问题分解为更小的、相同的子问题，然后对子问题进行求解，最终产生一个整体最优解。
求解步骤：
分析最优解的性质，刻画最优解的结构特征。
最优子结构的性质分析（整体最优包含子问题最优）
递归定义最优值。
建立最优值的递归关系式
以自底向上的方式计算出最优值，并记录相关信息。
根据计算最优值时得到的信息，构造出最优解。
基本要素：
最优子结构性质
子问题重叠性质
自底向上的求解方法
4.Prim算法与Kruskal算法的比较
设无向连通带权图G具有n个顶点和e条边
（a）从算法的思想上说，如果G的边数较小时，可以采用Kruskal，因为Kruskal每次查找最短的边；
边数多可以采用Prim算法，因为它每次加一个顶点。
可见Kruskal用于稀疏图，Prim用于稠密图。
（b）从时间上说，Prim算法的时间复杂度O（n2）,Kruskal的时间复杂度O（eloge）（e为边数）
（c）从空间上说，Prim算法需要很小的空间，Kruskal算法需要占用很大的空间。
算法设计题（本题15分）
分别用贪心算法、动态规划法、回溯法设计0-1背包问题。
分析算法的时间。
（1）贪心算法O（nlog（n））
Ø
首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。
若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。
依此策略一直地进行下去，直到背包装满为止。
（2）动态规划法O（nc）
m（i，j）是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。
由0-1背包问题的最优子结构性质，可以建立计算m（i，j）的递归式如下。
（3）回溯法O（2n）
cw:
当前重量cp:
当前价值bestp：
当前最优值
void
backtrack（int
i）
//回溯法
i初值1
{
if（i
>
n）//到达叶结点
{bestp
=
cp;
return;
}
if（cw
+
w[i]
<
c）//搜索左子树
cw
+=
w[i];
cp
p[i];
backtrack（i+1）;
-=
cp
if（Bound（i+1）>
bestp）
//搜索右子树
backtrack（i+1）;
升级会员 