计算机级公共基础知识考前必看课件.ppt

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

1、关于计算机级公共基础知识考前必看现在学习的是第1页，共105页第2页计算机二级考试公共基础知识计算机二级考试公共基础知识大纲大纲q数据结构与算法数据结构与算法q程序设计基础程序设计基础q软件工程基础软件工程基础q数据库设计基础数据库设计基础这四个方面在试卷中出现的情况是：选择题10个（20分），填空题5个（10分），总分值占到了试卷卷面分的30，是一个不小的比例。现在学习的是第2页，共105页第3页算法算法算法的基本算法的基本概念概念2.2.算法复杂度算法复杂度的概念和意的概念和意义义一、基本数据结构与算法一、基本数据结构与算法 数据结构数据结构数据结构的概念数据结构的概念线性表线性表栈和队列

2、栈和队列树与二叉树树与二叉树查找技术查找技术排序技术排序技术对于等级考试，这个部分的考核对于等级考试，这个部分的考核重点主要重点主要在在算法和数据结构的基本概念算法和数据结构的基本概念、二叉二叉树树(遍历、结点），遍历、结点），还有还有排序和查找排序和查找考试中也经常会涉及到。考试中也经常会涉及到。现在学习的是第3页，共105页第4页算法的定义算法的定义u对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。算法是程序设计的核心算法是程序设计的核心算法的基本概念算法的基本概念 算法是在有限步骤内求解某一问题所使用的一组定义明算法是在有限步骤内求解某一问题所使用的一组定义明确的

3、规则。通俗点说，就是计算机解题的过程确的规则。通俗点说，就是计算机解题的过程(计算的方法计算的方法)。在这个过程中，无论是形成解题思路在这个过程中，无论是形成解题思路(推理实现的算法推理实现的算法)还是编写程序还是编写程序(操作实现的算法操作实现的算法)，都是在实施某种算法。，都是在实施某种算法。例：例：n个数从大到小进行排序。个数从大到小进行排序。有多种排序方法有多种排序方法，常用的有冒泡排序、选择排序等。，常用的有冒泡排序、选择排序等。现在学习的是第4页，共105页第5页2.算法的基本特征算法的基本特征一个算法应该具有以下五个重要的特征：一个算法应该具有以下五个重要的特征：u有穷性有穷性u

4、确定性确定性u输入输入u输出输出u可行性可行性一个算法必须保证执行有限步之后结束；算法的每一步骤必须有确切的定义；一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成现在学习的是第5页，共105页第6页u算法与计算机程序算法与计算机程序算法算法_是一组逻辑步骤是一组逻辑步骤程序程序用计算机语言描述的算法用计算机语言描述的算法3.算法的表示算法的表示算法的表示算法的表示INPUT rINPUT rS=3.14*

5、r*rS=3.14*r*rPTINT SPTINT S开始开始输入输入R RS=3.14 S=3.14*R*RR*R输出输出S S结束结束问题：输入园的半径，计算园的面积一个算法的表示需要使用一些语言形式。一个算法的表示需要使用一些语言形式。传统的算法传统的算法-图形法，如图形法，如“流程图流程图”和和N-S图图目前常用的方法目前常用的方法-使用伪码描述算法。使用伪码描述算法。现在学习的是第6页，共105页第7页4.算法评价算法评价评价一个算法优劣的主要标准是算法的执行效率和存储需求：评价一个算法优劣的主要标准是算法的执行效率和存储需求：n时间复杂度：执行这个算法所需要的时间复杂度：执行这个算

6、法所需要的计算工作量计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量n空间复杂度：执行这个算法所需要的空间复杂度：执行这个算法所需要的内存空间内存空间算法在算法在执执行行过过程中程中临时临时占用的存占用的存储储空空间间时间复杂度时间复杂度它大致等于计算机它大致等于计算机执行一种简单操作所需的平均时间执行一种简单操作所需的平均时间与算法中进行与算法中进行简单操简单操作的次数的乘积作的次数的乘积。一个算法在计算机存储器上所占用的存储空间，包括一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存

7、储空存储算法本身所占用的存储空间间、算法中的输入输出数据所占用的存储空间算法中的输入输出数据所占用的存储空间和和算法在运行过程中临时占用的存储空间算法在运行过程中临时占用的存储空间这三个部分这三个部分现在学习的是第7页，共105页第8页总结总结uu对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法不等于程序，也不等计算机方法，程序的编制不可能优于算法不等于程序，也不等计算机方法，程序的编制不可能优于算法不等于程序，也不等计算机方法，程序的编制不

8、可能优于算法的设计。算法的设计。算法的设计。算法的设计。u算法评价算法评价：n时间复杂度：执行这个算法所需要的计算工作量时间复杂度：执行这个算法所需要的计算工作量n空间复杂度：执行这个算法所需要的内存空间空间复杂度：执行这个算法所需要的内存空间现在学习的是第8页，共105页第9页(1)在在计计算机中，算法是指算机中，算法是指_。A.查询查询方法方法B.加工方法加工方法C.解解题题方案的准确而完整的描述方案的准确而完整的描述D.排序方法排序方法(2)下列叙述中正确的是下列叙述中正确的是A)算法的效率只与算法的效率只与问题问题的的规规模有关，而与数据的存模有关，而与数据的存储结储结构无关构无关B)

