最新计算机二级公共基础知识课件.ppt

1、计算机二级公共基础知识课件计算机二级公共基础知识课件第2页计算机二级考试公共基础知识计算机二级考试公共基础知识大纲 q 数据结构与算法数据结构与算法q 程序设计基础程序设计基础q 软件工程基础软件工程基础q 数据库设计基础数据库设计基础这四个方面在试卷中出现的情况是：选择题10个（20分），填空题5个（10分），总分值占到了试卷卷面分的30，是一个不小的比例。第9页4.算法的两个基本要素：算法的两个基本要素：n 算术运算算术运算n 关系运算关系运算n 逻辑运算逻辑运算n 数据传输数据传输n 顺序顺序n 选择选择n 循环循环u一是对数据对象的运算和操作；u二是算法的控制结构。u算法基本设计方法：

2、列举法、归纳法、递推、递归、减斗递推技术、回溯法 第10页 评价一个算法优劣的主要标准是算法的执行效率和存储需求：评价一个算法优劣的主要标准是算法的执行效率和存储需求：n 时间复杂度：执行这个算法所需要的时间复杂度：执行这个算法所需要的计算工作量计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量n 空间复杂度：执行这个算法所需要的空间复杂度：执行这个算法所需要的内存空间内存空间 算法在执行过程中临时占用的存储空间算法在执行过程中临时占用的存储空间 时间复杂度时间复杂度它大致等于计算机它大致等于计算机执行一种

3、简单操作所需的平均时间执行一种简单操作所需的平均时间与算法与算法中进行中进行简单操作的次数的乘积简单操作的次数的乘积。一个算法在计算机存储器上所占用的存储空间，包括一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用存储算法本身所占用的存储空间的存储空间、算法中的输入输出数据所占用的存储空间算法中的输入输出数据所占用的存储空间和和算法在运行过程中算法在运行过程中临时占用的存储空间临时占用的存储空间这三个部分这三个部分第11页：n 时间复杂度：执行这个算法所需要的计算工作量时间复杂度：执行这个算法所需要的计算工作量n 空间复杂度：执行这个算法所需要的内存空间空间复杂度：执行这个算法所

4、需要的内存空间第12页(1)在计算机中，算法是指在计算机中，算法是指_。A.查询方法查询方法 B.加工方法加工方法 C.解题方案的准确而完整的描述解题方案的准确而完整的描述 D.排序方法排序方法(2)下列叙述中正确的是下列叙述中正确的是（07年年4月月）A)算法的效率只与问题的规模有关，而与数据的存储结构无关算法的效率只与问题的规模有关，而与数据的存储结构无关B)算法的时间复杂度是指执行算法所需要的计算工作量算法的时间复杂度是指执行算法所需要的计算工作量C)数据的逻辑结构与存储结构是一一对应的数据的逻辑结构与存储结构是一一对应的D)算法的时间复杂度与空间复杂度一定相关算法的时间复杂度与空间复杂

5、度一定相关(3)算法的有穷性是指算法的有穷性是指(08年年4月月)A）算法程序的运行时间是有限的）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的）算法程序所处理的数据量是有限的 C）算法程序的长度是有限的）算法程序的长度是有限的 D）算法只能被有限的用户使用）算法只能被有限的用户使用(c)(B)算法习题:(A)第13页(4)算法的时问复杂度是指算法的时问复杂度是指 (2010年年3月月)A)算法的执行时间算法的执行时间B)算法所处理的数据量算法所处理的数据量C)算法程序中的语句或指令条数算法程序中的语句或指令条数D)算法在执行过程中所需要的基本运算次数算法在执行过程中所需要的基

6、本运算次数(5)算法的空间复杂度是指算法的空间复杂度是指(09年年9月月)A）算法在执行过程中所需要的计算机存储空间）算法在执行过程中所需要的计算机存储空间B）算法所处理的数据量）算法所处理的数据量C）算法程序中的语句或指令条数）算法程序中的语句或指令条数D）算法在执行过程中所需要的临时工作单元数）算法在执行过程中所需要的临时工作单元数(6)下列叙述中正确的是下列叙述中正确的是(06年年9月月)A）一个算法的空间复杂度大，则其时间复杂度也必定大）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小）一个算法的空间复杂度大，则其时间复杂度必定小C）一个算

