算法设计与分析考点精讲串烧

1、一、选择题(每小题3分，共15分)算法与程序的主要区别在于算法具有()。A.能行性B.确定性C.有限性。.输入和输出答案：C。对一个有序序列，以比较为基础的搜索算法的最坏情况时间复杂性的下界为()。A. Q (n)B. Q (n2)C. Q (nlogn)D. Q (logn)答案：D。背包问题：n=6, C=10, V(1：6) = (15,59,21,30,60,5), W(1：6) = (1,5,2,3,6,1)。该问题 的最大价值为()。A. 101 B. 110 C. 115 D. 120答案：C。矩阵连乘积问题：Mi(5x10), M2(10 x4), M3(4x6)0矩阵链乘MM

2、2M3需要的最少乘法次数为 ()。A. 348 B. 328 C. 720 D. 320答案：Do用贪心策略设计算法的关键是()。A.将问题分解为多个子问题来分别处理B.选好贪心策略C.获取各阶段间的递推关系式D.满足最优性原理答案：Bo二、填空题(每小题4分，共20分)某算法的计算时间T(n)满足递归关系式：T(n)=2T(n-1)+O(1), n1； T=1。则T(n)=。答案：2n-1。 用 方法对状态空间树进行搜索时，每个结点有可能多次成为扩 展结点。子集和数问题一般陈述如下：已知n+1个正数：w (IWiWn)和M，要求找出Wj的和数是M的所有子集。其解可以表示为n-元组(X , x

3、2 , , xn)，这里xiG0,1，1i %,有fn)cf(n)。类似地，对于任意gi (n) g O(g(n)，存在正常数c2和自然数n2,使得对所有n n2, 有 gi (n) 气，有f(n) +gi (n) =N1,有：F (N) =N2,有：G(N)=N3,有FN=C1f(N)=C3f(N);GN=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) (8分)用动态规划解决0-1背包问题的改进算法求解如下实例：n=4, c=12, v= (18, 15

4、, 8, 12), w= (10, 2, 3, 4)。(要求：先写出计算公式，再写具体的求解过程，指出最 优值和最优解)解：pn+1 = (0,0)pi=pi+1Upi+1代工)去掉受控点。P5 = (0,0)P4 = (0,0),(4,12)P3 = (0,0),(3,8),(4,12),(7,20)P2 = (0,0),(2,15),(5,23),(6,27),(9,35)P1 = (0,0),(2,15),(5,23),(6,27),(9,35)最优值为35,最优解为(0,1,1,1)(10分)用单纯性算法求解下面线性规划问题：max z=-x2+3x3-2x4s.t . X+3x2-

5、x3+2x4= 7-4x2+3x3 +8%W102x2-4x3 3T2x.0 (i=1,2,3,4)要求：步骤描述写清每一迭代步的选择，单纯形表，可行解及可行解对应的目标函数的值。解：线性规划的约束标准型为：max z=-x2+3x3-2x4s.t . x1+3x2- x3+2x4= 7x5-4x2+3x3 +8x4= 10 x6-2x2+4x3 =12xi0 (i=1,2,3,4,5,6)初始单纯形表Cx2x3x4z0-13-2x173-12x510-438x612-240z=0,x=(7,0,0,0,10,12)第一步迭代选入基变量x3选离基变量x6转轴变换Cx2x6x4z91/2-3/4

6、-2x1105/21/42x51-5/2-3/48x33-1/21/40z=9,x=(10,0,3,0,1,0)第二步迭代选入基变量x2选离基变量x1转轴变换Cx1x6x4z11-1/5-4/5-12/5x242/51/104/5x5111-1/210 x351/53/102/5Z行非基变量的系数全部为负，迭代结束，最大值为11,最优解为(0,4,5,0,11,0)(10分)单源最短路径问题：在下图实例上指定源点为!，目标点为6,应用优先队列式分支限界法找出1到6的最短路径。(要求写明优先级，画出搜索树，标出最短路径)解：优先级：当前结点所代表的最短路径长度，长度越小，优先级越高搜索树：01|

