计算机二级考试公共基础知识.pdf

《计算机二级考试公共基础知识.pdf》由会员分享，可在线阅读，更多相关《计算机二级考试公共基础知识.pdf（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机等级考试公共基础知识计算机二级考试公共基础知识大纲数据结构与算法程序设计基础 软件工程基础 数据库设计基础这四个方面在试卷中出现的情况是：选择题10个（2 0分），填空题5 个（10分），总分值占到了试 卷卷面分的3 0%,是一个不小的比例。第 2 页计算机二级考试公共基础知识试卷分析章节考试时间数据结构程序设软件工数据库设计基础程基础计基础与算法2 007 年 4月 2 007 年 9 月 2 008 年 4月 2 008 年 9 月 2 009年 3月 2 009年 9 月 2 010年 3 月10分 12 分 10分 10分 10分 10分 10分2 分 4 分 2 分 2 分 2

2、 分 2 分 0 分10分 8 分 8 分 8 分 8 分 8 分 10分8 分 6 分 10分 10分 10分 10分 10分第 3 页一、基本数据结构与算法算法1.算 法 的 基 本 概 念2.算 法 复 杂2.算 法 复杂度的概念和意义数据结构1.数 据 结 构 的 概 念2,线 性 表3.栈 和 队 列4.树与二叉树5.查 找 技 术6.排序技术对于等级考试，这个部分的考核重点主要在对于等级考试，这个部分的考核重点主要在算法和数据结构的基本概重点主要遍历、），还有排序和查找考试中也经常会涉及到二叉树遍历结点）,还有排序和查找考试中也经常会涉及到。念、二叉树（遍历、结点）,还有排序和查找

3、考试中也经常会涉及到。第4页1.算法的基本概念算法的定义算法是程序设计的核心对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，定义明确的规则。通俗点说，就是计算机解题的过 计算的方法）在这个过程中，程（计算的方法）。在这个过程中，无论是形成解题 思路（推理实现的算法）还是编写程序（思路（推理实现的算法）还是编写程序（操作实现的算都是在实施某种算法。法），都是在实施某种算法。个数从大到小进行排序。例：n个数从大到小进行排序。个数从大到小进行排序常用的有冒泡排序、选择排序等。有多种排序方法，常用的有冒泡排序、

4、选择排序等。第5页2.算法的基本特征一个算法应该具有以下五个重要的特征：一个算法应该具有以下五个重要的特征：有穷性确定性输入输出可行性一个算法必须保证执行有限步之后结束；算法的每一步骤必须有确切的定义；一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成第6页3.算法的表示一个算法的表示需要使用一些语言形式。一个算法的表示需要使用一些语言形式。传统的算法图形法，如“流程图”和N-S图图形法，传统的算法图形法

5、流程图”图目前常用的方法使用伪码描述算法。使用伪码描述算法。目前常用的方法使用伪码描述算法算法与计算机程序 算法是一组逻辑步骤 算法 是一组逻辑步骤程序用计算机语言描述的算法 程序用计算机语言描述的算法问题：输入园的半径，计算园的面积I N P U T r S=3.1 4*r*rP T I N T S开始输入R输入R S=3.1 4*R*R输出S输出S结 束 第 7 页算法举例：个数排序算法举例：n 个数排序冒泡排序的方法：冒泡排序的方法：1.扫描整个线性表，逐次对扫描整个线性表，扫描整个线性表相邻的两个元素进行比较，相邻的两个元素进行比较，若为逆序，则交换；若为逆序，则交换；第一趟扫描的结果

6、使最大的元素排到表的最后；2.除最后一个元素，对剩余除最后一个元素，除最后一个元素的元素重复上述过程，的元素重复上述过程，将次大的数排到表的倒数第二个位置；位置；3.重复上述过程；重复上述过程；重复上述过程对于长度为n的线性表，对于长度为的线性表，冒泡的线性表排序需要对表扫描n-1 遍。排序需要对表扫描遍第 8 页4.算法的两个基本要素：算法的两个基本要素：一是对数据对象的运算和操作；二是算法的控制结构。基本运算和操作算 术 运 算 关 系 运 算 逻辑 运 算 数据传输控制结构顺 序 选 择 循 环算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回 溯 法 第9页5.算法评价评价