7、法的时间复杂度大，则其空间复杂度必定小）一个算法的时间复杂度大，则其空间复杂度必定小 D）上述三种说法都不对）上述三种说法都不对(D)计算工作量(A)(D)第14页 计算机在进行数据处理时，实际需要处理的数据元素一般有计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的的数据元素在计算机中如何组织，以便提高数据处理的效率，并且数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，节省计算机的存储空间，这是进行数据处理的关键问题。这是进行数据处理的关键问题

8、。程序程序=算法算法+数据结构数据结构数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。一般情况下，在具有相同特征的数据元素集合中，各个数据一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。合中的数据元素所固有的一种结构。第15页二二.数据结构数据结构数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关

9、联的数据元素的集合。数据结构数据结构是研究数据和数据之间关系的一门是研究数据和数据之间关系的一门学科，它包括三个方面。学科，它包括三个方面。（1）数据集合中各数据元素之间所固有的逻）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。）对各种数据结构进行的运算。第16页u 1.逻辑结构逻辑结构 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构是指反映数据元素之间逻

10、辑关系的数据结构。数据的逻辑结构包含：数据的逻辑结构包含：（1）表示数据元素的信息；）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。）表示各数据元素之间的前后件关系。例：例：1.一年四季的数据结构一年四季的数据结构 B=(D,R)D=春，夏，秋，冬春，夏，秋，冬 R=(春，夏春，夏),(夏，秋夏，秋),(秋，冬秋，冬)2.家庭成员的数据结构家庭成员的数据结构 B=(D,R)D=父亲，儿子，女儿父亲，儿子，女儿 R=(父亲，儿子父亲，儿子),(父亲，女儿父亲，女儿)春夏秋冬数据结构的图形表示数据结构的图形表示父亲儿子女儿第17页u常见的常见的逻辑结构逻辑结构有：有：线性结构、树形结构

11、和图形结构。线性结构、树形结构和图形结构。线性结构线性结构树形结构树形结构图形结构图形结构u 线性结构线性结构 结构中的每个元素之间存在一个对一个的关系；结构中的每个元素之间存在一个对一个的关系；u 树形结构树形结构 结构中的每个元素之间存在一个对多个的关系；结构中的每个元素之间存在一个对多个的关系；u 图形结构或网状结构图形结构或网状结构 结构中的每个元素之间存在多个对多个的关系。结构中的每个元素之间存在多个对多个的关系。其中，其中，树形结构和图形结构统称为非线形结构树形结构和图形结构统称为非线形结构。数据的逻辑结构可。数据的逻辑结构可以用二元关系表示，也可以直观地用图形来表示。以用二元关系

12、表示，也可以直观地用图形来表示。第18页u 2.存储结构（物理结构存储结构（物理结构）计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。它们的逻辑关系不一定是相同的，而且一般也不可能相同。如：如：一年四季 家庭成员 计算机存储空间怎样存放？存储结构指数据结构在计算机存储空间中的具体实现。存储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有：常见

13、的存储结构有：n 顺序存储结构顺序存储结构n 链式存储结构链式存储结构n索引存储结构存储结构 只抽象地反映数据元素之间的关只抽象地反映数据元素之间的关系的结构，而不管其存储方式的系的结构，而不管其存储方式的数据结构称为逻辑结构。数据结构称为逻辑结构。一种一种数据结构可以根据需要表示数据结构可以根据需要表示成一种或多种存储结构成一种或多种存储结构。第19页u3.数据的运算数据的运算n 检索检索n 插入插入n 删除删除n 更新更新n 排序排序 通常，一个数据结构中的元素结点可能是动态变化的。根通常，一个数据结构中的元素结点可能是动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结据

14、需要或在处理过程中，可以在一个数据结构中增加一个新结点（插入运算），也可以删除某个结点（删除运算），除此之点（插入运算），也可以删除某个结点（删除运算），除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和外，对数据结构的运算还有查找、分类、合并、分解、复制和修改。修改。在对数据结构的处理过程中，不仅数据结构中结点的个数在对数据结构的处理过程中，不仅数据结构中结点的个数在动态变化，而且，各数据元素之间的关系也有可能在动态地在动态变化，而且，各数据元素之间的关系也有可能在动态地变化。变化。如：无序表变有序表数据结构是研究数据和数据之间数据结构是研究数据和数据之间关系的一门学科，研究以下三

