武汉大学算法设计复习提纲

第一章：1、 通俗地将，算法是指解决问题的一种方法或一个过程；更严格地将，算法是由若干条指令组成的有穷序列。

2、 算法满足4条性质：（1） 输入：有零个或者多个由外部提供的量作为算法的输入。

（2） 输出：算法产生至少一个量作为输出。

（3） 确定性：组成算法的每条指令是清晰的，无歧义的。

（4） 有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。

3、 程序是算法用某种程序设计语言的具体实现。

4、 程序可以是无穷的，算法必须是有穷的。

5、 算法的复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要空间资源的量称为空间复杂性。

6、 本书只考虑三种情况下的时间复杂性，即最坏情况、最好情况和平均情况下的时间复杂性，并分别记为T max (N)、T main (N)和T avg (N)。

在数学上有：),(),(),(max ),(max (N)T **11max I N T I N e t I N e t I N T k i i i k i i i D I D I N N ====∑∑==∈∈),(),(),(min ),(max )(~1~1max I N T I N e t I N e t I N T N T k i i i k i i i D I D I N N ====∑∑==∈∈ ∑∑∑∈=∈==N N D I k i i i D I avg I N e t I P I N T I P N T ),()(),()()(17、 一般来说，当N 单调增大且趋于∞时，T(N)也将单调增大且趋于∞，对于T(N)，如果存在)(~~N T ，使得当∞→N 时有0)(/))()((~~→-N T N T N T ，那么，就是说)(~~N T 为算法A 当∞→N 的渐进复杂性，而与T(N)相区别。

07log 437log 4)(/))(~)((2→+++=-N N N N N N T N T N T 8、 以下设)(N f 和)(N g 是定义在正数集上的正函数。

二、算法与程序设计模块1.利用计算机解决问题的基本过程（1）利用计算机解决问题的基本过程（P3）①分析问题②设计算法③编写程序④调试程序（2）算法的基本特征（P9）①输入（0个或多个）②确定性（算法的每一步都必须要确切地定义）③有穷性（一个算法在执行有穷步之后必须结束）④输出（算法有一个或多个输出）⑤能行性（算法中有待执行的运算和操作必须是相当基本的）（3）算法描述（P10）表示描述算法的语言主要有：自然语言、流程图、伪代码等。

自然语言描述算法的优缺点：优点：通俗易懂缺点：具有歧义性、自然语言语句较长、难以清晰地表示循环与分支较多的算法、不便翻译成计算机程序设计语言流程图：开始/结束框输入/输出框处理框判断框流程线连接点（4）计算机程序的基本概念及执行的基本过程（P14）计算机程序是一组机器操作的指令或语句的序列，是算法的一种描述程序执行的基本过程：除非特殊声明，程序都从第一条语句开始顺序执行；有时语句要求执行者做出判定，即在某种条件成立的情况下执行一条或一组语句，否则执行另一条或另一组语句；一条或一组语句可能需要重复执行多次（循环体）。

程序的三种基本结构：顺序结构、选择结构、循环结构（5）程序设计语言产生与发展过程（P18）程序设计语言的发展历程：①机器语言（0、1代码）②汇编语言（带有助记符）③高级语言常见的高级语言：Fortran、Basic、C、C++、Pascal、JAVA（6）程序的编译与解释的过程（P20）程序的翻译：计算机程序转为机器语言程序（计算机只能识别和执行机器语言代码）程序的翻译有两种类型：编译程序（高级语言程序执行前翻译成等效的机器语言程序，然后再执行）解释程序（翻译一句，执行一句）2.程序设计语言初步（1）程序设计语言的基本概念程序设计语言是指人们编制程序时所使用的计算机语言（2）整型、字符型、实型和逻辑型等基本数据类型(P27)数据：描述客观事物的数、字符以及所有能输入到计算机中，并被计算机程序加工处理的符号的集合。

《算法与程序设计》复习提纲以问题解决为主线复习用计算机解决问题的一般过程：分析问题——设计算法——编写程序——运行程序、验证结果一、分析问题二、设计算法（一）算法的概念：算法是解决问题的方法和步骤算法的特征：输入、确定性、有穷性、输出、能行性（二）算法的描述方法：1算法的描述：可分多种表达方法，一般用自然语言、流程图和伪代码进行描述。

2自然语言描述法：指用人们日常生活中使用的语言（本国语言），用自然语言描述符合我们的习惯，且容易理解。

3流程图描述：也称程序框图，它是算法的一种图形化表示方法。

且描述算法形象、直观，更易理解。

4伪代码描述法：是介于自然语言和计算机程序语言之间的一种算法描述。

是专业软件开发人员常用方法。

（三）程序设计语言发展过程机器语言：由一串“0”和“1”构成二进制代码。

汇编语言：是一种符号化（英文助记符）的机器语言。

高级语言：如Basic、C/C++、Fortran、Pascal、Cobol、Java等。

（四）程序设计与程序设计语言之间的关系：算法—解决某一问题而设计的确定的有限的步骤称为算法。

程序设计—寻求解决问题的方法，并将其实现步骤写成计算机可执行的程序的过程。

程序设计语言——泛指一切用于书写计算机程序的语言。

算法是程序设计的前提，它包含方法和步骤；程序是实现算法中的思想的过程；三、编写程序（一）界面设计：在VB窗口中添加控件（二）属性设置：控件的常用属性1面向对象的程序设计语言：其中的对象主要是系统设计好的对象，包括窗体等、控件等2控件：是指工具箱中的工具在窗体中画出的、能实现一定功能的部件，如文本框，命令按钮等。

对象属性＝属性值对象中属性可以在设计界面时通过属性窗中设置，也可以在运行时通过程序代码设置,方法如下例：给文本框“Txt123”的“Text”属性赋值为字符串“20”，代码如下Txt123.text =”20”变量＝对象.属性如果要获取对象的状态或特性，这时就要读取对象的属性值，方法如下例：读取文本框“txt123”的“Text”属性的代码如下a = txt123.text2方法［对象］.方法［参数名表］例：form.print ”欢迎使用”该语句使用print方法在form1窗体中显示字符串“欢迎使用”（三）编写代码：3事件及事件驱动事件是对象对外部操作的响应，如在程序执行时，单击命令按钮会产生一个Click事件。

算法设计与分析复习要点一、单项选择题（本大题共15小题，每小题2分，共30分）二、填空题（本大题共15空，每空1分，共15分）三、分析题（本大题共5小题，每小题5分，共25分）四、综合题（本大题共4小题，1、2题每题6分，3题8分，4题10分，共30分）第2章，导引与基本数据结构：1、什么是算法, 算法的5个特性；对一个算法作出全面分析的两个阶段。

P245个特性：确定性、能行性、输入、输出、有穷性两个阶段：事前分析、事后测试2、O(g(n))，Ω(g(n))， (g(n))的含义。

3、多项式时间算法：可用多项式（函数）对其计算时间限界的算法。

4、常见的多项式限界函数所表示算法时间复杂度的排序：Ο(1) <Ο(logn) < Ο(n) < Ο(nlogn) < Ο(n2) < Ο(n3)5、指数时间算法：计算时间用指数函数限界的算法6、常见的指数时间限界函数：Ο(2n) < Ο(n！) < Ο(n n)11()2(1)11()21nn T n T n n T n =⎧=⎨-+>⎩⇒=-7、什么是算法的复杂性：是该算法所需要的计算机资源的多少，它包括时间和空间资源。

8、复习栈和队列、树、图的基本知识，了解二元树、完全二元树，满二元树、二分检索树、了解图的邻接矩阵和邻接表存储方法。

9、能写出图的深度优先序列和广度优先序列。

10、会求如下一些简单的函数的上界表达式： 3n 2+10n =O(n 2)第3、4章 递归与分治算法1、理解递归算法的优缺点，深刻理解递归算法的执行过程。

如能写出解决n 阶汉诺塔问题的解，并能分析写出3阶汉诺塔问题的递归执行轨迹。

2、递归算法的优点：结构清晰，可读性强，容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。

3、递归算法的缺点：运行效率较低，耗费的计算时间和占用的存储空间都多。

为了达到此目的，根据具体程序的特点对递归调用工作栈进行简化，尽量减少栈操作，压缩栈存储空间以达到节省计算时间和存储空间的目的。

高一年算法与程序复习提纲一、基础知识1．算法算法是用计算机求解某一问题的方法和步骤，是能被机械地执行的动作或指令的有穷集合，是程序设计的核心。

用计算机解决问题的基本步骤流程图。

（1）分析问题可以采用建立数学模型的方式使问题变得更加明确、更容易理解。

（2）算法就是解决问题的方法和步骤,解决一个问题的算法可能不只一种。

（3）编写程序就是用计算机能接受的程序设计语言来描述问题求解的算法(实现算法)。

（4）调试程序的目的是查找和改正程序中存在的错误，使程序能顺利地执行，得出正确的结果。

程序调试的首要任务是查错。

程序错误一般分为编译错误、执行错误和逻辑错误。

2．算法的描述自然语言、流程图、伪代码用流程图描述算法：3．算法的特征（1）输入：一个算法有0个或多个输入。

（2）确定性：算法的每个步骤必须要确切地定义，不能有二义性。

（3）有穷性：一个算法在执行有穷步之后必须结束。

（4）输出：算法有一个或多个的输出。

开始和结束输入和输出计算或处理判断流程线连接点（5）能行性：算法中的每一个步骤都是能精确进行的，即根据算法中的每一个步骤进行操作，就可得到预期的结果。

4．程序的三种基本结构 （1）顺序结构（2）选择结构（分支结构） （3）循环结构5．程序设计语言的发展 （1）机器语言直接用二进制代码指令表达的计算机语言，指令是用0和1组成的一串代码，计算机只能直接执行机器语言的程序。

（2）汇编语言符号式的机器语言，用汇编语言编写的程序比用机器语言写的程序容易阅读、调试及修改，并且需要经过转换（称为汇编）后形成计算机可以直接执行的机器语言。

（3）高级语言计算机无法直接执行高级语言程序，必须将高级语言写的程序翻译成机器语言程序才能由计算机执行。

翻译的方法有编译和解释两种。

编译是将整个程序翻译成机器语言后执行，而解释是翻译一句执行一句。

如:VB 、Fortran 、Algol 、Cobol 、Basic 、Pascal 、C 、C++、Prolog 、Lisp 、Java 等。

第一章算法概述1、时间复杂度的元运算有那些？答：算数运算（+ - * /）、关系运算(< = >)、逻辑运算(^ v !)2、时间复杂度的本质是什么？3、答：在一定规模的输入（或数据）下，算法进行元运算的次数。

如：T(n)=8n表示规模为n时，元运算进行8n次第二章递归与分治策略1、整数划分解：设对整数n,其最大划分数不大于m的划分方式有q(n,m)种。

当m<1或n<1时，q(n,m)=0;(容错)当m=1时，q(n,m)=1;当n=1时，q(n,m)=1;当m>n>1时，q(n,m)=q(n,n);当n=m>1时，q(n,m)=q(n,n-1)+1;当n>m>1时，q(n,m)=q(n,m-1)+q(n-m,m);于是q(n,m)= { 0 ,m<1||n<11 , m=1||n=1q(n,n-1)+1 ,m>n>1;q(n,m-1)+q(n-m,m) ,n>m>1}按上式不断递归可得解。

2、汉诺塔答：设子问题为hanio(n,c,d,a),其中n代表当前要移动的盘子总数，c表示当前盘子所在的杆，d表示当前盘子要移动到的杆，a表示移动盘子时借用的杆。

当n<1时，hanio(n,c,d,a)什么也不干；当n>0时，hanio(n,c,d,a)={hanio(n-1,c,a,d);把c上的那个盘子移到d;hanio(n-1,a,d,c);}按照以上方式不断迭代，即可解出。

3、二分搜索答：描述：在a[0]~a[n-1]这n个数中查找x.子问题：search(p,q),在a[p]~a[q]这q-p+1个数中查找x.原问题等价于search(0,n-1).算法步骤1)p=0,q=n-1;2)如果p>q,,返回未找到3)m=(p+q)/23.1）如果a[m]等于x,返回m;3.2)如果a[m]>x,p=m+1,从2）开始重新执行3.3)如果a[m]<x,q=m-1,从2)开始重新执行4、快速排序答：问题描述：将a[0:n-1]进行快速排序。

