发布时间 : 星期六 文章算法设计与分析考点精讲串烧更新完毕开始阅读a793662a5901020207409c5d
三、问答题（每小题5分，共20分）
1. 快速排序算法是根据分治策略来设计的，简述其基本思想。 答：
快速分类算法是根据分治策略设计出来的算法。其关键步骤就是“划分”：根据某个元素v 为标准，将序列中的元素重新整理，使得整理后的序列中v 之前的元素都不大于v，而v 之后的元素都不小于v。此时，元素v 即找到了其最终的位置。要得到序列的排序结果，再只需对v 之前的元素和v 之后的元素分别排序即可，这可通过递归处理来完成。 3． 简述回溯法的基本思想。
答：回溯法的基本思想是：深度优先搜索+剪枝。从根结点开始，以深度优先的方式进行搜索，搜索的过程中，每搜索到一个结点，检查是否满足约束函数和限界函数，如果满足，则更深一层的搜索，如果不满足，则剪枝，搜索过程直到找到问题的解或所有活结点变成死结点为止。回溯法用来求问题的多个解。
4．简述最小生成树的Kruskal 算法的基本思想。
答：按照图中边权由大到小的次序依次考虑每条边是否加入最小生成树中。当考虑到某条边时，如果该边与已经加入到最小生成树中的边不形成回路，则将该边加入进去。 四、求解题
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）
4.（10分）单源最短路径问题：在下图实例上指定源点为1，目标点为6，应用优先队列式分支限界法找出1到6的最短路径。（要求写明优先级，画出搜索树，标出最短路径）
914243125134352615 解：优先级：当前结点所代表的最短路径长度，长度越小，优先级越高 搜索树：
01922141354172834517645132920628164618
五、算法设计（共13分）： 简答题：
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) 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.何谓最优子结构性质？
某个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 14. 简述二分检索（折半查找）算法的基本过程。
设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较，如果
A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2] 算法是解决某类问题的一系列运算的集合【2分】。具有有穷行、可行性、确定性、0个或者多个输入、1个或者多个输出【8分】。 补充算法思想 1.贪心法： 基本思想：适用于求解最优化问题的算法往往包含一系列步骤，每一步都有一组选择。贪心算法总是作出在当前看来是最好的选。择贪心算法并不从整体最优上加以考虑，它所作出的选择只是在某种意义上的局部最优选择。 贪心算法的基本要素： 1）最优子结构性质：整体最优一定包括子问题最优 2）贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择获得 2. 单源最短路径问题 算法的思想：先求出长度最短的一条路径，再参照它求出长度次短的一条路径，以此类推，