15、方面关系的一门学科，研究以下三方面内容：内容：n 数据的逻辑结构数据的逻辑结构n 数据的存储结构数据的存储结构n 数据的运算数据的运算第20页常见的数据结构 1.线性表 2.栈和队列 3.树第21页 线性表是由线性表是由n（n0）个数据元素）个数据元素 a1，a2，ai，an组成的一个有限序列。组成的一个有限序列。春春夏夏秋秋冬冬记录记录1 02011001 张三张三 男男记录记录2 02011003 李四李四 女女 记录记录3记录记录4第22页 顺序存储结构把顺序存储结构把逻辑上相邻逻辑上相邻的的数据元素存储在数据元素存储在物理上相邻物理上相邻的存的存储单元里，顺序存储结构储单元里，顺序存储

16、结构只存储只存储结点的值结点的值，不存储结点间的关系，不存储结点间的关系，结点间的关系由存储单元的邻接结点间的关系由存储单元的邻接关系来体现。关系来体现。a1a2aian存储地址存储地址200020042000+4*(i-1)2000+4*(n-1)占占4个字节个字节第i个数的地址第一个数的地址L为该类型数所占的字节线性表的存储结构有两种：线性表的存储结构有两种：u 顺序存储结构顺序存储结构u 链式存储结构链式存储结构第23页u 顺序表的插入运算顺序表的插入运算u 顺序表的删除运算顺序表的删除运算 在线性表顺序存储情况下，要插入或删除一个元在线性表顺序存储情况下，要插入或删除一个元素，都会由于

17、数据元素的移动而消耗大量的处理时间，素，都会由于数据元素的移动而消耗大量的处理时间，所以这种存储方式对于小线性表或其中数据元素不经所以这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的。常变动的线性表是合适的。线性表的顺序存储结构称为顺序表。线性表的顺序存储结构称为顺序表。第24页u 线性表的链式存储结构称为线性链表。线性表的链式存储结构称为线性链表。u 链式存储结构不要求逻辑上相邻的数据元素物理位链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且各数据元素的存储顺序也是任意的。置也相邻，而且各数据元素的存储顺序也是任意的。各数据元素的先后关系是由各结点的指针域指示。各数

18、据元素的先后关系是由各结点的指针域指示。u 链式存储结构的每一个存储结点不仅存储结点的值，链式存储结构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系：而且存储结点之间的关系：数据域数据域指针域指针域第25页设线性表为设线性表为（a1，a2，a3，a4，a5）1a2923a1145a4106789a3510a50HEAD3a1a2a5a3a4HEAD319510线性链表的逻辑状态线性链表的逻辑状态线性链表线性链表的物理状态的物理状态1 a12 a23 a34 a45 a567注意:1 2 3 此类编号不代表所在的地址单元的地址编码第26页u 单链表的插入运算单链表的插入运算u 单链表的

19、删除运算单链表的删除运算采用链式存储结构，存储空间开销较大，但是进行插采用链式存储结构，存储空间开销较大，但是进行插入和删除运算不会造成大量元素的移动。入和删除运算不会造成大量元素的移动。循环链表是加一种形式的链式存储结构。它的特点是循环链表是加一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点。表中最后一个结点的指针域指向头结点。a1a2a5a3a4HEAD319510第27页双向链表的存储结构 提问：单向链表的缺点是什么？提示：如何寻找结点的直接前趋。双向链表可以克服单链表的单向性的缺点。在双向链表的结点中有两个指针域，其一指向在双向链表的结点中有两个指针域，其一指向直接

20、后继，另一指向直接前趋。直接后继，另一指向直接前趋。HEAD31510 a2 a3 a4 a1双向循环链表双向循环链表 第28页u 顺序存储结构顺序存储结构注意：注意：n 数据元素在计算机数据元素在计算机存储空间中的位置关存储空间中的位置关系与它们的逻辑关系系与它们的逻辑关系不一定是相同的。不一定是相同的。n 一个逻辑数据结构一个逻辑数据结构可以有多种存储结构，可以有多种存储结构，且不同的存储结构影且不同的存储结构影响数据处理的效率响数据处理的效率。1a2923a1145a4106789a3510a50HEAD31 a12 a23 a34 a45 a567u链式存储结构链式存储结构线性表线性表