9、算法的算法的时间时间复复杂杂度是指度是指执执行算法所需要的行算法所需要的计计算工作量算工作量C)数据的数据的逻辑结逻辑结构与存构与存储结储结构是一一构是一一对应对应的的D)算法的算法的时间时间复复杂杂度与空度与空间间复复杂杂度一定相关度一定相关(3)算法的有算法的有穷穷性是指性是指A）算法程序的运行）算法程序的运行时间时间是有限的是有限的B）算法程序所）算法程序所处处理的数据量是有限的理的数据量是有限的C）算法程序的）算法程序的长长度是有限的度是有限的D）算法只能被有限的用）算法只能被有限的用户户使用使用(c)(B)算法习题:(A)现在学习的是第9页，共105页第10页(4)算法的算法的时问时

10、问复复杂杂度是指度是指A)算法的算法的执执行行时间时间B)算法所算法所处处理的数据量理的数据量C)算法程序中的算法程序中的语语句或指令条数句或指令条数D)算法在算法在执执行行过过程中所需要的基本运算次数程中所需要的基本运算次数(5)算法的空算法的空间间复复杂杂度是指度是指A）算法在）算法在执执行行过过程中所需要的程中所需要的计计算机存算机存储储空空间间B）算法所）算法所处处理的数据量理的数据量C）算法程序中的）算法程序中的语语句或指令条数句或指令条数D）算法在）算法在执执行行过过程中所需要的程中所需要的临时临时工作工作单单元数元数(6)下列叙述中正确的是下列叙述中正确的是A）一个算法的空）一个

11、算法的空间间复复杂杂度大，度大，则则其其时间时间复复杂杂度也必定大度也必定大B）一个算法的空）一个算法的空间间复复杂杂度大，度大，则则其其时间时间复复杂杂度必定小度必定小C）一个算法的）一个算法的时间时间复复杂杂度大，度大，则则其空其空间间复复杂杂度必定小度必定小D）上述三种）上述三种说说法都不法都不对对(D)计算工作量(A)(D)现在学习的是第10页，共105页第11页计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的些大量的数据元素都需要存放在计算机中，因此，大量的数

12、据元素在计算机数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。这是进行数据处理的关键问题。二、数据结构二、数据结构程序程序=算法算法+数据结构数据结构数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。一般情况下，在具有相同特征的数据元素集合中，各个数据元一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（

13、即联系），这种关系反映了该集合中素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。的数据元素所固有的一种结构。现在学习的是第11页，共105页第12页二二.数据结构数据结构数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。数据结构数据结构是研究数据和数据之间关系的一门学科，是研究数据和数据之间关系的一门学科，它包括三个方面。它包括三个方面。（1）数据集合中各数据元素之间所固有的逻辑）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算）在对数据进行处理时，各数

