算法考试重点

1、心之所向，所向披靡算法考试重点1、 算法的概念答：算法是求解一类问题的任意一种特殊的方法。 较严格的说法是， 一个算法是对特定问题求解的一种描述，它是指令的有限序列。2、 算法具有的五个特征： （ 1）输入（ 2）输出（ 3）确定性（ 4）能行性（ 5）有穷性3、 问题求解过程（1）理解问题（ 2）设计方案（3）实现方案（ 4）回顾复查4、 系统生命周期：一个计算机程序的开发过程就是使用计算机求解问题的过程。软件工程将软件开发和维护分成若干段，称为系统生命周期。通常把软件生命周期划分为分析、设计、编码、测试和维护等五个阶段。5、 算法问题的求解过程： （1）理解问题 （ 2）选择求解方法确定数

2、据结构（ 3）设计算法 （ 4）正确性证明（ 5）分析算法（ 6）编写代码6、 递归定义是一种间接或直接引用自身的定义方法。一个合法的递归定义包括两部分基础情况和递归部分。7、 程序健壮性是指当输入不合法数据时，程序应能做适当处理而不至于引起严重后果。8、 影响程序运行时间的因素：（ 1）程序所依赖的算法（2）问题规模和输入数据·（ 3）计算机系统性能。9、 时间复杂度：一个算法的时间复杂度是指算法运行所需要的时间。10、最好、最坏和平均时间复杂度如果待查元素刚好是第一个元素，则所需的查找时间最短这就是算法的最好情况。如果待查元素师最后一个元素，则所需的查找时间最长，则是算法执行时间