7、一个算法优劣的主要标准是算法的执行效率和存储需求：评价一个算法优劣的主要标准是算法的执行效率和存储需求：时间复杂度：执行这个算法所需要的计算工 作 量 时间复杂度：执行这个算法所需要的计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量空间复杂度：执行这个算法所需要的内存空间空间复杂度：执行这个算法所需要的内存空间算法在执行过程中临时占用的存储空间时间复杂度它大致等于计算机执行一种简单操作所需的平均时间时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法它大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积简单操作的次数的乘积。中进行简单

8、操作的次数的乘积。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法中的输入输出数据所占用的存储空间和的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个部分临时占用的存储空间这三个部分第 1 0 页一、算法对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。算法不等于程序，也不等计算机方法，程序的编制不算法不等于程序，也不等计算机方法，可能优于算法的设计。可能优于算法的设计。算法评价：时间复杂度：时间复杂度：执行这个算法所需要的计算工作量空间

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

10、间复杂度一定相关算法的时间复杂度与空间复杂度一定相关（3）算法的有穷性是指（0 8 年 4 月）算法的有穷性是指 年 月 A）算法程序的运行时间是有限的）（A）B）算法程序所处理的数据量是有限的）C）算法程序的长度是有限的）D）算法只能被有限的用户使用）第 1 2 页（4）算法的时间复杂度是指（2 0 1 0 年 3月）年 月 A）算法的执行时间算法的执行时间B）算法所处理的数据量算法所处理的数据量 C）算法程序中的语句或指令条数算法程序中的语句或指令条数D）算法在执行过程中所需要的基本运算次数算法在执行过程中所需要的基本运算次数（5）算法的空间复杂度是指（0 9 年 9月）年 月A）算法在执

11、行过程中所需要的计算机存储空间）B）算法所处理的数据量）O 算法程序中的语句或指令条数）D）算法在执行过程中所需要的临时工作单元数）（6）下列叙述中正确的是（0 6 年 9月）年 月（D）计算工作量（A）（D）A）一个算法的空间复杂度大，则其时间复杂度也必定大）一个算法的空间复杂度大，B）一个算法的空间复杂度大，则其时间复杂度 必 定 小）一个算法的空间复杂度大，C）一个算法的时间复杂度大，则其空间复杂度必定小）一个算法的时间复杂度大，D）上述三种说法都不对）第1 3页二、数据结构程序=算 法 数 据 结 构 程序 算 法+数 据 结 构 算 法计算机在进行数据处理时，计算机在进行数据处理时，

12、实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大 量 很 多，而这些大量的数据元素都需要存放在计算机中，因此，数据元素在计算机中如何组织，以便提高数据处理的效率，的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。节省计算机的存储空间，这是进行数据处理的关键问题。数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。一般情况下，在具有相同特征的数据元素集合中，

13、一般情况下,在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关 系（即联系），）,这种关系反映了该集元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。合中的数据元素所固有的一种结构。第 1 4 页二.数据结构数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。数据结构是研究数据和数据之间关系的一门学科，它包括三个方面。学科，它包括三个方面。（1）数据集合中各数据元素之间所固有的逻）辑关系，即数据的逻辑结构；辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计）在对数据进行处理时，算机中的存储关系，即数据的存储

14、结构；算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。）对各种数据结构进行的运算。第 1 5 页1.逻辑结构数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构包含：数据的逻辑结构包含：（1）表示数据元素的信息；）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。）表示各数据元素之间的前后件关系。例:1 .一年四季 的数据结构B=（D,R）D=春，夏，秋，冬春R=（春，夏），（夏，秋），（秋，冬）春 夏 秋 2.家庭成员的数据结构 B=（D,R）D=父亲，儿子，女儿 父亲，父亲 儿子，女儿 R=（

