计算机二级公共基础知识(完整版).ppt

二级公共基础知识,第一章 数据结构基础,2,内容提要,算法:算法的基本概念、算法复杂度数据结构的基本概念：什么是数据结构、数据结构的图形表示、线性结构与非线性结构线性表及其顺序存储结构：线性表的基本概念、顺序存储结构、插入运算、删除运算栈和队列：栈及其基本运算、队列及其基本运算线性链表：基本概念、基本运算、循环链表及其基本运算树与二叉树：树的基本概念、二叉树及其基本性质、二叉树的存储结构、二叉树的遍历查找技术：顺序查找、二分法查找排序技术：交换类排序法、插入类排序法、选择类排序法,1.1 算法,4,1.1.1 算法的基本概念,算法是解题方案的准确而完整的描述，它不等于程序，也不等计算方法。1算法的基本特征可行性(effectiveness)确定性(definiteness)有穷性(finiteness)拥有足够的情报2算法的基本要素算法中对数据的运算和操作算术运算:包括加、减、乘、除等）逻辑运算:包括“与”、“或”、“非”等运算）关系运算:包括“大于”、“小于”、“等于”、“不等于”等）数据传输:包括赋值、输入、输出等操作算法的控制结构(描述算法的工具传统流程图、),5,算法的控制结构描述算法的工具:传统流程图、N-S结构化流程图、算法描述语言算法一般可以用顺序、选择和循环三种控制结构组合而成。,6,1.1.1 算法的基本概念,3算法设计的基本方法列举法归纳法递推递归减半递推技术回溯法,7,1.1.2 算法复杂度,算法复杂度：时间复杂度、空间复杂度1算法的时间复杂度执行算法所需要的计算工作量与下列因素无关：书写算法的程序设计语言编译产生的机器语言，代码质量机器执行指令的速度问题的规模,8,1.1.2 算法复杂度,问题的规模函数算法的工作量=f(n)算法中基本操作重复执行的频率T(n)，是问题规模n的某个函数f(n)，记作：T(n)=O(f(n)记号“O”读作“大O”。表示随问题规模n的增加，算法执行时间的增长率和f(n)相应增加。常见算法复杂度：O(1)：常数阶 O(n)：作线性阶 O(n2)：平方阶O(n3)：立方阶 O(logn)：对数阶 O(2n)：指数阶,9,1.1.2 算法复杂度,nn矩阵相乘算法：时间复杂度为O(n3)。,10,1.1.2 算法复杂度,分析算法的工作量两种方法：平均性态A(n)=p(x)t(x)xDn最坏情况复杂性所谓最坏情况分析，是指在规模为n时，算法所执行的基本运算的最大次数。它定义为W(n)=maxt(x)xDn,11,例12 采用顺序搜索法，在长度为n的一维数组中查找值为x的元素。,例12 采用顺序搜索法，在长度为n的一维数组中查找值为x的元素。即从数组的第一个元素开始，逐个与被查值x进行比较。基本运算为x与数组元素的比较。首先考虑平均性态分析。设被查项x在数组中出现的概率为q。当需要查找的x为数组中第i个元素时，则在查找过程中需要做i次比较，当需要查找的x不在数组中时（即数组中没有x这个元素），则需要与数组中所有的元素进行比较。即 i,1inti=n,i=n+1其中i=n+1表示x不在数组中的情况。其中i=n+1表示x不在数组中的情况。如果假设需要查找的x出现在数组中每个位置上的可能性是一样的，则x出现在数组中每一个位置上的概率为q/n（因为前面已经假设x在数组中的概率为q），而x不在数组中的概率为1-q。即q/n,1inpi=1-q,i=i+1其中i=n+1表示x不在数组中的情况,12,例12 采用顺序搜索法，在长度为n的一维数组中查找值为x的元素。,因此，用顺序搜索法在长度为n的一维数组中查找值为x的元素，在平均情况下需要做的比较次数为n+1 nA(n)=piti=(q/n)i+(1-q)n=(n+1)q/2+(1-q)ni=1 i=1如果已知需要查找的x一定在数组中，此时q=1，则A(n)=(n+1)/2。这就是说，在这种情况下，用顺序搜索法在长度为n的一维数组中查找值为x的元素，在平均情况下需要检查数组中一半的元素。如果已知需要查找的x有一半的机会在数组中，此时q=1/2，则A(n)=(n+1)/4+n/23n/4这就是说，在这种情况下，用顺序搜索法在长度为n的一维数组中查找值为x的元素，在平均情况下需要检查数组中3/4的元素。,13,例12 采用顺序搜索法，在长度为n的一维数组中查找值为x的元素。,再考虑最坏情况分析。在这个例子中，最坏情况发生在需要查找的x是数组中的最后一个元素或x不在数组中的时候，此时显然有W(n)=maxti|1in+1=n在上述例子中，算法执行的工作量是与具体的输入有关的，A(n)只是它的加权平均值，而实际上对于某个特定的输入，其计算工作量未必是A(n),且A(n)也不一定等于W(n)。但在另外一些情况下，算法的计算工作量与输入无关，即当规模为n时，在所有可能的输入下，算法所执行的基本运算次数是一定的，此时有A(n)=W(n)。例如，两个n阶的矩阵相乘，都需要做n3次实数乘法，而与输入矩阵的具体元素无关。,14,1.1.2 算法复杂度,2算法的空间复杂度算法执行过程中所需的最大存储空间存储量包括以下三部分算法程序所占的空间输入的初始数据所占的存储空间算法执行过程中所要的额外空间算法空间复杂度可定义为：S(n)=O(f(n)原地工作(in place)的算法：记作O(1)压缩存储技术,15,习题,（1）算法的空间复杂度是指A）算法程序的长度B）算法程序中的指令条数C）算法程序所占的存储空间D）执行过程中所需要的存储空间解析：算法的复杂度主要包括算法的时间复杂度和算法的空间复杂度。所谓算法的时间复杂度是指执行算法所需要的计算工作量；算法的空间复杂度一般是指执行这个算法所需要的内存空间。,16,习题,算法的时间复杂度是指A）执行算法程序所需要的时间B）算法程序的长度C）算法执行过程中所需要的基本运算次数D）算法程序中的指令条数解析：算法的复杂度主要包括算法的时间复杂度和算法的空间复杂度。所谓算法的时间复杂度是指执行算法所需要的计算工作量；算法的空间复杂度一般是指执行这个算法所需要的内存空间。,17,习题,算法的基本特征是可行性、确定性、和拥有足够的情报。解析：算法是指解题方案的准确而完整的描述。它有4个基本特征，分别是可行性、确定性、有穷性和拥有足够的情报,18,习题,在计算机中，算法是指A）加工方法B）解题方案的准确而完整的描述 C）排序方法D）查询方法解析：计算机算法是指解题方案的准确而完整的描述，它有以下几个基本特征：可行性、确定性、有穷性和拥有足够的情报。,19,习题,算法分析的目的是A）找出数据结构的合理性B）找出算法中输入和输出之间的关系C）分析算法的易懂性和可靠性 D）分析算法的效率以求改进解析：算法分析是指对一个算法的运行时间和占用空间做定量的分析，一般计算出相应的数量级，常用时间复杂度和空间复杂度表示。分析算法的目的就是要降低算法的时间复杂度和空间复杂度，提高算法的执行效率。,20,习题,算法的工作量大小和实现算法所需的存储单元多少分别称为算法的【1】。【命题目的】本题考查了考生对算法的理解程度。【解题要点】算法的复杂性是指对一个在有限步骤内终止算法和所需存储空间大小的估计。算法的计算量是算法的时间复杂性，算法所需存储空间大小是算法的空间复杂性。,1.2 数据结构的基本概念,22,1.2.1 什么是数据结构,1数据结构研究的主要内容数据的逻辑结构数据的存储结构对各种数据结构进行的运算2研究数据结构目的提高数据处理的速度尽量节省在数据处理过程中所占用的计算机存储空间,23,1.2.1 什么是数据结构,1数据结构研究的主要内容数据的逻辑结构数据的存储结构对各种数据结构进行的运算2研究数据结构目的提高数据处理的速度尽量节省在数据处理过程中所占用的计算机存储空间,24,1.2.1 什么是数据结构,25,1.2.1 什么是数据结构,3数据结构的定义相互有关联的数据元素的集合数据元素之间的关系可以用前后件关系来描述一个数据结构应包含以下两方面信息：表示数据元素的信息 表示各数据元素之间的前后件关系,26,1.2.1 什么是数据结构,4数据的逻辑结构对数据元素之间的逻辑关系的描述只抽象地反映数据元素之间的逻辑关系，与计算机中的存储无关两个要素：数据元素的集合，通常记为D；前后件关系，通常记为R一个数据结构B可以表示为(P12)B=（D，R）,27,1.2.1 什么是数据结构,5数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式常用的存储结构：顺序链式索引一种数据结构可根据需要采用不同的存储结构。采用不同的存储结构，其数据处理的效率是不同,28,例如，如果把一年四季看作一个数据结构，则可表示成B=（D,R）D=春季，夏季，秋季，冬季R=（春季，夏季）,（夏季，秋季），（秋季，冬季）,29,1.2.2 数据结构的图形表示,数据结点：用方框表示根结点、终端结点前后件关系：用有向线段表示基本运算：插入运算删除运算查找、分类、合并、分解、复制、修改、,30,1.2.3 线性结构与非线性结构,空的数据结构：一个数据元素都没有线性结构如果一个非空数据结构满足下列两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。常见的线性结构有：线性表、栈与队列、线性链表非线性结构如果一个数据结构不是线性结构常见的非线性结构有：树、二叉树、图,31,习题,下列叙述中，错误的是A）数据的存储结构与数据处理的效率密切相关B）数据的存储结构与数据处理的效率无关C）数据的存储结构在计算机中所占的空间不一定是连续的D）一种数据的逻辑结构可以有多种存储结构解析：一般来说，一种数据结构根据需要可以表示成多种存储结构。常用的存储结构有顺序、链接、索引等，而采用不同的存储结构，其数据处理的效率是不同的；一个数据结构中的各数据元素在计算机存储空间中的位置关系与逻辑关系是有可能不同的。,32,习题,线性表若采用链式存储结构时，要求内存中可用存储单元的地址A）必须是连续的 B）部分地址必须是连续的C）一定是不连续的 D）连续不连续都可以解析：在链式存储结构中，存储数据结构的存储空间可以是连续的，也可以是不连续的，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。,33,习题,根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成A）动态结构和静态结构B）紧凑结构和非紧凑结构C）线性结构和非线性结构 D）内部结构和外部结构【命题目的】考查考生对数据结构分类的理解。【解题要点】根据数据结构中各数据元素之间前后件关系的复杂程序，一般将数据结构分为两大类：线性结构和非线性结构。线性结构是指满足以下两个条件的非空的数据结构：一是有且只有一个根结点，二是每一个结点最多有一个前件，也最多有一个后件。如是一个数据结构不是线性结构，则称为非线性结构。,34,习题,数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及A）数据的存储结构 B）计算方法C）数据映象D）逻辑存储解析：数据结构是研究数据元素及其之间的相互关系和数据运算的一门学科，它包含3个方面的内容，即数据的逻辑结构、存储结构和数据的运算。,35,习题,数据结构中，与所使用的计算机无关的是数据的A）存储结构B）物理结构C）逻辑结构D）物理和存储结构解析：数据结构概念一般包括3个方面的内容，数据的逻辑结构、存储结构及数据上的运算集合。数据的逻辑结构只抽象的反映数据元素之间的逻辑关系，而不管它在计算机中的存储表示形式。,36,习题,数据的逻辑结构有线性结构和【1】两大类。解析：数据的逻辑结构有线性结构和非线性结构两大类,1.3 线性表及其顺序存储结构,38,1.3.1 线性表的基本概念,线性表：由n(n0)个相同类型数据元素构成的有限序列：n定义为线性表的表长；n=0 时的线性表被称为空表。称i为在线性表中的位序。例如：英文大写字母表（A，B，C，D，E，F，X，Y，Z）同一花色的13张扑克牌(2,3,4,5,6,7,8,9,10,J,Q,K,A),39,1.3.1 线性表的基本概念,线性表的结构特征数据元素在表中的位置由序号决定，数据元素之间的相对位置是线性的；对于一个非空线性表，有且只有一个根结点a1，它无前件，有且只有一个终端结点an，它无后件，除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表的存储结构顺序存储链式存储,40,1.3.2 线性表的顺序存储结构,两个基本特点：线性表中所有元素所占的存储空间是连续的。线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。存储示意图,41,1.3.3 顺序表的插入运算,42,1.3.4 顺序表的删除运算,43,顺序表的插入和删除分析,插入算法的分析假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：删除算法的分析在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：分析结论顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑,44,习题,线性表的顺序存储结构和线性表的链式存储结构分别是A）顺序存取的存储结构、顺序存取的存储结构B）随机存取的存储结构、顺序存取的存储结构C）随机存取的存储结构、随机存取的存储结构D）任意存取的存储结构、任意存取的存储结构【命题目的】考查有关线性表存储结构的基本知识。【解题要点】顺序存储结构中，数据元素存放在一组地址连续的存储单元中，每个数据元素地址可通过公式LOC（ai）=LOC（a1）+（i-1）L计算得到，从而实现了随机存取。对于链式存储结构，要对某结点进行存取，都得从链的头指针指向的结点开始，这是一种顺序存取的存储结构。,45,习题,下列叙述中正确的是A）线性表是线性结构B）栈与队列是非线性结构C）线性链表是非线性结构D）二叉树是线性结构解析：线性表是一种线性结构，数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的；栈、队列、线性链表实际上也是线性表，故也是线性结构；树是一种简单的非线性结构。,46,习题,度为n的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为【1】。解析：在线性表的任何位置插入一个元素的概率相等，即概率为p=1/（n+1），则插入一个元素时所需移动元素的平均次数为E=1/（n+1）n+1 n=1（n-i+1）=n/2。,47,习题,线性表L=(a1,a2,a3,ai，an)，下列说法正确的是A）每个元素都有一个直接前件和直接后件B）线性表中至少要有一个元素C）表中诸元素的排列顺序必须是由小到大或由大到小D）除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件解析：线性表可以为空表；第一个元素没有直接前件，最后一个元素没有直接后件；线性表的定义中，元素的排列并没有规定大小顺序。,48,习题,线性表若采用链式存储结构时，要求内存中可用存储单元的地址A）必须是连续的B）部分地址必须是连续的C）一定是不连续的 D）连续不连续都可以解析：在链式存储结构中，存储数据结构的存储空间可以是连续的，也可以是不连续的，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。,1.4 栈和队列,50,1.4.1 栈及其基本运算,1栈的定义栈（stack）：一种只允许在表的一端进行插入或删除操作的特殊的线性表栈顶(top)：允许进行插入与删除操作的一端栈底(bottom)：不允许插入与删除操作的另一端先进后出（FILO）或后进先出(LIFO)的线性表,51,1.4.1 栈及其基本运算,2栈的顺序存储及其运算top=0：栈空 top=m：栈满栈的基本运算 入栈运算退栈运算读栈顶元素,52,1.4.2 队列及其基本运算,1队列的定义限定只能在表的一端进行插入和在另一端进行删除操作的线性表队尾(rear)：允许插入的一端队头(front)：允许删除的另一端先进先出（FIFO）表或后进后出（LILO）线性表基本操作入队运算：往队列的队尾插入一个元素，队尾指针rear的变化退队运算：从队列的排头删除一个元素，队头指针front的变化,53,1.4.2 队列及其基本运算,2循环队列及其运算队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用 入队运算：队尾指针加1，并当rear=m+1时置rear=1出队运算：队头指针加1，并当front=m+1时置front=1,54,习题,栈和队列的共同特点是A）都是先进先出B）都是先进后出C）只允许在端点处插入和删除元素 D）没有共同点解析：栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。二者的区别是：栈只允许在表的一端进行插入或删除操作，是一种后进先出的线性表；而队列只允许在表的一端进行插入操作，在另一端进行删除操作，是一种先进先出的线性表。,55,习题,如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是A）e3,e1,e4,e2B）e2,e4,e3,e1C）e3,e4,e1,e2D）任意顺序解析：由栈后进先出的特点可知：A）中e1不可能比e2先出，C）中e3不可能比e4先出，且e1不可能比e2先出，D）中栈是先进后出的，所以不可能是任意顺序。B）中出栈过程如图所示：,56,习题,栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是A）ABCEDB）DCBEAC）DBCEA D）CDABE解析：栈操作原则上“后进先出”，栈底至栈顶依次存放元素A、B、C、D，则表明这4个元素中D是最后进栈，B、C处于中间，A最早进栈。所以出栈时一定是先出D，再出C，最后出A。,57,习题,下列数据结构中，按先进后出原则组织数据的是A）线性链表B）栈C）循环链表D）顺序表【命题目的】本题主要考查对于栈的理解。【解题要点】栈是限定在一端进行插入与删除的线性表。在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素，即栈是按照“先进后出”或“后进先出”的原则组织数据的。,58,习题,以下不是栈的基本运算的是A 删除栈顶元素 B 删除栈底元素C 判断栈是否为空 D 将栈置为空栈,59,习题,栈通常采用的两种存储结构是A）线性存储结构和链表存储结构B）散列方式和索引方式C）链表存储结构和数组（还需要其他信息，不仅是数组）D）线性存储结构和非线性存储结构【命题目的】考查栈的存储结构的基本知识。【解题要点】和线性表类似，栈也有两种存储方法，一是顺序栈，二是链式栈。栈的顺序存储结构是利用一组地址连续的存储单元一次存储自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素的位置，由于栈的操作是线性表操作的特例，相对而言，链式栈的操作更易于实现。,60,习题,已知一个栈的进栈序列为1、2、3.n，出栈序列第一个是3，则第二个是可能是1一定是1可能是2一定是2,61,习题,栈的初始状态为空，6个元素的入栈顺序为1、2、3、4、5、6，若出栈顺序为2、4、3、6、5、1，则该栈的容量至少是,1.5 线性链表,63,1.5.1 线性链表的基本概念,1线性表顺序存储的缺点插入或删除的运算效率很低。在顺序存储的线性表中，插入或删除数据元素时需要移动大量的数据元素。线性表的顺序存储结构下，线性表的存储空间不便于扩充。线性表的顺序存储结构不便于对存储空间的动态分配。,64,1.5.1 线性链表的基本概念,2线性链表线性表的链式存储结构物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接来实现的每个结点由两部分组成：数据域和指针域,65,1.5.1 线性链表的基本概念,双向链表：每个结点设置两个指针左指针：指向其前件结点右指针：指向其后件结点,66,1.5.2 线性链表的基本运算,插入删除合并分解逆转复制排序查找,67,1.5.2 线性链表的基本运算,1在线性链表中查找指定元素链表不是随机存取结构从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止2线性链表的插入,68,1.5.2 线性链表的基本运算,3线性链表的删除与顺序存储相比，链表的优点有：插入和删除元素时，不需要移动数据元素，只需要修改指针即可,69,1.5.3 栈和队列的链式存储结构,1栈的链式存储结构链栈,70,1.5.3 栈和队列的链式存储结构,2队列链式存储结构链队列,71,1.5.4 循环链表及其基本运算,循环链表特点：在链表中增加了一个表头结点最后一个结点的指针域指向表头结点，构成了一个环状链循环链表优点：从任一结点出发来访问表中其他所有结点空表与非空表的运算的统一,72,习题,非空的循环单链表head的尾结点（由p所指向），满足A）p-next=NULL B）p=NULLC）p-next=head D）p=head解析：循环链表就是将链表的最后一个结点指向链表头结点（或第一个结点），即p-next=head。,73,习题,循环链表的主要优点是A）不再需要头指针了B）从表中任一结点出发都能访问到整个链表C）在进行插入、删除运算时，能更好的保证链表不断开D）已知某个结点的位置后，能够容易的找到它的直接前件解析：循环链表就是将单向链表中最后一个结点的指针指向头结点，使整个链表构成一个环形，这样的结构使得从表中的任一结点出发都能访问到整个链表。,74,习题,链表不具有的特点是A）不必事先估计存储空间 B）可随机访问任一元素C）插入删除不需要移动元素D）所需空间与线性表长度成正比解析：链表采用的是链式存储结构，它克服了顺序存储结构的缺点：它的结点空间可以动态申请和释放；它的数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素。但是链式存储结构也有不足之处：每个结点中的指针域需额外占用存储空间；链式存储结构是一种非随机存储结构。,75,习题,当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为【2】。【命题目的】本题考查了队列的基本性质。【解题要点】入队运算是指在循环队列的队尾加入一个新元素。这个运算有两个基本操作：首先将队尾指针进一（即rear=rear+1），并当rear=m+1时置rear=1；然后将新元素插入队尾指针指向的位置。当循环队列非空（s=1）时且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算，这种情况称为“上溢”。,76,1.6 树与二叉树,1树的定义树(Tree)是n(n0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：（1）有且仅有一个特定的称为根(Root)的结点；（2）其余的结点可分为m(m0)个互不相交的子集T1，T2，T3，Tm，其中每个子集又是一棵树，并称其为子树。,77,1.6 树与二叉树,2树中的基本概念父结点与树的根：每个结点最多只允许有一个前件，称为该结点的父结点。没有前件的结点中有一个，称为树的根结点。子结点与叶子结点：在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。结点的度和树的度：一个结点所拥有后件个数称为该结点的度。一棵树中各个结点度数的最大值叫做这棵树的度。层和树的深度：树结构是一种层次结构，根结点为第一层，根的子结点为第二层，其余各结点的层数逐层由上而下计算。一棵树中结点的最大层数叫做此树的深度。,78,1.6.1 树的基本概念,树的特点（1）树中只有根结点没有前件；（2）除根外，其余结点都有且仅一个前件；（3）树的结点，可以有零个或多个后件；（4）除根外的其他结点，都存在唯一条从根到该结点的路径；（5）树是一种分支结构（除根的结点外）每个元素都有且仅有一个直接前件，有且仅有零个或多个直接后件。树的存储用多重链表来表示,79,1.6.2 二叉树及其基本性质,1二叉树的定义一个二叉树是n个结点的有限集合（n0），此集合或者是空集（n=0），或者是由一个根结点及两棵互不相交的、分别称为左子树和右子树的二叉树组成，并且左右子树都是二叉树。特点：非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。,80,1.6.2 二叉树及其基本性质,2二叉树的性质性质1 在二叉树的第k层上，最多有 个结点。性质2 深度为m的二叉树最多有个 结点。性质3 在任意一棵二叉树中，度数为0的结点（即叶子结点）总比度为2的结点多一个。即：其中，n0表示度数为0的结点数，n2表示度数为2的结点数。性质4 具有n个结点的二叉树的深度至少为，其中 表示取 的整数部分。,81,1.6.1 树的基本概念,82,1.6.2 二叉树及其基本性质,3满二叉树和完全二叉树满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。,83,1.6.2 二叉树及其基本性质,性质5 具有n个结点的完全二叉树深度为。性质6 设完全二叉树共有n个结点，如果从根结点开始，按层序（每一层从左到右）用自然数1，2，n给结点进行编号，则对于编号为k（k=1，2，n）的结点有以下结论：若k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点的编号为INT(k/2)。若2kn，则编号为k的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。若2k+1n，则编号为k的右子结点编号为2k+1；否则该结点无右子结点。,84,1.6.3 二叉树的存储结构,普通二叉树采用链式存储结构存储结点由两部分组成：数据域与指针域两个指针域：左指针域右指针域满二叉树与完全二叉树采用顺序存储结构,85,1.6.4 二叉树的遍历,二叉树的遍历：不重复地访问二叉树中的所有结点 1前序遍历（DLR）首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。2中序遍历（LDR）首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树3后序遍历（LRD）首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。,86,1.6.4 二叉树的遍历,前序遍历：A、B、D、G、C、E、F中序遍历：D、G、B、A、E、C、F 后序遍历：G、D、B、E、F、C、A,87,习题,已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是A）acbedB）decabC）deabcD）cedba解析：依据后序遍历序列可确定根结点为c；再依据中序遍历序列可知其左子树由deba构成，右子树为空；又由左子树的后序遍历序列可知其根结点为e，由中序遍历序列可知其左子树为d，右子树由ba构成，,88,已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为A）GEDHFBCAB）DGEBHFCAC）ABCDEFGHD）ACBFEDHG解析：利用前序和中序遍历的方法可以确定二叉树的结构，具体步骤如下：前序遍历的第一个结点A为树的根结点；中序遍历中A的左边的结点为A的左子树，A右边的结点为A的右子树；再分别对A的左右子树进行上述两步处理，直到每个结点都找到正确的位置。,89,习题,树是结点的集合，它的根结点数目是A）有且只有1B）1或多于1C）0或1D）至少2解析：树是一个或多个结点组成的有限集合，其中一个特定的结点称为根，其余结点分为若干个不相交的集合。每个集合同时又是一棵树。树有且只有1个根结点。,90,习题,在深度为5的满二叉树中，叶子结点的个数为A）32 B）31 C）16 D）15解析：所谓满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个叶子结点。这就是说，在满二叉树中，层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。,91,习题,具有3个结点的二叉树有A）2种形态B）4种形态C）7种形态D）5种形态【命题目的】考查二叉树的基础知识。【解题要点】具有3个结点的二叉树具有以下的几种形态：,92,习题,设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为A）12 B）13C）14 D）15【命题目的】本题考查二叉树的基本概念及其基本性质。,93,设有下列二叉树：对此二叉树前序遍历的结果为A）ZBTYCPXAB）ATBZXCYPC）ZBTACYXPD）ATBZXCPY【命题目的】本题考查二叉树的遍历。【解题要点】所谓二叉树的前序遍历（DLR）是指在访问根结点、遍历左子树与遍历右子树这3者中，首先访问根结点，然后遍历左子树，最后遍历右子树，并且，在遍历左右子树时，上述规则同样适用，即根左右。故该二叉树的前序遍历结果为ATBZXCYP。,习题,94,习题,在树形结构中，树根结点没有【1】。解析：在树形结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点；每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。,95,习题,完全二叉树有n个结点，则有多少个叶子结点、度为1的结点、最底层有多少个叶子、倒数第二层有多少个叶子？如n、m是二叉树的两个结点，在中序遍历中，n在m前的条件是n在m的右子树上n在m的左子树上n是m祖先n是m子孙深度为h的二叉树上只有度为0和2的结点，则此二叉树中结点数至少是2h2h+12h-1h+1某二叉树的先序遍历和后序遍历序列正好相反，则该二叉树一定是空或只有一个结点完全二叉树二叉排序树深度等于结点数,1.7 查找技术,97,1.7 查找技术,查找（Searching）：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。查找结果：查找成功：找到查找不成功：没找到平均查找长度：查找过程中关键字和给定值比较的平均次数,98,1.7.1 顺序查找,基本思想：从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。平均要与表中一半以上元素进行比较，最坏情况下需要比较n次。下列两种情况下只能采用顺序查找：如果线性表是无序表（即表中的元素是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。,99,1.7.2 二分法查找,思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。前提：必须在具有顺序存储结构的有序表中进行。查找过程：1）若中间项的值等于x,则说明已查到。2）若x小于中间项的值，则在线性表的前半部分查找；3）若x大于中间项的值，则在线性表的后半部分查找。特点：比顺序查找方法效率高。最坏的情况下，需要比较 log2n次。,100,1.7.2 二分法查找,例：查找元素22过程：,1.8 排序技术,102,1.8.1 交换类排序法,基本思想两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。方法冒泡排序快速排序,103,1.冒泡排序,基本思想对存放原始数据的数组，按从后往前的方向进行多次扫描，当发现相邻两个数据的次序与排序要求的“递增次序”不符合时，即将这两个数据进行互换。这样，较小的数据就会逐单元向前移动，好象气泡向上浮起一样。性能分析假设线性表的长度n，则在最坏情况下，需要的比较次数为n(n-1)/2。,104,1.冒泡排序,105,2快速排序,基本思想任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。快速排序的平均时间复杂度为O(nlog2n)。,106,2快速排序,107,1.8.2 插入类排序法,基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。方法:简单插入排序希尔排序,108,1简单插入排序法,基本思想：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。在最坏的情况下，需要n(n-1)/2次比较。,109,1简单插入排序法,110,2希尔排序,基本思想先将整个待排元素序列分割成若干个子序列（由相隔某个增量h的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。增量序列一般取，其中n为待排序序列的长度在最坏情况下，希尔排序的时间复杂度为,111,2希尔排序,112,1.8.3 选择类排序法,基本思想：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子序列的最后，直到全部记录排序完毕。方法：简单选择排序堆排序,113,1简单选择排序法,基本思想：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。最坏情况下，需要比较n(n-1)/2次。,114,1简单选择排序法,115,2堆排序法,堆的定义具有n个元素的序列，当且仅当满足 或 时称之为堆。称为大根堆；称为小根堆。,116,2堆排序法,建堆在建堆的过程中，总是将根结点值与左、右子树的根结点值进行比较，若不满足堆的条件，则将左、右子树根结点值中的大者与根结点值进行交换。这个调整过程一直做到所有子树均为堆为止。堆排序（1）首先将一个无序序列建成堆。（2）然后将堆顶元素(序列中的最大项)与堆中最后一个元素交换(最大项应该在序列的最后)。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序列，将该子序列调整为堆。反复做步骤（2），直到剩下的子序列空为止。在最坏情况下，堆排序法需要比较的次数为O(nlog2n)。,117,各种排序法比较,典型考题分析,119,【例1-1】问题处理方案的正确而完整的描述称为。（2005年4月）答案 算法,120,【例1-2】算法复杂度主要包括时间复杂度和 复杂度。（2005年9月）答案 空间,121,【例1-3】算法的时间复杂度是指_。A）执行算法程序所需要的时间B）算法程序的长度C）算法执行过程中所需要的基本运算次数D）算法程序中的指令条数答案C,122,【例1-4】算法的空间复杂度是指_。A）算法程序的长度B）算法程序中的指令条数C）算法程序所占的存储空间D）算法执行过程中所需要的存储空间答案D,123,【例1-5】下列叙述中正确的是。（2006年9月）A）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间可复杂度必定小D）上述三种说法都不对答案 D,124,【例1-6】下列叙述中正确的是。（2005年9月）A）一个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率答案 D,125,【例1-7】数据结构分为逻辑结构和存储结构，循环队列属于 结构。（2005年9月）答案 逻辑,126,【例1-8】数据结构分为线性结构和非线性结构，带链的队列属于。（2006年9月）答案 线性结构,127,【例1-9】下列叙述中正确的是_。（2006年4月）A）线性链表是线性表的链式存储结构B）栈