21、:a1，a2，a3，a4，a5 第29页栈和队列都是特殊的线性表。栈和队列都是特殊的线性表。第30页是一种特殊的是一种特殊的线性表线性表。其特点是插入和删。其特点是插入和删除运算都只能在线性表的一端进行。除运算都只能在线性表的一端进行。u 栈是按照栈是按照“”或或“”的原则组织数的原则组织数据的线性表。据的线性表。u 栈的物理存储结构可以用顺序结构，也可以用链表结栈的物理存储结构可以用顺序结构，也可以用链表结构。构。u 下面讨论顺序存储结构中栈元素的插入和删除运算。下面讨论顺序存储结构中栈元素的插入和删除运算。n 顺序栈的进栈和出栈运算顺序栈的进栈和出栈运算 n栈的基本运算有三种：入栈、退栈和

22、读栈顶元素栈的基本运算有三种：入栈、退栈和读栈顶元素 在顺序栈中插入和删除运算不需要在顺序栈中插入和删除运算不需要移动表中其他数据元素移动表中其他数据元素。第31页是一种特殊的线性表。其特点是所有的是一种特殊的线性表。其特点是所有的插入都在表的一端插入都在表的一端进行，所有的进行，所有的删除删除运算都在表的运算都在表的另另一端一端进行。进行。u 队列是按照队列是按照“”或或“”的原则组织的原则组织数据的线性表。数据的线性表。u 队列的物理存储结构可以用顺序结构，也可以用链式队列的物理存储结构可以用顺序结构，也可以用链式结构。结构。u 顺序队列的运算顺序队列的运算 栈有三种操作：栈有三种操作：入

23、栈出栈读栈顶元素入栈出栈读栈顶元素队列有三种操作：入队出队读队首元素队列有三种操作：入队出队读队首元素例：有入栈元素序列：例：有入栈元素序列：ABCD，求可能的出栈序列，求可能的出栈序列如是队列又是什么情况呢？如是队列又是什么情况呢？第32页 把队列的存储空间在逻辑上看作一个环，当把队列的存储空间在逻辑上看作一个环，当R指向存指向存储空间的末端后，就把它重新置于始端。储空间的末端后，就把它重新置于始端。u 循环队列的运算循环队列的运算队列中进行插入的一端称做队尾队列中进行插入的一端称做队尾(rear),进行删除的一端进行删除的一端称做队首称做队首(front)。习题：数据结构分为逻辑结构和存储

24、结构，循环队习题：数据结构分为逻辑结构和存储结构，循环队列属于列属于【】结构。（结构。（2005年年9月）月）答案：存储结构。答案：存储结构。第33页常见数据结构的逻辑结构常见数据结构的逻辑结构u线性表线性表 线性结构u栈栈 是特殊的线性表 u队列队列 也是一种操作受限的特殊的线性表u树树（树型结构）（树型结构）是一种重要的非线形数据结构第34页数据存储结构方面的考题数据存储结构方面的考题 1：数据的存储结构是指：数据的存储结构是指 （2005年年4月）月）A)存储在外存中的数据存储在外存中的数据 B)数据所占的存储空间量数据所占的存储空间量C)数据在计算机中的顺序存储方式数据在计算机中的顺序

25、存储方式 D)数据的逻辑结构在计算机中的表示数据的逻辑结构在计算机中的表示2.下列叙述中正确的是下列叙述中正确的是（2009年年3月）月）A）栈是）栈是“先进先出先进先出”的线性表的线性表 B）队列是）队列是“先进后出先进后出”的线性表的线性表 C）循环队列是非线性结构）循环队列是非线性结构 D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构 3.数据结构分为线性结构和非线性结构，带链的队列属于数据结构分为线性结构和非线性结构，带链的队列属于 。4.下列数据结构中，属于非线性结构的是下列数据结构中，属于非线性结构的是A）循环队

26、列）循环队列 B)带链队列带链队列C)二叉树二叉树 D）带链栈）带链栈答案：答案：D。答案：答案：D。答案：线性结构。答案：线性结构。答案：答案：c第35页5。下列叙述中正确的是（下列叙述中正确的是（）。）。（2008年年9月）月）A）顺序存储结构的存储一定是连续的，链式存储结构的存储空）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的间不一定是连续的 B）顺序存储结构只针对线性结构，链式存储结构只针对非线性）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构结构 C）顺序存储结构能存储有序表，链式存储结构不能存储有序表）顺序存储结构能存储有序表，链式存储结构不能存储