14、据元素在计算机中的存储关系，即数据的存储结构；机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。）对各种数据结构进行的运算。现在学习的是第12页，共105页第13页u1.逻辑结构逻辑结构数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构包含：数据的逻辑结构包含：（1）表示数据元素的信息；）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。）表示各数据元素之间的前后件关系。例：例：1.一年四季的数据结构一年四季的数据结构B=(D,R)D=春，夏，秋，冬春，夏，秋，冬R=(春，夏春，夏),(夏，秋夏，秋

15、),(秋，冬秋，冬)2.家庭成员的数据结构家庭成员的数据结构B=(D,R)D=父亲，儿子，女儿父亲，儿子，女儿R=(父亲，儿子父亲，儿子),(父亲，女儿父亲，女儿)春夏秋冬数据结构的图形表示数据结构的图形表示父亲儿子女儿现在学习的是第13页，共105页第14页u常见的常见的逻辑结构逻辑结构有：有：线性结构、树形结构和图形结构。线性结构、树形结构和图形结构。线性结构线性结构树形结构树形结构图图形形结结构构u线性结构线性结构结构中的每个元素之间存在一个对一个的关系；结构中的每个元素之间存在一个对一个的关系；u树形结构树形结构结构中的每个元素之间存在一个对多个的关系；结构中的每个元素之间存在一个对多

16、个的关系；u图形结构或网状结构图形结构或网状结构结构中的每个元素之间存在多个对多个的关系。结构中的每个元素之间存在多个对多个的关系。其中，其中，树形结构和图形结构统称为非线形结构树形结构和图形结构统称为非线形结构。数据的逻辑结构可以用二元。数据的逻辑结构可以用二元关系表示，也可以直观地用图形来表示。关系表示，也可以直观地用图形来表示。现在学习的是第14页，共105页第15页常见的数据结构1.线性表2.栈和队列3.树现在学习的是第15页，共105页第16页 线性表（线性表（线性表（线性表（LinearListLinearList）线性表是由线性表是由n（n0）个数据元素）个数据元素a1，a2，a

17、i，an组成的一个有限序列。组成的一个有限序列。简单的线性表简单的线性表简单的线性表简单的线性表春春夏夏秋秋冬冬复杂的线性表复杂的线性表复杂的线性表复杂的线性表记录记录102011001张三张三男男记录记录202011003李四李四女女记录记录3记录记录4现在学习的是第16页，共105页第17页2.栈和队列栈和队列栈和队列都是特殊的线性表。栈和队列都是特殊的线性表。uu 栈（栈（栈（栈（StackStack）及其基本运算）及其基本运算）及其基本运算）及其基本运算uu 队列（队列（队列（队列（QueueQueue）及其基本运算）及其基本运算）及其基本运算）及其基本运算uu 循环队列及其基本运算循

18、环队列及其基本运算循环队列及其基本运算循环队列及其基本运算现在学习的是第17页，共105页第18页栈（栈（栈（栈（StackStack）是一种特殊的是一种特殊的线性表线性表。其特点是插入和删除运。其特点是插入和删除运算都只能在线性表的一端进行。算都只能在线性表的一端进行。u栈是按照栈是按照“先进后出先进后出先进后出先进后出”或或“后进先出后进先出后进先出后进先出”的原则组织数据的的原则组织数据的线性表。线性表。u栈的物理存储结构可以用顺序结构，也可以用链表结构。栈的物理存储结构可以用顺序结构，也可以用链表结构。u下面讨论顺序存储结构中栈元素的插入和删除运算。下面讨论顺序存储结构中栈元素的插入和

19、删除运算。n顺序栈的进栈和出栈运算顺序栈的进栈和出栈运算n栈的基本运算有三种：入栈、退栈和读栈顶元素栈的基本运算有三种：入栈、退栈和读栈顶元素在顺序栈中插入和删除运算不需要移动在顺序栈中插入和删除运算不需要移动表中其他数据元素表中其他数据元素。现在学习的是第18页，共105页第19页队列（队列（队列（队列（QueueQueue）是一种特殊的线性表。其特点是所有的是一种特殊的线性表。其特点是所有的插入都插入都在表的一端在表的一端进行，所有的进行，所有的删除删除运算都在表的运算都在表的另一端另一端进行。进行。u队列是按照队列是按照“先进先出先进先出先进先出先进先出”或或“后进后出后进后出后进后出后