7、9 23 421 4 13 52 8 5 174,州争5 1317 29 2016 （46 28618五、算法设计（共13分）：说明：任意选择所使用的算法策略。要求：说明所使用的算法策略；写出算法实现的主要步骤；题目：n后问题策略1：回溯法（定义解的结构，确定解空间树，确定约束函数，深度优先方式搜索，判断 当前是否到叶子节点，若到了叶子节点，则找到了一种着色方案，将其方案输出，并将方案 个数加1，若是中间节点，判断是否满足约束条件，若满足，则深一步搜索，否则剪枝。） 策略2：分支限界法（定义解的结构，确定解空间树，确定约束函数，以广度优先方式搜索，判断当前是否到叶子节点，若到了叶子节点，则找到

8、了一种放置方案，方案个数累加1，并且输出对应的方案，若是中间节点，判断有没有合适的放置位置，若有，则扩展该节点，将其可行的孩子节点加入到活节点表中，若没有，则从活节点表中取下一个活节点）简答题：1操作系统是算法吗？请说说算法和程序的区别。答：不是。算法是满足下述性质的指令序列：（1）输入：有零个或多个外部量作为算法的输入。（2）输出：算法产生至少一个量作为输出。（3）确定性：组成算法的每条指令清晰、无歧义。（4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质（4）即有限性。2、插入排序、合并排序和快速排序这三种算法

9、，哪几种使用了分治策略？请简述之。 答：合并排序和快速排序使用了分治的策略。合并排序：对要排序的数组Alow.high，令mid=（low+high）/2，用 Amid把原数组 Alow.high 分成两个子数组，然后对两个子数组进行排序，在合并两个已牌子徐的子数组， 产生排序数组。快速排序：对要排序的数组Alow.high,先使用算法SPLIT重新排列元素，使得原先在 Alow中的祝愿占据其正确的位置Aw，并且所有小于或等于Aw的元素所处的位置为 Alow.w-1，而所有大于Aw的元素所处的位置是Aw+1.high。在对子数组Alow.w-1 和Aw+1.high递归地排序，产生整个排序数组

10、。归并排序要好于插入排序，插入排序要好于冒泡排序。分治法适合求解的问题一般具有那些特征？分治法可分为哪三个主要步骤？答：适合分治法求解的问题一般具有以下特征：图（1）问题的规模缩小到一定程度就可以容易地解决图（2）问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质（3）基于子问题的解可以合并为原问题的解图（4）问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 分治法可分为以下三个步骤：图分解（Divide）：将原问题分解为子问题图解决（Conquer）：求解子问题图合并（Combine）：组合子问题的解得到原问题的解。贪心算法的基本思想是什么？贪心算法适合

11、求解的问题具有哪些特征？贪心算法求解的 问题一定可以获得最优解码？答：贪心算法的基本思想：适用于求解最优化问题的算法往往包含一系列步骤，每一步都有一组选择。贪心算法总 是作出在当前看来是最好的选。择贪心算法并不从整体最优上加以考虑，它所作出的选择只 是在某种意义上的局部最优选择。贪心算法适合求解的问题具有的特征：1）最优子结构性质：整体最优一定包括子问题最优2）贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择获得贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。在一 些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。合并排序算法是根据

12、分治策略来设计的，简述其基本思想。将待排序元素分成大小大致相同的两个子集合，分别对两个子集合进行排序，最终将排好序 的子集合合并成所要求的排好序的集合。算法复杂度为：O（nlogn）简述拉斯韦加斯算法的算法特点及提高拉斯韦加斯算法得到解得概率的方法？（1）绝不返回错误的解，一旦找到一个解，那么这个解一定是正确的，也可能找不到 解。（2）由于得到正确解的概率岁算法执行时间的增加而提高。对于所求解的问题的任一 实例，只要用同一拉斯韦加斯算法对该实例反复求解足够多得次数，可使求解失效的概率任 意小。简述分枝限界法的基本思想。分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。