27、有序表 D）链式存储结构比顺序存储结构节省存储空间）链式存储结构比顺序存储结构节省存储空间答案：答案：A。6 6。下列关于栈的叙述正确的是。下列关于栈的叙述正确的是 （2008年年4月）月）A A）栈按）栈按“先进先出先进先出”组织数据组织数据 B)B)栈按栈按“先进后出先进后出”组织数据组织数据 C C）只能在栈底插入数据）只能在栈底插入数据 D D）不能删除数据）不能删除数据 答案：答案：B。7.一个队列的初始状态为空。现将元素一个队列的初始状态为空。现将元素A，B，C，D，E，F，5，4，3，2，1依次入队，然后再依次退队，则元素退队的顺序为依次入队，然后再依次退队，则元素退队的顺序为【

28、1】。（。（2010年年3月）月）答案：答案：A，B，C，D，E，F，5，4，3，2，1第36页9.设某循环队列的容量为设某循环队列的容量为50，如果头指针，如果头指针front=45(指向指向队头元素的前一位置队头元素的前一位置)，尾指针，尾指针rear=10(指向队尾元素指向队尾元素)，则该循环队列中共有则该循环队列中共有【2】个元素。个元素。（2010年年3月）月）8。假设用一个长度为。假设用一个长度为50的数组（数组元索的下标从的数组（数组元索的下标从0到到49）作为栈的存储空间，栈底指针）作为栈的存储空间，栈底指针bottom指间栈底指间栈底元素，栈顶指针元素，栈顶指针top指向栈顶

29、元素，如果指向栈顶元素，如果bottom=49，top=30（数组下标），则栈中具有【（数组下标），则栈中具有【】个元素。】个元素。（2009年年3月）月）答案：答案：19答案：答案：15第37页一个非空的数据结构若满足下面的两个条件，则这种数据结一个非空的数据结构若满足下面的两个条件，则这种数据结构即为构即为。有且仅有一个根结点；有且仅有一个根结点；除第一个结点外，每一个结点最多有一个直接前驱结点；除第一个结点外，每一个结点最多有一个直接前驱结点；除最后一个结点外，每一个结点最多有一个直接后继结点。除最后一个结点外，每一个结点最多有一个直接后继结点。u 线性结构与非线性结构线性结构与非线性结

30、构线性表、栈和队列都是线性结构线性表、栈和队列都是线性结构 一个数据结构不是线性结构，则称其为一个数据结构不是线性结构，则称其为。a1a2a5a3a4HEAD319510线性链表的逻辑状态线性链表的逻辑状态第38页树型结构是一种重要的非线性结构。树型结构是一种重要的非线性结构。u 树的概念树的概念u 二叉树的概念二叉树的概念u 二叉树的存储二叉树的存储u 二叉树的遍历二叉树的遍历第39页u 树的定义：树的定义：n个结点的有限集。（个结点的有限集。（n=0）ABDFECGHIJKMn 根：根：only onen 若若n=0，则称为空树；，则称为空树；n 否则，当否则，当n1时，其余结时，其余结点

31、被分成点被分成m（m0）个互不）个互不相交的子集相交的子集T1，T2，.，Tm，每个子集又是一棵树。，每个子集又是一棵树。由此可以看出，树的定义是由此可以看出，树的定义是递归的。递归的。n Question：如何辨别根？：如何辨别根？A只有一个只有一个结点的树结点的树第40页ABDFECGHIJKMn 一个结点的子树的一个结点的子树的个数；个数；Q：结点结点A、G的度数？的度数？n 树中所有结点度的最树中所有结点度的最大值；大值；Q：右图中树的度？右图中树的度？n 度为度为0的结点；的结点；Q：图中叶子结点有几个？图中叶子结点有几个？7 度不为度不为0的结点；的结点；Q：图中非终端结点有几个？

32、图中非终端结点有几个？5第41页ABDFECGHIJKMn 树中根结点的层树中根结点的层次为次为1，根结点子树的根为第，根结点子树的根为第2层，层，以此类推；以此类推；Q：图中结点图中结点F的层次？的层次？n 树中所有结点层次树中所有结点层次的最大值；的最大值；Q：图中树的深度？图中树的深度？n 如果树中每如果树中每棵子树从左向右的排列拥有一定棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序的顺序，不得互换，则称为有序树，否则称为无序树。树，否则称为无序树。第42页 二叉树是一种有序的树形结构。它与一般二叉树是一种有序的树形结构。它与一般树形结构的区别是：树形结构的区别是：n 每个结点

