数据结构与算法专项培训课件

精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远数据结构与算法专项培数据结构与算法专项培训训2024/6/25精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远数据结构与算法数据结构与算法精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远数据结构与算法数据结构与算法n1.算法算法n2.数据结构的基本概念数据结构的基本概念n3.线性表及其顺序存储结构线性表及其顺序存储结构n4.栈和队列栈和队列n5.线性链表线性链表n6.树与二叉树树与二叉树n7.查找技术查找技术n8.排序技术排序技术精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n重点：掌握数据结构与算法的基本概念及几重点：掌握数据结构与算法的基本概念及几种常用数据结构种常用数据结构线性表、栈、队列、链线性表、栈、队列、链表、树、二叉树的基本运算，以及常用的查表、树、二叉树的基本运算，以及常用的查找和排序技术。找和排序技术。n难点：链表的插入和删除、二叉树的遍历以难点：链表的插入和删除、二叉树的遍历以及查找和排序算法的时间复杂度。及查找和排序算法的时间复杂度。精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远数据结构学习框图数数据据结结构构学学习习内内容容数据的逻数据的逻辑结构辑结构数据的存数据的存储结构储结构算法算法线性结构线性结构(线性表、栈、队列、数组线性表、栈、队列、数组和串）和串）非线性结构（非线性结构（树、二叉树树、二叉树、图）、图）顺序存储顺序存储链式存储链式存储索引存储索引存储散列存储散列存储查找查找(顺序顺序、二分二分、分块、哈希、分块、哈希)排序排序(插入插入、交换交换、选择选择、归并、归并)精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远数据结构与算法数据结构与算法n1.算法算法n2.数据结构的基本概念数据结构的基本概念n3.线性表及其顺序存储结构线性表及其顺序存储结构n4.栈和队列栈和队列n5.线性链表线性链表n6.树与二叉树树与二叉树n7.查找技术查找技术n8.排序技术排序技术精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远1.算法n算法是指解题方案的准确而完整的描述，是一组算法是指解题方案的准确而完整的描述，是一组严谨地定义运算顺序的规则，并且每一个规则都严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数是有效的，且是明确的，此顺序将在有限的次数下终止。下终止。n算法不等于程序，也不等于计算方法。程序也可算法不等于程序，也不等于计算方法。程序也可以作为算法的一种描述，但程序通常还需考虑很以作为算法的一种描述，但程序通常还需考虑很多与方法和分析无关的细节问题多与方法和分析无关的细节问题,这是因为在编写这是因为在编写程序时要受到计算机系统运行环境的限制。通常，程序时要受到计算机系统运行环境的限制。通常，程序的编制不可能优于算法的设计。程序的编制不可能优于算法的设计。精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远算法的基本特征算法的基本特征n可行性可行性：算法在执行过程中往往要受到计算：算法在执行过程中往往要受到计算工具的限制，使执行结果产生偏差，因此设工具的限制，使执行结果产生偏差，因此设计时应考虑其可行性。计时应考虑其可行性。n确定性确定性:算法的每一个步骤都必须是有明确定算法的每一个步骤都必须是有明确定义的。义的。n有穷性有穷性：算法必须能在有限的时间内做完，：算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的即能在执行有限个步骤后终止，包括合理的执行时间的含义；执行时间的含义；n拥有足够的情报拥有足够的情报(有输入和输出）有输入和输出）精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n算法的基本要素：算法的基本要素：一是对数据对象的运算和操作；一是对数据对象的运算和操作；二是算法的控制结构。二是算法的控制结构。n基本运算和操作包括：基本运算和操作包括：算术运算算术运算逻辑运算逻辑运算关系运算关系运算数据传输数据传输 n算法的控制结构算法的控制结构顺序结构顺序结构选择结构选择结构循环结构循环结构精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n算法基本设计方法：算法基本设计方法：列举法列举法归纳法归纳法递推递推递归递归减半递推技术减半递推技术回溯法回溯法精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n算法复杂度：算法算法复杂度：算法时间复杂度时间复杂度和和算法空间算法空间复杂度复杂度。n算法时间复杂度是指执行算法所需要的计算法时间复杂度是指执行算法所需要的计算工作量。算工作量。n算法空间复杂度是指执行这个算法所需要算法空间复杂度是指执行这个算法所需要的内存空间。包括：程序空间、输入数据的内存空间。包括：程序空间、输入数据的空间、执行过程中所需额外空间。的空间、执行过程中所需额外空间。精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n一个问题的算法实现的时间复杂度一个问题的算法实现的时间复杂度和空间复杂度往往是相互矛盾的，和空间复杂度往往是相互矛盾的，要降低算法的执行时间要降低算法的执行时间往往往往要以使要以使用更多的存储空间为代价，要节省用更多的存储空间为代价，要节省存储空间又存储空间又可能要可能要以增加算法的执以增加算法的执行时间为代价。行时间为代价。精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远算法例题n(2007-9)下列叙述中正确的是 nA）程序执行的效率与数据的存储结构密切相关 nB）程序执行的效率只取决于程序的控制结构 nC）程序执行的效率只取决于所处理的数据量 nD）以上三种说法都不对 A精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2007-4)下列叙述中正确的是nA）算法的效率只与问题的规模有关，而与数据的存储结构无关nB）算法的时间复杂度是指执行算法所需要的计算工作量nC）数据的逻辑结构与存储结构是一一对应的nD）算法的时间复杂度与空间复杂度一定相关B精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2006-9)下列叙述中正确的是_。nA）一个算法的空间复杂度大，则其时间复杂度也必定大 nB）一个算法的空间复杂度大，则其时间复杂度必定小nC）一个算法的时间复杂度大，则其空间可复杂度必定小 nD）上述三种说法都不对D精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2008-4)算法的有穷性是指_nA算法程序的运行时间是有限的 nB算法程序所处理的数据量是有限的 nC算法程序的长度是有限的 nD算法只能被有限的用户使用A精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远数据结构与算法数据结构与算法n1.算法算法n2.数据结构的基本概念数据结构的基本概念n3.线性表及其顺序存储结构线性表及其顺序存储结构n4.栈和队列栈和队列n5.线性链表线性链表n6.树与二叉树树与二叉树n7.查找技术查找技术n8.排序技术排序技术精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远2.数据结构的基本概念n数据结构研究的数据结构研究的内容内容：n（1 1）数据集合中各数据元素之间所固有的逻辑关）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；系，即数据的逻辑结构；n（2 2）在对数据进行处理时，各数据元素在计算机）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；中的存储关系，即数据的存储结构；n（3 3）对各种数据结构进行的运算。）对各种数据结构进行的运算。n数据结构研究的目的：数据结构研究的目的：n目的目的是提高数据处理的效率，包括提高数据处理速是提高数据处理的效率，包括提高数据处理速度和尽量节省在数据处理过程中所占用的计算机存度和尽量节省在数据处理过程中所占用的计算机存储空间。储空间。精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n数据的数据的逻辑结构逻辑结构包含：包含：n（1）表示数据元素的信息；）表示数据元素的信息；n（2）表示各数据元素之间的前后件关系。）表示各数据元素之间的前后件关系。n数据的数据的存储结构存储结构有顺序、链接、索引等。有顺序、链接、索引等。n一般来说，一种数据的逻辑结构根据需要一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构。采用不同的存可以表示成多种存储结构。采用不同的存储结构的效率是不同的。储结构的效率是不同的。精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n根据数据结构中数据元素之间前后件关系根据数据结构中数据元素之间前后件关系的复杂程度，将数据结构分为：线性结构的复杂程度，将数据结构分为：线性结构与非线性结构与非线性结构n线性结构条件：线性结构条件：n（1）有且只有一个根结点；）有且只有一个根结点；n（2）每一个结点最多有一个前件，也最多）每一个结点最多有一个前件，也最多有一个后件。有一个后件。n非线性结构：不满足线性结构条件的数据非线性结构：不满足线性结构条件的数据结构。结构。精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远数据结构的基本概念例题n(2007-9)下列叙述中正确的是 nA）数据的逻辑结构与存储结构必定是一一对应的 nB）由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构 nC）程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构 nD）以上三种说法都不对 D精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2005-4)n数据的存储结构是指_。nA）存储在外存中的数据 nB）数据所占的存储空间量nC）数据在计算机中的顺序存储方式nD）数据的逻辑结构在计算机中的表示D精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2005-9)下列叙述中正确的是nA）一个逻辑数据结构只能有一种存储结构 nB）数据的逻辑结构属于线性结构，存储结构属于非线性结构nC）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率nD）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率D精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远数据结构与算法数据结构与算法n1.算法算法n2.数据结构的基本概念数据结构的基本概念n3.线性表及其顺序存储结构线性表及其顺序存储结构n4.栈和队列栈和队列n5.线性链表线性链表n6.树与二叉树树与二叉树n7.查找技术查找技术n8.排序技术排序技术精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远3.线性表及其顺序存储结构线性表及其顺序存储结构n线性表由一组数据元素构成，数据元素的线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相位置只取决于自己的序号，元素之间的相对位置是线性的。对位置是线性的。n在复杂线性表中，由若干项数据元素组成在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的数据元素称为记录，而由多个记录构成的线性表又称为文件。的线性表又称为文件。精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远线性表及其顺序存储结构线性表及其顺序存储结构n非空线性表的结构特征：非空线性表的结构特征：n（1）有且只有一个根结点）有且只有一个根结点a1，它无前件；，它无前件；n（2）有且只有一个终端结点）有且只有一个终端结点an，它无后件；，它无后件；n（3）除根结点与终端结点外，其他所有结点）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结有且只有一个前件，也有且只有一个后件。结点个数点个数n称为线性表的长度，当称为线性表的长度，当n=0时，称为时，称为空表。空表。精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n线性表的线性表的顺序存储顺序存储结构具有以下两个基本特点：结构具有以下两个基本特点：n（1）线性表中所有元素所占的存储空间是连续的；）线性表中所有元素所占的存储空间是连续的；n（2）线性表中各数据元素在存储空间中是按逻辑顺）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。序依次存放的。nai的存储地址为：的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，为第一个元素的地址，k代表每个元素代表每个元素占的字节数。占的字节数。n顺序表的运算：插入、删除。顺序表的运算：插入、删除。n线性表的顺序存储适合元素不常变动的线性表。线性表的顺序存储适合元素不常变动的线性表。精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远数据结构与算法数据结构与算法n1.算法算法n2.数据结构的基本概念数据结构的基本概念n3.线性表及其顺序存储结构线性表及其顺序存储结构n4.栈和队列栈和队列n5.线性链表线性链表n6.树与二叉树树与二叉树n7.查找技术查找技术n8.排序技术排序技术精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远4.栈和队列栈是限定在一端进行插入与删除的栈是限定在一端进行插入与删除的线性表线性表，允许插，允许插入与删除的一端称为栈顶，不允许插入与删除的另入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。一端称为栈底。栈按照栈按照“先进后出先进后出”（FILO）或）或“后进先出后进先出”（LIFO）组织数据，栈具有记忆作用。用）组织数据，栈具有记忆作用。用top表表示栈顶位置，用示栈顶位置，用bottom表示栈底。表示栈底。栈的基本运算：栈的基本运算：（1）插入元素称为入栈运算；）插入元素称为入栈运算；（2）删除元素称为退栈运算；）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。此时指针无变化。精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远队列是指允许在一端（队尾）进入插入，而在另一队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的端（队头）进行删除的线性表线性表。队列是队列是“先进先出先进先出”（FIFO）或）或“后进后出后进后出”（LILO）的线性表。）的线性表。队列运算包括：队列运算包括：（1）入队运算：从队尾插入一个元素；）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。）退队运算：从队头删除一个元素。精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远栈和队列n(2007-9)线性表的存储结构主要分为顺线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的特殊的线性表，循环队列是队列的_ 存储结构。存储结构。顺序顺序精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2006-9)数据结构分为线性结构和非线数据结构分为线性结构和非线性结构，带链的队列属于性结构，带链的队列属于 _线性结构线性结构精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2005-4)下列叙述中正确的是nA)线性链表是线性表的链式存储结构 nB)栈与队列是非线性结构nC)双向链表是非线性结构 nD)只有根结点的二叉树是线性结构A精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2007-4)下列对队列的叙述正确的是nA）队列属于非线性表nB）队列按“先进后出”原则组织数据nC）队列在队尾删除数据nD）队列按“先进先出”原则组织数据D精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2006-9)按“先进后出”原则组织数据的数据结构是 _n栈精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2006-4)n按照”后进先出”原则组织数据的数据结构是nA)队列 nB)栈 nC)双向链表 nD)二叉树B精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2005-4)下列关于栈的描述中错误的是_。nA）栈是先进后出的线性表nB）栈只能顺序存储nC）栈具有记忆作用nD）对栈的插入与删除操作中，不需要改变栈底指针B精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2005-9)下列关于栈的描述正确的是nA）在栈中只能插入元素而不能删除元素 nB）在栈中只能删除元素而不能插入元素nC）栈是特殊的线性表，只能在一端插入或删除元素nD）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素C精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远数据结构与算法数据结构与算法n1.算法算法n2.数据结构的基本概念数据结构的基本概念n3.线性表及其顺序存储结构线性表及其顺序存储结构n4.栈和队列栈和队列n5.线性链表线性链表n6.树与二叉树树与二叉树n7.查找技术查找技术n8.排序技术排序技术精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远5.线性链表线性链表n链表的引入顺序结构的缺点:1、在插入、删除时要移动大量的节点，效率低2、表的大小固定。预先指定，无法更改，不便扩充原因：结构存放的连续性n突破离散存放用指针来表示元素之间的关系。n链接的形式：单链表、双链表、循环链表精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远线性表的链式存储结构数数据据结结构构中中的的每每一一个个结结点点对对应应于于一一个个存存储储单单元元，这种存储单元称为存储结点，简称结点。这种存储单元称为存储结点，简称结点。结结点点由由两两部部分分组组成成：（1 1）用用于于存存储储数数据据元元素素值值，称称为为数数据据域域；（2 2）用用于于存存放放指指针针，称称为为指指针针域域，用于指向前一个或后一个结点。用于指向前一个或后一个结点。数据域数据域data 指针域指针域next存放该元素的数据存放该元素的数据存放下一个元素的地址存放下一个元素的地址精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远单链表headinfoinfoinfoNULLinfo头指针头指针精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远双链表n如果在单链表的每个结点上再添加一个指向线性表中每个元素的前趋结点的指针域，使每个结点既可指向它的直接前驱又可指向它的直接后继的链表称为双链表。n双链表的结点结构：n带头结点的非空双链表示例：priordatanexta1anhead精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远线性链表n(2005-4)下列对于线性链表的描述中正确的是_。nA）存储空间不一定是连续，且各元素的存储顺序是任意的nB）存储空间不一定是连续，且前件元素一定存储在后件元素的前面nC）存储空间必须连续，且前件元素一定存储在后件元素的前面nD）存储空间必须连续，且各元素的存储顺序是任意的A精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远数据结构与算法数据结构与算法n1.算法算法n2.数据结构的基本概念数据结构的基本概念n3.线性表及其顺序存储结构线性表及其顺序存储结构n4.栈和队列栈和队列n5.线性链表线性链表n6.树与二叉树树与二叉树n7.查找技术查找技术n8.排序技术排序技术精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远6.树与二叉树n树是一种简单的非线性结构，所有元素之间具树是一种简单的非线性结构，所有元素之间具有明显的层次特性。有明显的层次特性。n在树结构中，每一个结点只有一个前件，称为在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点后件，称为该结点的子结点。没有后件的结点称为叶子结点。称为叶子结点。树 树树是一个或多个结点元素组成的有限集合是一个或多个结点元素组成的有限集合T T，对任意一个非，对任意一个非空树，它都满足如下条件：空树，它都满足如下条件：(1)(1)有且仅有一个特定的称为根有且仅有一个特定的称为根(Root)(Root)的结点。的结点。(2)(2)其余结点可分为其余结点可分为m(m0)m(m0)个互不相交的有限集合个互不相交的有限集合T1T1，T2T2，.，TmTm。其中每个集合又是一棵树，被称为根的子树。其中每个集合又是一棵树，被称为根的子树。A AB BC CD DE EH HI IJ JK KF FL LG GM MN NH HI IJ J结点的度结点的度 一个结点一个结点的子树的个数的子树的个数称为该结点的称为该结点的度。结点度。结点B B的的度为度为2 2。树的度树的度树中各结点的度的最大值，用来表征一棵树中各结点的度的最大值，用来表征一棵树的茂密程度。树的茂密程度。分支结点分支结点度不为度不为0的结点称的结点称为分支结为分支结点或非终点或非终端结点端结点叶子叶子度为度为0的结的结点称为叶点称为叶子或终端子或终端结点结点结点的层次结点的层次：根结点的层次为：根结点的层次为1，其余任一结点的层次等于它的父结点的层次，其余任一结点的层次等于它的父结点的层次加加1。树的深度树的深度：树中结点的最大层次称为树的深度或高度。：树中结点的最大层次称为树的深度或高度。精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n二叉树二叉树是有限个结点的集合，它或者为空集是有限个结点的集合，它或者为空集(此时称为空此时称为空二叉树二叉树)，或者是由一个根结点和两棵互不相交的且分别，或者是由一个根结点和两棵互不相交的且分别称为这个根的左子树和右子树的二叉树组成。称为这个根的左子树和右子树的二叉树组成。AAAABBBC 二叉树的五种基本形态二叉树的五种基本形态 精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远二叉树的性质n（1）在二叉树的第k层上，最多有2k-1(k1)个结点；n（2）深度为m的二叉树最多有2m-1个结点n（3）度为0的结点（即叶子结点）总是比度为2的结点多一个精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远树与二叉树n(2007-9)一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为 nA）219nB）221nC）229nD）231 A精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2007-4)某二叉树中有n个度为2的结点,则该二叉树中的叶子结点数为nA)n+1nB)n-1nC)2nnD)n/2A精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远几个特殊二叉树的概念n满二叉树满二叉树 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶结点都在同一层上，这样的二叉树称为满二叉树。特点：（1）每一层上结点数都达到最大（2）度为1的结点n1=0n结点层序编号方法：从根结点起从上到下逐层（层内从左到右）对二叉树的结点进行连续编号。对一棵深度为对一棵深度为h的二叉树，若结点编号的二叉树，若结点编号为为i,则有如下规律则有如下规律1.第第k层结点个数为层结点个数为2k-12.若若i2h-1-1，则结点，则结点I的左子树根编的左子树根编号为号为2*i,右子树根的编号为右子树根的编号为2*i+13.若若1i2h-1，则结点，则结点I的父结点编的父结点编号为号为(int)(i/2)精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远几个特殊二叉树的概念n完全二叉树完全二叉树 若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。不满足该条件的都是非完全二叉树。即：深度为即：深度为k k，结点数为，结点数为n n的二叉树，当且仅当每个结点的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从的编号都与相同深度的满二叉树中从1 1到到n n的结点一一对的结点一一对应。应。精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2007-4)在深度为7的满二叉树中，度为2的结点个数为_。63精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2006-4)在深度为7的满二叉树中,叶子结点的个数为nA)32 nB)31 nC)64 nD)63C精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n设一棵完全二叉树共有设一棵完全二叉树共有700个结点，则有个结点，则有几个叶子结点？几个叶子结点？350精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远二叉树的遍历二叉树的遍历n遍历二叉树是指按一定的规律对二叉树的每个结遍历二叉树是指按一定的规律对二叉树的每个结点，访问且仅访问一次的处理过程。点，访问且仅访问一次的处理过程。n访问是一种抽象操作，是对结点的某种处理，例访问是一种抽象操作，是对结点的某种处理，例如可以是求结点的度或层次、打印结点的信息，如可以是求结点的度或层次、打印结点的信息，或做其他任何工作。或做其他任何工作。n 一次遍历后，使树中结点的非线性排列，按访一次遍历后，使树中结点的非线性排列，按访问的先后顺序变为某种线性排列。问的先后顺序变为某种线性排列。n 遍历的次序：若设二叉树根为遍历的次序：若设二叉树根为D D，左子树为，左子树为L L，右子树为右子树为R R，并限定先左后右，则有以下三种遍，并限定先左后右，则有以下三种遍历次序：历次序：LDR LDR 中序遍历；中序遍历；LRD LRD 后序遍历；后序遍历；DLR DLR 先序遍历先序遍历精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2007-4)对下列二叉树n进行前序遍历的结果为nA)DYBEAFCZX nB)YDEBFZXCAnC)ABDYECFXZnD)ABCDEFXYZABCDEFXYZC精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2007-9)对下列二义树进行中序遍历的结果为FCEADBGPHACBDFEHGP 精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2006-9)对下列二叉树进行中序遍历的结果是_。nA）ACBDFEG nB）ACBDFGE nC）ABDCGEF nD）FCADBEGFCEADGBA精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远二叉树的构造n通过同一棵二叉树的先序和中序遍历序列，或者通过同一棵二叉树的先序和中序遍历序列，或者后序和中序遍历序列可以构造出惟一的一棵二叉后序和中序遍历序列可以构造出惟一的一棵二叉树。树。n构造步骤：构造步骤：从先序遍历序列中取出第一个结点，该结点一定是二从先序遍历序列中取出第一个结点，该结点一定是二叉树的根。然后在中序遍历序列中找到根结点，根结叉树的根。然后在中序遍历序列中找到根结点，根结点前面的结点序列是左子树的中序遍历序列，根结点点前面的结点序列是左子树的中序遍历序列，根结点后面的结点序列是右子树的中序遍历序列。后面的结点序列是右子树的中序遍历序列。对根的左子树先序遍历序列和中序遍历序列及右子树对根的左子树先序遍历序列和中序遍历序列及右子树的先序遍历序列和中序遍历序列，执行上一步，直到的先序遍历序列和中序遍历序列，执行上一步，直到得出所有叶结点为止得出所有叶结点为止精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n设一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为_。DEBFCA精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远数据结构与算法数据结构与算法n1.算法算法n2.数据结构的基本概念数据结构的基本概念n3.线性表及其顺序存储结构线性表及其顺序存储结构n4.栈和队列栈和队列n5.线性链表线性链表n6.树与二叉树树与二叉树n7.查找技术查找技术n8.排序技术排序技术精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远7.查找技术n查找是指在一个给定的数据结构中查找某个指定的元查找是指在一个给定的数据结构中查找某个指定的元素。不同数据结构采用不同的查找方法。素。不同数据结构采用不同的查找方法。n顺序查找顺序查找一般是在线性表中查找指定的元素，为了查一般是在线性表中查找指定的元素，为了查找某个元素需要与线性表中所有元素进行比较，这是找某个元素需要与线性表中所有元素进行比较，这是顺序查找的最坏情况。顺序查找的最坏情况。如果线性表是无序表，不管是顺序存储还是链式存储都只如果线性表是无序表，不管是顺序存储还是链式存储都只能顺序查找能顺序查找即使有序线性表，如果采用链式存储，也只能是用顺序查即使有序线性表，如果采用链式存储，也只能是用顺序查找找n二分法查找二分法查找适用于顺序存储的有序表。在长度为适用于顺序存储的有序表。在长度为n的的有序线性表中进行二分查找，需要比较次数为有序线性表中进行二分查找，需要比较次数为log2n精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远查找技术例题n(2006-9)在长度为 64 的有序线性表中进行顺序查找，最坏情况下需要比较的次数为_。nA）63 B）64 C）6 D）7B精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2005-4)对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为_。nA）log2n B）n/2 C）n D）n+1C精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2005-9)下列数据结构中，能用二分法进行查找的是nA）顺序存储的有序线性表 nB）线性链表 nC）二叉链表 nD）有序线性链表A精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远数据结构与算法数据结构与算法n1.算法算法n2.数据结构的基本概念数据结构的基本概念n3.线性表及其顺序存储结构线性表及其顺序存储结构n4.栈和队列栈和队列n5.线性链表线性链表n6.树与二叉树树与二叉树n7.查找技术查找技术n8.排序技术排序技术精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远8.排序技术排序技术n排序是指将一个无序序列整理成按值非递减顺序排列的排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。有序序列。n交换类排序法交换类排序法：n（1）冒泡排序法，需要比较的次数为）冒泡排序法，需要比较的次数为n(n-1)/2；n（2）快速排序法）快速排序法n(n-1)/2。n插入类排序法插入类排序法：n（1）简单插入排序法，最坏情况需要）简单插入排序法，最坏情况需要n(n-1)/2次比次比较较n（2）希尔排序法，最坏情况需要）希尔排序法，最坏情况需要(n1.5)次比较。次比较。n选择类排序法选择类排序法：n（1）简单选择排序法）简单选择排序法,最坏情况需要最坏情况需要n(n-1)/2次比较次比较n（2）堆排序法，最坏情况需要）堆排序法，最坏情况需要(nlog2n)次比较。次比较。精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远排序技术例题 n(2007-9)冒泡排序在最坏情况下的比较次数是 nA）(n1)/2nB）nlog2 nnC）n(n1)/2nD）/2 C精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2005-4)对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是_。nA）冒泡排序为n/2 nB）冒泡排序为nnC）快速排序为nnD）快速排序为n(n-1)/2D精彩展示精彩展示精彩展示精彩展示路漫漫其悠远路漫漫其悠远n(2008-4)对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-1)/2的排序方法是nA快速排序 nB冒泡排序 nC直线插入排序 nD堆排序D