二级公共基础知识数据结构与算法.ppt

*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,二级公共基础知识数据结构与算法,二级公共基础知识数据结构与算法,考试形式,1,、公共基本知识部份只考选择题，没有操作题。,2,、公共基本知识占,10,分，共,10,道题，每题,1,分。,注意事项,公共基础知识部份的内容是属于计算机专业本科生的专业课，知识点特别散，而且有一定的难度。所以考生在学习的过程中，一定要克服畏难情绪，跟上老师的节奏。老师让记的，要记住。没做要求的，要学会放弃。,放弃该放弃的，选择轻装上阵,一、数据结构与算法,1.,算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。,2.,数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。,3.,线性表的定义；线性表的顺序存储结构及其插入与删除运算。,4.,栈和队列的定义；栈和队列的顺序存储结构及其基本运算。,5.,线性单链表、双向链表与循环链表的结构及其基本运算。,6.,树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。,7.,顺序查找与二分法查找算法；基本排序算法（交换类排序，插入类排序，选择类排序）。,1.1,算法,算法,(algorithm),基本概念,它是指令的有限序列，其中每一条指令表示一个或多个操作。,对解题方案准确而完整的描述称为算法。,算法,计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。,算法的基本特征,:,(1),有穷性,(2),确定性,(3),可行性,(4),拥有足够的情报,（有零个或多个输入，有一个或多个输出）,一个算法,有零个或多个输入,，以刻画运算对象的初始情况，所谓零个输入是指算法本身定出了初始条件；,一个算法,有一个或多个输出,，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；,伪代码,:,S1:,输入圆的半径,R;,S2:,求面积,R,2,;,S3:,输出面积,;,例,1:,已知圆的半径,求圆的面积,.,描述算法的工具通常有传统流程图、,N-S,结构化流程图、伪代码等。,开始,输入,R,S=3.14,*,R*R,输出,S,结束,传统流程图,第,9,页,算法与计算机程序,算法,是一组逻辑步骤,程序,用计算机语言描述的算法,算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计。,算法是程序设计的核心,算法,:,S1:,输入圆的半径,R;,S2:,求面积,R,2,;,S3:,输出面积,;,例题,:,已知圆的半径,求圆的面积,.,程序,#include,int main(),float r,s;,do,printf(Please input r:);,scanf(%f,if(r0)printf(Error,！,n);,while(r=0);,s=PI*r*r;,printf(Area=%fn,s);,return 0;,算法的基本要素,1,、对数据对象的运算和操作,算术运算,逻辑运算,关系运算,数据传输,2,、算法的控制结构,算法中各操作之间的执行顺序,一个算法一般可以用顺序、选择、循环,3,种基本结构组合而成。,算术运算,逻辑运算,关系运算,数据传输,顺序、选择、循环,3,种基本结构,#include,int main(),float R,S;,do,printf(Please input R:);,scanf(%f,if(R0)printf(Error,！,n);,while(R=0);,s=PI*R*R;,printf(Area=%fn,S);,return 0;,算法设计基本方法,列举法,归纳法,递推,递归（以简洁的形式设计和描述算法）,减半递推技术,回溯法,1.2,算法复杂度,时间复杂度,是指执行算法所需要的计算工作量。,通常有事后统计法和事前分析估算法。,算法的工作量用算法所执行的基本运算次数来度量,.,算法所执行的基本运算次数与问题的规模,n,有关（即算法所执行的基本次数是问题规模的函数）,.,执行算法所需要的计算工作量和,f(n),同步增长，记为,:,算法的工作量,=f(n),时间复杂度,=O(f(n),而对于一个固定的规模，算法所执行的基本次数还与特定的输入有关。,例子,4,：,for(i=2;i=n;+i),for (j=2;j=i-1;+j)+x ;,基本运算：,基本运算的执行次数：,X,增,1,i=2 0,i=3 1,i=4 2,i=n n-2,1+2+3+(n-2),=(n-1)(n-2)/2,O,（）,例子,2,：,+x;,O,（,1,）,例子,3,：,for(i=1;i=n;+i)+x;,O,（,n,）,时间复杂度：,O(n*n-3n+2)/2),基本运算：,基本运算的执行次数：,时间复杂度：,1,X,增,1,基本运算：,基本运算的执行次数：,时间复杂度：,X,增,1,n,算法的空间复杂度,一般是指执行这个算法所需要的内存空间,一个算法所占用的内存空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法在执行过程中所需要的额外空间这,3,部分。,算法的时间复杂度是指,A),执行算法程序所需要的时间,B),算法程序的长度,C),算法执行过程中所需要的基本运算次数,D),算法程序中的指令条数,算法的基本特征是可行性、确定性、,【1】,和拥有足够的情报。,算法的空间复杂度是指,A),算法程序的长度,B),算法程序中的指令条数,C),算法程序所占的存储空间,D),执行过程中所需要的存储空间,在计算机中，算法是指,A),加工方法,B),解题方案的准确而完整的描述,C),排序方法,D),查询方法,例题讲解,有穷性,算法分析的目的是,A),找出数据结构的合理性,B),找出算法中输入和输出之间的关系,C),分析算法的易懂性和可靠性,D),分析算法的效率以求改进,算法的工作量大小和实现算法所需的存储单元多少分别称为算法的,【1】,。,时间复杂度和空间复杂度,1.2,数据结构,数据结构的定义,数据的逻辑结构和存储结构,数据结构的图形表示,线性结构与非线性结构,能输入到计算机中,并能被计算机程序处理的,符号的集合。,整数,(1,2),、实数,(1.1,1.2),字符串,(Beijing),、,图形、声音。,基本概念和术语,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,计算机管理图书问题,在图书馆里有各种卡片：有按书名编排的、,有按作者编排的、有按分类编排,如何将查询图书的这些信息存入计算机中,既要考虑查询时间短，又要考虑节省空间,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,最简单的办法之一是建立一张表，,每一本书的信息在表中占一行，如,如何将,0,1,2,3,4,5,6,7,8,9,这,10,个数存放在,计算机中能最快地达到你所需要的目的？,目的不同，最佳的存储方方法就不同。,从大到小排列：,9,8,7,6,5,4,3,2,1,0,输出偶数：,0,2,4,6,8,1,3,5,7,9,数据元素在,计算机中的表示,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,对数据结构中的节点进行,操作处理,(,插入、删除、修改、查找、排序,),计算机中能最快地达到你所需要的目的？,在深度为5的满二叉树中，叶子结点的个数为,n(n-1)/2次,A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA,对此二叉树前序遍历的结果为,栈和队列的顺序存储结构及其基本运算。,正序：比较次数为O(n-1),rear=front=-1(队空）,性质：对任何一棵二叉树T，如果其终端结点数为n0,度,A）数据所占的存储空间,计算机中能最快地达到你所需要的目的？,D=1,2,3,4,大则交换，关键字最大的记录交换到最后一个位置上；,折半查找（二分法查找）,设一棵完全二叉树共有700个结点，则该二叉树中有（）个叶子结点。,数据域和指针域。,C)随机存取的存储结构、随机存取的存储结构,C)线性链表是非线性结构D)二叉树是线性结构,1,数据的逻辑结构,2,、数据的存储结构,3,、数据的运算：检索、排序、插入、删除、修改等。,A,线性结构,B,非线性结构,A,顺序存储,B,链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,数据结构可描述为,Group=,（,D,，,R,）,1.,数据的逻辑结构：,是指反映数据元素之间逻辑关系的数据结构。它包括,数据元素的集合和数据元素之间的前后关系两个因素。,有限个数据元素的集合,有限个数据元素,间关系的集合,数据的逻辑结构简称数据结构。,数据元素,(Data Element),数据元素是数据的基本单位，即数据集合中的个体。,有时一个数据元素可由若干数据项,(Data Item),组成。数据项是数据的最小单位。,数据元素亦称,结点,或,记录,。,线性,树,图,常用数据结构,:,A.,线性结构,(A,B,C,，,X,Y,Z),例,:,学生成绩表,86,胡孝臣,9861103,95,刘忠赏,9861107,100,张卓,9861109,成绩,姓名,学号,线性表,栈,后进先出,队列,先进先出,例,:,英文字母表,数据结构,S=(D,R),D=,春,夏,秋,冬,R=,什么型的数据结构,?,用图形工具,线性结构,数据元素：用中间标有元素值的方框表示，称为结点,逻辑关系：用有向线段从前件指向后件（不引起误会情况下，箭头可以省去）,冬,春,夏,秋,树形结构,例,:,家庭成员数据结构可表示成,例,:,计算机文件管理系统也是典型的树形结构,B,非线性结构,父亲,儿子,女儿,没有前件的结点称为根结点；,没有后件的结点称为终端结点（叶子结点）,1,4,2,3,例,:,数据结构,B(D,R),D=1,2,3,4,R=(1,2),(1,3),(1,4),(2,3),(3,4),(2,4),2,1,3,例,:,数据结构,C(D,R),D=1,2,3,R=,图形结构,元素,n,.,元素,i,.,元素,2,元素,1,L,o,L,o,+m,L,o,+(i-1)*m,L,o,+,（,n-1)*m,存储地址,存储内容,Loc(a,i,)=L,o,+,（,i-1)*m,1,、顺序存储,每个元素所占用,的存储单元个数,（,3,）存储结构,例：线性表,(zhao,qian,sun,li,zhou,wu,zheng,wang),顺序存储结构：,存储地址,数据,7,8,9,10,11,12,13,14,zhao,qian,sun,li,zhou,wu,zheng,wang,7,基地址,顺序存储结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里,具有以下特点,:,1.,随机存取。,2.,作插入或删除操作时，需移动大量元数。,3.,长度变化较大时，需按最大空间分配。,4.,表的容量难以扩充。,数据结构是一门研究数据组织、存储和运算的一般方法的学科。,n=12 k=4,性质1:二叉树的第i层上至多有2 i-1（i 1）个结点。,A）数据所占的存储空间,A)动态结构和静态结构 B)紧凑结构和非紧凑结构,a1 ,a2 ,a3 ,a4 ,an-1 ,an,数据元素是数据的基本单位，即数据集合中的个体。,用一组连续的存储单元存放二叉树的数据元素。,此种结构称为先进先出（FIFO）表。,(a):堆顶元素取最大值,B)数据的存储结构与数据处理的效率无关,A)ABCED B)DCBEA C)DBCEA D)CDABE,A)不必事先估计存储空间 B)可随机访问任一元素,A)动态结构和静态结构 B)紧凑结构和非紧凑结构,可以从任何一个结点开始访问链表的所有结点.,2,、链式存储,每个节点都由两部分组成：,数据域和指针域。,数据域,存放元素本身的数据，,指针域,存放指针。,数据元素之间逻辑上的联系由指针来体现。,例：线性表,(zhao,qian,sun,li,zhou,wu,zheng,wang),链式存储结构：,存储地址,数据,1,7,13,19,25,31,37,43,li,qian,sun,wang,wu,zhao,zheng,zhou,指针,43,13,1,null,37,7,19,25,31,头指针,通常我们把链表画成用箭头相链接的结点的序列，结点之间的箭头表示链域中的指针。,zhao,qian,sun,li,zhou,wu,zheng,wang/,H,存储地址,数据,1,7,13,19,25,31,37,43,li,qian,sun,wang,wu,zhao,zheng,zhou,指针,43,13,1,null,37,7,19,25,31,头指针,1.,比顺序存储结构多用空间,(,存储密度小,),(,每个节点都由数据域和指针,域,组成,),。,2.,逻辑上相邻的节点物理上不必相邻。,3.,插入、删除灵活,(,不必移动节点，只要改变节点中的指针,),。,4.,非随机存取。,链接存储结构特点：,1,数据的逻辑结构,2,、数据的存储结构,3,、数据的运算：检索、排序、插入、删除、修改等。,A,线性结构,B,非线性结构,A,顺序存储,B,链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(,亦称物理结构,),链表不具有的特点是,A),不必事先估计存储空间,B),可随机访问任一元素,C),插入删除不需要移动元素,D),所需空间与线性表长度成正比,数据结构分为逻辑结构与存储结构，线性链表属于,【1】,。,数据结构中，与所使用的计算机无关的是数据的,A),存储结构,B),物理结构,C),逻辑结构,D),物理和存储结构,数据的逻辑结构有线性结构和,【1】,两大类。,数据的存储结构是指,A,）数据所占的存储空间,B,）数据的逻辑结构在计算机中的表示,C,）数据在计算机中的顺序存储方式,D,）存储在外存中的数据,例题讲解,存储结构,非线性结构,顺序存储方法是把逻辑上相邻的结点存储在物理位置,【2】,的存储单元中。,数据处理的最小单位是,A),数据,B),数据元素,C),数据项,D),数据结构,数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及,A),数据的存储结构,B),计算方法,C),数据映象,D),逻辑存储,线性表的顺序存储结构和线性表的链式存储结构分别是,A),顺序存取的存储结构、顺序存取的存储结构,B),随机存取的存储结构、顺序存取的存储结构,C),随机存取的存储结构、随机存取的存储结构,D),任意存取的存储结构、任意存取的存储结构,相邻,根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成,A),动态结构和静态结构,B),紧凑结构和非紧凑结构,C),线性结构和非线性结构,D),内部结构和外部结构,数据结构包括数据的逻辑结构、数据的,【2】,以及对数据的操作运算。,数据的基本单位是,【5】,。,下列叙述中，错误的是,A),数据的存储结构与数据处理的效率密切相关,B),数据的存储结构与数据处理的效率无关,C),数据的存储结构在计算机中所占的空间不一定是连续的,D),一种数据的逻辑结构可以有多种存储结构,存储结构,数据元素,1.3,线性表,线性表的概念,线性表的定义：,线性表是,n,个元素的有限序列，它们之间的关系可以排成一 个线性序列：,(a1,，,a2,，,，,ai,，,，,an),其中,n,称作表的长度，当,n=0,时，称作空表。,线性表的特点：,1.,线性表中所有元素的性质相同。,2.,除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前驱和一个后继,.,第一个数据元素无前驱,最后一个数据元素无后继。,3.,数据元素在表中的位置只取决于它自身的序号。,在线性表上常用的运算有：,初始化、求长度、取元素、修改、前插、删除、查找、排序。,1.4,线性表的顺序存储结构及其插入与删除操作,特点：,1.,线性表中数据元素类型一致，只有数据域，存储空间利用率高。,2.,所有元素所占的存储空间是连续的,3.,各数据元素在存储空间中是按逻辑顺序依次存放的,4.,做插入、删除时需移动大量元素。,5.,空间估计不明时，按最大空间分配。,顺序存储结构：,存储地址,数据,7,8,9,10,11,12,13,14,zhao,qian,sun,li,zhou,wu,zheng,wang,7,基地址,元素,a,n,.,元素,a,i,.,元素,a,2,元素,a,1,b,b+m,b+(i-1)*m,b+(maxlen-1)*m,存储地址,内存状态,Loc(,元素,i)=b+,（,i-1)*m,顺序存储结构示意图,(,顺序表,),：,首地址,起始地址,基地址,每个元素所占用,的存储单元个数,1-,1,插入运算,a,i-1,.,a,2,a,1,a,length,a,i+1,a,i,x,a,i-1,.,a,2,a,1,a,length,a,i+1,a,i,X,插入算法的分析,:,假设线性表中含有,n,个数据元素，在进行插入操作时，若假定在,n+1,个位置上插入元素的可能性均等，则平均移动元素的个数为：,1-,2,删除运算,a,i-1,.,a,2,a,1,a,length,a,i+1,a,i,a,i-1,.,a,2,a,1,a,length,a,i+1,删除算法的分析,:,在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：,总结,:,顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。,链表不具有的特点是,A),不必事先估计存储空间,B),可随机访问任一元素,C),插入删除不需要移动元素,D),所需空间与线性表长度成正比,顺序存储方法是把逻辑上相邻的结点存储在物理位置,【2】,的存储单元中。,长度为,n,的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为,【1】,。,线性表若采用顺序存储结构时，要求内存中可用存储单元的地址,A),必须是连续的,B),部分地址必须是连续的,C),一定是不连续的,D),连续不连续都可以,例题讲解,相邻,线性表,L=(a1,a2,a3,ai,，,an),，下列说法正确的是,A),每个元素都有一个直接前件和直接后件,B),线性表中至少要有一个元素,C),表中诸元素的排列顺序必须是由小到大或由大到小,D),除第一个元素和最后一个元素外，其余每个元素都有一个 且只有一个直接前件和直接后件,线性表的顺序存储结构和线性表的链式存储结构分别是,A),顺序存取的存储结构、顺序存取的存储结构,B),随机存取的存储结构、顺序存取的存储结构,C),随机存取的存储结构、随机存取的存储结构,D),任意存取的存储结构、任意存取的存储结构,下列叙述中，错误的是,A),数据的存储结构与数据处理的效率密切相关,B),数据的存储结构与数据处理的效率无关,C),数据的存储结构在计算机中所占的空间不一定是连续的,D),一种数据的逻辑结构可以有多种存储结构,根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成,A),动态结构和静态结构,B),紧凑结构和非紧凑结构,C),线性结构和非线性结构,D),内部结构和外部结构,当线性表采用顺序存储结构实现存储时，其主要特点是,【1】,。,随机存取,线性表的链式存储结构及其插入与删除操作,zhao,qian,sun,li,zhou,wu,zheng,wang/,H,存储地址,数据,1,7,13,19,25,31,37,43,li,qian,sun,wang,wu,zhao,zheng,zhou,指针,43,13,1,null,37,7,19,25,31,头指针,单链表,b,a,P,b,a,P,1-1,单链表的插入运算,x,S,在,P,所指向的结点之后插入新的结点,1-2,单链表,删除运算,La,ai,an,ai-1,ai+1,要求,:,删除结点,ai,。,1-3.,循环链表,:,首尾相接的链表。,将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。,a,1,a,2,a,n,a,3,L,.,带头结点的单链表,a,1,a,2,a,n,a,3,L,.,循环单链表,特点,:,可以从任何一个结点开始访问链表的所有结点,.,1-4,双向链表,在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的前驱和后继结点。可提高效率。,data,next,before,链表不具有的特点是,A),不必事先估计存储空间,B),可随机访问任一元素,C),插入删除不需要移动元素,D),所需空间与线性表长度成正比,用链表表示线性表的优点是,A),便于随机存取,B),花费的存储空间较顺序存储少,C),便于插入和删除操作,D),数据元素的物理顺序与逻辑顺序相同,长度为,n,的顺序存储线性表中,当在任何位置上插入一个元素概率都相等时,插入一个元素所需移动元素的平均个数为,【1】,。,在单链表中，增加头结点的目的是,A),方便运算的实现,B),使单链表至少有一个结点,C),标识表结点中首结点的位置,D),说明单链表是线性表的链式存储实现,例题讲解,非空的循环单链表,head,的尾结点,(,由,p,所指向,),，满足,A)p-next=NULLB)p=NULL,C)p-next=head D)p=head,循环链表的主要优点是,A),不再需要头指针了,B),从表中任一结点出发都能访问到整个链表,C),在进行插入、删除运算时，能更好的保证链表不断开,D),已知某个结点的位置后，能够容易的找到它的直接前件,当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为,【2】,。,用链表表示线性表的突出优点是,【1】,。,上溢,插入、删除灵活,1.6,栈和队列,栈和队列的定义,栈和队列是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为限定性的数据结构。,1.,栈,栈,是限定仅在表尾进行插入或删除操作的线性表。,栈顶,表尾。,栈底,表头。,空栈,不含元素的空表。,a1,a2,an,栈底,栈顶,进栈,出栈,栈,s=(a1,a2,an),后进先出（,LIFO,）,2.,栈的顺序存储结构及其基本运算,a,2,a,1,a,1,a,2,top,用顺序存储结构表示的栈,:,顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量,top,指示栈顶位置，,称为栈顶指针，它始终指向待插入元素的位置。,基本运算：,压（进）栈：,PUSH,出栈：,POP,读栈顶元素：,gettop,例子：,top,base,EDCBA,top,base,CBA,base,top,A,base,top,空桟：,top,base,非空桟：,top,始终在桟顶元素的后一个位置,桟的元素个数：,top-base,上溢,下溢,3.,队列,定义：一种特殊的线性结构，限定只能在表的一端进行插入，在 表的另一端进行删除的线性表 。此种结构称为先进先出（,FIFO,）表。,a,1,a,2,a,3,a,4,a,n-1,a,n,队 列 示 意 图,队头,队尾,e,3,e,4,(c),e1,e2,出队，,e4,入队,队 满,rear=3,front,e,1,e,2,e,3,(b),rear,front,(b)e1,e2,e3,入队,4.,队列的顺序存储结构及其基本运算,3 2 1 0,(a),rear=front=-1(,队空）,rear,front,空队列,:,非空队列,:,队列元素个数,:,rear=front=-1,front,始终指向队头元素前一个位置，而,rear,始终指向队尾元素的位置,rear-front,循环队列,基本思想：把队列设想为一个循环的表，臆想,elem0,接在,elemmaxsize-1,之后,.,front,rear,Maxsize-1,0,1,e,3,e,4,rear=3,front,0,0,1,2,3,4,5,front,A,B,C,D,E,F,rear,上溢,0,0,1,2,3,4,5,front,rear,下溢,front=rear,队满,front=rear,队空,栈和队列的共同特点是,A),都是先进先出,B),都是先进后出,C),只允许在端点处插入和删除元素,D),没有共同点,如果进栈序列为,e1,e2,e3,e4,，则可能的出栈序列是,A)e3,e1,e4,e2 B)e2,e4,e3,e1,C)e3,e4,e1,e2D),任意顺序,一些重要的程序语言,(,如,C,语言和,Pascal,语言,),允许过程的递归调用。而实现递归调用中的存储分配通常用,A),栈,B),堆,C),数组,D),链表,例题讲解,栈底至栈顶依次存放元素,A,、,B,、,C,、,D,，在第五个元素,E,入栈前，栈中元素可以出栈，则出栈序列可能是,A)ABCED B)DCBEA C)DBCEA D)CDABE,栈通常采用的两种存储结构是,A),线性存储结构和链表存储结构,B),散列方式和索引方式,C),链表存储结构和数组,D),线性存储结构和非线性存储结构,栈和队列通常采用的存储结构是,【1】,。,下列数据结构中，按先进后出原则组织数据的是,A),线性链表,B),栈,C),循环链表,D),顺序表,当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为,【2】,。,链表存储结构和数组,上溢,由两个栈共享一个存储空间的好处是,A),减少存取时间，降低下溢发生的机率,B),节省存储空间，降低上溢发生的机率,C),减少存取时间，降低上溢发生的机率,D),节省存储空间，降低下溢发生的机率,自由区,lefttop,righttop,0,MAXNUM-1,两个栈共享邻接空间,下列关于栈的叙述中正确的是,）在栈中只能插入数据,B,）在栈中只能删除数据,C,）栈是先进先出的线性表,D,）栈是后进先出的线性表,下列关于队列的叙述中正确的是,）在队列中只能插入数据,B,）在队列中只能删除数据,C,）队列是先进先出的线性表,D,）队列是后进先出的线性表,树的定义,由一个或多个结点组成的有限集合,。,仅有一个根结点，结点间有明显的层次结构关系。,A,C,G,T,2,D,H,I,T,3,J,M,B,E,L,K,T,1,F,现实世界中，能用树的结构表示的例子：,学校的行政关系、书的层次结构、人类的家族血缘关系等。,1.7,树,介绍几个概念：,结点（,Node,）：树中的元素，包含数据项及若干指向其子树的分支。,结点的度（,Degree,）：结点拥有的子树数。,结点的层次：从根结点开始算起，根为第一层。,叶子（,Leaf,）：度为零的结点，也称端结点。,孩子（,Child,）：结点子树的根称为该结点的孩子结点。,兄弟（,Sibling,）：,同一双亲的孩子。,双亲（,Parent,）：孩子结点的上层结点，称为这些结点的 双亲。,树的深度（,Depth),：树中结点的最大层次数。,树的度：结点所具有的最大的度,.,森林（,Forest,）：,M,棵互不相交的树的集合。,A,C,G,D,H,I,J,M,B,E,L,K,T,1,F,二叉树（,Binary Tree,）,1,、二叉树的定义及其性质,(1),二叉树的定义,二叉树的五种基本形态,二叉树一种特殊的树形结构，特点是树中每个结点最多只能有两棵子树,(,即二叉树中不存在度大于,2,的结点,),，且子树有左右之分，次序不能颠倒。,空二叉树,仅有,根结点,右子树为空,左子树为空,左右子树均非空,二叉,树,是,n(n,0),个结点的有限集合。它或为空数,(n=0),或由一个根结点和两棵分别称为根的左子树和右子树的互不相交的二叉树组成。,特别要注意：二叉,树,不是,一般树的特殊情况,而是另一种树形结构,.,a,a,b,b,两棵不同的二叉,树,a,b,一,棵,树,性质,1:,二叉树的第,i,层上至多有,2,i-1,（,i,1,）个结点。,(2),二叉树的基本性质,4,2,3,1,6,7,8,9,10,11,12,13,14,15,5,第三层上,(i=3),，有,2,3-1,=4,个节点。,第四层上,(i=4),，有,2,4-1,=8,个节点。,性质,2:,深度为,k,的二叉树中至多含有,2,k,-1,个结点。,性质：对任何一棵二叉树,T,，如果其终端结点数为,n,0,度,为,2,的结点数为,n,2,则,n,0,=n,2,+1,。,证明：,设,n,1,为二叉树,T,中度为,1,的结点数；,二叉树中所有结点的度均小于或等于,2,其结点总数为：,n=n,0,+n,1,+n,2,二叉树中除了根结点外，其余结点都有一个分支进入,设分支总数为,B,；则,n=B+1;,二叉树的分支是由度为,1,或,2,的结点射出的,B=n,1,+2*n,2,n=n,1,+2*n,2,+1=n,0,+n,1,+n,2,n,0,=n,2,+1,A,B,F,C,J,M,一般树,满二叉树,4,2,3,1,6,7,8,9,10,11,12,13,14,15,5,特点：每一层上都含有最大结点数。,完全二叉树,4,2,3,1,6,7,8,9,10,11,12,5,特点：,(1),除最后一层外，每一层都取最 大结点数，,(2),最后一层结点都集中在该层最左边的若干位置。,性质：具有,n,个结点的完全二叉树的深度为,11,2,3,4,5,6,7,8,9,10,12,1,例：,n=2 k=2,n=6 k=3,n=7 k=3,n=8 k=4,n=12 k=4,性质：如果对一棵有,n,个结点的完全二叉树的结点按层,序编号，则对任一结点,i(1=i=n,则结点,i,无左孩子,(,结点,i,为叶子结点,);,否则其左孩子,Lchild(i),是结点,2i,。,(3),如果,2i+1n,则结点,i,无右孩子,;,否则其右孩子,Rchild(i),是结点,2i+1,。,(1),如果,i=1,则结点,i,是二叉树的根,无双亲,;,如果,i1,则双亲,Parent(i),是结点,|i/2|,。,例：,11,2,3,4,5,6,7,8,9,10,12,1,i=6,其双亲为,|i/2|=3,；其左孩子为,2*i=12;,i=1,是树的根,无双亲,;,其左孩子为,2*i=2,右孩子为,2*i+1=3.,2*i=1812 2*i+1=1912 ,其无左、右孩子。,2*i+1=1312 ,其无右孩子。,i=9,其双亲为,|i/2|=4,；,树与二叉树的区别,A,树和二叉树的结点个数最少都可为,0,。,B,树中结点的最大度数没有限制，二叉树结点最大度数为,2,。,C,树的,结点,无左、右之分，二叉树的,结点,子树有明确的左、右之分。,3,个结点的,树,3,个结点的,二叉,树,2,、二叉树的存储结构,(2),链式存储结构,T16,若父结点在数组中,i,下标处，其左孩子在,2*i,处，右孩子在,2*i+1,处。,11,A,B,c,F,E,D,1,2,4,8,9,10,5,6,3,7,12,13,14,15,(1),顺序存储结构,(1),顺序存储结构,2,h,-1=,2,4,-1=15,用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。,0,0,0,0,F,E,0,0,0,D,C,0,B,A,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,0,一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。,(2),、链式存储结构,链式存储结构,二叉链表,三叉链表,二叉链表：,二叉链表的结点包含三个域：数据域、左、右指针域。,例：,A,B,C,D,E,F,G,A,B,C,D,E,F,G,三叉链表：,三叉链表的结点包含四个域：,数据域、左、右、双亲指针域。,例：,A,B,C,D,E,F,G,A ,B,C ,D,E,F ,G ,链式存储结构的特点：,（,1,）操作便于实现 （,2,）结构复杂,二叉树的遍历,查找某个结点，或对二叉树中全部结点进行某种处理，就需要遍历。,（,1,）遍历定义及遍历算法,遍历是指按某条搜索路线寻访树中每个结点，且每个结点只被访 问一次。,按先左后右的原则，一般使用三种遍历：,先序遍历,(D L R):,访问根结点，按先序遍历左子树，按先序遍历右子树。,中序遍历,(L D R):,按中序遍历左子树，访问根结点，按中序遍历右子树。,后序遍历,(L R D):,按后序遍历左子树，按后序遍历右子树，访问根结点。,二叉树为空时，执行空操作，即空二叉树已遍历完。,（,2,）遍历算法,先序遍历：,D L R,中序遍历：,L D R,后序遍历：,L R D,A,D,B,C,D L R,A,D L R,D L R,B,D,C,D L R,以先序遍历,D L R,为例演示遍历过程,ABDC,BDAC,DBCA,e,-,+,a,*,b,-,c,d,/,f,L D R,L D R,a,+,L D R,b,*,LDR,c,-,d,-,LDR,e,/,f,中序遍历示图,已知二叉树后序遍历序列是,dabec,，中序遍历序列是,debac,，它的前序遍历序列是,A)acbed B)decab C)deabc D)cedba,已知一棵二叉树前序遍历和中序遍历分别为,ABDEGCFH,和,DBGEACHF,，则该二叉树的后序遍历为,A)GEDHFBCA B)DGEBHFCA,C)ABCDEFGH D)ACBFEDHG,树是结点的集合，它的根结点数目是,A),有且只有,1B)1,或多于,1,C)0,或,1D),至少,2,下列叙述中正确的是,A),线性表是线性结构,B),栈与队列是非线性结构,C),线性链表是非线性结构,D),二叉树是线性结构,例题讲解,在深度为,5,的满二叉树中，叶子结点的个数为,A)32B)31 C)16 D)15,若某二叉树的前序遍历访问顺序是,abdgcefh,，中序遍历访问顺序是,dgbaechf,，则其后序遍历的结点访问顺序是,A)bdgcefha B)gdbecfha C)bdgaechf D)gdbehfca,在树结构中，树根结点没有,【1】,。,具有,3,个结点的二叉树有,A)2,种形态,B)4,种形态,C)7,种形态,D)5,种形态,设一棵二叉树中有,3,个叶子结点，有,8,个度为,1,的结点，则该二叉树中总的结点数为,A)12 B)13 C)14D)15,双亲结点,设有下列二叉树：,对此二叉树前序遍历的结果为,A)ZBTTCPXA B)ATBZXCTP C)ZBTACTXP D)ATBZXCPT,设有下列二叉树：,对此二叉树的中序遍历的结果为,A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA,设树,T,的度为,4,其中度为,1,、,2,、,3,、,4,的结点个数分别为,4,、,2,、,1,、,1,。则,T,中的叶子结点数为,A,）,8 B,）,7 C,）,6 D,）,5,设一棵完全二叉树共有,700,个结点，则该二叉树中有（）个叶子结点。,350,解法一：根据,二叉树,的性质,3,可知：,叶子结点,数,n0,n2+1,，根据,完全二叉树,的概念可知，度为,1,的结点数要么为,1,，要么为,0,，,二叉树,总结点数,N,n0+n1+n2,2n0+n1,1,，得出,n0,（,N+1,n1,）,/2,N/2,向上取整，所以本题答案是,350,个,叶子结点,。,解法二：易求出总层数和末层叶子数。总层数,k=log2N,向上取整,=10;,且前,9,层总结点数为,29-1=511(,完全二叉树,的前,k-1,层肯定是满的,),所以末层叶子数为,700-511=189,个。请注意,叶子结点,总数末层叶子数！还应当加上第,k-1,层（靠右边）的,0,度结点个数。末层的,189,个叶子只占据了上层的,95,个结点（,189/2),，上层（,k=9),右边的,0,度结点数还有,2(9-1)-95=161,个。所以，全部叶子数,189(,末层,),16