33、最多有两棵子树；每个结点最多有两棵子树；n 子树有左右之分，次序不能任意颠倒。子树有左右之分，次序不能任意颠倒。二叉树的二叉树的5种基本形态种基本形态第43页【性质1】在二叉树的第在二叉树的第i层上最多有层上最多有2i-1个结点（个结点（i1）ABCDFEHG第44页【性质2】深度为深度为h的二叉树最多有的二叉树最多有2h-1个结点（个结点（h 1）如果一个深度为如果一个深度为h的二叉树拥有的二叉树拥有2h-1个结个结点，则将它称为点，则将它称为满二叉树满二叉树。有一棵深度为有一棵深度为h，具有，具有n个结点的二叉树，个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上若将它与一棵同

34、深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为的每个结点分别与满二叉树中编号为1n的结点位置的结点位置一一对应，则称这棵二叉树为一一对应，则称这棵二叉树为完全二叉树完全二叉树。第45页1213 141589 10 114567123满二叉树满二叉树完全二叉树完全二叉树121389 10 114567123 完全二叉树是满二叉树 满二叉树也是完全二叉树第46页121389 10 11456123非完全二叉树非完全二叉树深度为深度为4的的完全二叉树完全二叉树84567123第47页【性质3

35、】二叉树上叶子结点数比度为二叉树上叶子结点数比度为2的结点数多的结点数多1ABCDFEHG度为2的结点叶子结点第48页【性质4】具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2(n+1)其中，其中，log2n 的结果是不大于的结果是不大于log2n的最大整数的最大整数1213 141589 10 114567123深度为深度为4的的满二叉树满二叉树深度为深度为4的的完全二叉树完全二叉树84567123深度为深度为3的完全二叉树具有的完全二叉树具有47深度为深度为4的完全二叉树具有的完全二叉树具有815深度为深度为5的完全二叉树具有的完全二叉树具有1531 log2(8+

36、1)=ln9/In2=4 log2(15+1)=In16/In2=4深度为深度为6的完全二叉树的完全二叉树 具有具有3263深度为深度为7的完全二叉树的完全二叉树 具有具有64127深度为深度为8的完全二叉树的完全二叉树 具有具有128255深度为深度为9的完全二叉树的完全二叉树 具有具有256511深度为深度为10的完全二叉树具有的完全二叉树具有5121023深度为深度为11的完全二叉树具有的完全二叉树具有10242047第49页1 1：在深度为：在深度为7 7的满二叉树中的满二叉树中,叶子结点的个数为（叶子结点的个数为（20062006年年4 4月）月）A)32 A)32 B)31 B)3