20、进后出”的原则组织数据的原则组织数据的线性表。的线性表。u队列的物理存储结构可以用顺序结构，也可以用链式结构。队列的物理存储结构可以用顺序结构，也可以用链式结构。u顺序队列的运算顺序队列的运算栈有三种操作：栈有三种操作：入栈出栈读栈顶元素入栈出栈读栈顶元素队列有三种操作：入队出队读队首元素队列有三种操作：入队出队读队首元素例：有入栈元素序列：例：有入栈元素序列：ABCD，求可能的出栈序列，求可能的出栈序列如是队列又是什么情况呢？如是队列又是什么情况呢？现在学习的是第19页，共105页第20页uu 循环队列循环队列循环队列循环队列 把队列的存储空间在逻辑上看作一个环，当把队列的存储空间在逻辑上看

21、作一个环，当R指向存储空间指向存储空间的末端后，就把它重新置于始端。的末端后，就把它重新置于始端。u循环队列的运算循环队列的运算队列中进行插入的一端称做队尾队列中进行插入的一端称做队尾(rear),进行删除的一端称做队首进行删除的一端称做队首(front)。习题：数据结构分为逻辑结构和存储结构，循环队列属习题：数据结构分为逻辑结构和存储结构，循环队列属于于【】结构。（结构。（2005年年9月）月）答案：存储结构。答案：存储结构。现在学习的是第20页，共105页第21页常见数据结构的逻辑结构常见数据结构的逻辑结构u线性表线性表线性结构u栈栈是特殊的线性表u队列队列也是一种操作受限的特殊的线性表u

22、树树（树型结构）（树型结构）是一种重要的非线形数据结构现在学习的是第21页，共105页第22页数据存储结构方面的考题数据存储结构方面的考题1：数据的存：数据的存储结储结构是指构是指A)存存储储在外存中的数据在外存中的数据B)数据所占的存数据所占的存储储空空间间量量C)数据在数据在计计算机中的算机中的顺顺序存序存储储方式方式D)数据的数据的逻辑结逻辑结构在构在计计算机中的表示算机中的表示2.下列叙述中正确的是下列叙述中正确的是A）栈栈是是“先先进进先出先出”的的线线性表性表B）队队列是列是“先先进进后出后出”的的线线性表性表C）循）循环队环队列是非列是非线线性性结结构构D）有序）有序线线性表既可

23、以采用性表既可以采用顺顺序存序存储结储结构，也可以采用构，也可以采用链链式存式存储结储结构构3.数据结构分为线性结构和非线性结构，带链的队列属于数据结构分为线性结构和非线性结构，带链的队列属于。4.下列数据结构中，属于非线性结构的是下列数据结构中，属于非线性结构的是A）循环队列）循环队列B)带链队列带链队列C)二叉树二叉树D）带链栈）带链栈答案：答案：D。答案：答案：D。答案：线性结构。答案：线性结构。答案：答案：c现在学习的是第22页，共105页第23页5。下列叙述中正确的是（下列叙述中正确的是（）。）。A）顺顺序序存存储储结结构构的的存存储储一一定定是是连连续续的的，链链式式存存储储结结构

24、构的的存存储储空空间间不不一一定定是是连续的连续的B）顺顺序序存存储储结结构构只只针针对对线线性性结结构构，链链式式存存储储结结构构只只针针对对非非线线性性结结构构C）顺序存储结构能存储有序表，链式存储结构不能存储有序表）顺序存储结构能存储有序表，链式存储结构不能存储有序表D）链式存储结构比顺序存储结构节省存储空间）链式存储结构比顺序存储结构节省存储空间答案：答案：A。6 6。下列关于。下列关于栈栈的叙述正确的是的叙述正确的是 A A）栈栈按按“先先进进先出先出”组织组织数据数据 B)B)栈栈按按“先先进进后出后出”组织组织数据数据 C C）只能在）只能在栈栈底插入数据底插入数据 D D）不能