13、在分 支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次 性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍 弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点， 并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。补充：分支限界法与回溯法求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界 法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义 下的最优解搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优 先或

14、以最小耗费优先的方式搜索解空间树。当前节点的扩展方式不同：回溯法每个活结点有可能多次成为扩展结点，而分支限界 法的每一个活结点最多只有一次机会变成扩展结点。简述最小生成树的Prim算法的基本思想设G=(V,E)是连通带权图，V=1,2，,n。构造G的最小生成树的Prim算法 的基本思想是：置 S=1只要S是V的真子集，就作如下的贪心选择选取满足条件i e S，j e V-S，且cij最小的边，将顶点j添加到S中。 一直到S=V时为止。选取到的所有边恰好构成G的一棵最小生成树。简单描述分治法的基本思想。将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题 相同；对这k个子

15、问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问 题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止；将求出的小规 模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。简述动态规划方法所运用的最优化原理。最优化原理”用数学化的语言来描述：假设为了解决某一优化问题，需要依次作出n个 决策D1，D2,，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 k n, 不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态， 即以后的决策Dk+1，Dk+2，Dn也是最优的。何谓最优子结构性质？某个问题的最优解包含着其子问题的最优解。这种

16、性质称为最优子结构性质。何谓P、NP、NPC问题简述二分检索(折半查找)算法的基本过程。设输入是一个按非降次序排列的元素表Ai： j和x，选取A(i+j)/2与x比较，如果 A(i+j)/2=x，则返回(i+j)/2,如果A(i+j)/2x，则 Ai： (i+j)/2-1找 x，否则在 A (i+j)/2+1： j找x。上述过程被反复递归调用。什么是算法？算法的特征有哪些? 算法是解决某类问题的一系列运算的集合【2分】。具有有穷行、可行性、确定性、0个或者 多个输入、1个或者多个输出【8分】。什么是P类问题？什么是NP类问题？什么是NPC问题?请描述集合覆盖问题的近似算法 的基本思想。用确定的

17、图灵机可以在多项式实践内可解的判定问题称为P类问题【2分】。用不确定 的图灵机在多项式实践内可解的判定问题称为NP类问题。【2分】只有把解域里面的 所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题 就是NPC问题。集合覆盖问题的近似算法采用贪心思想：对于问，每次选择F中覆盖了尽可能 多的未被覆盖元素的子集S，然后将U中被S覆盖的元素删除，并将S加入C中，最后得到 的C就是近似最优解。【6分】补充算法思想贪心法：基本思想：适用于求解最优化问题的算法往往包含一系列步骤，每一步都有一组选择。贪心 算法总是作出在当前看来是最好的选。择贪心算法并不从整体最优上加以考虑，它所作出

18、的 选择只是在某种意义上的局部最优选择。贪心算法的基本要素：1）最优子结构性质：整体最优一定包括子问题最优2）贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择获得单源最短路径问题算法的思想：先求出长度最短的一条路径，再参照它求出长度次短的一条路径，以此类推，直到从源点到其他各个定点的最短路径全部求出为止，该算法俗称Dijkstra算法。动态规划：基本思想：实质是分治思想和解决冗余。将待求解问题分解为更小的、相同的子问题，然后 对子问题进行求解，最终产生一个整体最优解。求解步骤：分析最优解的性质，刻画最优解的结构特征。最优子结构的性质分析（整体最优包含子问题最优）递归定义最优值。建立最优值的递归关系式3以自底向上的方式计算出最优值，并记录相关信息。根据计算最优值时得到的信息，构造出最优解。基本要素：最优子结构性质子问题重叠性质自底向上的求解方法Prim算法与Kruskal算法的比较设无向连通带权图G具有n个顶点和e条边从算法的思想上说，如果G