37、1 C)64C)64 D)63D)632 2：在深度为：在深度为7 7的满二叉树中，度为的满二叉树中，度为2 2的结点个数为的结点个数为【】。(07(07年年4 4月）月）3 3：一棵二叉树中共有：一棵二叉树中共有7070个叶子结点与个叶子结点与8080个度为个度为1 1的结点，则该二叉树中的总的结点，则该二叉树中的总结点数为结点数为 （0707年年9 9月）月）A A）219 B219 B）221 C221 C）229 D229 D）2312314 4：某二叉树中度为某二叉树中度为2 2的结点有的结点有1818个，则该二叉树中有个，则该二叉树中有 【】个叶子结点。个叶子结点。（2005200

38、5年年4 4月）月）5 5：一棵二叉树第六层（根结点为第一层）的结点数最多为：一棵二叉树第六层（根结点为第一层）的结点数最多为【】个。（个。（20052005年年9 9月）月）树型结构方面的考题树型结构方面的考题 1答案：答案：C。3答案：答案：A。5答案：答案：32。2答案：答案：63。4答案：答案：19。第50页u 在计算机中，二叉树通常采用链式存储结构。在计算机中，二叉树通常采用链式存储结构。LlinkinfoRlink二叉树的存储结点的结构二叉树的存储结点的结构ABDCFGE A G E F B C Dt第51页u 遍历指遍历指不重复地不重复地访问二叉树中的访问二叉树中的所有结点所有结

39、点。u 二叉树的遍历的次序与树型结构上的大多二叉树的遍历的次序与树型结构上的大多数运算有联系。数运算有联系。（1）先（前）序遍历（）先（前）序遍历（DLR）（2）中序遍历（）中序遍历（LDR）（3）后序遍历（）后序遍历（LRD）ABCDFEHG第52页u 遍历指遍历指不重复地不重复地访问二叉树中的访问二叉树中的所有结点所有结点。（1）先（前）序遍历（）先（前）序遍历（DLR）若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则n访问根结点；访问根结点；遍历左子树；遍历左子树；遍历右子树。遍历右子树。ABCDFEHG先序遍历的结果：先序遍历的结果：A A B E C F G H

40、D B E C F G H D第53页（2）中序遍历（）中序遍历（LDR）若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则n中序遍历左子树；中序遍历左子树；n访问根结点；访问根结点；n中序遍历右子树。中序遍历右子树。中序遍历的结果：中序遍历的结果：E B A F H G C D（3）后序遍历（）后序遍历（LRD）若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则n后序遍历左子树；后序遍历左子树；n后序遍历右子树；后序遍历右子树；n访问根结点。访问根结点。后序遍历的结果：后序遍历的结果：E B H G F D C AABCDFEHG第54页u先序序列：先序序

41、列：ABDGCEFHu中序序列：中序序列：DGBAECHFu后序序列：后序序列：GDBEHFCAABCFHDEG下图所示的二叉树经过三种遍历得到的顺序分别为？下图所示的二叉树经过三种遍历得到的顺序分别为？练习：练习：根据先序遍历序列，建立二叉树根据先序遍历序列，建立二叉树第55页1:设二叉树如下：设二叉树如下：（2010年年3月）月）对该二叉树进行后序遍历的对该二叉树进行后序遍历的结果为结果为【3】树型结构方面的考题树型结构方面的考题 22:对如下二叉树（对如下二叉树（2006年年4月）月）进行后序遍历的结果为进行后序遍历的结果为A)ABCDEF B)DBEAFC C)ABDECF D)DEB

42、FCA EDBGHFCA DABCFHDGE第56页 查找是数据处理的重要内容。查找是数据处理的重要内容。u 查找指在一个给定的数据结构中查找指定的元素，查找指在一个给定的数据结构中查找指定的元素，该元素也称关键字。该元素也称关键字。u 若找到了满足条件的结点，称查找成功；否则称查若找到了满足条件的结点，称查找成功；否则称查找失败。找失败。u衡量一个查找算法的主要标准是查找过程中对关键衡量一个查找算法的主要标准是查找过程中对关键字进行的平均比较次数。字进行的平均比较次数。u 通常根据不同的数据结构，采用不同的查找方法：通常根据不同的数据结构，采用不同的查找方法：n 顺序查找顺序查找n 二分查找

43、二分查找第57页u线性表中最简单的查找方法。线性表中最简单的查找方法。u 方法：从线性表的第一个元素开始，依次将线性方法：从线性表的第一个元素开始，依次将线性表中的元素与关键字进行比较，若相等，则查找成表中的元素与关键字进行比较，若相等，则查找成功；若将所有元素都与关键字进行了比较但不相等，功；若将所有元素都与关键字进行了比较但不相等，则查找失败。则查找失败。u 顺序查找法的适用场合：顺序查找法的适用场合：n 对线性表中元素的排列次序没有要求；对线性表中元素的排列次序没有要求；n 对线性表的存储结构没有要求，链式结构和顺对线性表的存储结构没有要求，链式结构和顺序结构均可。序结构均可。第58页折

44、半查找)u 是一种效率较高的查找方法，但是只适合是一种效率较高的查找方法，但是只适合顺序存储顺序存储的有序表的有序表。u二分查找的方法：首先将关键字与线性表中间位置二分查找的方法：首先将关键字与线性表中间位置的结点比较，相等则查找成功；不相等则根据比较的结点比较，相等则查找成功；不相等则根据比较结果确定下一步查找应在哪个子表中进行；重复上结果确定下一步查找应在哪个子表中进行；重复上述过程，直至查找成功或子表长度为述过程，直至查找成功或子表长度为0。u 二分查找法的适用场合：二分查找法的适用场合：n 线性表中的元素按关键字值递增或递减的次序排线性表中的元素按关键字值递增或递减的次序排列；列；n

