二级公共基础- ppt课件

1、二级公共根底知识二级公共根底知识第一章第一章 数据构造根底数据构造根底内容提要内容提要 n算法算法: :算法的根本概念、算法复杂度算法的根本概念、算法复杂度n数据构造的根本概念：什么是数据构造、数据构造的根本概念：什么是数据构造、 数据构造的图数据构造的图形表示、形表示、 线性构造与非线性构造线性构造与非线性构造n线性表及其顺序存储构造：线性表的根本概念、线性表及其顺序存储构造：线性表的根本概念、 顺序存顺序存储构造、插入运算、删除运算储构造、插入运算、删除运算n栈和队列：栈及其根本运算、队列及其根本运算栈和队列：栈及其根本运算、队列及其根本运算n线性链表：根本概念、根本运算、循环链表及其根本

2、运算线性链表：根本概念、根本运算、循环链表及其根本运算n树与二叉树：树的根本概念、二叉树及其根本性质、树与二叉树：树的根本概念、二叉树及其根本性质、 二二叉树的存储构造、二叉树的遍历叉树的存储构造、二叉树的遍历n查找技术：查找技术： 顺序查找、二分法查找顺序查找、二分法查找n排序技术：交换类排序法、排序技术：交换类排序法、 插入类排序法、选择类排序插入类排序法、选择类排序法法1.1 1.1 算法算法1.1.1 1.1.1 算法的根本概念算法的根本概念n算法是解题方案的准确而完好的描画，它不等于程序，也算法是解题方案的准确而完好的描画，它不等于程序，也不等计算方法。不等计算方法。n1 1算法的根

3、本特征算法的根本特征n可行性可行性(effectiveness)(effectiveness)n确定性确定性(definiteness)(definiteness)n有穷性有穷性(finiteness)(finiteness)n拥有足够的情报拥有足够的情报n2 2算法的根本要素算法的根本要素n算法中对数据的运算和操作算法中对数据的运算和操作n算术运算算术运算: :包括加、减、乘、除等包括加、减、乘、除等n逻辑运算逻辑运算: :包括包括“与、与、“或、或、“非等运算非等运算n关系运算关系运算: :包括包括“大于、大于、“小于、小于、“等于、等于、“不等于不等于等等n数据传输数据传输: :包括赋值

4、、输入、输出等操作包括赋值、输入、输出等操作n算法的控制构造算法的控制构造1.1.1 1.1.1 算法的根本概念算法的根本概念n3 3算法设计的根本方法算法设计的根本方法n列举法列举法n归纳法归纳法n递推递推n递归递归n减半递推技术减半递推技术n回溯法回溯法1.1.2 1.1.2 算法复杂度算法复杂度n算法复杂度：时间复杂度、空间复杂度算法复杂度：时间复杂度、空间复杂度n1 1算法的时间复杂度算法的时间复杂度n执行算法所需求的计算任务量执行算法所需求的计算任务量n与以下要素有关：与以下要素有关：n书写算法的程序设计言语书写算法的程序设计言语n编译产生的机器言语，代码质量编译产生的机器言语，代码