15、父亲，儿 子，（父亲，女儿父亲，父亲，父亲儿子）父亲女儿）春数据结构的图形表示夏 父 亲 秋 冬儿子女 儿 第 1 6 页常见的逻辑结构有：线性结构、树形结构和图形结构。线性结构、树形结构和图形结构。图形结线性结构树形结构构线性结构结 构 的 的 的树形结构结构的图形结构结构的线形结构。线形结构。图 形。的。结构第 1 7 页结构的树形结构和图形结构2 .存储结构（物理结构）存储结构（计算机在实际进行数据处理时，计算机在实际进行数据处理时,被处理的各数据元素总是被存放在计算机的存储空间中，并且，算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也

16、不可能相同。它们的逻辑关系不一定是相同的，而且一般也不可能相同。如：一年四季 家庭成员计算机存储空间怎样存放？存储结构指数据结构在计算机存储空间中的具体实现。存储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有：常见的存储结构有：顺序存储结构链式存储结构索引存储结构存储结构只抽象地反映数据元素之间的关系的结构，系的结构，而不管其存储方式的数据结构称为逻辑结构。数据结构称为逻辑结构。？一种数据结构可以根据需要表示一种数据结构可以根据需要表示成一种或多种存储结构。成一种或多种存储结构。第18页通常，一个数据结构中的元素结点可能是动态变化的。通常，一个数据结构中的元素结点可能是动态变化的

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