25、）不能删删除数据除数据答案：答案：B。7.一个队列的初始状态为空。现将元素一个队列的初始状态为空。现将元素A，B，C，D，E，F，5，4，3，2，1依次入依次入队，然后再依次退队，则元素退队的顺序为队，然后再依次退队，则元素退队的顺序为【1】。（。（2010年年3月）月）答案：答案：A，B，C，D，E，F，5，4，3，2，1现在学习的是第23页，共105页第24页一个非空的数据结构若满足下面的两个条件，则这种数据结构即一个非空的数据结构若满足下面的两个条件，则这种数据结构即为为线性结构线性结构线性结构线性结构。有且仅有一个根结点；有且仅有一个根结点；除第一个结点外，每一个结点最多有一个直接前驱

26、结点；除第一个结点外，每一个结点最多有一个直接前驱结点；除最后一个结点外，每一个结点最多有一个直接后继结点。除最后一个结点外，每一个结点最多有一个直接后继结点。u线性结构与非线性结构线性结构与非线性结构线性表、栈和队列都是线性结构线性表、栈和队列都是线性结构一个数据结构不是线性结构，则称其为一个数据结构不是线性结构，则称其为非线性结构非线性结构非线性结构非线性结构。a1a2a5a3a4HEAD319510线性链表的逻辑状态线性链表的逻辑状态现在学习的是第24页，共105页第25页树型结构是一种重要的非线性结构。树型结构是一种重要的非线性结构。u树的概念树的概念u二叉树的概念二叉树的概念u二叉树

27、的存储二叉树的存储u二叉树的遍历二叉树的遍历3.树与二叉树树与二叉树现在学习的是第25页，共105页第26页树的概念树的概念u树的定义：树的定义：n个结点的有限集。（个结点的有限集。（n=0）ABDFECGHIJKMn根：根：onlyonen若若n=0，则称为空树；，则称为空树；n否则，当否则，当n1时，其余结点时，其余结点被分成被分成m（m0）个互不相交）个互不相交的子集的子集T1，T2，.，Tm，每个，每个子集又是一棵树。由此可以看出，子集又是一棵树。由此可以看出，树的定义是递归的。树的定义是递归的。nQuestion：如何辨别根？：如何辨别根？A只有一个结只有一个结点的树点的树现在学习的

28、是第26页，共105页第27页树型结构的常用术语树型结构的常用术语ABDFECGHIJKMu结点的度结点的度结点的度结点的度一个结点的子树的个数；一个结点的子树的个数；Q：结点结点A、G的度数？的度数？u树的度树的度树的度树的度树中所有结点度的最大值；树中所有结点度的最大值；Q：右图中树的度？右图中树的度？u终端结点终端结点终端结点终端结点度为度为0的结点；的结点；Q：图中叶子结点有几个？图中叶子结点有几个？7uu 非终端结点非终端结点非终端结点非终端结点度不为度不为0的结点；的结点；Q：图中非终端结点有几个？图中非终端结点有几个？5孩子结点、双亲结点、兄弟结点、结点的子孙、结点的祖先孩子结点

29、、双亲结点、兄弟结点、结点的子孙、结点的祖先孩子结点、双亲结点、兄弟结点、结点的子孙、结点的祖先孩子结点、双亲结点、兄弟结点、结点的子孙、结点的祖先现在学习的是第27页，共105页第28页树型结构的常用术语树型结构的常用术语ABDFECGHIJKMu结点的层次结点的层次结点的层次结点的层次树中根结点的层次为树中根结点的层次为1，根结点子树的根为第，根结点子树的根为第2层，以此类推；层，以此类推；Q：图中结点图中结点F的层次？的层次？u树的深度树的深度树的深度树的深度 树中所有结点层次的树中所有结点层次的最大值；最大值；Q：图中树的深度？图中树的深度？u有序树、无序树有序树、无序树有序树、无序树

30、有序树、无序树如果树中每棵子如果树中每棵子树从左向右的排列拥有一定的顺序，不树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序得互换，则称为有序树，否则称为无序树。树。现在学习的是第28页，共105页第29页二叉树的概念二叉树的概念定义：定义：定义：定义：二叉树是一种有序的树形结构。它与一般树形结构二叉树是一种有序的树形结构。它与一般树形结构的区别是：的区别是：n每个结点最多有两棵子树；每个结点最多有两棵子树；n子树有左右之分，次序不能任意颠倒。子树有左右之分，次序不能任意颠倒。二叉树的二叉树的5种基本形态种基本形态现在学习的是第29页，共105页第30页二叉树的性质二叉树的

