《算法设计与分析考点精讲串烧》由会员分享，可在线阅读，更多相关《算法设计与分析考点精讲串烧（12页珍藏版）》请在金锄头文库上搜索。
1、一、选择题(每小题3分，共15分)1. 算法与程序的主要区别在于算法具有()。A.能行性B.确定性C.有限性D.输入和输出答案:Co2. 对一个有序序列，以比较为基础的搜索算法的最坏情况时间复杂性的下界为()。A. Q (/?) B. Q (刀2) C. Q (Mogz?) D. Q (log/?)答案：Do3. 背包问题：77=6, 010, 7(1:6) = (15,59,21,30,60,5),风 1:6)二(1, 5, 2,3,6, 1)。该问题 的最大价值为()。A. 101 氏 110 C. 115 D. 120答案：Co4. 矩阵连乘积问题：Mi(5xl0), M2(10x4),
2、 5(4x6)。矩阵链乘M 1M2M3:要的最少乘法次数为()。A. 348 B. 328 C. 720 D. 320答案：Do5. 用贪心策略设计算法的关键是()。A.将问题分解为多个子问题來分别处理B.选好贪心策略C.获取各阶段间的递推关系式D.满足最优性原理答案:Bo二、填空题(每小题4分，共20分)1. 某算法的计算时间T3)满足递归关系式：T(/7)=2T(/t-1)+0(1), /71； T二1。则T(/7)二0答案：2=2. 用方法对状态空间树进行搜索时，每个结点有可能多次成为扩展结点。3. 子集和数问题一般陈述如下：己知卅1个正数：叭(lWfW/?)和必要求找出旳的和数是的所有
3、子集。其解可以表示为/7元组(加，左，几)，这里尢0, 1, 1W2W/7。如果没有 选择肥，则相应的脸=0；如果选择了旳，则出=1。此解空间的空间树上有个叶结点，共有个结点。答案：2n, 2n，1-lo4. 已知将两个分别包含个和/个记录的己分类文件归并在一起得到一个分类文件需作卅刃 次记录移动。现有五个已分类文件用，忆 碍M,阿，它们的记录个数分别为25, 40,15, 10, 40,将这五个文件归并成一个分类文件需作次记录移动。注：每次只能归并两个文件。答案：285o5. 两个序列A二“xyxxzxyzxy”和B二“zxzyyzxxyxxz”的最长的公共子序列的长度为。其中一个最长公共子
4、序列为o答案：6, xzyzxy0三、问答题（每小题5分，共20分）1. 快速排序算法是根据分治策略来设计的，简述其基木思想。答：快速分类算法是根据分治策略设计出來的算法。其关键步骤就是“划分”：根据某个元素卩为 标准，将序列中的元素重新整理，使得整理后的序列中孑之前的元素都不大于-而/之后 的元索都不小于厶此时，元素亍即找到了其最终的位置。要得到序列的排序结果，再只需 对y Z前的元素和y Z后的元素分别排序即可，这可通过递归处理来完成。2. 简述蒙特卡罗算法的特点及提高蒙特卡罗算法得到的为正确的概率的措施？答：在某些实际应用中经常会遇到一些问题，不论采用确定性算法还是概率算法都无法保证每次
5、 得到正确的解。蒙特卡罗算法在一般情况下，可以保证对问题的所有实例都以高概率给出正 确解，但是通常无法判定一个具体解是否止确。使用蒙特卡罗算法肯定能得到问题的一个解, 但是这个解未必是正确的。可以通过重复调用同一个蒙特卡洛算法多次來提高获得正确解的概率。3. 简述回溯法的基本思想。答：冋溯法的基本思想是：深度优先搜索+剪枝。从根结点开始，以深度优先的方式进行搜 索，搜索的过程中，每搜索到一个结点，检查是否满足约束函数和限界函数，如果满足，则 更深一层的搜索，如果不满足，则剪枝，搜索过程直到找到问题的解或所有活结点变成死结 点为止。回溯法用来求问题的多个解。4简述最小生成树的Kruskal算法的
6、基本思想。答：按照图川边权由大到小的次序依次考虑每条边是否加入最小生成树中。当考虑到某条边 时，如果该边与已经加入到最小生成树中的边不形成回路，则将该边加入进去。四、求解题1. (5分)设f(?0、g(N)是定义在正数集上的正函数。如果存在正的常数C和自然数使得当时有f(肋则成函数f(肋当艸 充分大时上有界，且是它的一个上界，记为(妙)。证明：0(广(旳)+0(旳)二 O(max /(A), g(M)。解：对于任意S) e 0(fS),存在正常数。和自然数，使得对所有nn有(刀) C /(/?)。类似地，对于任意gi(/7)G 0(g(/?),存在正常数02和自然数灿，使得对所有虑处， 有 g
7、 (/?) 773,有fS +g(/7) Cl A 77) + C2gri) Cif(n) + Czgn) = Ca (/(/?)+ g(刀) 2 maxAn), gn)=2c、hS - =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);因此有：0(f)+0(g)= O(f+g)2. (8分)用动态规划解决0T背包问题的改进算法求解如下实例：n=4, c二12, v= (18,15, 8, 12),(10, 2,
8、3, 4)o (要求：先写出计算公式，再写具体的求解过程，指出最优值和最优解)解：pn+l = (0, 0)pi二pi+l Upi+1(wi, Vi)去掉受控点。P5 = (0, 0)P4 = (0, 0), (4,P3 = (0, 0), (3,8), (4, 12), (7, 20)P2 = (0, 0), (2, 15), (5,23), (6, 27), (9, 35)Pl = (0, 0), (2, 15), (5,23), (6, 27), (9, 35)最优值为35,最优解为(0,1, 1,1)3. (10分)用单纯性算法求解下面线性规划问题：max z二-X2+3X3-2x4s
9、. t .x】+3x2- x3 +2x4= 7- 4x?+3x3 +8x，iW102x2-4x3 $-12XiNO (i二 1,2, 3,4)要求：(1) 步骤描述(2) 写清每-迭代步的选择，单纯形表，可行解及可行解对应的目标函数的值。解：线性规划的约束标准型为：max z=-x2+3x3-2x4s. t . Xi+3x2- X3 +2xi = 7X5-4x2+3x3 +8x1 = 10X6_2x2+4x3 =12x0(i=l,2, 3, 4, 5,6)初始单纯形表Cx2x3x4Z0-13-2X173-12x510-438x612-240z=0, x二(7, 0, 0, 0, 10, 12)
10、第一步迭代(1) 选入基变量x3(2) 选离基变量x6(3) 转轴变换Cx2x6x4Z91/2-3/4-2xl105/21/42x51-5/2-3/48x33-1/21/40z二9, x=(10, 0, 3, 0, 1, 0)第二步迭代(1) 选入基变量x2(2) 选离基变量xl(3) 转轴变换Cxlx6x4z11-1/5-4/5-12/5x242/51/104/5x5111-1/210x351/53/102/5Z行非基变量的系数全部为负，迭代结束，最大值为11,最优解为(0,4,5,0,11,0)4. (10分)单源最短路径问题：在下图实例上指定源点为1,目标点为6,应用优先队列式分支限界法
11、找出1到6的最短路径。(要求写明优先级，画出搜索树，标出最短路径)解：优先级：当前结点所代表的最短路径长度，长度越小，优先级越高搜索树：!-1 21 413 5 / 1 /2飞 5464513172920广116 Q62818五、算法设计（共13分）：说明：任意选择所使用的算法策略。要求：说明所使用的算法策略；写出算法实现的主耍步骤；题目：n后问题策略1：回溯法（定义解的结构，确定解空间树，确定约束函数，深度优先方式搜索，判断 当前是否到叶子节点，若到了叶子节点，则找到了一种着色方案，将其方案输出，并将方案 个数加1,若是中间节点，判断是否满足约束条件，若满足，则深一步搜索，否则剪枝。）策略2
12、：分支限界法（定义解的结构，确定解空间树，确定约束函数，以广度优先方式搜索, 判断当前是否到叶子节点，若到了叶子节点，则找到了一种放置方案，方案个数累加1,并且输出对应的方案，若是中间节点，判断有没有合适的放置位置，若有，则扩展该节点，将其可行的孩子节点加入到活节点表中，若没有，则从活节点表中取下一个活节点）简答题：1操作系统是算法吗？请说说算法和程序的区别。答：不是。算法是满足下述性质的指令序列：（1）输入：有零个或多个外部量作为算法的输入。（2）输汕：算法产生至少一个量作为输出。（3）确定性：组成算法的每条指令清晰、无歧义。（4）有限性：算法中每条指令的执行次数有限，执行每条指令的吋间也有
13、限程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质即有限性。2、插入排序、合并排序和快速排序这三种算法，哪几种使用了分治策略？请简述之。 答：合并排序和快速排序使用了分治的策略。合并排序：对要排序的数组Alow.high,令mid=（low+high）/2,用Amid把原数组 Alow.high分成两个子数组，然后对两个子数组进行排序，在合并两个已牌子徐的子数组, 产生排序数组。快速排序：对要排序的数组Alow.high,先使用算法SPLIT重新排列元素，使得原先在 Alow中的祝愿占据其正确的位置Aw,并且所有小于或等于Aw的元素所处的位置为 Alow.w-1,而所有大于Aw的元素所处的位置是Aw+l.higho在对子数组Alow.w-1 和Aw+l.high递归地排序，产生整个排序数组。归并排序要好于插入排序，插入排序要好于冒泡排序。3. 分治法适合求解的问题一般具有那些特征？分治法可分为哪三个主要步骤？ 答：适合分治法求解的问题一般具有以下特征：(1) 问题的规模缩小到一定程度就可以容易地解决(2) 问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