18、学科，研究以下三 方 面 内容：内容：数据的逻辑结构数据的存储结构数据的运算第 1 9 页常见的数据结构1.线性表线性表2.栈和队列栈和队列3.树树上一页下一页停止放映第 2 0|9 2 页 2 0|9 2 页|9 21 .线性表(L in ea r L i s t)线性表(L is t)线性表是由n (线 性 表是由(n 0)个数据元素al,a2,ai,，,an 组成的一个有限序列。，,组成的一个有限序列。简单的线性表春 夏 秋 冬复杂的线性表记录1 记录记录2 记录记录3 记录记录4 记录第 2 1 页 0 2 0 1 1 0 0 1张 三 男 李 四 女0 2 0 1 1 0 0 3线性

19、表的存储结构线性表的存储结构有两种：线性表的存储结构有两种：顺序存储结构链式存储结构存储地址2 0 0 0 2 0 0 4al a2 ai an 占4个字节 个字节线性表的顺序存储结构顺序存储结构把逻辑上相邻的顺序存储结构把逻辑上相邻的逻辑上相邻数据元素存储在物理上相邻物理上相邻的存数据元素存储在物理上相邻的存储单元里，顺序存储结构只存储储单元里，顺序存储结构只存储结点的值，不存储结点间的关系，结点的值，不存储结点间的关系，结点间的关系由存储单元的邻接关系来体现。关系来体现。2 0 0 0+4*(1-1)2 0 0 0+4*(n-1)L o a(L o a(ai)=L o a(al)+L*(i

20、 l)=L o a(+L*(第 i个数的地址第一个数的地址L为该类型数所占的字节第2 2 页顺序表的插入和删除运算线性表的顺序存储结构称为顺序表。线性表的顺序存储结构称为顺序表。顺序表的插入运算顺序表的删除运算在线性表顺序存储情况下，在线性表顺序存储情况下，要插入或删除一个元素，都会由于数据元素的移动而消耗大量的处理时间，都会由于数据元素的移动而消耗大量的处理时间，所以这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的。常变动的线性表是合适的。第 2 3 页线性表的链式存储结构线性表的链式存储结构称为线性链表。线性表的链式存储结构称为线性链表。链式存储结构不要求逻辑上相邻的数据元

21、素物理位置也相邻，而且各数据元素的存储顺序也是任意的。置也相邻，而且各数据元素的存储顺序也是任意的。各数据元素的先后关系是由各结点的指针域指示。各数据元素的先后关系是由各结点的指针域指示。链式存储结构的每一个存储结点不仅存储结点的值，链式存储结构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系：而且存储结点之间的关系:数据域指针域第 2 4 页线性链表的物理状态线性链表的物理状态应用举例应用举例线性链表的存储结构线性链表的存储结构设线性表为(al,a2,a3,a4,a5)1 al线性表的顺线性表的顺序存储结构序存储结构H E A D123456789 1 0 3a2 al a49 1

22、1 02 a2 3a 34a 45a 5 6 73 1注意：1 2 3此类编号不代表所在的地址单元的地址编码a3 a51 05 095H E A Dala2a3a4a5第 2 5 页线性链表的逻辑状态线性链表的插入和删除运算单链表的插入运算单链表的删除运算采用链式存储结构，存储空间开销较大，采用链式存储结构，存储空间开销较大，但是进行插入和删除运算不会造成大量元素的移动。入和删除运算不会造成大量元素的移动。循环链表是加一种形式的链式存储结构。循环链表是加一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点。表中最后一个结点的指针域指向头结点。3 H E A D 1 9 5 1

23、0ala2a3a4a5第 2 6 页双向链表的存储结构提问：单向链表的缺点是什么？提示：如何寻找结点的直接前趋。双向链表可以克服单链表的单向性的缺点。在双向链表的结点中有两个指针域，在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。直接后继，另一指向直接前趋。3 H E A D 1 5 1 0ala2a3a4双向循环链表第 2 7 页线 性 表：al,a2,a3,a4,a5 ,注意：注意：数据元素在计算机存储空间中的位置关系与它们的逻辑关系 不一定是相同的。不一定是相同的。一个逻辑数据结构可以有多种存储结构，可以有多种存储结构，且不同的存储结构影响数据处理的效率。线性表的存储

24、结构有两种顺序存储结构1 al 2a 23a 34a 45a 5 6 7H E A D 3链式存储结构1 2 3 4 5 6 7 8 9 1 0 a3 a5 5 0 a4 1 0 al 1 a2 9第 2 8 页2.栈和队列栈和队列都是特殊的线性表。栈和队列都是特殊的线性表。栈(S t ac k)及其基本运算S t ac k)队列(Q u e u e)及其基本运算队列(Q u e u e)循环队列及其基本运算第 2 9 页栈(S t ac k)是一种特殊的线性表。其特点是插入和删S t ac k)是一种特殊的线性表线性表。除运算都只能在线性表的一端进行。除运算都只能在线性表的一端进行。栈是按照

25、“先进后出”后进先出”栈是按照“先进后出”或“后进先出”的原则组织数 据的线性表。据的线性表。栈的物理存储结构可以用顺序结构，栈的物理存储结构可以用顺序结构，也可以用链表结构。下面讨论顺序存储结构中栈元素的插入和删除运算。下面讨论顺序存储结构中栈元素的插入和删除运算。顺序栈的进栈和出栈运算栈的基本运算有三种：入栈、栈的基本运算有三种：入栈、退栈和读栈顶元素在顺序栈中插入和删除运算不需要移动表中其他数据元素。移动表中其他数据元素。第 3 0页队 列(Q u e u e)是一种特殊的线性表。其特点是所有的队列(Q u e u e)是一种特殊的线性表。插入都在表的一端进行所有的删除运算都在表的另进行

26、，删除运算都在表的插入都在表的一端进行，所有的删除运算都在表的另一端进行进行。一端进行。队列是按照“先进先出”后进后出”队列是按照“先进先出”或“后进后出”的原则组织数据的线性表。数据的线性表。队列的物理存储结构可以用顺序结构，也可以用链式队列的物理存储结构可以用顺序结构，结构。结构。顺序队列的运算栈有三种操作：入栈 出栈栈有三种操作：入栈 出栈读栈顶元素队列有三种操作：入队 出队队列有三种操作：入队 出队 读队首元素例：有入栈元素序列：A B C D,求可能的出栈序列.有入栈元素序列：，求可能的出栈序列.如是队列又是什么情况呢？如是队列又是什么情况呢？第 3 1 页循环队列把队列的存储空间在

27、逻辑上看作一个环，把队列的存储空间在逻辑上看作一个环，当R 指向存指向存储空间的末端后，就把它重新置于始端。储空间的末端后，就把它重新置于始端。循环队列的运算队列中进行插入的一端称做队尾(r e ar),进行删除的一端 进行删除的一端队列中进行插入的一端称做队尾称做队首(f r o n t)。称做队首。习题：数据结构分为逻辑结构和存储结构，习题：数据结构分为逻辑结构和存储结构，循环队列属于【结构。(。(2 005年 9月)列属于【】结构。(年 月答案：存储结构。答案：存储结构。第 3 2 页常见数据结构的逻辑结构线性表栈队列也是一种操作受限的特殊的线性表线性结构是特殊的线性表树型结构）树（树型

28、结构）是一种重要的非线形数据结构第 3 3 页数据存储结构方面的考题1：数据的存储结构是指（2 005年 4 月）：年 月 A）存储在外存中的数据0数据在计算机中的顺序存储方式2.下列叙述中正 确 的 是（2 009 年 3 月）年 月 A）栈是“先进先出”的线性表）栈 是“先进先出”B）队列是“先进后出”的线性表）队列是“先进后出 C）循环队列是非线性结构）D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构）有序线性表既可以采用顺序存储结构，B）数据所占的存储空间量D）数据的逻辑结构在计算机中的表示答案：Do答案：。答案：Do答案：。3.数据结构分为线性结构和非线性结构，带链的队列

29、属于数据结构分为线性结构和非线性结构，带链的队列属于 4,下列数据结构中，属于非线性结构的是下列数据结构中，A）循环队列）C）二叉 树 B）带链队列D）带链栈）o o 答案：线性结构。答案：线性结构。答案：答案：c 第3 4页5 o 下列叙述中正确的是（）。（2 008年 9月）。下列叙述中正确的是（年 月答案：。答案：A oA）顺序存储结构的存储一定是连续的，链式存储结构的存储空）顺序存储结构的存储一定是连续的，间不一定是连续的B）顺序存储结构只针对线性结构，链式存储结构只针对非线性）顺序存储结构只针对线性结构，结 构 O 顺序存储结构能存储有序表，链式存储结构不能存储有序表）顺序存储结构能

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

31、 3 5 页8 o 假设用一个长度为50的数组（数组元索的下标从。假设用一个长度为的数组数组元索的下标从0 的数组（到 49）作为栈的存储空间，栈底指针）作为栈的存储空间，栈底指针bo t t o m 指间栈底 指间栈底 元素，栈顶指针t o p指向栈顶元素，如果bo t t o m=49,元素，栈顶指针 指向栈顶元素，如 果，指向栈顶元素t o p=3 0（数组下标），则栈中具有【1个元素。），则栈中具有个元素。（数组下标），则栈中具有【（2 009 年 3 月）年 月答案：答案：1 99.设某循环队列的容量为，如果头指针设某循环队列的容量为 50,如果头指针f r o n t=45（指向指

32、向队头元素的前一位置），尾指 针 r e ar=1 0（指向队尾元素，指向队尾元素），队头元素的前一位 置，尾指针 指向队尾元素则该循环队列中共有【2】个元素。（2 01 0年 3 月）】个元素。年 月答案：答案：1 5 第 3 6页线性结构与非线性结构线性表、线性表、栈和队列都是线性结构一个数据结构不是线性结构，则称其为非线性结一个数据结构不是线性结构，则称其为非线性结构。一个非空的数据结构若满足下面的两个条件，一个非空的数据结构若满足下面的两个条件，则这种数据结构即为线性结构线性结构。构即为线性结构。有且仅有一个根结点；有且仅有一个根结点；除第一个结点外，每一个结点最多有一个直接前驱结点；

33、除第一个结点外，每一个结点最多有一个直接前驱结点；除最后一个结点外，每一个结点最多有一个直接后继结点。除最后一个结点外，每一个结点最多有一个直接后继结点。3 HE AD 1 9 5 1 0a la 2a 3a 4a 5第 3 7 页线性链表的逻辑状态3.树与二叉树树型结构是一种重要的非线性结构。树型结构是一种重要的非线性结构。树的概念二叉树的概念二叉树的存储二叉树的遍历第 3 8 页树的概念树的定义：个结点的有限集。（n =0）个结点的有限集。（树的定义：n个结点的有限集。（）根：o n l y o n e若 n=0,则称为空树；，则称为空树；否则，否则，当 n l 时，其余结时点被分成 m

34、（点 被 分 成（m 0）个 互 不）相交的子集T1,相交的子 集，T 2,，T m,每个子集又是一棵树。，每个子集又是一棵树。由此可以看出，由此可以看出，树的定义是 递归的。递归的。Qu esti o n：如何辨别根？：如何辨别根？第 3 9 页 EBFJ A CGKDH M I只有一个结点的树A树型结构的常用术语结点的度一个结点的子树的个数；：结 点 A、的度数的度数？个数；Q：结 点、G的度数？树的度树中所有结点度的最大值；：右图中树的度？大值；Q：右图中树的度？终端结点度为的结点；度为0的结点的结点；Q：图中叶子结点有儿个？7 ：图中叶子结点有儿个？非终端结点度不为的结点；度不为0的结

35、点的结点；Q：图中非终端结点有儿个？5 ：图中非终端结点有儿个？孩子结点、双亲结点、兄弟结点、结点的子孙、孩子结点、双亲结点、兄弟结点、结点的子孙、结点的祖先第 4 0 页 BEFJ A CGKDH M I树型结构的常用术语结点的层次树中根结点的层次为1,根结点子树的根为第2层 次 为，根结点子树的根为第层，以此类推；以此类推；Q：图中结点F的层次？：图中结点的层次的层次？EA BFJ CGKDH M I树的深度树中所有结点层次的最大值；：图中树的深度？的最大值；Q：图中树的深度？有序树、无序树如果树中每有序树、棵子树从左向右的排列拥有一定的顺序，不得互换，的顺序，不得互换，则称为有序否则称为

36、无序树。树，否则称为无序树。第 4 1 页二叉树的概念定义：二叉树是一种有序的树形结构。定义：二叉树是一种有序的树形结构。它与一般树形结构的区别是：树形结构的区别是：每个结点最多有两棵子树；每个结点最多有两棵子树；子树有左右之分，次序不能任意颠倒。子树有左右之分，次序不能任意颠倒。二叉树的5 种基本形态二叉树的种基本形态第 4 2 页二叉树的性质【性 质 1】在二叉树的第层上最多有iT个结点（i Nl）在二叉树的第i 层上最多有个结点（）层上最多有2A B E F G H第 4 3 页C D【性质2 深度为的二叉树最多有2 h -1 个结点（h 2 1）深度为h的二叉树最多有个结点（）深度为的

37、二叉树最多有个结点满二叉树：如果一个深度为的二叉树拥有满二叉树：如果一个深度为h的二叉树拥有h-1 个结的二叉树拥有2个结点，则将它称为满二叉树。则将它称为满二叉树。满二叉树完全二叉树：有一棵深度为，具有个结点的二叉树，完全二叉树：有一棵深度为h,具有n个结点的二叉树，个结点的二叉树若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1 n的结点位置的结点位置的每个结点分别与满二叉树中编号为一一对应，则称这棵二叉树为完全二叉树。一一对应，则称这棵二叉树为完全二叉树。完全二叉树第 4 4 页

38、满 二 叉 树 满 二 叉 树 也 是 完 满 全 二 二 叉 树 完 全 二叉树第 4 5 页完 全 二 叉 树 是 叉 树非完全二叉树深度为4的 深度为 的完全二叉树第 4 6 页【性质3】二叉树上叶子结点数比度为的结点数多二叉树上叶子结点数比度为2的结点数多二叉树上叶子结点数比度为的结点数多1A BEFGH CD叶子结点度为2的结点第 4 7 页【性质4】具有个结点的完全二叉树的深度为？l o g 2 (n+1)?具有 n个结点的完全二叉树的深度为具有其中，其中，？l o g 2 n?的结果是不大于？的结果是不大于l o g 2 n 的最大整数的最大整数深度为4的深度为的满二叉树深度为4

39、的深度为的完全二叉树l o g 2(8+1)?=In 9/In 2=4?l o g 2 (1 5+1)?=In l 6/In 2=4?深度 为 3的完全二叉树具有4 深度为的完全二叉树具有 7深度为4 的完全二叉树具有8 深度为的完全二叉树具有 1 5 深度为5的完全二叉树具有1 5 深度为的完全二叉树具有 3 1深度为6的完全二叉树深度为的完全二叉树深度为7的完全二叉树深度为的完全二叉树深度为8的完全二叉树深度为的完全二叉树深度为9的完全二叉树深度为的完全二叉树深度为1 0的完全二叉树深度为的完全二叉树深度为1 1 的完全二叉树深度为的完全二叉树具有3 2 具 有 6 3 具有6 4 具 有

40、 1 2 7 具有1 2 8 2 5 5 具有 具 有 2 5 6 5 1 1 具 有 具 有 5 1 2 1 0 2 3 具 有 具 有1 0 2 4 2 0 4 7 具 有 第 4 8 页树型结构方面的考题1：在深度为7的满二叉树中，叶子结点的个数为(2 0 0 6 年 4月)在深度为7的满二叉树中，叶子结点的个数为(2 0 0 6 年 A)3 2 A)3 2B)3 1 B)3 1 C)6 4 C)6 4 D)6 3 D)6 31 答案：Co答案：。答案2：在深度为7的满二叉树中，度为2的结点个数为【在深度为7的满二叉树中，度为2的结点个数为【0 7 年】。(0 7 年 4月)2 答案：6