31、性质二叉树的性质二叉树的性质【性质1】在二叉树的第在二叉树的第i层上最多有层上最多有2i-1个结点（个结点（i1）ABCDFEHG现在学习的是第30页，共105页第31页【性质2】深度为深度为h的二叉树最多有的二叉树最多有2h-1个结点（个结点（h1）n n满二叉树满二叉树满二叉树满二叉树：除最后一层外，每一层上的所有结点都有两个除最后一层外，每一层上的所有结点都有两个子结点。子结点。n n完全二叉树完全二叉树完全二叉树完全二叉树：除最后一层外，每一层上的结点数均达到最大值；除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。在最后一层上只缺少右边的若干结点。现在学习

32、的是第31页，共105页第32页121314158910114567123满二叉树满二叉树完全二叉树完全二叉树12138910114567123完全二叉树是满二叉树满二叉树也是完全二叉树现在学习的是第32页，共105页第33页1213891011456123非完全二叉树非完全二叉树深度为深度为4的完的完全二叉树全二叉树84567123现在学习的是第33页，共105页第34页【性质3】二叉树上叶子结点数比度为二叉树上叶子结点数比度为2的结点数多的结点数多1ABCDFEHG度为2的结点叶子结点现在学习的是第34页，共105页第35页1 1：在深度：在深度为为7 7的的满满二叉二叉树树中中,叶子叶子

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

34、一棵二叉树树第六第六层层（根（根结结点点为为第一第一层层）的）的结结点数最多点数最多为为【】个。个。树型结构方面的考题树型结构方面的考题1答案：答案：C。3答案：答案：A。5答案：答案：32。2答案：答案：63。4答案：答案：19。现在学习的是第35页，共105页第36页二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历u遍历指遍历指不重复地不重复地访问二叉树中的访问二叉树中的所有结点所有结点。u二叉树的遍历的次序与树型结构上的大多数运二叉树的遍历的次序与树型结构上的大多数运算有联系。算有联系。uu遍历的方式有三种遍历的方式有三种遍历的方式有三种遍历的方式有三种（1）先（前）序遍历（）先（前）序

35、遍历（DLR）（2）中序遍历（）中序遍历（LDR）（3）后序遍历（）后序遍历（LRD）ABCDFEHG现在学习的是第36页，共105页第37页二叉树的遍历二叉树的遍历u遍历指遍历指不重复地不重复地访问二叉树中的访问二叉树中的所有结点所有结点。（1）先（前）序遍历（）先（前）序遍历（DLR）若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则n访问根结点；访问根结点；n n先序先序先序先序遍历左子树；遍历左子树；n n先序先序先序先序遍历右子树。遍历右子树。ABCDFEHG先序遍历的结果：先序遍历的结果：A A B E C F G H D B E C F G H D现在学习的是第

36、37页，共105页第38页（2）中序遍历（）中序遍历（LDR）若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则n中序遍历左子树；中序遍历左子树；n访问根结点；访问根结点；n中序遍历右子树。中序遍历右子树。中序遍历的结果：中序遍历的结果：EBAFHGCD（3）后序遍历（）后序遍历（LRD）若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则n后序遍历左子树；后序遍历左子树；n后序遍历右子树；后序遍历右子树；n访问根结点。访问根结点。后序遍历的结果：后序遍历的结果：EBHGFDCAABCDFEHG现在学习的是第38页，共105页第39页u先序序列：先序序列：AB

37、DGCEFHu中序序列：中序序列：DGBAECHFu后序序列：后序序列：GDBEHFCAABCFHDEG下图所示的二叉树经过三种遍历得到的顺序分别为？下图所示的二叉树经过三种遍历得到的顺序分别为？练习：练习：根据先序遍历序列，建立二叉树根据先序遍历序列，建立二叉树现在学习的是第39页，共105页第40页1:设二叉树如下：设二叉树如下：（2010年年3月）月）对该二叉树进行后序遍历的结对该二叉树进行后序遍历的结果为果为【3】树型结构方面的考题树型结构方面的考题22:对如下二叉树（对如下二叉树（2006年年4月）月）进行后序遍历的结果为进行后序遍历的结果为A)ABCDEFB)DBEAFCC)ABD