45、线性表采用顺序存储结构。线性表采用顺序存储结构。第59页u练习假设待查有序（升序）顺序表中数据元素的关键字序列为（8,18,27,42,47,50,56,68,95,120），用折半查找方法查找关键字值为27的数据元素.对于长度为对于长度为n n的有序线性表，最坏情况只需比较的有序线性表，最坏情况只需比较log2nlog2n次。次。第60页u 排序指排序指将一个无序序列整理成按关键字值递增或递减排列的有序将一个无序序列整理成按关键字值递增或递减排列的有序序列序列。u 排序方法中其排序对象一般是排序方法中其排序对象一般是顺序存储顺序存储的线性表。的线性表。u 根据排序序列的规模以及数据处理的要求

46、，可以采用不同的排序根据排序序列的规模以及数据处理的要求，可以采用不同的排序方法方法：交换类排序法交换类排序法 n冒泡排序冒泡排序n快速排序快速排序 插入类排序法插入类排序法n简单插入排序简单插入排序n希尔排序希尔排序选择类排序法选择类排序法n简单选择排序简单选择排序n堆排序堆排序第61页u 冒泡排序的方法：冒泡排序的方法：n扫描整个线性表，逐次对相邻的两个元素进行比扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最较，若为逆序，则交换；第一趟扫描的结果使最大大(或最小或最小)的元素排到表的最后的元素排到表的最后(或最前或最前)；n除最后除最后(或最前或最前)

47、一个元素，对剩余的元素重复上一个元素，对剩余的元素重复上述过程，将次大述过程，将次大(或次小或次小)的数排到表的倒数的数排到表的倒数(或正或正数数)第二个位置；第二个位置；n重复上述过程；重复上述过程；n对于长度为对于长度为n的线性表，冒泡排序需要对表扫描的线性表，冒泡排序需要对表扫描n-1遍。遍。第62页冒泡排序的方法冒泡排序的方法u 设待排数据元素的关键字为（18，20，15，32，4，25），冒泡排序后的序列状态如图所示：18 20 15 32 4 25 18 20 15 32 4 25 18 15 20 32 4 25 18 15 20 32 4 25 18 15 20 4 32 25

48、 18 15 20 4 25 32 最大数u第二趟冒泡排序第二趟冒泡排序下一页上一页停止放映第第6363|92|92页页Q：第二趟冒泡排序后的结果是什么样的？达到第二趟冒泡排序后的结果是什么样的？达到了最终的排序目标吗？一共需要多少次能够最了最终的排序目标吗？一共需要多少次能够最后成为有序序列？后成为有序序列？Q：你觉得冒泡排序的效率如何？如果是你，你：你觉得冒泡排序的效率如何？如果是你，你会用什么方法来排序？会用什么方法来排序？冒泡排序比较简单，当初始序列基本有序时，冒泡排序比较简单，当初始序列基本有序时，冒泡排序有较高的效率，反之效率较低。冒泡排序有较高的效率，反之效率较低。u冒泡排序终止

49、条件冒泡排序终止条件:本趟排序未发生交换，终止排序算法本趟排序未发生交换，终止排序算法 下一页上一页停止放映第第6464|92|92页页初始初始 第一趟第一趟 第二趟第二趟 第三趟第三趟 第四趟第四趟 第五趟第五趟序列序列 排序后排序后 排序后排序后 排序后排序后 排序后排序后 排序后排序后26 18 18 18 18 918 26 26 26 9 1532 32 32 9 15 1854 47 9 15 2647 9 15 329 15 4715 54设待排数据元素的关键字为设待排数据元素的关键字为（26,18,32,54,47,9,15)冒泡排序法，需要比较的次数为冒泡排序法，需要比较的次

50、数为n(n-1)/2n(n-1)/2；第65页u 选择排序的方法：选择排序的方法：n扫描整个线性表，从中找出最小的元素，与第扫描整个线性表，从中找出最小的元素，与第一个元素交换；一个元素交换；n除第一个元素，对剩下的子表采用相同的方法除第一个元素，对剩下的子表采用相同的方法找出次小的数，与第二个数交换；找出次小的数，与第二个数交换；n重复上述过程；重复上述过程；n对于长度为对于长度为n的线性表，选择排序需要对表扫的线性表，选择排序需要对表扫描描n-1遍。遍。简单选择排序法简单选择排序法,最坏情况需要最坏情况需要n(n-1)/2n(n-1)/2次比较；次比较；下一页上一页停止放映第第6666|9