41、 3 o 答案：。答案一棵二叉树中共有7 0 个叶子结点与8 0 个度为1 的结点，7 0 个叶子结点与8 0 个度为3：一棵二叉树中共有7 0 个叶子结点与8 0 个度为1 的结点，则该二叉树中的总0 7 年 结 点 数 为（0 7 年 9月）A）2 1 9 B）2 2 1 C）2 2 93 答案：A o答案：。答案D）2 3 1 个叶子结点。】个叶子结点。】个。（2 0 0 54 答案：1 9。答案：。答案某二叉树中度为2的结点有1 8 1 8 个 4：某二叉树中度为2的结点有1 8 个，则该二叉树中有【（2 0 0 5 年4月）2 0 0 5 年 年 9 月）一棵二叉树第六层（根结点为第

42、一层）的结点数最多为【5：一棵二叉树第六层（根结点为第一层）的结点数最多为【5 答案：3 2。答案：。答 案 第 4 9 页二叉树的存储在计算机中，二叉树通常采用链式存储结构。在计算机中，二叉树通常采用链式存储结构。L l i n k i n f o R l i n kt二叉树的存储结点的结构A B D GAA C B FA ACAED GAEAAFA第 5 0 页二叉树的遍历遍历指不重复地访问二叉树中的所有结点。遍历指不重复地访问二叉树中的所有结点。不重复地访问二叉树中的所有结点二叉树的遍历的次序与树型结构上的大多数运算有联系。数运算有联系。遍历的方式有三种 序遍历（1）先（前）序遍历（D

