算法考试要点

1、题型:一、选择（2*8=16 分）二、填空（2*10=20 分）三、程序设计与分析题（2*9=18分）四、简答（4小题，共17分）五、综合题（4小题，共29分）范围:第一章算晶设计的步骤算法时间复杂度的分类算法的性质第二章递归与分治的基本思想、分治法解题的基本步骤及特征二分搜索、快速排序、大整数乘法第三章贪心法的定义贪心法的特点、基本要素及证明过程描述哈夫曼编码（前缀码）、迪杰斯特拉最短路径、活动安排第四章动态规划的基本思想、基本步骤投资问题、矩阵连乘问题、最长公共子序列第五章回溯法的基本思想及解题步骤0-1背包问题、八皇后问题、图的M着色第六章分支限界法与回溯法的比较常见的两种分支限界法（以

2、0-1背包问题为例）第一章算法的形式化表示算法是一个四元组(Q、I、。、f )Q是一个集合，表示计算的状态I是Q的一个子集，表示计算的输入。是Q的一个子集，表示计算的输出f是Q到它自身的一个映射，表示计算的规则算法设计的步骤问题求解(Problem Solving)算法时间复杂度的分类最坏情况下的时间复杂性 Tmax(n) = max T(I) size(I)=n 最好情况 F的时间复杂性 Tnun(n) = nun T(I) | size(I)=n E p(i)w)平均情况下的时间复杂性Tavg(n)=血心卜时间复杂性顺序：O(l) O(logn) O(n) O(n*10gii)O(n2)O

3、(n3). O(2n)O(3n). .O(n!)1、求下列函数的渐近表达式3112+lOn： n2/10+2n： 21+1/n： logn3； 101og3n答 n22n 1 logn n2、讨论O和0(2)的区别3、按照渐近阶从低到高的顺序排列以卜.表达式：4112； logn： 3n； 20n；2； 112/3； n!答 2 Logn n2/3 20n4n2 3n n!算法的性序输入：有0个或多个外部提供的量作为算法的输入。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令是清晰，无歧义的。有限性：算法的执行次数是有限的，执行每条指令的时间也是有限的。可行性:算法中的所有运算都是

4、基本的，原则上它们都能够精确地进行,而且进行有穷次即可完成。6.算法与程序的区别程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)有限性。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法 来实现。该子程序得到输出结果后便终止。第二章分治法的基本思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治 法解决一个问题可以分为“分”和“治”两个阶段，而且整个过程使用的是递归的思想。因此，通 常都是利用递归方式进行描述。分治法所能解决的问题一般具

5、有以下几个特征(适用条件)：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。分治法的基本步骤divide-aiid-conquer(P)(if (| P | = 1)(int m = (1+t)/2;if (x = am) return m;if (x am) i = m-1; else 1 = m+1;return -1;i最坏情况下的计算时间复杂性为O(logn)注：一个大问题分成两部分并舍弃一部分(相当

6、于分解成1个子问题)快速排序：适用于随机性很强的序列最好时间复杂度O(nlogn),最坏O(n2)大整数乘法丁, 、/。 =1T(n) = 1T(n)=o(nR3)=O(n*-59)是用分治法求解的。n = l . .T(ri) = nm +f (n / m，)n 1；=o分治法时间复杂度r()=。kT(n/m) + f(n)第三章贪心的性质：从问题初始状态出发，通过若干次贪心选择，得到一个最优解或近似最优解的一种解题策略局部最优不一定达到全局最优，只是一个启发式算法基本要素：最优子结构性质(全局最优包含局部最优)和贪心选择属性(局部最优达到全局最优)贪心选择性质-指所求问题的整体最优解可以通

7、过一系列局部最优的选择，即贪心选择来达到。与动 态规划算法的主要区别。最优子结构性质-当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。该 问题可用动态规划算法或贪心算法求解的关键特征。哈弗曼编码对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这 种编码称为前缀码地接斯科拉应用策略时间复杂度O(1F)活动安排templatevoid GreedySelector(int n, Type s, Type。, bool A)(Al=tme;intj=l;fbr (int i=2;i=fj) Ai=tnie;j=i; )else Ai=fal

8、se;时间复杂度O(n)证明贪心选择性质假设A=X1, X2, X3X11)是E=E1, E2, E3, En活动集合的最优解，E中活动按照结束时间非递减排序。如果X1=E1, A是以贪心选择开始的。如果XI ! =E1,假设B=E1, X2, X3Xn,又因为Fl=Fxl并旦A中个活动相容，则B中活动也是相容的，因此B是一个以贪心选择开始的最优解。最有子结构性质E，=E2, E3, EnA，=X2, X3Xn)假设A不是E 的最优解，B比A更优,那么 B5U(E1=B 优于 A，UE1=A,即B是一个更优解，与假设A为最优解矛盾。贪心选择次数由数学归纳法可以证明，因此贪心算法可以求得该问题的

9、最优解。例如，对右图中的有 向图，应用Dijkst珥 算法计算从源顶点1 到其它顶点间最短路 径的过程列在下页的 表中。Sudist2dist3dist4dist5初始110maxint3010011,2210GO3010021, 2, 44105030903IX L 4, 3)3105030604IX 2, 4, 3, 5)510503060第四章1 .动态规划基本思想：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，然后 从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解 得到的子问题往往不是相互独立的。基本步骤：1.找出最优解的