3、的最坏情况。11 设函数f(n)和 g(n)是定义在非负整数集合上的正函数，如果存在两个正常数c 和 n0，使得当 n n0 时，有 f(n) cg(n)，则记做f(n) = O(g(n) ，称为大O 记号（ big Oh notation ）。O(g(n) = f(n) |存在正常数c 和 n0 使得对所有nn0 有： 0f(n)=O(g(n) 表示所有增长阶数不超过g(n) 的函数的集合。f(n)cg(n) g(n)的形式要比f(n) 简单。如f(n)=2n+3=O(n),称一个算法具有O(g(n) ，指n 足够大时， 运行时间不会超过g(n)的某个常数倍，g(n) 是上界。12设有函数

4、f(n)和 g(n) 是定义在非负整数集合上的正函数，如果存在两个正常数c 和 n0，使得当 nn0时，有 f(n) c g(n)，则记做 f(n) =(g(n) ，称为记号（ omega notation ）。(g(n) = f(n) | 存在正常数 c 和 n0 使得对所有 nn0 有： 0cg(n)f(n) 称一个算法具有(g(n) ，指 n 足够大时，运行时间至少需要g(n)的某个常数倍， g(n)是下界，可以认为是最小值。13设有函数 f(n) 和 g(n)是定义在非负整数集合上的正函数，如果存在正常数c1， c2 和 n0，使得当 n n0时，有 c1 g(n) f(n) c2g(

5、n)，则记做 f(n) =(g(n)，称为记号（ Thetanotation ）。14定义 2-4小 o 记号 f(n) = o(g(n) 当且仅当 f(n) = O(g(n) 且 f(n)(g(n)15渐近分析记号的若干性质(1）传递性：f(n)=(g(n)，f(n)= O(g(n) ，g(n)=(h(n)g(n)= O (h(n)f(n)=(h(n) ；f(n)= O (h(n) ；f(n)= (g(n) ， g(n)=(h(n)f(n)= (h(n) ；f(n)= o(g(n) ， g(n)= o(h(n)f(n)= o(h(n) ；（2）反身性：f(n)= (f(n) ； f(n)=

6、O(f(n) ； f(n)=(f(n).（3）对称性：f(n)= (g(n)g(n)=(f(n)（4）互对称性：f(n)= O(g(n)g(n)=(f(n)（5）算术运算：O(f(n)+O(g(n) = O(maxf(n),g(n)；O(f(n)+O(g(n) = O(f(n)+g(n)；O(f(n)*O(g(n) = O(f(n)*g(n)；O(cf(n) = O(f(n)；g(n)= O(f(n)O(f(n)+O(g(n) = O(f(n)16 最常见的多项式时间算法的渐近时间复杂度O(1) O(log n) O(n) O(nlog n) O(n2) O(n3)最常见的指数时间算法的渐近时

7、间复杂度O(2n) O(n！ ) O(nn)16 二叉搜索树是一棵二叉树，他要求的左子树上所有的结点的值都小于根节点，右子树上·所有节点的值都大于根节点。17 二叉平衡树：是一种平衡搜索树；即是任何结点的左子树和右子树高度最多相差 1 的二叉搜索树。 每次插入或删除后， 按规则重新平衡树形， 使之始终保持平衡， 限制树形的高度，避免退化。能保证性能，但增加了实现难度。18 自调节搜索树。在伸展树上，执行一个 m 次运算（搜索、插入、删除）序列，总的时间为 O(mlogn)具有良好的平均分摊代价。是平衡搜索树的很好替代结构。19 伸展树 : 一颗二叉搜索树 ,但要求每访问一个元素后 ,

8、将最新访问的元素移至二叉搜索树的根部 ,以保证经常被访问的元素靠近根节点，而较少访问的元素位于搜索树较低的层次上是自调整搜索树， 将一个元素移至根部的操作称为一次伸展 .一般情况下 ,一个元素被访问后 , 下一次还要访问它的机会比较大 .20 伸展节点的确定1.搜索成功的节点2.新插入的节点3.被删除节点的双亲4.若上述运算失败,则搜索过程中遇到的最后一个节点为伸展节点.21 搜索 : 一种通过系统地检查给定数据对象的每个结点,寻找一条从开始结点到答案结点的路径 ,最终输出问题解的求解方法.22 遍历 :要求系统地检查数据对象的每个结点.分为：树遍历和图遍历23 状态空间 :用于描述所求问题的

9、各种可能的情况。每一种情况对应状态空间的一个状态。分为：初始状态 代表搜索开始,目标（答案）状态 代表已求得问题的解24 问题的求解过程：从初始状态出发，以某种次序系统地检查状态空间的每一个状态，搜索答案状态的过程。问题的状态空间常用树或图表示,树或图中的一个结点代表问题的一个状态.穷举搜索 =盲目搜索 =无知搜索，把所有的状态逐个检查，直到找到解或者检查完。深度搜索和广度搜索都是无知搜索有知搜索已知的信息为指导，排除一部分状态空间。有时可能找不到解，比如指导搜索的信息是错误的，则会误入歧途。启发式搜索使用经验法则，边搜索边评估到达目标状态的剩余距离。24 广度优先搜索对于一个未检测结点,访问

10、完其全部后继结点后才访问其他未检测结点深度优先搜索 :如果一个算法一旦访问某个结点， 该结点成为未检测结点后， 便立即被算法检测，成为 E- 结点，而此时，原 E- 结点尚未检测完毕，仍处于检测状态，需要在以后适当时候才能继续检测，这种做法成为深度优先搜索25 活结点 未检测结点死结点 其后续结点已全部访问过26 分治法的设计思想是， 将一个难以直接解决的大问题， 分割成一些规模较小的相同问题，以便各个击破，分而治之。27 分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出

11、的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。28 将问题表示为：I=(n,a1, ,an,x)选取一个下标k，可得到三个子问题：I1=(k- 1,a1, ,ak-1,x)I2=(1,ak,x)I3=(n- k,ak+1, ,an,x)如果对所求解的问题（或子问题）所选的下标k 都是中间元素的下标，k=(n+1)/2 ，则由此产生的算法就是二分检索算法。29 int m=Divide(left, right);1.二分搜索是按照某种规则求分割点m,m 不一定取为left 与 right 的中点2. 如果每次都选择 left 与 rig

12、ht 的中点 ,则是对半搜索30 成功的检索共有n 种不成功的检索共有n+1 种31 二分检索的时间复杂度引理 2.2 ：若 n 在区域 2k-1,2k) 中，则对于一次成功的检索，二分检索至多作比较，至少作1 次比较；而对于一次不成功的检索，或者作k-1 次比较或者作比较。最坏情况下的成功检索计算时间 (logn)最坏情况下的不成功检索计算时间 (logn)最好情况下的成功检索计算时间 (1)最好情况下的不成功检索计算时间 (logn)k 次k 次每种不成功的检索时间都为 (logn)32 .分治法求解1.将待排序序列一分为二，得到两个长度基本一致的子序列。2.如果子序列较长，可继续再分，直

13、到序列长度不超过1，对两个子序列分别排序，3.当分解的子序列排好序后，使用merge 函数合并33 快速排序基本思想1. 在待排序序列 (K0,K1, ,Kn-1)中选择一个元素作为主元2.通过循环 ,将序列中所有元素依次与主元比较,并将比主元小的元素移到主元前面主元大的元素移到主元后面.(称为分划 ),比3. 一次分划后 ,使序列以主元为轴心 ,分成左右两个子序列 ,左侧子序列的元素都比主元小 ,右侧子序列的元素都比主元大 .4. 对两子序列按同样的方法继续排序.直至整个序列有序34. 改善快速排序性能的方法改进主元的选择方法子序列不必分解到只有一个元素才终止划分,对足够小的序列可以使用直接

14、插入法排序 .化递归算法为非递归算法35 算法思想简单描述：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换35冒泡排序是稳定的。算法时间复杂度O(n2)-n 的平方 36 贪心法求解?最优量度标准选择使得迄今为止已入选S 中边的代价之和增量最小的边普里姆 (Prim) 算法的贪心准则是：在保证 S 所代表的子图是一棵树的前提下选择一条最小代价的边e=(u,v)。克鲁斯卡尔 (Kruskal) 算法的贪心准则是：按边代价的非减次序考察E 中的边，

15、从中选择一条代价最小的边e=(u,v)。37 定理 66普里姆算法和克鲁斯卡尔算法都将产生一个带权无向连通图的最小代价生成树。38 迪杰斯特拉（Dijkstra ） 算法首先求得长度最短的一条最短路径，再求得长度次短的一条最短路径，依此类推，直到从源点到其它所有结点之间的最短路径都已求得为止。39 动态规划法利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，40 动态规划法的实质-也是将较大问题分解为较小的同类子问题这一点上它与分治法和贪心法类似。但动态规划法有自己的特点。分治法的子问题相互独立，相同的子问题被重复计算，动态规划法解决这种子问题重叠现象。 贪心法要求针对问题设

16、计最优量度标准， 但这在很多情况下并不容易。动态规划法利用最优子结构， 自底向上从子问题的最优解逐步构造出整个问题的最优解，动态规划则可以处理不具备贪心准则的问题。41 与贪心法的区别：贪心法每一步根据最优量度标准做出决策， 用于决策的贪心标准仅依赖于局部和以前的选择，不依赖尚未做出的选择和子问题的解。动态规划法每一步决策依赖子问题的解42 弗洛伊德算法弗洛伊德算法的基本思想是：令k=0,1,n-1，每次考察一个结点k 。二维数组d 用于保存各条最短路径的长度，其中， dij 存放从结点i 到结点 j 的最短路径的长度。在算法的第k步上应作出决策：从i 到 j 的最短路径上是否包含结点k。弗洛伊德算法的时间复杂度为O(n3)43 一组给定的作业的最优完成时间是F(S)的最小值。OFT 表示指非抢先调度最优完成时间POFT 表示抢先调度最优完成时间。OMFT表示非抢先调度最优平均完成时间，POMFT表示抢先调度最优平均完成时间。本节只讨论当m=2 时获得 OFT 的调度方案的算法， 这就是双机流水作业调度问题。44 Johnson 算法的时间取决于对作业集合的排序，因此，在最坏情况下算法的时间复杂度为 O(nlogn)，所需的空间复杂度为 O(n) 。初夏早