43、LR）（2）中序遍历（LD R）中序遍历（）（3）后序遍历（LR D）后序遍 历（）H第 51 页A C F G DB E二叉树的遍历遍历指不重复地访问二叉树中的所有结点。遍历指不重复地访问二叉树中的所有结点。不重复地访问二叉树中的所有结点序遍历(1)先(前)序 遍 历(D L R)若二叉树为空，则结束遍历操作；若二叉树为空，则结束遍历操作；否则访问根结点；访问根结点；先序遍历左子树；先序遍历左子树；遍历左子树先序遍历右子树。先序遍历右子树。遍历右子树G E B F A C D先序遍历的结果：先序遍历的结果：ABECFGHDH第 52页(2)中序遍历(L D R)中序遍历()若二叉树为空，则结

44、束遍历操作；若二叉树为空，则结束遍历操作；否则中序遍历左子树；中序遍历左子树；访问根结点；访问根结点；中序遍历右子树。中序遍历右子树。中序遍历的结果：中序遍历的结果：E B AF H G C D (3)后序遍历(L R D)后序遍历()若二叉树为空,则结束遍历操作；若二叉树为空，则结束遍历操作；否则后序遍历左子树；后序遍历左子树；后序遍历右子树；后序遍历右子树；访问根结点。访问根结点。后序遍历的结果：后序遍历的结果：E BH G F D C A第 53 页ABEFGHCD练习：练习：下图所示的二叉树经过三种遍历得到的顺序分别为？下图所示的二叉树经过三种遍历得到的顺序分别为？ABDGEHCF先序