10、性质，并刻划其结构特征。2.递归地定义最优值。3.以自底向上的方式计 算出最优值。4.根据计算最优值时得到的信息，构造最优解。投资问题算法：Invest(m,n,fnm,gnni) for(j=0=mj+)( fllU=glU；dlU=j; )for(i=2;i=n;i+)for(j=0；j=mj+) fiE=O；for( k=0; kfiU) (fiU=s; diU=k;)具体方法：手写矩阵连乘void MatrixChainfint *p* int n int *m int *s)for (int i = 1： i = n; i+)= 0:for (int r = 2: r = n: r+

11、)for (int i = 1; i = n - r+1： i+) ( int j=i+r-1;A1A2A3A4A5A630 x3535x1515x55x1010 x2020 x25碱25 =m23 + m45 +-m(2K21 + plp2p5 = 0+25(X) + 35x15x20=13000二二 ： 2625 + 1000+ 35 x 5 x 20 = 7125a24 + jw(55 + AAA = 4375 + 0 + 35x10 x20 = 11375mij = mi+1D+pi.i*pi*p si。】=i；for (int k = i+1; k j: k+) (int t = m

12、ik + mk+1D + p if(t2023330?602W063TS303330200040450$000(0560e 0lcs(int i,int j,char x .int b)if (i =0 | j=0) return;if(bij=)(lcs(iljl,x,b);prmt(xi);else if (bij= t )lcs(i.lj,x,b) else lcs(ijl,x,b);时间复杂度0(112/ log n)最长公共子序列void LCSLength(mtni,iiitn, char *xhar*y, int*c, int*b)(1 for (inti= 1; i= m; i

13、+) ci0=0;2: for (inti= 1; i= n; i+) c0i=0;3: for (inti= 1; i= m; i+)4:for(mtj = l;j=cij-l)9: ( cij=ci-lj;io：bij=,r；11: else12: ( ci|j=cij-l;13：bij=L；第五章回溯法的基本思想扩展结点:一个正在产生儿子的结点称为扩展结点活结点:一个自身己生成但其儿子还没有全部生成的节点称做活结点死结点:一个所有儿子己经产生的结点称做死结点确定了解空间的组织结构后，回溯法就从开始结点(根节点)出发，以深度优先的方式搜索整个解空间。 这个开始结点就成为一个活结点，同时成为

14、当前的扩展结点。在当前的扩展结点处，搜索向纵深方 向移至一个新结点。这个结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结 点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时应往回移动(回溯)至最近的一个 活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索, 直至找到所要求的解或解空间中己无活结点时为止。基本步骤针对所给问题，定义问题的解空间；确定易于搜索的解空间结构；以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。0背包解向量：(xl,x2, . ,xn)显约束：Xie(o,i)y w.x. n)SU111+；for (mt i=l; i=n; i+)cout xi 1cout endl;elsefor (mt(Xt=l；if (Ok(t) Backtrack(t+1);bool Color: :Ok(int k)(/检查颜色可用性fbr (int j=l j=n;j+)if (ak U= 1=xk) return false;return true;第六章分支限界法与回溯法的比较求解目标：回溯法的求解目标是找出解