38、ECFD)DEBFCAEDBGHFCADABCFHDGE现在学习的是第40页，共105页第41页查找技术查找技术查找是数据处理的重要内容。查找是数据处理的重要内容。u查找指在一个给定的数据结构中查找指定的元素，查找指在一个给定的数据结构中查找指定的元素，该元素也称关键字。该元素也称关键字。u若找到了满足条件的结点，称查找成功；否则称查若找到了满足条件的结点，称查找成功；否则称查找失败。找失败。u衡量一个查找算法的主要标准是查找过程中对关键衡量一个查找算法的主要标准是查找过程中对关键字进行的平均比较次数。字进行的平均比较次数。u通常根据不同的数据结构，采用不同的查找方法：通常根据不同的数据结构，

39、采用不同的查找方法：n顺序查找顺序查找n二分查找二分查找现在学习的是第41页，共105页第42页顺序查找顺序查找u线性表中最简单的查找方法。线性表中最简单的查找方法。u方法：从线性表的第一个元素开始，依次将线性表方法：从线性表的第一个元素开始，依次将线性表中的元素与关键字进行比较，若相等，则查找成功；中的元素与关键字进行比较，若相等，则查找成功；若将所有元素都与关键字进行了比较但不相等，则若将所有元素都与关键字进行了比较但不相等，则查找失败。查找失败。u顺序查找法的适用场合：顺序查找法的适用场合：n对线性表中元素的排列次序没有要求；对线性表中元素的排列次序没有要求；n对线性表的存储结构没有要求

40、，链式结构和顺对线性表的存储结构没有要求，链式结构和顺序结构均可。序结构均可。现在学习的是第42页，共105页第43页二分查找二分查找(折半查找)u是一种效率较高的查找方法，但是只适合是一种效率较高的查找方法，但是只适合顺序存储顺序存储的有序表的有序表。u二分查找的方法：首先将关键字与线性表中间位置的二分查找的方法：首先将关键字与线性表中间位置的结点比较，相等则查找成功；不相等则根据比较结果结点比较，相等则查找成功；不相等则根据比较结果确定下一步查找应在哪个子表中进行；重复上述过程，确定下一步查找应在哪个子表中进行；重复上述过程，直至查找成功或子表长度为直至查找成功或子表长度为0。u二分查找法

41、的适用场合：二分查找法的适用场合：n线性表中的元素按关键字值递增或递减的次序排线性表中的元素按关键字值递增或递减的次序排列；列；n线性表采用顺序存储结构。线性表采用顺序存储结构。现在学习的是第43页，共105页第44页 排序技术排序技术u排序指排序指将一个无序序列整理成按关键字值递增或递减排列的有序序列将一个无序序列整理成按关键字值递增或递减排列的有序序列。u排序方法中其排序对象一般是排序方法中其排序对象一般是顺序存储顺序存储的线性表。的线性表。u根据排序序列的规模以及数据处理的要求，可以采用不同的排序方法根据排序序列的规模以及数据处理的要求，可以采用不同的排序方法：交换类排序法交换类排序法冒

42、泡排序冒泡排序快速排序快速排序插入类排序法插入类排序法简单插入排序简单插入排序希尔排序希尔排序选择类排序法选择类排序法n简单选择排序简单选择排序n堆排序堆排序现在学习的是第44页，共105页第45页冒泡排序冒泡排序冒泡排序冒泡排序u冒泡排序的方法：冒泡排序的方法：n扫描整个线性表，逐次对相邻的两个元素进行比扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最较，若为逆序，则交换；第一趟扫描的结果使最大大(或最小或最小)的元素排到表的最后的元素排到表的最后(或最前或最前)；n除最后除最后(或最前或最前)一个元素，对剩余的元素重复上一个元素，对剩余的元素重复上述过程

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