45、序列：先序序列：A B D G C E F H 中序序列：中序序列：D G B A E C H F 后序序列：后序序列：G D B E H F C A根据先序遍历序列，根据先序遍历序列，建立二叉树第 54页树型结构方面的考题21:设二叉树如下：设二叉树如下：设二叉树如下（201 0年 3月）年 月 对该二叉树进行后序遍历的结果为3E D B G H F C AA B C F E G HD2:对如下二叉树（2006年 4 月）对如下二叉树（年 月进行后序遍历的结果为 A）A B C D E F B）D B E A F C D C）A B D E C F D）D E B F C A第 55页5.查

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

47、元素开始，依次将线性表中的元素与关键字进行比较，若相等，则查找成功；中的元素与关键字进行比较，若相等，则查找成功；若将所有元素都与关键字进行了比较但不相等，则若将所有元素都与关键字进行了比较但不相等，查找失败。查找失败。顺序查找法的适用场合：顺序查找法的适用场合：对线性表中元素的排列次序没有要求；对线性表中元素的排列次序没有要求；对线性表的存储结构没有要求，对线性表的存储结构没有要求，链式结构和顺序结构均可。序结构均可。第57页二分查找（折半查找）是一种效率较高的查找方法，但是只适合顺序存储是一种效率较高的查找方法，但是只适合顺序存储的有序表。的有序表。二分查找的方法：二分查找的方法：首先将关

