1、计算机等级考试计算机等级考试公共基础知识公共基础知识 第2页计算机二级考试公共基础知识计算机二级考试公共基础知识大纲 q 数据结构与算法数据结构与算法q 程序设计基础程序设计基础q 软件工程基础软件工程基础q 数据库设计基础数据库设计基础第3页 算法的基算法的基本概念本概念 2.2.算法复杂算法复杂度的概念和度的概念和意义意义 数据结构的概念数据结构的概念 线性表线性表 栈和队列栈和队列 树与二叉树树与二叉树 查找技术查找技术 排序技术排序技术 对于等级考试，这个部分的考核对于等级考试，这个部分的考核重点主要重点主要在在算法和数据结构的基本概算法和数据结构的基本概念念、二叉树二叉树(遍历、结点
2、），遍历、结点），还有还有排序和查找排序和查找考试中也经常会涉及到。考试中也经常会涉及到。第4页算法的定义算法的定义算法是程序设计的核心算法是程序设计的核心 算法是在有限步骤内求解某一问题所使用的一组算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过定义明确的规则。通俗点说，就是计算机解题的过程程(计算的方法计算的方法)。在这个过程中，无论是形成解题。在这个过程中，无论是形成解题思路思路(推理实现的算法推理实现的算法)还是编写程序还是编写程序(操作实现的算操作实现的算法法)，都是在实施某种算法。，都是在实施某种算法。例：例：n个数从大到小进行排序。个数从大到
3、小进行排序。有多种排序方法有多种排序方法 ，常用的有冒泡排序、选择排序等。，常用的有冒泡排序、选择排序等。第5页 2.算法的基本特征算法的基本特征一个算法应该具有以下五个重要的特征：一个算法应该具有以下五个重要的特征：n 有穷性有穷性n 确定性确定性n 输入输入n 输出输出n 可行性可行性一个算法必须保证执行有限步之后结束；算法的每一步骤必须有确切的定义；一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成
4、第6页u算法与计算机程序算法与计算机程序 算法算法_是一组逻辑步骤是一组逻辑步骤 程序程序用计算机语言描述的算法用计算机语言描述的算法INPUT rS=3.14*r*rPTINT S开始开始输入输入R RS=3.14*R*R输出输出S S结束结束问题：输入园的半径，计算园的面积 一个算法的表示需要使用一些语言形式。一个算法的表示需要使用一些语言形式。传统的算法传统的算法-图形法，如图形法，如“流程图流程图”和和N-S图图目前常用的方法目前常用的方法-使用伪码描述算法。使用伪码描述算法。第7页冒泡排序的方法：冒泡排序的方法：1.扫描整个线性表，逐次对扫描整个线性表，逐次对相邻的两个元素进行比较，
5、相邻的两个元素进行比较，若为逆序，则交换；第一趟若为逆序，则交换；第一趟扫描的结果使最大的元素排扫描的结果使最大的元素排到表的最后到表的最后；2.除最后一个元素，对剩余除最后一个元素，对剩余的元素重复上述过程，将次的元素重复上述过程，将次大的数排到表的倒数第二个大的数排到表的倒数第二个位置；位置；3.重复上述过程；重复上述过程；对于长度为对于长度为n的线性表，冒泡的线性表，冒泡排序需要对表扫描排序需要对表扫描n-1遍。遍。算法举例：算法举例：n个数排序个数排序第8页4.算法的两个基本要素：算法的两个基本要素：n 算术运算算术运算n 关系运算关系运算n 逻辑运算逻辑运算n 数据传输数据传输n 顺
6、序顺序n 选择选择n 循环循环u一是对数据对象的运算和操作；u二是算法的控制结构。u算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法 第9页 评价一个算法优劣的主要标准是算法的执行效率和存储需求：评价一个算法优劣的主要标准是算法的执行效率和存储需求：n 时间复杂度：执行这个算法所需要的时间复杂度：执行这个算法所需要的计算工作量计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量n 空间复杂度：执行这个算法所需要的空间复杂度：执行这个算法所需要的内存空间内存空间 算法在执行过程中临时占用的存储
7、空间算法在执行过程中临时占用的存储空间 时间复杂度时间复杂度它大致等于计算机它大致等于计算机执行一种简单操作所需的平均时间执行一种简单操作所需的平均时间与算法与算法中进行中进行简单操作的次数的乘积简单操作的次数的乘积。一个算法在计算机存储器上所占用的存储空间，包括一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用存储算法本身所占用的存储空间的存储空间、算法中的输入输出数据所占用的存储空间算法中的输入输出数据所占用的存储空间和和算法在运行过程中算法在运行过程中临时占用的存储空间临时占用的存储空间这三个部分这三个部分第10页：n 时间复杂度：执行这个算法所需要的计算工作量时间复杂度：
8、执行这个算法所需要的计算工作量n 空间复杂度：执行这个算法所需要的内存空间空间复杂度：执行这个算法所需要的内存空间第11页(1)在计算机中，算法是指在计算机中，算法是指_。A.查询方法查询方法 B.加工方法加工方法 C.解题方案的准确而完整的描述解题方案的准确而完整的描述 D.排序方法排序方法(2)下列叙述中正确的是下列叙述中正确的是 A)算法的效率只与问题的规模有关，而与数据的存储结构无关算法的效率只与问题的规模有关，而与数据的存储结构无关B)算法的时间复杂度是指执行算法所需要的计算工作量算法的时间复杂度是指执行算法所需要的计算工作量C)数据的逻辑结构与存储结构是一一对应的数据的逻辑结构与存
9、储结构是一一对应的D)算法的时间复杂度与空间复杂度一定相关算法的时间复杂度与空间复杂度一定相关(3)算法的有穷性是指算法的有穷性是指 A）算法程序的运行时间是有限的）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的）算法程序所处理的数据量是有限的 C）算法程序的长度是有限的）算法程序的长度是有限的 D）算法只能被有限的用户使用）算法只能被有限的用户使用(c)(B)算法习题:(A)第12页(4)算法的时问复杂度是指算法的时问复杂度是指 (2010年年3月月)A)算法的执行时间算法的执行时间B)算法所处理的数据量算法所处理的数据量C)算法程序中的语句或指令条数算法程序中的语句或指令条
10、数D)算法在执行过程中所需要的基本运算次数算法在执行过程中所需要的基本运算次数(5)算法的空间复杂度是指算法的空间复杂度是指(09年年9月月)A）算法在执行过程中所需要的计算机存储空间）算法在执行过程中所需要的计算机存储空间B）算法所处理的数据量）算法所处理的数据量C）算法程序中的语句或指令条数）算法程序中的语句或指令条数D）算法在执行过程中所需要的临时工作单元数）算法在执行过程中所需要的临时工作单元数(6)下列叙述中正确的是下列叙述中正确的是(06年年9月月)A）一个算法的空间复杂度大，则其时间复杂度也必定大）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间
11、复杂度必定小）一个算法的空间复杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间复杂度必定小）一个算法的时间复杂度大，则其空间复杂度必定小 D）上述三种说法都不对）上述三种说法都不对(D)计算工作量(A)(D)第13页 计算机在进行数据处理时，实际需要处理的数据元素一般有计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的的数据元素在计算机中如何组织，以便提高数据处理的效率，并且数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，节省计算
12、机的存储空间，这是进行数据处理的关键问题。这是进行数据处理的关键问题。程序程序=算法算法+数据结构数据结构数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。一般情况下，在具有相同特征的数据元素集合中，各个数据一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。合中的数据元素所固有的一种结构。第14页二二.数据结构
13、数据结构数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。数据结构数据结构是研究数据和数据之间关系的一门是研究数据和数据之间关系的一门学科，它包括三个方面。学科，它包括三个方面。（1）数据集合中各数据元素之间所固有的逻）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。）对各种数据结构进行的运算。第15页u 1.逻辑结构逻辑结构 数据的逻辑结构是指反映
14、数据元素之间逻辑关系的数据结构。数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构包含：数据的逻辑结构包含：（1）表示数据元素的信息；）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。）表示各数据元素之间的前后件关系。例：例：1.一年四季的数据结构一年四季的数据结构 B=(D,R)D=春，夏，秋，冬春，夏，秋，冬 R=(春，夏春，夏),(夏，秋夏，秋),(秋，冬秋，冬)2.家庭成员的数据结构家庭成员的数据结构 B=(D,R)D=父亲，儿子，女儿父亲，儿子，女儿 R=(父亲，儿子父亲，儿子),(父亲，女儿父亲，女儿)春夏秋冬数据结构的图形表示数据结构的图形表示父亲儿子
15、女儿第16页u常见的常见的逻辑结构逻辑结构有：有：线性结构、树形结构和图形结构。线性结构、树形结构和图形结构。线性结构线性结构树形结构树形结构图形结构图形结构u 线性结构线性结构 结构中的每个元素之间存在一个对一个的关系；结构中的每个元素之间存在一个对一个的关系；u 树形结构树形结构 结构中的每个元素之间存在一个对多个的关系；结构中的每个元素之间存在一个对多个的关系；u 图形结构或网状结构图形结构或网状结构 结构中的每个元素之间存在多个对多个的关系。结构中的每个元素之间存在多个对多个的关系。其中，其中，树形结构和图形结构统称为非线形结构树形结构和图形结构统称为非线形结构。数据的逻辑结构可。数据
16、的逻辑结构可以用二元关系表示，也可以直观地用图形来表示。以用二元关系表示，也可以直观地用图形来表示。第17页u 2.存储结构（物理结构存储结构（物理结构）计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。它们的逻辑关系不一定是相同的，而且一般也不可能相同。如：如：一年四季 家庭成员 计算机存储空间怎样存放？存储结构指数据结构在计算机存储空间中的具体实现。存
17、储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有：常见的存储结构有：n 顺序存储结构顺序存储结构n 链式存储结构链式存储结构n索引存储结构存储结构 只抽象地反映数据元素之间的关只抽象地反映数据元素之间的关系的结构，而不管其存储方式的系的结构，而不管其存储方式的数据结构称为逻辑结构。数据结构称为逻辑结构。一种一种数据结构可以根据需要表示数据结构可以根据需要表示成一种或多种存储结构成一种或多种存储结构。第18页u3.数据的运算数据的运算n 检索检索n 插入插入n 删除删除n 更新更新n 排序排序 通常，一个数据结构中的元素结点可能是动态变化的。根通常，一个数据结构中的元素结点可能是动
18、态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结据需要或在处理过程中，可以在一个数据结构中增加一个新结点（插入运算），也可以删除某个结点（删除运算），除此之点（插入运算），也可以删除某个结点（删除运算），除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和外，对数据结构的运算还有查找、分类、合并、分解、复制和修改。修改。在对数据结构的处理过程中，不仅数据结构中结点的个数在对数据结构的处理过程中，不仅数据结构中结点的个数在动态变化，而且，各数据元素之间的关系也有可能在动态地在动态变化，而且，各数据元素之间的关系也有可能在动态地变化。变化。如：无序表变有序表数据结构是研究
19、数据和数据之间数据结构是研究数据和数据之间关系的一门学科，研究以下三方面关系的一门学科，研究以下三方面内容：内容：n 数据的逻辑结构数据的逻辑结构n 数据的存储结构数据的存储结构n 数据的运算数据的运算第19页常见的数据结构 1.线性表 2.栈和队列 3.树第20页 线性表是由线性表是由n（n0）个数据元素）个数据元素 a1，a2，ai，an组成的一个有限序列。组成的一个有限序列。春春夏夏秋秋冬冬记录记录1 02011001 张三张三 男男记录记录2 02011003 李四李四 女女 记录记录3记录记录4第21页 顺序存储结构把顺序存储结构把逻辑上相邻逻辑上相邻的的数据元素存储在数据元素存储在
20、物理上相邻物理上相邻的存的存储单元里，顺序存储结构储单元里，顺序存储结构只存储只存储结点的值结点的值，不存储结点间的关系，不存储结点间的关系，结点间的关系由存储单元的邻接结点间的关系由存储单元的邻接关系来体现。关系来体现。a1a2aian存储地址存储地址200020042000+4*(i-1)2000+4*(n-1)占占4个字节个字节第i个数的地址第一个数的地址L为该类型数所占的字节线性表的存储结构有两种：线性表的存储结构有两种：u 顺序存储结构顺序存储结构u 链式存储结构链式存储结构第22页u 顺序表的插入运算顺序表的插入运算u 顺序表的删除运算顺序表的删除运算 在线性表顺序存储情况下，要插
21、入或删除一个元在线性表顺序存储情况下，要插入或删除一个元素，都会由于数据元素的移动而消耗大量的处理时间，素，都会由于数据元素的移动而消耗大量的处理时间，所以这种存储方式对于小线性表或其中数据元素不经所以这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的。常变动的线性表是合适的。线性表的顺序存储结构称为顺序表。线性表的顺序存储结构称为顺序表。第23页u 线性表的链式存储结构称为线性链表。线性表的链式存储结构称为线性链表。u 链式存储结构不要求逻辑上相邻的数据元素物理位链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且各数据元素的存储顺序也是任意的。置也相邻，而且各数据元素的
22、存储顺序也是任意的。各数据元素的先后关系是由各结点的指针域指示。各数据元素的先后关系是由各结点的指针域指示。u 链式存储结构的每一个存储结点不仅存储结点的值，链式存储结构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系：而且存储结点之间的关系：数据域数据域指针域指针域第24页设线性表为设线性表为（a1，a2，a3，a4，a5）1a2923a1145a4106789a3510a50HEAD3a1a2a5a3a4HEAD319510线性链表的逻辑状态线性链表的逻辑状态线性链表线性链表的物理状态的物理状态1 a12 a23 a34 a45 a567注意:1 2 3 此类编号不代表所在的地址单
23、元的地址编码第25页u 单链表的插入运算单链表的插入运算u 单链表的删除运算单链表的删除运算采用链式存储结构，存储空间开销较大，但是进行插采用链式存储结构，存储空间开销较大，但是进行插入和删除运算不会造成大量元素的移动。入和删除运算不会造成大量元素的移动。循环链表是加一种形式的链式存储结构。它的特点是循环链表是加一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点。表中最后一个结点的指针域指向头结点。a1a2a5a3a4HEAD319510第26页双向链表的存储结构 提问：单向链表的缺点是什么？提示：如何寻找结点的直接前趋。双向链表可以克服单链表的单向性的缺点。在双向链表的结点
24、中有两个指针域，其一指向在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。直接后继，另一指向直接前趋。HEAD31510 a2 a3 a4 a1双向循环链表双向循环链表 第27页u 顺序存储结构顺序存储结构注意：注意：n 数据元素在计算机数据元素在计算机存储空间中的位置关存储空间中的位置关系与它们的逻辑关系系与它们的逻辑关系不一定是相同的。不一定是相同的。n 一个逻辑数据结构一个逻辑数据结构可以有多种存储结构，可以有多种存储结构，且不同的存储结构影且不同的存储结构影响数据处理的效率响数据处理的效率。1a2923a1145a4106789a3510a50HEAD31 a12 a
25、23 a34 a45 a567u链式存储结构链式存储结构线性表线性表:a1，a2，a3，a4，a5 第28页栈和队列都是特殊的线性表。栈和队列都是特殊的线性表。第29页是一种特殊的是一种特殊的线性表线性表。其特点是插入和删。其特点是插入和删除运算都只能在线性表的一端进行。除运算都只能在线性表的一端进行。u 栈是按照栈是按照“”或或“”的原则组织数的原则组织数据的线性表。据的线性表。u 栈的物理存储结构可以用顺序结构，也可以用链表结栈的物理存储结构可以用顺序结构，也可以用链表结构。构。u 下面讨论顺序存储结构中栈元素的插入和删除运算。下面讨论顺序存储结构中栈元素的插入和删除运算。n 顺序栈的进栈
26、和出栈运算顺序栈的进栈和出栈运算 n栈的基本运算有三种：入栈、退栈和读栈顶元素栈的基本运算有三种：入栈、退栈和读栈顶元素 在顺序栈中插入和删除运算不需要在顺序栈中插入和删除运算不需要移动表中其他数据元素移动表中其他数据元素。第30页是一种特殊的线性表。其特点是所有的是一种特殊的线性表。其特点是所有的插入都在表的一端插入都在表的一端进行，所有的进行，所有的删除删除运算都在表的运算都在表的另另一端一端进行。进行。u 队列是按照队列是按照“”或或“”的原则组织的原则组织数据的线性表。数据的线性表。u 队列的物理存储结构可以用顺序结构，也可以用链式队列的物理存储结构可以用顺序结构，也可以用链式结构。结
27、构。u 顺序队列的运算顺序队列的运算 栈有三种操作：栈有三种操作：入栈出栈读栈顶元素入栈出栈读栈顶元素队列有三种操作：入队出队读队首元素队列有三种操作：入队出队读队首元素例：有入栈元素序列：例：有入栈元素序列：ABCD，求可能的出栈序列，求可能的出栈序列如是队列又是什么情况呢？如是队列又是什么情况呢？第31页 把队列的存储空间在逻辑上看作一个环，当把队列的存储空间在逻辑上看作一个环，当R指向存指向存储空间的末端后，就把它重新置于始端。储空间的末端后，就把它重新置于始端。u 循环队列的运算循环队列的运算队列中进行插入的一端称做队尾队列中进行插入的一端称做队尾(rear),进行删除的一端进行删除的
28、一端称做队首称做队首(front)。习题：数据结构分为逻辑结构和存储结构，循环队习题：数据结构分为逻辑结构和存储结构，循环队列属于列属于【】结构。（结构。（2005年年9月）月）答案：存储结构。答案：存储结构。第32页常见数据结构的逻辑结构常见数据结构的逻辑结构u线性表线性表 线性结构u栈栈 是特殊的线性表 u队列队列 也是一种操作受限的特殊的线性表u树树（树型结构）（树型结构）是一种重要的非线形数据结构第33页数据存储结构方面的考题数据存储结构方面的考题 1：数据的存储结构是指：数据的存储结构是指 （2005年年4月）月）A)存储在外存中的数据存储在外存中的数据 B)数据所占的存储空间量数据
29、所占的存储空间量C)数据在计算机中的顺序存储方式数据在计算机中的顺序存储方式 D)数据的逻辑结构在计算机中的表示数据的逻辑结构在计算机中的表示2.下列叙述中正确的是下列叙述中正确的是（2009年年3月）月）A）栈是）栈是“先进先出先进先出”的线性表的线性表 B）队列是）队列是“先进后出先进后出”的线性表的线性表 C）循环队列是非线性结构）循环队列是非线性结构 D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构 3.数据结构分为线性结构和非线性结构，带链的队列属于数据结构分为线性结构和非线性结构，带链的队列属于 。4.下列数据结
30、构中，属于非线性结构的是下列数据结构中，属于非线性结构的是A）循环队列）循环队列 B)带链队列带链队列C)二叉树二叉树 D）带链栈）带链栈答案：答案：D。答案：答案：D。答案：线性结构。答案：线性结构。答案：答案：c第34页5。下列叙述中正确的是（下列叙述中正确的是（）。）。（2008年年9月）月）A）顺序存储结构的存储一定是连续的，链式存储结构的存储空）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的间不一定是连续的 B）顺序存储结构只针对线性结构，链式存储结构只针对非线性）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构结构 C）顺序存储结构能存储有序表，链式存
31、储结构不能存储有序表）顺序存储结构能存储有序表，链式存储结构不能存储有序表 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依次入队，然后再依次退
32、队，则元素退队的顺序为依次入队，然后再依次退队，则元素退队的顺序为【1】。（。（2010年年3月）月）答案：答案：A，B，C，D，E，F，5，4，3，2，1第35页9.设某循环队列的容量为设某循环队列的容量为50，如果头指针，如果头指针front=45(指向指向队头元素的前一位置队头元素的前一位置)，尾指针，尾指针rear=10(指向队尾元素指向队尾元素)，则该循环队列中共有则该循环队列中共有【2】个元素。个元素。（2010年年3月）月）8。假设用一个长度为。假设用一个长度为50的数组（数组元索的下标从的数组（数组元索的下标从0到到49）作为栈的存储空间，栈底指针）作为栈的存储空间，栈底指针b
33、ottom指间栈底指间栈底元素，栈顶指针元素，栈顶指针top指向栈顶元素，如果指向栈顶元素，如果bottom=49，top=30（数组下标），则栈中具有（数组下标），则栈中具有【】个元素。个元素。（2009年年3月）月）答案：答案：19答案：答案：15第36页一个非空的数据结构若满足下面的两个条件，则这种数据结一个非空的数据结构若满足下面的两个条件，则这种数据结构即为构即为。有且仅有一个根结点；有且仅有一个根结点；除第一个结点外，每一个结点最多有一个直接前驱结点；除第一个结点外，每一个结点最多有一个直接前驱结点；除最后一个结点外，每一个结点最多有一个直接后继结点。除最后一个结点外，每一个结点最
34、多有一个直接后继结点。u 线性结构与非线性结构线性结构与非线性结构线性表、栈和队列都是线性结构线性表、栈和队列都是线性结构 一个数据结构不是线性结构，则称其为一个数据结构不是线性结构，则称其为。a1a2a5a3a4HEAD319510线性链表的逻辑状态线性链表的逻辑状态第37页树型结构是一种重要的非线性结构。树型结构是一种重要的非线性结构。u 树的概念树的概念u 二叉树的概念二叉树的概念u 二叉树的存储二叉树的存储u 二叉树的遍历二叉树的遍历第38页u 树的定义：树的定义：n个结点的有限集。（个结点的有限集。（n=0）ABDFECGHIJKMn 根：根：only onen 若若n=0，则称为空
35、树；，则称为空树；n 否则，当否则，当n1时，其余结时，其余结点被分成点被分成m（m0）个互不）个互不相交的子集相交的子集T1，T2，.，Tm，每个子集又是一棵树。，每个子集又是一棵树。由此可以看出，树的定义是由此可以看出，树的定义是递归的。递归的。n Question：如何辨别根？：如何辨别根？A只有一个只有一个结点的树结点的树第39页ABDFECGHIJKMn 一个结点的子树的一个结点的子树的个数；个数；Q：结点结点A、G的度数？的度数？n 树中所有结点度的最树中所有结点度的最大值；大值；Q：右图中树的度？右图中树的度？n 度为度为0的结点；的结点；Q：图中叶子结点有几个？图中叶子结点有几
36、个？7 度不为度不为0的结点；的结点；Q：图中非终端结点有几个？图中非终端结点有几个？5第40页ABDFECGHIJKMn 树中根结点的层树中根结点的层次为次为1，根结点子树的根为第，根结点子树的根为第2层，层，以此类推；以此类推；Q：图中结点图中结点F的层次？的层次？n 树中所有结点层次树中所有结点层次的最大值；的最大值；Q：图中树的深度？图中树的深度？n 如果树中每如果树中每棵子树从左向右的排列拥有一定棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序的顺序，不得互换，则称为有序树，否则称为无序树。树，否则称为无序树。第41页 二叉树是一种有序的树形结构。它与一般二叉树是一种有序的树
37、形结构。它与一般树形结构的区别是：树形结构的区别是：n 每个结点最多有两棵子树；每个结点最多有两棵子树；n 子树有左右之分，次序不能任意颠倒。子树有左右之分，次序不能任意颠倒。二叉树的二叉树的5种基本形态种基本形态第42页【性质1】在二叉树的第在二叉树的第i层上最多有层上最多有2i-1个结点（个结点（i1）ABCDFEHG第43页【性质2】深度为深度为h的二叉树最多有的二叉树最多有2h-1个结点（个结点（h 1）如果一个深度为如果一个深度为h的二叉树拥有的二叉树拥有2h-1个结个结点，则将它称为点，则将它称为满二叉树满二叉树。有一棵深度为有一棵深度为h，具有，具有n个结点的二叉树，个结点的二叉
38、树，若将它与一棵同深度的满二叉树中的所有结点按从上若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为的每个结点分别与满二叉树中编号为1n的结点位置的结点位置一一对应，则称这棵二叉树为一一对应，则称这棵二叉树为完全二叉树完全二叉树。第44页121314158910114567123满二叉树满二叉树完全二叉树完全二叉树12138910114567123 完全二叉树是满二叉树 满二叉树也是完全二叉树第45页1213891011456123非完全二叉树非完全二叉树深度为深度为4的的完
39、全二叉树完全二叉树84567123第46页【性质3】二叉树上叶子结点数比度为二叉树上叶子结点数比度为2的结点数多的结点数多1ABCDFEHG度为2的结点叶子结点第47页【性质4】具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2(n+1)其中，其中，log2n 的结果是不大于的结果是不大于log2n的最大整数的最大整数121314158910114567123深度为深度为4的的满二叉树满二叉树深度为深度为4的的完全二叉树完全二叉树84567123深度为深度为3的完全二叉树具有的完全二叉树具有47深度为深度为4的完全二叉树具有的完全二叉树具有815深度为深度为5的完全二叉树
40、具有的完全二叉树具有1531 log2(8+1)=ln9/In2=4 log2(15+1)=In16/In2=4深度为深度为6的完全二叉树的完全二叉树 具有具有3263深度为深度为7的完全二叉树的完全二叉树 具有具有64127深度为深度为8的完全二叉树的完全二叉树 具有具有128255深度为深度为9的完全二叉树的完全二叉树 具有具有256511深度为深度为10的完全二叉树具有的完全二叉树具有5121023深度为深度为11的完全二叉树具有的完全二叉树具有10242047第48页1 1：在深度为：在深度为7 7的满二叉树中的满二叉树中,叶子结点的个数为（叶子结点的个数为（20062006年年4 4
41、月）月）A)32 A)32 B)31 B)31 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个，则该二叉树中有个，则该二叉树中有
42、【】个叶子结点。个叶子结点。（20052005年年4 4月）月）5 5：一棵二叉树第六层（根结点为第一层）的结点数最多为：一棵二叉树第六层（根结点为第一层）的结点数最多为【】个。（个。（20052005年年9 9月）月）树型结构方面的考题树型结构方面的考题 1答案：答案：C。3答案：答案：A。5答案：答案：32。2答案：答案：63。4答案：答案：19。第49页u 在计算机中，二叉树通常采用链式存储结构。在计算机中，二叉树通常采用链式存储结构。LlinkinfoRlink二叉树的存储结点的结构二叉树的存储结点的结构ABDCFGE A G E F B C Dt第50页u 遍历指遍历指不重复地不重复
43、地访问二叉树中的访问二叉树中的所有结点所有结点。u 二叉树的遍历的次序与树型结构上的大多二叉树的遍历的次序与树型结构上的大多数运算有联系。数运算有联系。（1）先（前）序遍历（）先（前）序遍历（DLR）（2）中序遍历（）中序遍历（LDR）（3）后序遍历（）后序遍历（LRD）ABCDFEHG第51页u 遍历指遍历指不重复地不重复地访问二叉树中的访问二叉树中的所有结点所有结点。（1）先（前）序遍历（）先（前）序遍历（DLR）若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则n访问根结点；访问根结点；遍历左子树；遍历左子树；遍历右子树。遍历右子树。ABCDFEHG先序遍历的结果：先序
44、遍历的结果：A A B E C F G H D B E C F G H D第52页（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
45、AABCDFEHG第53页u先序序列：先序序列：ABDGCEFHu中序序列：中序序列：DGBAECHFu后序序列：后序序列：GDBEHFCAABCFHDEG下图所示的二叉树经过三种遍历得到的顺序分别为？下图所示的二叉树经过三种遍历得到的顺序分别为？练习：练习：根据先序遍历序列，建立二叉树根据先序遍历序列，建立二叉树第54页1:设二叉树如下：设二叉树如下：（2010年年3月）月）对该二叉树进行后序遍历的对该二叉树进行后序遍历的结果为结果为【3】树型结构方面的考题树型结构方面的考题 22:对如下二叉树（对如下二叉树（2006年年4月）月）进行后序遍历的结果为进行后序遍历的结果为A)ABCDEF B
46、)DBEAFC C)ABDECF D)DEBFCA EDBGHFCA DABCFHDGE第55页 查找是数据处理的重要内容。查找是数据处理的重要内容。u 查找指在一个给定的数据结构中查找指定的元素，查找指在一个给定的数据结构中查找指定的元素，该元素也称关键字。该元素也称关键字。u 若找到了满足条件的结点，称查找成功；否则称查若找到了满足条件的结点，称查找成功；否则称查找失败。找失败。u衡量一个查找算法的主要标准是查找过程中对关键衡量一个查找算法的主要标准是查找过程中对关键字进行的平均比较次数。字进行的平均比较次数。u 通常根据不同的数据结构，采用不同的查找方法：通常根据不同的数据结构，采用不同
47、的查找方法：n 顺序查找顺序查找n 二分查找二分查找第56页u线性表中最简单的查找方法。线性表中最简单的查找方法。u 方法：从线性表的第一个元素开始，依次将线性方法：从线性表的第一个元素开始，依次将线性表中的元素与关键字进行比较，若相等，则查找成表中的元素与关键字进行比较，若相等，则查找成功；若将所有元素都与关键字进行了比较但不相等，功；若将所有元素都与关键字进行了比较但不相等，则查找失败。则查找失败。u 顺序查找法的适用场合：顺序查找法的适用场合：n 对线性表中元素的排列次序没有要求；对线性表中元素的排列次序没有要求；n 对线性表的存储结构没有要求，链式结构和顺对线性表的存储结构没有要求，链
48、式结构和顺序结构均可。序结构均可。第57页折半查找)u 是一种效率较高的查找方法，但是只适合是一种效率较高的查找方法，但是只适合顺序存储顺序存储的有序表的有序表。u二分查找的方法：首先将关键字与线性表中间位置二分查找的方法：首先将关键字与线性表中间位置的结点比较，相等则查找成功；不相等则根据比较的结点比较，相等则查找成功；不相等则根据比较结果确定下一步查找应在哪个子表中进行；重复上结果确定下一步查找应在哪个子表中进行；重复上述过程，直至查找成功或子表长度为述过程，直至查找成功或子表长度为0。u 二分查找法的适用场合：二分查找法的适用场合：n 线性表中的元素按关键字值递增或递减的次序排线性表中的
49、元素按关键字值递增或递减的次序排列；列；n 线性表采用顺序存储结构。线性表采用顺序存储结构。第58页u练习假设待查有序（升序）顺序表中数据元素的关键字序列为（8,18,27,42,47,50,56,68,95,120），用折半查找方法查找关键字值为27的数据元素.对于长度为对于长度为n n的有序线性表，最坏情况只需比较的有序线性表，最坏情况只需比较log2nlog2n次。次。第59页u 排序指排序指将一个无序序列整理成按关键字值递增或递减排列的有序将一个无序序列整理成按关键字值递增或递减排列的有序序列序列。u 排序方法中其排序对象一般是排序方法中其排序对象一般是顺序存储顺序存储的线性表。的线性
50、表。u 根据排序序列的规模以及数据处理的要求，可以采用不同的排序根据排序序列的规模以及数据处理的要求，可以采用不同的排序方法方法：交换类排序法交换类排序法 n 冒泡排序冒泡排序n 快速排序快速排序 插入类排序法插入类排序法n 简单插入排序简单插入排序n 希尔排序希尔排序选择类排序法选择类排序法n 简单选择排序简单选择排序n 堆排序堆排序第60页u 冒泡排序的方法：冒泡排序的方法：n扫描整个线性表，逐次对相邻的两个元素进行比扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最较，若为逆序，则交换；第一趟扫描的结果使最大大(或最小或最小)的元素排到表的最后的元素排到