5、质量n机器执行指令的速度机器执行指令的速度n问题的规模问题的规模1.1.2 1.1.2 算法复杂度算法复杂度n问题的规模函数问题的规模函数n算法的任务量算法的任务量=f(n)=f(n)n算法中根本操作反复执行的频率算法中根本操作反复执行的频率T(n)T(n)，是问题规，是问题规模模n n的某个函数的某个函数f(n)f(n)，记作：，记作：nT(n)=O(f(n)T(n)=O(f(n)n记号记号“O O读作读作“大大O O。表示随问题规模。表示随问题规模n n的添加，的添加，算法执行时间的增长率和算法执行时间的增长率和f(n)f(n)相应添加。相应添加。n常见算法复杂度：常见算法复杂度：nO(1

6、)O(1)：常数阶：常数阶 O(n) O(n)：作线性阶：作线性阶 O(n2) O(n2)：平方阶平方阶nO(n3)O(n3)：立方阶：立方阶 O(logn) O(logn)：对数阶：对数阶 O(2n) O(2n)：指数阶指数阶1.1.2 1.1.2 算法复杂度算法复杂度nn nn n矩阵相乘算法：矩阵相乘算法：n时间复杂度为时间复杂度为O(n3)O(n3)。1.1.2 1.1.2 算法复杂度算法复杂度n分析算法的任务量两种方法：分析算法的任务量两种方法：n平均性态平均性态n最坏情况复杂性最坏情况复杂性1.1.2 1.1.2 算法复杂度算法复杂度n2算法的空间复杂度n算法执行过程中所需的最大存

7、储空间n存储量包括以下三部分n算法程序所占的空间n输入的初始数据所占的存储空间n算法执行过程中所要的额外空间n算法空间复杂度可定义为：nS(n)=O(f(n)n原地任务(in place)的算法：记作O(1)n紧缩存储技术1.2 1.2 数据构造的根本概念数据构造的根本概念1.2.1 1.2.1 什么是数据构造什么是数据构造n1 1数据构造研讨的主要内容数据构造研讨的主要内容n数据的逻辑构造数据的逻辑构造n数据的存储构造数据的存储构造n对各种数据构造进展的运算对各种数据构造进展的运算n2 2研讨数据构造目的研讨数据构造目的n提高数据处置的速度提高数据处置的速度n尽量节省在数据处置过程中所占用的

8、计算尽量节省在数据处置过程中所占用的计算机存储空间机存储空间1.2.1 1.2.1 什么是数据构造什么是数据构造n1 1数据构造研讨的主要内容数据构造研讨的主要内容n数据的逻辑构造数据的逻辑构造n数据的存储构造数据的存储构造n对各种数据构造进展的运算对各种数据构造进展的运算n2 2研讨数据构造目的研讨数据构造目的n提高数据处置的速度提高数据处置的速度n尽量节省在数据处置过程中所占用的计算尽量节省在数据处置过程中所占用的计算机存储空间机存储空间1.2.1 1.2.1 什么是数据构造什么是数据构造 1数据的逻辑构造 2、数据的存储构造 3、数据的运算：检索、排序、插入、删除、修正等。 A线性构造

9、B非线性构造A 顺序存储 B 链式存储 线性表栈队树形构造图形构造数据构造的三个方面 1.2.1 1.2.1 什么是数据构造什么是数据构造n3数据构造的定义n相互有关联的数据元素的集合n数据元素之间的关系可以用前后件关系来描画n一个数据构造应包含以下两方面信息：n表示数据元素的信息 n表示各数据元素之间的前后件关系1.2.1 1.2.1 什么是数据构造什么是数据构造n4 4数据的逻辑构造数据的逻辑构造n对数据元素之间的逻辑关系的描画对数据元素之间的逻辑关系的描画n只笼统地反映数据元素之间的逻辑关系，只笼统地反映数据元素之间的逻辑关系，与计算机中的存储无关与计算机中的存储无关n两个要素：两个要素

10、：n数据元素的集合，通常记为数据元素的集合，通常记为D D；n前后件关系，通常记为前后件关系，通常记为R Rn一个数据构造一个数据构造B B可以表示为：可以表示为：nB=B=D D，R R1.2.1 1.2.1 什么是数据构造什么是数据构造n5 5数据的存储构造数据的存储构造n数据的逻辑构造在计算机存储空间中的存数据的逻辑构造在计算机存储空间中的存放方式放方式n常用的存储构造：常用的存储构造：n顺序顺序n链式链式n索引索引n一种数据构造可根据需求采用不同的存储一种数据构造可根据需求采用不同的存储构造。采用不同的存储构造，其数据处置构造。采用不同的存储构造，其数据处置的效率是不同的效率是不同1.

11、2.2 1.2.2 数据构造的图形表示数据构造的图形表示n数据结点：用方框表示数据结点：用方框表示n根结点、终端结点根结点、终端结点n前后件关系：用有向线段表示前后件关系：用有向线段表示n根本运算：根本运算：n插入运算插入运算n删除运算删除运算n查找、分类、合并、分解、复制、修正、查找、分类、合并、分解、复制、修正、1.2.3 1.2.3 线性构造与非线性构造线性构造与非线性构造n空的数据构造：一个数据元素都没有空的数据构造：一个数据元素都没有n线性构造线性构造n假设一个非空数据构造满足以下两个条件：假设一个非空数据构造满足以下两个条件：n有且只需一个根结点；有且只需一个根结点；n每一个结点最

12、多有一个前件，也最多有一每一个结点最多有一个前件，也最多有一个后件。个后件。n常见的线性构造有：线性表、栈与队列、常见的线性构造有：线性表、栈与队列、线性链表线性链表n非线性构造非线性构造n假设一个数据构造不是线性构造假设一个数据构造不是线性构造n常见的非线性构造有：树、二叉树、图常见的非线性构造有：树、二叉树、图1.3 1.3 线性表及其顺序存储构造线性表及其顺序存储构造1.3.1 1.3.1 线性表的根本概念线性表的根本概念n线性表：由线性表：由n(n0)n(n0)个一样类型数据元素构成的有个一样类型数据元素构成的有限序列：限序列：nn n定义为线性表的表长；定义为线性表的表长；n=0 n

13、=0 时的线性表被称为空时的线性表被称为空表。称表。称i i为在线性表中的位序。为在线性表中的位序。n例如：例如：n英文大写字母表英文大写字母表nA A，B B，C C，D D，E E，F F，XX，Y Y，Z Zn同一花样的同一花样的1313张扑克牌张扑克牌 n(2,3,4,5,6,7,8,9,10,J,Q,K,A)(2,3,4,5,6,7,8,9,10,J,Q,K,A),(21niaaaa1.3.1 1.3.1 线性表的根本概念线性表的根本概念n线性表的构造特征线性表的构造特征n数据元素在表中的位置由序号决议，数据数据元素在表中的位置由序号决议，数据元素之间的相对位置是线性的；元素之间的相

14、对位置是线性的；n对于一个非空线性表，有且只需一个根结对于一个非空线性表，有且只需一个根结点点a1a1，它无前件，有且只需一个终端结点，它无前件，有且只需一个终端结点anan，它无后件，除根结点与终端结点外，它无后件，除根结点与终端结点外，其他一切结点有且只需一个前件，也有且其他一切结点有且只需一个前件，也有且只需一个后件。只需一个后件。n线性表的存储构造线性表的存储构造n顺序存储顺序存储n链式存储链式存储1.3.2 1.3.2 线性表的顺序存储构造线性表的顺序存储构造n两个根本特点：两个根本特点：n线性表中一切元素所占的存储空间是延续的。线性表中一切元素所占的存储空间是延续的。n线性表中各数

15、据元素在存储空间中是按逻辑顺序依次存线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。放的。n存储表示图存储表示图kiaLocaLoci*) 1()()(11.3.3 1.3.3 顺序表的插入运算顺序表的插入运算1.3.4 1.3.4 顺序表的删除运算顺序表的删除运算顺序表的插入和删除分析顺序表的插入和删除分析n插入算法的分析插入算法的分析n假设线性表中含有假设线性表中含有n n个数据元素，在进展插入操作时，假设假定在个数据元素，在进展插入操作时，假设假定在n+1n+1个位置上插入元素的能够性均等，那么平均挪动元素的个数为：个位置上插入元素的能够性均等，那么平均挪动元素的个数为：n删除算法

16、的分析删除算法的分析n在进展删除操作时，假设假定删除每个元素的能够性均等，那么平均在进展删除操作时，假设假定删除每个元素的能够性均等，那么平均挪动元素的个数为：挪动元素的个数为：n分析结论分析结论n顺序存储构造表示的线性表，在做插入或删除操作时，平均需求挪动顺序存储构造表示的线性表，在做插入或删除操作时，平均需求挪动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需求值得思索做插入或删除操作时，这一点需求值得思索niidlninpnE121)(1112) 1(11niiisninpnE1.4 1.

17、4 栈和队列栈和队列1.4.1 1.4.1 栈及其根本运算栈及其根本运算n1 1栈的定义栈的定义n栈栈stackstack：一种只允许在表的一端进展插入或：一种只允许在表的一端进展插入或删除操作的特殊的线性表删除操作的特殊的线性表n栈顶栈顶(top) (top) ：允许进展插入与删除操作的一端：允许进展插入与删除操作的一端n栈底栈底(bottom)(bottom)：不允许插入与删除操作的另一端：不允许插入与删除操作的另一端n先进后出先进后出FILOFILO或后进先出或后进先出(LIFO)(LIFO)的线性表的线性表1.4.1 1.4.1 栈及其根本运算栈及其根本运算n2栈的顺序存储及其运算nt

18、op=0：栈空 top=m：栈满n栈的根本运算 n入栈运算n退栈运算n读栈顶元素1.4.2 1.4.2 队列及其根本运算队列及其根本运算n1 1队列的定义队列的定义n限定只能在表的一端进展插入和在另一端进展删除操作的限定只能在表的一端进展插入和在另一端进展删除操作的线性表线性表n队尾队尾(rear)(rear)：允许插入的一端：允许插入的一端n队头队头(front)(front)：允许删除的另一端：允许删除的另一端n先进先出先进先出FIFOFIFO表或后进后出表或后进后出LILOLILO线性表线性表n根本操作根本操作n入队运算：往队列的队尾插入一个元素，队尾指针入队运算：往队列的队尾插入一个元

19、素，队尾指针rearrear的的变化变化n退队运算：从队列的排头删除一个元素，队头指针退队运算：从队列的排头删除一个元素，队头指针frontfront的变化的变化1.4.2 1.4.2 队列及其根本运算队列及其根本运算n2 2循环队列及其运算循环队列及其运算n队列存储空间的最后一个位置绕到第一个位置，构成逻辑队列存储空间的最后一个位置绕到第一个位置，构成逻辑上的环状空间，供队列循环运用上的环状空间，供队列循环运用 n入队运算入队运算 ：队尾指针加：队尾指针加1 1，并当，并当rear=m+1rear=m+1时置时置rear=1rear=1n出队运算：队头指针加出队运算：队头指针加1 1，并当，

20、并当front=m+1front=m+1时置时置front=1front=11.5 1.5 线性链表线性链表1.5.1 1.5.1 线性链表的根本概念线性链表的根本概念n1 1线性表顺序存储的缺陷线性表顺序存储的缺陷n插入或删除的运算效率很低。在顺序存储插入或删除的运算效率很低。在顺序存储的线性表中，插入或删除数据元素时需求的线性表中，插入或删除数据元素时需求挪动大量的数据元素。挪动大量的数据元素。n线性表的顺序存储构造下，线性表的存储线性表的顺序存储构造下，线性表的存储空间不便于扩展。空间不便于扩展。n线性表的顺序存储构造不便于对存储空间线性表的顺序存储构造不便于对存储空间的动态分配。的动态

21、分配。1.5.1 1.5.1 线性链表的根本概念线性链表的根本概念n2 2线性链表线性链表n线性表的链式存储构造线性表的链式存储构造n物理存储单元上非延续、非顺序的存储构物理存储单元上非延续、非顺序的存储构造，数据元素的逻辑顺序是经过链表中的造，数据元素的逻辑顺序是经过链表中的指针链接来实现的指针链接来实现的n每个结点由两部分组成：数据域和指针域每个结点由两部分组成：数据域和指针域1.5.1 1.5.1 线性链表的根本概念线性链表的根本概念n双向链表：每个结点设置两个指针双向链表：每个结点设置两个指针n左指针：指向其前件结点左指针：指向其前件结点n右指针：指向其后件结点右指针：指向其后件结点1

22、.5.2 1.5.2 线性链表的根本运算线性链表的根本运算n插入插入n删除删除n合并合并n分解分解n逆转逆转n复制复制n排序排序n查找查找1.5.2 1.5.2 线性链表的根本运算线性链表的根本运算n1 1在线性链表中查找指定元素在线性链表中查找指定元素n链表不是随机存取构造链表不是随机存取构造n从链表的头指针出发，顺着链域从链表的头指针出发，顺着链域nextnext逐个逐个结点往下搜索，直至搜索到第结点往下搜索，直至搜索到第i i个结点为止个结点为止n2 2线性链表的插入线性链表的插入1.5.2 1.5.2 线性链表的根本运算线性链表的根本运算n3 3线性链表的删除线性链表的删除n与顺序存储

23、相比，链表的优点有：与顺序存储相比，链表的优点有：n插入和删除元素时，不需求挪动数据元素，插入和删除元素时，不需求挪动数据元素，只需求修正指针即可只需求修正指针即可 1.5.3 1.5.3 栈和队列的链式存储构造栈和队列的链式存储构造 n1栈的链式存储构造链栈1.5.3 1.5.3 栈和队列的链式存储构造栈和队列的链式存储构造 n2队列链式存储构造链队列1.5.4 1.5.4 循环链表及其根本运算循环链表及其根本运算n循环链表特点：循环链表特点：n在链表中添加了一个表头结点在链表中添加了一个表头结点n最后一个结点的指针域指向表头结点，构成了一最后一个结点的指针域指向表头结点，构成了一个环状链个

24、环状链n循环链表优点：循环链表优点：n从任一结点出发来访问表中其他一切结点从任一结点出发来访问表中其他一切结点n空表与非空表的运算的一致空表与非空表的运算的一致 1.6 1.6 树与二叉树树与二叉树n1树的定义n树(Tree)是n(n0)个结点的有限集T，T为空时称为空树，否那么它满足如下两个条件：n1有且仅有一个特定的称为根(Root)的结点；n2其他的结点可分为m(m0)个互不相交的子集T1，T2，T3，Tm，其中每个子集又是一棵树，并称其为子树。1.6 1.6 树与二叉树树与二叉树n2 2树中的根本概念树中的根本概念n父结点与树的根：每个结点最多只允许有一个前父结点与树的根：每个结点最多

25、只允许有一个前件，称为该结点的父结点。没有前件的结点中有件，称为该结点的父结点。没有前件的结点中有一个，称为树的根结点。一个，称为树的根结点。n子结点与叶子结点：在树构造中，每一个结点可子结点与叶子结点：在树构造中，每一个结点可以有多个后件，它们都称为该结点的子结点。没以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。有后件的结点称为叶子结点。n结点的度和树的度：一个结点所拥有后件个数称结点的度和树的度：一个结点所拥有后件个数称为该结点的度。一棵树中各个结点度数的最大值为该结点的度。一棵树中各个结点度数的最大值叫做这棵树的度。叫做这棵树的度。n层和树的深度：树构造是一种层次构

26、造，根结点层和树的深度：树构造是一种层次构造，根结点为第一层，根的子结点为第二层，其他各结点的为第一层，根的子结点为第二层，其他各结点的层数逐层由上而下计算。一棵树中结点的最大层层数逐层由上而下计算。一棵树中结点的最大层数叫做此树的深度。数叫做此树的深度。1.6.1 1.6.1 树的根本概念树的根本概念n树的特点树的特点n1 1树中只需根结点没有前件；树中只需根结点没有前件；n2 2除根外，其他结点都有且仅一个前件；除根外，其他结点都有且仅一个前件；n3 3树的结点，可以有零个或多个后件；树的结点，可以有零个或多个后件；n4 4除根外的其他结点，都存在独一条从根到该除根外的其他结点，都存在独一

27、条从根到该结点的途径；结点的途径；n5 5树是一种分支构造除根的结点外每个元树是一种分支构造除根的结点外每个元素都有且仅有一个直接前件，有且仅有零个或多素都有且仅有一个直接前件，有且仅有零个或多个直接后件。个直接后件。n树的存储树的存储n用多重链表来表示用多重链表来表示1.6.2 1.6.2 二叉树及其根本性质二叉树及其根本性质n1 1二叉树的定义二叉树的定义n一个二叉树是一个二叉树是n n个结点的有限集合个结点的有限集合n0n0，此集合或者，此集合或者是空集是空集n=0n=0，或者是由一个根结点及两棵互不相交的、，或者是由一个根结点及两棵互不相交的、分别称为左子树和右子树的二叉树组成，并且左

28、右子树都分别称为左子树和右子树的二叉树组成，并且左右子树都是二叉树。是二叉树。n特点：特点：n非空二叉树只需一个根结点；非空二叉树只需一个根结点；n每一个结点最多有两棵子树，且分别称为该结点的左子树每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。与右子树。1.6.2 1.6.2 二叉树及其根本性质二叉树及其根本性质n2 2二叉树的性质二叉树的性质n性质性质1 1 在二叉树的第在二叉树的第k k层上，最多有层上，最多有 个结点。个结点。n性质性质2 2 深度为深度为m m的二叉树最多有个的二叉树最多有个 结点。结点。n性质性质3 3 在恣意一棵二叉树中，度数为在恣意一棵二叉树中，度数

29、为0 0的结点的结点即叶子结点总比度为即叶子结点总比度为2 2的结点多一个。即：的结点多一个。即：n 其中，其中，n0n0表示度数为表示度数为0 0的结点数，的结点数，n2n2表示度数表示度数为为2 2的结点数。的结点数。n性质性质4 4 具有具有n n个结点的二叉树的深度至少个结点的二叉树的深度至少为为 ，其中，其中 表示取表示取 的整数部分。的整数部分。)1(21kk12 m120 nn1log2nlog2nn2log1.6.2 1.6.2 二叉树及其根本性质二叉树及其根本性质n3满二叉树和完全二叉树n满二叉树：除最后一层外，每一层上的一切结点都有两个子结点。n完全二叉树：除最后一层外，每

30、一层上的结点数均到达最大值；在最后一层上只短少右边的假设干结点。1.6.2 1.6.2 二叉树及其根本性质二叉树及其根本性质n性质性质5 5 具有具有n n个结点的完全二叉树深度为个结点的完全二叉树深度为 。n性质性质6 6 设完全二叉树共有设完全二叉树共有n n个结点，假设从根结点开场，个结点，假设从根结点开场，按层序每一层从左到右用自然数按层序每一层从左到右用自然数1 1，2 2，n n给结点给结点进展编号，那么对于编号为进展编号，那么对于编号为k kk=1k=1，2 2，n n的结点有的结点有以下结论：以下结论：n假设假设k=1k=1，那么该结点为根结点，它没有父结点；假设，那么该结点为

31、根结点，它没有父结点；假设k1k1，那么该结点的父结点的编号为，那么该结点的父结点的编号为INT(k/2)INT(k/2)。n假设假设2kn2kn，那么编号为，那么编号为k k的左子结点编号为的左子结点编号为2k2k；否那么；否那么该结点无左子结点显然也没有右子结点。该结点无左子结点显然也没有右子结点。n假设假设2k+1n2k+1n，那么编号为，那么编号为k k的右子结点编号为的右子结点编号为2k+12k+1；否；否那么该结点无右子结点。那么该结点无右子结点。1log2n1.6.3 1.6.3 二叉树的存储构造二叉树的存储构造n普通二叉树普通二叉树n采用链式存储构造采用链式存储构造n存储结点由

32、两部分组成：数据域与指针域存储结点由两部分组成：数据域与指针域n两个指针域：两个指针域：n左指针域左指针域n右指针域右指针域n满二叉树与完全二叉树满二叉树与完全二叉树n采用顺序存储构造采用顺序存储构造1.6.4 1.6.4 二叉树的遍历二叉树的遍历n二叉树的遍历：不反复地访问二叉树中的一切结点二叉树的遍历：不反复地访问二叉树中的一切结点 n1 1前序遍历前序遍历DLRDLRn首先访问根结点，然后遍历左子树，最后遍历右子树；并首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，依然先访问根结点，然后遍历左且，在遍历左右子树时，依然先访问根结点，然后遍历左子树，最后遍历右子树。

33、子树，最后遍历右子树。n2 2中序遍历中序遍历LDRLDRn首先遍历左子树，然后访问根结点，最后遍历右子树；并首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，依然先遍历左子树，然后访问且，在遍历左、右子树时，依然先遍历左子树，然后访问根结点，最后遍历右子树根结点，最后遍历右子树n3 3后序遍历后序遍历LRDLRDn首先遍历左子树，然后遍历右子树，最后访问根结点，并首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，依然先遍历左子树，然后遍历且，在遍历左、右子树时，依然先遍历左子树，然后遍历右子树，最后访问根结点。右子树，最后访问根结点。1.6.4

34、 1.6.4 二叉树的遍历二叉树的遍历n前序遍历：前序遍历：nA A、B B、D D、G G、C C、E E、F Fn中序遍历：中序遍历：nD D、G G、B B、A A、E E、C C、F F n后序遍历：后序遍历：nG G、D D、B B、E E、F F、C C、A A 1.7 1.7 查找技术查找技术1.7 1.7 查找技术查找技术n查找查找SearchingSearching：根据给定的某个值，：根据给定的某个值，在查找表中确定一个其关键字等于给定值在查找表中确定一个其关键字等于给定值的数据元素。的数据元素。n查找结果：查找结果：n查找胜利：找到查找胜利：找到n查找不胜利：没找到查找不

35、胜利：没找到n平均查找长度：查找过程中关键字和给定平均查找长度：查找过程中关键字和给定值比较的平均次数值比较的平均次数1.7.1 1.7.1 顺序查找顺序查找n根本思想：根本思想：n从表中的第一个元素开场，将给定的值与表中逐从表中的第一个元素开场，将给定的值与表中逐个元素的关键字进展比较，直到两者相符，查到个元素的关键字进展比较，直到两者相符，查到所要找的元素为止。否那么就是表中没有要找的所要找的元素为止。否那么就是表中没有要找的元素，查找不胜利。元素，查找不胜利。n平均要与表中一半以上元素进展比较，最坏情况平均要与表中一半以上元素进展比较，最坏情况下需求比较下需求比较n n次。次。n以下两种

36、情况下只能采用顺序查找：以下两种情况下只能采用顺序查找：n假设线性表是无序表即表中的元素是无序的，假设线性表是无序表即表中的元素是无序的，那么不论是顺序存储构造还是链式存储构造，都那么不论是顺序存储构造还是链式存储构造，都只能用顺序查找。只能用顺序查找。n即使是有序线性表，假设采用链式存储构造，也即使是有序线性表，假设采用链式存储构造，也只能用顺序查找。只能用顺序查找。1.7.2 1.7.2 二分法查找二分法查找n思想：先确定待查找记录所在的范围，然后逐渐减少范围，直到找到或确认找不到该记录为止。n前提：必需在具有顺序存储构造的有序表中进展。n查找过程：n1假设中间项的值等于x,那么阐明已查到

37、。n2假设x小于中间项的值，那么在线性表的前半部分查找；n3假设x大于中间项的值，那么在线性表的后半部分查找。n特点：比顺序查找方法效率高。最坏的情况下，需求比较 log2n次。1.7.2 1.7.2 二分法查找二分法查找n例：查找元素例：查找元素2222过程：过程： 1.8 1.8 排序技术排序技术1.8.1 1.8.1 交换类排序法交换类排序法n根本思想根本思想n两两比较待排序记录的关键字，发现两个两两比较待排序记录的关键字，发现两个记录的次序相反时即进展交换，直到没有记录的次序相反时即进展交换，直到没有反序的记录为止。反序的记录为止。n方法方法n冒泡排序冒泡排序n快速排序快速排序1.1.

38、冒泡排序冒泡排序 n根本思想根本思想n对存放原始数据的数组，按从后往前的方对存放原始数据的数组，按从后往前的方向进展多次扫描，当发现相邻两个数据的向进展多次扫描，当发现相邻两个数据的次序与排序要求的次序与排序要求的“递增次序不符合时，递增次序不符合时，即将这两个数据进展互换。这样，较小的即将这两个数据进展互换。这样，较小的数据就会逐单元向前挪动，好象气泡向上数据就会逐单元向前挪动，好象气泡向上浮起一样。浮起一样。n性能分析性能分析n假设线性表的长度假设线性表的长度n n，那么在最坏情况下，那么在最坏情况下，需求的比较次数为需求的比较次数为n(n-1)/2n(n-1)/2。1.1.冒泡排序冒泡排

39、序 2 2快速排序快速排序n根本思想根本思想n任取待排序序列中的某个元素作为基准任取待排序序列中的某个元素作为基准普通取第一个元素，经过一趟排序，普通取第一个元素，经过一趟排序，将待排元素分为左右两个子序列，左子序将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码那么大于基准排序码，右子序列的排序码那么大于基准元素的排序码，然后分别对两个子序列继元素的排序码，然后分别对两个子序列继续进展排序，直至整个序列有序。续进展排序，直至整个序列有序。n快速排序的平均时间复杂度为快速排序的平均时间复杂度为O(nlog2n)O

40、(nlog2n)。2 2快速排序快速排序1.8.2 1.8.2 插入类排序法插入类排序法n根本思想：根本思想：n每次将一个待排序的记录，按其关键字大每次将一个待排序的记录，按其关键字大小插入到前面曾经排好序的子序列中的适小插入到前面曾经排好序的子序列中的适当位置，直到全部记录插入完成为止。当位置，直到全部记录插入完成为止。n方法方法: :n简单插入排序简单插入排序n希尔排序希尔排序1 1简单插入排序法简单插入排序法n根本思想：根本思想：n把把n n个待排序的元素看成为一个有序表和一个待排序的元素看成为一个有序表和一个无序表，开场时有序表中只包含一个元个无序表，开场时有序表中只包含一个元素，无序

41、表中包含有素，无序表中包含有n-1n-1个元素，排序过程个元素，排序过程中每次从无序表中取出第一个元素，把它中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进展的排序码依次与有序表元素的排序码进展比较，将它插入到有序表中的适当位置，比较，将它插入到有序表中的适当位置，使之成为新的有序表。使之成为新的有序表。n在最坏的情况下，需求在最坏的情况下，需求n(n-1)/2n(n-1)/2次比较。次比较。1 1简单插入排序法简单插入排序法2 2希尔排序希尔排序n根本思想根本思想n先将整个待排元素序列分割成假设干个子序列先将整个待排元素序列分割成假设干个子序列由相隔某个增量由相隔某个增

42、量h h的元素组成的分别进展直接的元素组成的分别进展直接插入排序，待整个序列中的元素根本有序增量插入排序，待整个序列中的元素根本有序增量足够小时，再对全体元素进展一次直接插入排足够小时，再对全体元素进展一次直接插入排序。由于直接插入排序在元素根本有序的情况下序。由于直接插入排序在元素根本有序的情况下接近最好情况，效率是很高的。接近最好情况，效率是很高的。n增量序列普通取增量序列普通取 ，其中其中n n为待排序序列的长度为待排序序列的长度n在最坏情况下，希尔排序的时间复杂度为在最坏情况下，希尔排序的时间复杂度为 )log, 2 , 1(2/2nknhki)(5 . 1nO2 2希尔排序希尔排序1

43、.8.3 1.8.3 选择类排序法选择类排序法n根本思想：根本思想：n每一趟从待排序的记录中选出关键字最小每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子序列的最的记录，顺序放在已排好序的子序列的最后，直到全部记录排序终了。后，直到全部记录排序终了。n方法：方法：n简单项选择择排序简单项选择择排序n堆排序堆排序1 1简单项选择择排序法简单项选择择排序法 n根本思想：根本思想：n扫描整个线性表，从中选出最小的元素，扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。表采用同样的方法，直到子表

44、空为止。n最坏情况下，需求比较最坏情况下，需求比较n(n-1)/2n(n-1)/2次。次。1 1简单项选择择排序法简单项选择择排序法 2 2堆排序法堆排序法n堆的定义堆的定义n具有具有n n个元素的序列，当且仅当满足个元素的序列，当且仅当满足n 或或 n时称之为堆。称为大根堆；称为小根堆时称之为堆。称为大根堆；称为小根堆 。122iiiihhhh122iiiihhhh2 2堆排序法堆排序法n建堆建堆n在建堆的过程中，总是将根结点值与左、右子树的根结点在建堆的过程中，总是将根结点值与左、右子树的根结点值进展比较，假设不满足堆的条件，那么将左、右子树根值进展比较，假设不满足堆的条件，那么将左、右子

45、树根结点值中的大者与根结点值进展交换。这个调整过程不断结点值中的大者与根结点值进展交换。这个调整过程不断做到一切子树均为堆为止。做到一切子树均为堆为止。n堆排序堆排序n1 1首先将一个无序序列建成堆。首先将一个无序序列建成堆。n2 2然后将堆顶元素然后将堆顶元素( (序列中的最大项序列中的最大项) )与堆中最后一个与堆中最后一个元素交换元素交换( (最大项应该在序列的最后最大项应该在序列的最后) )。不思索曾经换到最。不思索曾经换到最后的那个元素，只思索前后的那个元素，只思索前n-1n-1个元素构成的子序列，将该个元素构成的子序列，将该子序列调整为堆。子序列调整为堆。n反复做步骤反复做步骤2

46、2，直到剩下的子序列空为止。，直到剩下的子序列空为止。n在最坏情况下，堆排序法需求比较的次数为在最坏情况下，堆排序法需求比较的次数为O(nlog2n)O(nlog2n)。各种排序法比较各种排序法比较 典型考题分析典型考题分析 n【例【例1-11-1】问题处置方案的正确而完好的描】问题处置方案的正确而完好的描画称为画称为 。20192019年年4 4月月n答案答案 算法算法n【例【例1-21-2】算法复杂度主要包括时间复杂度】算法复杂度主要包括时间复杂度和和 复杂度。复杂度。20192019年年9 9月月n答案答案 空间空间n【例【例1-31-3】算法的时间复杂度是指】算法的时间复杂度是指_。n

47、A A执行算法程序所需求的时间执行算法程序所需求的时间nB B算法程序的长度算法程序的长度nC C算法执行过程中所需求的根本运算次数算法执行过程中所需求的根本运算次数nD D算法程序中的指令条数算法程序中的指令条数n答案答案C Cn【例【例1-41-4】算法的空间复杂度是指】算法的空间复杂度是指_。nA A算法程序的长度算法程序的长度nB B算法程序中的指令条数算法程序中的指令条数nC C算法程序所占的存储空间算法程序所占的存储空间nD D算法执行过程中所需求的存储空间算法执行过程中所需求的存储空间n答案答案D Dn【例【例1-51-5】以下表达中正确的选项】以下表达中正确的选项是是 。201

48、92019年年9 9月月nA A一个算法的空间复杂度大，那么其时间一个算法的空间复杂度大，那么其时间复杂度也必定大复杂度也必定大nB B一个算法的空间复杂度大，那么其时间一个算法的空间复杂度大，那么其时间复杂度必定小复杂度必定小nC C一个算法的时间复杂度大，那么其空间一个算法的时间复杂度大，那么其空间可复杂度必定小可复杂度必定小nD D上述三种说法都不对上述三种说法都不对n答案答案 D Dn【例【例1-61-6】以下表达中正确的选项】以下表达中正确的选项是是 。20192019年年9 9月月nA A一个逻辑数据构造只能有一种存储构造一个逻辑数据构造只能有一种存储构造nB B数据的逻辑构造属于

49、线性构造，存储构数据的逻辑构造属于线性构造，存储构造属于非线性构造造属于非线性构造nC C一个逻辑数据构造可以有多种存储构造，一个逻辑数据构造可以有多种存储构造，且各种存储构造不影响数据处置的效率且各种存储构造不影响数据处置的效率nD D一个逻辑数据构造可以有多种存储构造，一个逻辑数据构造可以有多种存储构造，且各种存储构造影响数据处置的效率且各种存储构造影响数据处置的效率n答案答案 D Dn【例【例1-71-7】数据构造分为逻辑构造和存储构】数据构造分为逻辑构造和存储构造，循环队列属于造，循环队列属于 构造。构造。20192019年年9 9月月n答案答案 逻辑逻辑n【例【例1-81-8】数据构

50、造分为线性构造和非线性】数据构造分为线性构造和非线性构造，带链的队列属于构造，带链的队列属于 。20192019年年9 9月月n答案答案 线性构造线性构造n【例【例1-91-9】以下表达中正确的选项是】以下表达中正确的选项是_。20192019年年4 4月月nA A线性链表是线性表的链式存储构造线性链表是线性表的链式存储构造nB B栈与队列是非线性构造栈与队列是非线性构造nC C双向链表是非线性构造双向链表是非线性构造nD D只需根结点的二叉树是线性构造只需根结点的二叉树是线性构造n答案答案 A An【例【例1-101-10】某线性表采用顺序存储构造，】某线性表采用顺序存储构造，每个元素占每个

51、元素占4 4个存储单元，首地址为个存储单元，首地址为200200，那么第那么第1212个元素的存储地址为个元素的存储地址为 。nA A248248nB B247247nC C246246nD D244244n答案答案 D Dn【例【例1-111-11】在长度为】在长度为n n的顺序表的第的顺序表的第i i1in+11in+1个位置上插入一个元素，元个位置上插入一个元素，元素的挪动次数为素的挪动次数为 。nA An-i+1n-i+1nB Bn-in-inC Ci inD Di-1i-1n答案答案 A An【例【例1-121-12】在一个长度为】在一个长度为n n的顺序表中，删的顺序表中，删除第除

52、第i i1in1in个元素时，需求挪动的个元素时，需求挪动的元素个数为元素个数为 。nA An-i+1n-i+1nB Bn-in-inC Ci inD Di-1i-1n答案答案 B Bn【例【例1-131-13】以下描画的中，不是线性表的】以下描画的中，不是线性表的顺序存储构造的特征的是顺序存储构造的特征的是 。nA A不便于插入和删除不便于插入和删除nB B需求延续的存储空间需求延续的存储空间nC C可随机访问可随机访问nD D需另外开辟空间来保管元素之间的关系需另外开辟空间来保管元素之间的关系n答案答案 D Dn【例【例1-141-14】以下关于栈的描画中错误的选】以下关于栈的描画中错误的

53、选项是项是_。20192019年年4 4月月nA A栈是先进后出的线性表栈是先进后出的线性表nB B栈只能顺序存储栈只能顺序存储nC C栈具有记忆作用栈具有记忆作用nD D对栈的插入与删除操作中，不需求改动对栈的插入与删除操作中，不需求改动栈底指针栈底指针n答案答案 B Bn【例【例1-151-15】栈和队列的共同点是】栈和队列的共同点是_。nA A都是先进先出都是先进先出nB B都是先进后出都是先进后出nC C只允许在端点处插入和删除元素只允许在端点处插入和删除元素nD D没有共同点没有共同点n答案答案 C Cn【例【例1-161-16】栈的输入序列为】栈的输入序列为1 1，2 2，3 3，

54、n-1n-1，n n，输出序列的第，输出序列的第1 1个元素为个元素为n n，那么，那么第个输出元素为第个输出元素为_。nA An-i+1n-i+1nB Bn-1n-1nC Ci inD D哪个元素无所谓哪个元素无所谓n答案答案 A An【例【例1-171-17】一个队列的入队序列是】一个队列的入队序列是1 1、2 2、3 3、4 4，那么队列的输出序列是，那么队列的输出序列是 。nA A4 4、3 3、2 2、1 1nB B1 1、2 2、3 3、4 4nC C1 1、4 4、3 3、2 2nD D3 3、2 2、4 4、1 1n答案答案 A An【例【例1-181-18】队列是限定只能在表

55、的一端进】队列是限定只能在表的一端进展插入和在另一端进展删除操作的线性表。展插入和在另一端进展删除操作的线性表。允许插入的一端称作允许插入的一端称作_。n答案答案 队尾队尾n【例【例1-191-19】以下对于线性链表的描画中正】以下对于线性链表的描画中正确的选项是确的选项是 。20192019年年4 4月月nA A存储空间不一定是延续，且各元素的存存储空间不一定是延续，且各元素的存储顺序是恣意的储顺序是恣意的 nB B存储空间不一定是延续，且前件元素一存储空间不一定是延续，且前件元素一定存储在后件元素的前面定存储在后件元素的前面 nC C存储空间必需延续，且各前件元素一定存储空间必需延续，且各

56、前件元素一定存储在后件元素的前面存储在后件元素的前面 nD D存储空间必需延续，且各元素的存储顺存储空间必需延续，且各元素的存储顺序是恣意的序是恣意的 n答案答案 A An【例【例1-201-20】以下表达中，错误的选项】以下表达中，错误的选项是是 。nA A线性表是由线性表是由n n个数据元素组成的一个有个数据元素组成的一个有限序列限序列nB B线性表是一种线性构造。线性表是一种线性构造。nC C线性表的一切结点有且只需一个前件和线性表的一切结点有且只需一个前件和一个后件一个后件nD D线性表可以是空表。线性表可以是空表。n答案答案 C Cn【例【例1-211-21】以下描画的不是链表的优点

57、是】以下描画的不是链表的优点是_。nA A逻辑上相邻的结点物理上不用邻接逻辑上相邻的结点物理上不用邻接nB B插入、删除运算操作方便，不用挪动结插入、删除运算操作方便，不用挪动结点点nC C所需存储空间比线性表节省所需存储空间比线性表节省nD D无需事先估计存储空间的大小无需事先估计存储空间的大小n答案答案 C Cn【例【例1-221-22】某线性表最常用的运算是插入】某线性表最常用的运算是插入和删除，插入运算是指在表尾插入一个新和删除，插入运算是指在表尾插入一个新元素。删除运算是指删除表头第一个元素，元素。删除运算是指删除表头第一个元素，那么采用那么采用 存储方式最节省运算时间。存储方式最节

58、省运算时间。nA A仅有尾指针的单向循环链表仅有尾指针的单向循环链表nB B仅有头指针的单向循环链表仅有头指针的单向循环链表nC C单向链表单向链表nD D顺序存储顺序存储n答案答案 A An【例【例1-231-23】一棵二叉树第六层根结点为】一棵二叉树第六层根结点为第一层的结点数最多为第一层的结点数最多为 个。个。20192019年年9 9月月n答案答案 32 32n【例【例1-241-24】深度为】深度为5 5的二叉树至多有的二叉树至多有_个结点。个结点。nA A1616nB B3232nC C3131nD D1010n答案答案 C Cn【例【例1-251-25】设树】设树T T的度为的度

59、为4 4，其中度为，其中度为1 1，2 2，3 3，4 4的结点个数分别为的结点个数分别为4 4，2 2，1 1，1 1。那么。那么T T中的叶子结点为中的叶子结点为_。nA A8 8nB B7 7nC C6 6nD D5 5n答案答案 A An【例【例1-261-26】某二叉树中度为】某二叉树中度为2 2的结点有的结点有1818个，个，那么该二叉树中有那么该二叉树中有 个叶子结点。个叶子结点。20192019年年4 4月月n答案答案 19 19n【例【例1-271-27】具有】具有8888个结点的二叉树，其深个结点的二叉树，其深度至少为度至少为_。n答案答案 7 7n【例【例1-281-28

60、】在深度为】在深度为7 7的满二叉树中，叶子的满二叉树中，叶子结点的个数为结点的个数为20192019年年4 4月月nA A3232nB B3131nC C6464nD D6363n答案答案 C Cn【例【例1-291-29】设一棵完全二叉树共有】设一棵完全二叉树共有700700个结点，个结点，那么在该二叉树中有那么在该二叉树中有_个叶子结点。个叶子结点。n答案答案 350350n【例【例1-301-30】对如图】对如图1-301-30所示的二叉树，进所示的二叉树，进展后序遍历的结果为展后序遍历的结果为 。20192019年年4 4月月nA AABCDEFABCDEFnB BDBEAFCDBE