48、键字与线性表中间位置的结点比较，相等则查找成功；不相等则根据比较的结点比较，相等则查找成功；结果确定下一步查找应在哪个子表中进行；结果确定下一步查找应在哪个子表中进行；重复上述过程，直至查找成功或子表长度为O o 述过程，直至查找成功或子表长度为。二分查找法的适用场合：二分查找法的适用场合：线性表中的元素按关键字值递增或递减的次序排歹U；线性表采用顺序存储结构。线性表采用顺序存储结构。第 58页折半查找算法举例对给定数列(有序)3,11,17,21,23,2 8,对给定数列(有序)3,5,11,17,21,23,28,30,32,50,按折半查找算法,查找关键字值为30 30,32,50),按

49、折半查找算法，查找关键字值为 3 0 的数据元素。的数据元素。al a2 a3 a4 a5 a6 a7 a8 a9 alO 3,11,17,21,23,28,30,3 2,第 1 次：3,5,11,17,21,23,28,30,32,50 K=30midl=(1+10)midl=(1+10)/2=5lowmidhighka(midl)=a(5)=2123,28,30,32,第 2 次：23,28,30,32,50low上一页下一页停止放映h i g hmi dmi d 2=(6+1 0)/2=8 6+1 0)K=a (mi d 2)=a (8)=3 0第 59|92 页 59|92 页|92练

50、习假 设 待 查 有 序(升 序)顺 序 表 中 数 据 元 素 的 关 键 字 序 列 为(8,1 8,27,42,47,50,56,68,95,1 20),用折半查找 方法查找关键字值 为27的数据元素.对于长度为n的有序线性表，最坏情况只需比较log 2n次 对 于长度为n的有序线性表，最坏情况只需比较log 2n次。log 2n第60页6.排序技术排序指将一个无序序列整理成按关键字值递增或递减排列的有序排序指将一个无序序列整理成按关键字值递增或递减排列的有序序列。序列。顺序存储的线性表排序方法中其排序对象一般是顺序存储的线性表。排序方法中其排序对象一般是顺序存储的线性表。根据排序序列的