内部资料，转载请注明出处，谢谢合作。

考试题型一,问答题(16%)二,算法填空题(24%)三,运算题(20%)四,证明题(10%)五,算法设计题(30%)考试样题一,问答题(每小题8 分,共16 分)1. 什么是算法算法有哪几个特性2. 动态规划算法的基本思想是什么它和分治法有什么区别和联系3. 用动态规划算法求解问题的基本步骤有那些考试样题二,算法填空题(每小题12 分,共24 分)1.阅读下面的算法,在答题处填充所缺的语句:Void Knapsack(int n,float M,float v[],float w[],float x[]){Sort(n,v,w);int i;for(i=1;i<=n;i++) x[i]=0;float c=M;for(i=1;i<=n;i++){if( (1)) break;x[i]=1;(2) ;}if(ic(2) c-=w[i](3) x[i]=c/w[i]考试样题三,运算题(每小题10 分,共20 分)在矩阵连乘问题中,采用课本标准的动态规划算法,已知s[i,j]的值如下图所示,写出调用Traceback(1,6,s)后输出的最优次序.答案:最优计算次序为: ((A1(A2A3 ))((A4 A5)A6 ))考试样题四,证明题(每小题10 分,共10 分)证明装载问题具有贪心选择性质.参考答案:证明:设集装箱已依其重量从小到大排序, (x1,x2, …,xn)是最优装载问题的一个最优解.又设1.当k=1时, (x1,x2, …,xn)是一个满足贪心选择性质的最优解.2.当k>1时,取y1=1;yk=0;yi=xi,1<I≤N,I≠K因此,(y1,y2, …,yn)是所给最优装载问题的一个可行解另一方面,由(y1,y2, …,yn)是一个满足贪心选择性质的最优解所以,最优装载问题具有贪心选择性质考试样题五,算法设计题(每小题15 分,共30 分)1. 给定已排好序的n个元素a[0:n-1],现要在这n个元素中找出一特定的元素x,要求时间复杂度为O(logn).int BinarySearch(Type a[],const Type & x,int n)int BinarySearch(Type a[],const Type & x,int n){int left=0; int right=n-1;while(lefta[middle]) left=middle+1;else right=middle-1;}return -1;}第一章算法一.算法的概念与性质1）算法的特性和基本概念算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。

算法复习提纲题型及分数分布：1．填空题15分2．简答题、证明题25分左右3．计算题2-3题30分左右4．算法设计题2-3题30分左右复习提纲一、算法基础1. 什么是算法？2. 算法的五个重要特性3. 运算的分类：时间囿界于常数的运算、时间非囿界于常数的运算，为什么要定义时间囿界于常数的运算？怎么分析时间非囿界于常数的运算？4．什么是事前分析和事后测试？各阶段的目标和特点是什么？5．什么是函数表达式的数量级？数量级的大小怎么反应了算法复杂度的高低？6．什么是限界函数？怎么得来的？7．限界函数：上界函数、下界函数、“均值”函数的定义和性质8．理解定理1.2，P76定理9．掌握数学归纳法、反证法、反例法等证明方法二、递归与递归式1．什么是递归和递归程序设计？2．递归的结构是什么？3．什么是直接递归和间接递归？4．递归程序有哪些效率问题？各自的原因是什么？5．怎么消去递归（不要求）6．什么是代换法、递归树法、主方法？（例题、习题）三、分治法1．简述分治法的基本思想？分治法分解问题的基本要求是什么？为什么说分治与递归像一对孪生兄弟？2．可用分治法求解的问题应具有的特征？（了解）3．分治法求解的三个步骤。

4．二分检索（3.2节）1）了解算法2）重点掌握算法复杂度的分析技术（1）对成功和不成功检索情况的讨论（2）什么是二元比较树？内结点、外结点分别代表了什么？比较次数和结点在树中的级数（或根到结点的路径长度）之间的关系。

3）定理3.1及其证明过程和结论4）什么叫做以比较为基础的检索？其下界是什么？（了解）5）为什么说二分检索是解决检索问题的最优的最坏情况算法？5．找最大和最小元素（3.3节）：一般了解，理解递归程序的效率问题6．基于分治的分类算法（3.4节）：回顾数据结构相关知识，知道每种分类算法的基本思想、算法复杂度、适用性等方面的性质（不考算法，考应用）1）P46：以关键字比较为基础的分类算法的时间下界是什么？怎么证明的？（了解）2）P60：一个改进了的快速分类迭代算法模型，其空间复杂度为O(logn)是怎么得来的？7．选择问题（3.5节）1）了解基于partition 的选择算法设计思想、最坏、平均时间复杂度的结论和证明。

《算法设计与分析》复习提纲2021.1.4 1 引言(ch1)1.什么是算法及其特征2.问题实例和问题规模2 算法初步(ch2)1.插入排序算法2.算法复杂性及其度量(1)时间复杂性和空间复杂性；(2)最坏、最好和平均情形复杂性；3.插入排序的最坏、最好和平均时间4.归并排序算法及其时间复杂性3函数增长率(ch3)1.渐近记号O、Ω、θ的定义及其使用2.标准复杂性函数及其大小关系3.和式界的证明方法4 递归关系式(ch4，Sch1)1.替换法(1)猜测解 数学归纳法证明；(2)变量变换法；2.迭代法(1)展开法；(2)递归树法；3.主定理4.补充1：递归与分治法(sch1)- 递归设计技术- 递归程序的非递归化- 算法设计(1)Fibonacci数；(2)生成全排列；(3)二分查找；(4)大整数乘法；(5)Stranssen矩阵乘法；(6)导线和开关(略)；5 堆排序(ch6)1堆的概念和存储结构2.堆的性质和种类3.堆的操作：建堆；整堆；4.堆排序算法和时间复杂性5.优先队列及其维护操作6 快速排序(ch7)1.快速排序算法及其最好、最坏时间和平均时间2.随机快速排序算法及其期望时间3.Partition算法7 线性时间排序(ch8)1.基于比较的排序算法下界：Ω(nlogn)2.计数排序适应的排序对象、算法和时间3.基数排序适应的排序对象、算法和时间4.桶排序适应的排序对象、算法和时间8 中位数和顺序统计(ch9)1.最大和最小值的求解方法2.期望时间为线性的选择算法3.最坏时间为线性的选择算法及其时间分析9 红黑树(ch13)1.红黑树的定义和节点结构2.黑高概念3.一棵n个内点的红黑树的高度至多是2log(n+1)4.左旋算法5.插入算法的时间、至多使用2次旋转6.删除算法的时间、至多使用3次旋转10 数据结构的扩张(ch14)1.动态顺序统计：扩展红黑树，支持①选择问题(给定Rank求相应的元素)，②Rank问题(求元素x在集合中的Rank)(1)节点结构的扩展；(2)选择问题的算法；(3)Rank问题的算法；(4)维护树的成本分析；2.如何扩张一个数据结构：扩张的步骤；扩张红黑树的定理(略)；3.区间树的扩张和查找算法11 动态规划(ch15)1.方法的基本思想和基本步骤2.动态规划和分治法求解问题的区别3.最优性原理及其问题满足最优性原理的证明方法4.算法设计(1)多段图规划；(2)矩阵链乘法；(3)最大子段和；(4)最长公共子序列；12 贪心算法(ch16)1.方法的基本思想和基本步骤2.贪心算法的正确性保证：满足贪心选择性质3.贪心算法与动态规划的比较4.两种背包问题的最优性分析：最优子结构性质和贪心选择性质5.算法设计(1)小数背包；(2)活动安排；(3)找钱问题；13 回溯法(sch2)1.方法的基本思想和基本步骤2.回溯法是一种深度遍历的搜索3.术语: 三种搜索空间, 活结点, 死结点, 扩展结点, 开始结点, 终端结点4.两种解空间树和相应的算法框架5.算法设计(1)图和树的遍历；(2)n后问题；(3)0-1背包；(4)排列生成问题；(5)TSP问题；14 平摊分析(ch17)1.平摊分析方法的作用和三种平摊分析方法各自特点2.聚集分析法及应用3.记账分析法及应用4.势能法及应用15 二项堆(ch19 in textbook version 2)1.为什么需要二项堆？二项堆和二叉堆上的几个基本操作时间复杂性2.二项堆定义和存储结构3.二项堆上合并操作及过程4.二项堆应用（尤其是在哪些图论算法上有应用）16 不相交集数据结构(ch21)1.不相交数据集概念2.两种实现方式：链表表示和森林表示3.两种表示具体实现和其上操作的时间复杂性4.不相交集数据结构应用（尤其是在哪些图论算法上有应用）17 图论算法(ch22-ch25)1.BFS和DFS算法- 白色、灰色和黑色结点概念和作用- 计算过程及其时间复杂度2.最小生成树- 安全边概念和一般算法（Generic algorithm）- Kruskal算法和Prim算法的计算过程和计算复杂性- 两种贪心算法的贪心策略和贪心选择性质3.单源最短路径（略）- 单源最短路径δ(s, v)和短路径上界d[v]概念- 边松弛技术及其一些性质- 三种问题算法的计算过程及其时间复杂度：Bellman-Ford算法、DAG算法和Dijkstra算法4. 所有点对最短路径（略）- 为什么能转换为矩阵乘法？- 基于矩阵乘法的较慢和快速算法的时间复杂度- Floyd-Warshall Algorithm的思路和时间复杂度- Johnson Algorithm适应的问题及其时间复杂度（略）18 数论算法(ch31)1.gcd(a, b)及其表示成a, b线性组合方法2.Euclid’s Alg.的运行时间3.线性模方程的求解方法4.中国余数定理及其相应线性同余方程组的求解5.RSA算法过程及正确性基础6.简单素数测试算法和伪素数测试算法7.MR算法的改进措施和算法复杂性19 串匹配(ch32)1.朴素的串匹配算法及其时间复杂度2.Rabin-Karp串匹配算法及其时间复杂度3.有限自动机串匹配算法及其及其时间复杂度4.KMP串匹配算法及其时间复杂度20 模型和NPC(ch34)1.算法的严格定义2.几种计算模型的语言识别能力3.两类图灵机模型4.P问题、NP问题和NP完全问题的定义及P归约。

算法分析与设计复习大纲第1章绪论考点：1、算法的5个重要特性。

答：输入、输出、有穷性、确定性、可行性2、掌握扩展递归技术和通用分治递推式的使用。

扩展递归技术：通用分支递归式：5、使用扩展递归技术求解下列递推关系式（1）（2）第3章蛮力法1、掌握蛮力法的设计思想：蛮力法依赖的基本技术——扫描技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解;关键——依次处理所有元素。

2、蛮力法的代表算法及其时间复杂度：顺序查找，O(n)串匹配（BF O(n*m)，KMP O(n+m)选择排序，O(n2)冒泡排序，O(n2)生成排列对象（排列问题），O(n!)生成子集（组合问题），O(2n)0/1背包属于组合问题。

任务分配，哈密顿回路，TSP问题属于排列问题。

3、掌握BF和KMP算法的原理，能够画出比较过程。

要求给出一串字符串，能够求出对应的next数组，并能使用KMP算法进行比较匹配。

4、掌握选择排序和冒泡排序算法描述和时间复杂性，要求能够写出伪代码。

选择排序算法描述：选择排序开始的时候，扫描整个序列，找到整个序列的最小记录和序列中的第一记录交换，从而将最小记录放到它在有序区的最终位置上，然后再从第二个记录开始扫描序列，找到n-1个序列中的最小记录，再和第二个记录交换位置。

一般地，第i趟排序从第i个记录开始扫描序列，在n-i+1个记录中找到关键码最小的记录，并和第i个记录交换作为有序序列的第i个记录。

时间复杂性：O(n2)伪代码：冒泡排序算法描述：冒泡排序开始的时候扫描整个序列，在扫描过程中两两比较相邻记录，如果反序则交换，最终，最大记录就能被“沉到”了序列的最后一个位置，第二趟扫描将第二大记录“沉到”了倒数第二个位置，重复上述操作，直到n-1趟扫描后，整个序列就排好序了。

冒泡排序，O(n2)5、算法设计题：假设在文本“ababcabccabccacbab”中查找模式“abccac”,求分别采用BF算法和KMP算法进行串匹配过程中的字符比较次数。

算法和算法的表示1．使用计算机解决问题的一般过程——分析问题；寻找解决途径和方法；用计算机进行处理2．算法的特征（1）有穷性。

一个算法必须保证它的执行步骤是有限的，即它是能终止的。

（2）确定性。

既算法中的每个步骤必须有确切的含义。

（3）可执行性。

算法中的每个步骤都要实践能做的，而且能在有限的时间内完成。

（4）有0个或多个输入。

（5）有一个或多个输出。

3．算法的表示方法（1）自然语言就像写文章时所列的提纲一样，有序地用简洁的语言加数学符号来描述。

（如：课本10页）（2）流程图（Flowchart）常用的流程图构件有：（3）程序（4）伪代码——结构清晰、代码简单、可读性好，并且类似自然语言。

介于自然语言与编程语言之间。

（如：课本11页最上方），下面是一段伪代码：If △<0 Then无解Else有解End If五、VB程序设计初步1．对象、属性、类、事件和事件处理的概念[此部分复习以记忆为主]（1）对象是客观存在的事物或概念。

它有两个特点：状态和行为。

（2）一个对象的状态是通过若干个属性（property）来描述的；行为是指对属性进行操作和处理的方法（method）。

在面向对象的程序设计中，一个对象是由一组对象状态的数据和一组描述处理对象属性的方法的代码构成的。

对象的属性定义其外观，方法定义其行为，事件定义其与用户的交互。

（3）类（class）是对相同性质的对象的一种抽象，而一个对象则是类的一个“实例”。

（4）事件（event）就是发生在对象上的事情，通常是由用户在对象上激发的一种动作。

一个事件的发生，可以引起某个对象上某个方法（事件处理过程）的执行，即由某个事件驱动了相应的事件处理过程的执行。

这就是面向对象程序设计中的事件驱动概念。

例：对象名为Command1，Click为应用于对象Command1上的事件Private Sub Command1_Click()Print (S)End SubCommand1.Caption = "中华" 对象名为Command1，Caption为属性，“中华”为属性值List1.AddItem (Str(y(m))) 对象名为List1，AddItem为方法，Str(y(m))为添加进去的条目******点（.）前面的都是对象名，点（.）后面的可以属性也可以方法，区别在于——属性是相对“静态”的特征，而方法则是有“动作”的VB应用程序的界面设计与调试——重点认清工具箱中的各控件名字及用途习题：在Visual Basic工程设计中，要在文本框Text1中显示“你好”，则下列操作正确的是(A)在Text属性名中输入“你好”(B)在Caption属性名中输入“你好”(C)在Font属性名中输入“你好”(D)在Name属性名中输入“你好”答案：A习题：在Visual Basic工程设计中，要在标签中显示“你好”，则下列操作正确的是(A)在Text属性名中输入“你好”(B)在Caption属性名中输入“你好”(C)在Font属性名中输入“你好” (D)在Name属性名中输入“你好”答案：B习题：在Visual Basic工程设计中，下列控制哪个不能加载图片(A)TextBox (B)Image (C)PictureBox (D)CommandButton 答案：A习题『会考2010』:在Visual Basic中，如果要在命令按钮Cmd1上显示文字"开始"，下列语句正确的是(A)Cmd1.Caption ="开始" (B)Cmd1.Width ="开始"(C)Cmd1.Font ="开始" (D)Cmd1.Height ="开始" 答案：A习题『会考2010』:在Visual Basic中，语句Soft.Text="QQ2008"中的Soft是(A)属性名(B)属性值(C)对象名(D)软件名答案：c习题『会考2010』:在Visual Basic中，鼠标单击命令按钮Command1触发的事件处理过程名是(A)Command1_Click (B)Command1.Click (C)Click_Command1 (D)Command1Click 答案：A习题『会考2010』:在Visual Basic中，语句Label3.Caption="How Are You"中的Label3是(A)属性名(B)属性值(C)对象名(D)类名答案：C填空：窗体文件扩展名：.frm 工程文件扩展名：.vbp2．基本运算与表达式（1）VB的基本运算：VB的基本运算包括算术运算、关系运算和逻辑运算三大类。

一、题型
选择、填空、简答、求解题、算法设计
二、复习重点
1.算法的定义及特性
2.算法与程序的区别
3.算法复杂性的概念
4.渐进复杂性态
5.递归的概念及必需具备的两个条件
6.贪心法的思想及基本要素
7.哈夫曼编码的算法思想、给定一个字符集，按照算法思想构造一棵哈夫曼树、给出每个
字符的哈夫曼编码
8.最小生成树的两种算法思想、给定一个带权图，根据算法思想按照步骤构造一棵最小生
成树。

9.分治法的思想、特征，快速排序、合并排序算法思想、根据思想，完成将给定的待排序
元素排序。

10.动态规划的思想及要素，动态规划的步骤，最长公共子序列问题、0-1背包问题
11.回溯法的框架及思想、分支限界法的思想，分支限界法与回溯法的区别，0-1背包问题、
旅行售货员问题、图的m着色问题。

按照回溯法的框架，能够解决一个给定的具体问题（要求说明解的形式、分量的取值、解空间树、搜索的约束条件和限界条件、画出搜索树）。

12.随机化算法的类型及特点、素数测试算法、随机快速排序
13.一般线性规划转化成标准线性规划的方法、能够认识线性规划的约束标准性、网络流的
基本概念、给定一个网络及其上的可行流，能够画出对应的残余网络。

能够用增广路算法找出网络的最大流。

期末考试题型：1 判断题（10题，10分）2 填空题（5题，10分）3 简答题（4题，20分）4 应用题（5题，60分）期末考试复习要点：1 基本概念算法：有限条指令的序列，确定了解决某个问题的运算或操作顺序（了解概念）算法的时间复杂度（了解概念）函数渐进的界O ΩΘo ω有关函数渐进的界的定理（定理1、定理2）（记住、理解）主定理（会使用主定理求解递推方程）分治法相关：分治策略:适用条件:算法的设计步骤:时间复杂度：列出关于时间复杂度函数的递推方程和初值，求解递推方程提高分治算法效率的途径：动态规划算法相关：分治策略:适用条件:算法的设计步骤:时间复杂度：（备忘录的计算工作量）贪心法：贪心法:适用条件:算法的设计步骤:贪心法正确性的证明（第一归纳法、第二归纳法）回溯与分支界限：解空间：回溯算法：分支限界算法：代价函数：界函数：多米诺性质：NP完全性问题：P问题、NP问题、NP hard问题、NPC问题2 几个重要的算法二分检索红黑树插入排序二分归并排序：快速排序堆排序PrimKruskalBellman-FordFloyd-WarshallDijkstra3 几个重要的问题背包问题选最大最小问题第K小问题最长公共子序列问题最优二叉检索树矩阵链乘法问题活动选择问题Huffman编码最小生成树连续邮资问题4 求解递推方程（公式法、迭代法、递归树、主定理）：T (n )=T (n −1)+n 2T (n )=9T (n 3)+n T (n )=T (n 2)+T (n 4)+cn c 是常数 T (n )=3T (n −1)+lg3nT (n )=5T (n 2)+(nlgn )2 T (n )=2T (n 2)+n 2lgn T (n )=T (n −1)+1nT (n )=2T (n 3)+nlgn T (n )=3T (n 5)+lg 2n T (n )=T (n 2)+2n T (n )=T(√n)+θ(lglgn )T (n )=10T (n 3)+17n 1.2 T (n )=7T (n 2)+n 3 T (n )=T (n 2+√n)+√6046 T (n )=T (n −2)+lgnT (n )=T (n 5)+T (4n 5)+θ(n ) T (n )=√nT(√n)+100n。

一、查找二叉树1、什么是二分查找树？它是二叉树，具有左子树中的每个节点值都小于根节点值，右子树中的每个节点值都大于根节点值的性质。

2、如何查找？(1)将该值与根结点进行比较，(2)若相等，则查找成功，结束查找；(3)若小于，则对左子树进行查找操作，回到步骤(1)；(4)若大于，则对右子树进行查找操作，回到步骤(1)；(5)不满足(2) (3) (4)的条件，则查找失败，结束查找。

3、如何插入？(1)将插入的值与根结点相比，如相等，则算法结束；若为空树，则直接插入；(2)若小于，且左子树不为空，则对左子树进行插入操作，回到步骤(1),若左子树为空，则直接插入，算法结束；(3)若大于，且右子树不为空，则对右子树进行插入操作，回到步骤(1),若右子树为空，则直接插入，算法结束。

二、堆1、什么是堆？它是一棵完全二叉树，且每棵树都满足根结点值小于子树中其他结点值的性质。

2、如何插入？（1）为插入的堆增加一个存储单元存放要插入的值；（2）将该值与其所在树的父亲结点比较；（3）若小于，则交换，回到步骤（2）；（4）若大于，则结束交换，插入成功。

3、陈述堆排序的算法？先将这序列构造成一个最小堆，然后从堆中逐次弹出根结点，则得到由小到大的序列。

4、堆中结点（堆的根结点）的删除？（根据堆的定义，根结点值小于其子结点的值）（1）将堆的最后一个叶子结点的值存放在堆的根结点（称交换了的叶子节点为该节点）；（2）将该节点与其子结点中较小的那个结点进行比较；（3）若该节点〉子结点，则交换，回到步骤（2）；（4）若该节点＜子结点，则结束交换，删除成功。

三、图1、图的表示?分为邻接矩阵和邻接表（老师给出一个图，要会写出它的相应表示）2、什么是拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从Vi到Vj 的路径，那么在排序中的Vj出现在Vi的后面。

3、陈述拓扑排序算法（1）根据图示，找出入度为0的顶点；（2）删除该顶点，并将由这个顶点所出射的箭头删去（即与其相连的顶点度数-1）,回到步骤（1）（直至图中没有前驱的顶点为止）。

算法与程序设计复习知识点算法与程序设计复习知识点一、数据结构1.数组1.1 一维数组1.1.1 定义和初始化1.1.2 访问和修改元素1.1.3 数组的长度和容量1.1.4 数组的扩容和缩容1.2 二维数组1.2.1 定义和初始化1.2.2 访问和修改元素1.2.3 数组的长度和容量1.2.4 数组的扩容和缩容2.链表2.1 单链表2.1.1 节点定义2.1.2 头节点和尾节点 2.1.3 插入节点2.1.4 删除节点2.2 双链表2.2.1 节点定义2.2.2 头节点和尾节点 2.2.3 插入节点2.2.4 删除节点3.栈和队列3.1 栈3.1.1 定义和基本操作 3.1.2 栈的应用3.2 队列3.2.1 定义和基本操作3.2.2 队列的应用4.树4.1 二叉树4.1.1 定义和基本操作4.1.2 先序遍历、中序遍历和后序遍历 4.2 二叉搜索树4.2.1 定义和基本操作4.2.2 查找、插入和删除节点4.3 平衡二叉树4.3.1 定义和基本操作4.3.2 平衡因子和旋转操作4.4 堆4.4.1 定义和基本操作4.4.2 堆排序二、常用算法1.排序算法1.1 冒泡排序1.2 插入排序1.3 选择排序1.4 快速排序1.5 归并排序1.6 堆排序1.7 计数排序1.8 桶排序1.9 基数排序2.查找算法2.1 顺序查找2.2 二分查找2.3 哈希查找2.4 平衡二叉搜索树查找2.5 B+树查找3.图算法3.1 图的表示和基本操作 3.2 深度优先搜索3.3 广度优先搜索3.4 最小树3.5 最短路径3.6 图的遍历4.动态规划算法4.1 背包问题4.2 最长公共子序列4.3 最短编辑距离4.4 最大子序列和三、程序设计1.编程语言1.1 C语言1.1.1 基本语法1.1.2 数据类型和变量 1.1.3 控制语句1.1.4 函数和指针1.2 C++语言1.2.1 基本语法1.2.2 类和对象1.2.3 继承和多态2.算法设计和分析2.1 时间复杂度和空间复杂度2.2 递归和迭代2.3 动态规划和贪心算法2.4 分治算法2.5 回溯算法附件：●示例代码●算法示意图法律名词及注释：1.著作权：对作品享有的权利，包括复制权、发行权、展览权等。

选择题 算法分析与设计》期末复习题算法必须具备输入、输出和（ A .可行性和安全性 丨 C.有穷性和安全性 丨 算法分析中，记号 O 表示（ B A.渐进下界 C. 非紧上界 假设某算法在输入规模为 完成概算法的时间为 t 秒。

现有另一台计算机，其运行速度为第一台的 么在这台新机器上用同一算法在 题方法：3*2A 门*64=3*2仪 A . n+8 C . n+7 设问题规模为T （N ）=2T （N/2）+N/2，用0表示的时间复杂度为（ A . O （logN ） C . 0（NlogN ） 直接或间接调用自身的算法称为（ A .贪心算法C.迭代算法Fibonacci 数列中，第A . 5， 89 C . 5， 144 在有 8 个顶点的凸多边形的三角剖分中，恰有 A . 6 条弦和 7 个三角形B C . 6 条弦和 6个三角形 D一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ A 重叠子问题B C.贪心选择性质D 下列哪个问题不用贪心法求解（ C A .哈夫曼编码问题 BC.最大团问题 D 下列算法中通常以自底向上的方式求解最优解的是（A .备忘录法 C.贪心法 下列算法中不能解决 A .贪心法C.回溯法 下列哪个问题可以用贪心算法求解（ B. 等 4 个特性。

．确定性和易读性 ．有穷性和确定性 ，记号Q 表示（A ） 渐进上界紧渐进界 D. n 时的计算时间为T （n ）=3*2M 。

在某台计算机上实现并64 倍，那 B ）解t 秒内能解输入规模为多大的问题？ ．n+6 ．n+5 N 时，某递归算法的时间复杂度记为 C ．O（N ） ．O （N2logN ） ）。

．递归算法 ．回溯法 4 个和第 11 个数分别是 B D3， 3， 89 144 B ．5 条弦和 ．5 条弦和 ）。

T(N) ， ）。

）。

6 个三角形 5 个三角形 ．最优子结构性质 ．定义最优解）。

．单源最短路径问题 ．最小生成树问题 B ）。