44、的是第46页，共105页下一页上一页停止放映第第47479292页页 Q：第二趟冒泡排序后的结果是什么样的？达到了第二趟冒泡排序后的结果是什么样的？达到了最终的排序目标吗？一共需要多少次能够最后成最终的排序目标吗？一共需要多少次能够最后成为有序序列？为有序序列？Q：你觉得冒泡排序的效率如何？如果是你，你会用什：你觉得冒泡排序的效率如何？如果是你，你会用什么方法来排序？么方法来排序？冒泡排序比较简单，当初始序列基本有序时，冒泡排冒泡排序比较简单，当初始序列基本有序时，冒泡排序有较高的效率，反之效率较低。序有较高的效率，反之效率较低。u冒泡排序终止条件冒泡排序终止条件:本趟排序未发生交换，终止排序

45、算法本趟排序未发生交换，终止排序算法 现在学习的是第47页，共105页下一页上一页停止放映第第48489292页页 初始初始第一趟第一趟第二趟第二趟第三趟第三趟第四趟第四趟第五趟第五趟序列序列排序后排序后排序后排序后排序后排序后排序后排序后排序后排序后261818181891826 2626 9153232 329 15185447 915264791532915 471554设待排数据元素的关键字为设待排数据元素的关键字为（26,18,32,54,47,9,15)冒泡排序法，需要比较的次数为冒泡排序法，需要比较的次数为n(n-1)/2n(n-1)/2；现在学习的是第48页，共105页第49页

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

47、92页页 u初态：初态：15，14，22，30，37，15，11u第一趟：第一趟：11 14，22，30，37，15，15u第二趟：第二趟：11，14 22，30，37，15，15u第三趟：第三趟：11，14，15 30，37，22，15u第四趟：第四趟：11，14，15，15 37，22，30u第五趟：第五趟：11，14，15，15，22 37，30u第六趟：第六趟：11，14，15，15，22，30 37 有序序列有序序列例：设待排数据元素的关键字为（例：设待排数据元素的关键字为（15，14，22，30，37，11），每一趟排序后的序列状态如图所示），每一趟排序后的序列状态如图所示：现在学

48、习的是第50页，共105页第51页排序法小结：排序法小结：u简单选择排序法简单选择排序法,最坏情况需要最坏情况需要n(n-1)/2次比较；次比较；u冒泡排序法冒泡排序法,最坏情况需要最坏情况需要n(n-1)/2次比较；次比较；u快速排序法，快速排序法，最坏情况需要最坏情况需要n(n-1)/2次比较；次比较；u希尔排序法希尔排序法,最坏情况需要最坏情况需要O(n1.5)次比较；次比较；u堆排序法堆排序法,最坏情况需要最坏情况需要O(nlog2n)次比较；次比较；现在学习的是第51页，共105页第52页排序查找方面的考题：排序查找方面的考题：(1)对对于于长长度度为为n的的线线性表，在最坏情况下，

49、下列各排序法所性表，在最坏情况下，下列各排序法所对应对应的比的比较较次数中正确的是次数中正确的是A)冒泡排序冒泡排序为为n/2B)冒泡排序冒泡排序为为nC)快速排序快速排序为为nD)快速排序快速排序为为n(n-1)/2(2)在长为在长为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为的有序线性表中进行顺序查找，最坏情况下需要比较的次数为_。A）、）、63B）、）、64C）、）、6D）、）、7(3)下列数据下列数据结结构中，能用二分法构中，能用二分法进进行行查查找的是找的是A）顺顺序存序存储储的有序的有序线线性表性表B）线线性性链链表表C）二叉）二叉链链表表D）有序）有序线线性性链链表

50、表(4)下列排序方法中，最坏情况下比下列排序方法中，最坏情况下比较较次数最少的是（次数最少的是（09年年3月月）A）冒泡排序）冒泡排序B）简单选择简单选择排序排序C）直接插入排序）直接插入排序D）堆排序）堆排序DBAD现在学习的是第52页，共105页第53页第二章第二章程序设计基础程序设计基础内容：内容：1.程序设计方法与风格。程序设计方法与风格。2.结构化程序设计。结构化程序设计。3.面向对象的程序设计方法，对象，方法，面向对象的程序设计方法，对象，方法，属性及继承与多态性。属性及继承与多态性。现在学习的是第53页，共105页第54页1结构化程序设计结构化程序设计u结构化程序构化程序设计方法