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

计算机等级考试公共基础知识数计学院卫春芳计算机二级考试公共基础知识大纲数据结构与算法程序设计基础软件工程基础数据库设计基础这四个方面在试卷中出现的情况是选择题10个（20分），填空题5个（10分），总分值占到了试卷卷面分的30，是一个不小的比例。第2页计算机二级考试公共基础知识试卷分析章节考试时间数据结构程序设软件工数据库设计基础程基础计基础与算法2007年4月2007年9月2008年4月2008年9月2009年3月2009年9月2010年3月10分12分10分10分10分10分10分2分4分2分2分2分2分0分10分8分8分8分8分8分10分8分6分10分10分10分10分10分第3页一、基本数据结构与算法算法算法的基本概念2算法复杂2算法复杂度的概念和意义数据结构数据结构的概念线性表栈和队列树与二叉树查找技术排序技术对于等级考试，这个部分的考核重点主要在对于等级考试，这个部分的考核重点主要在算法和数据结构的基本概重点主要遍历、），还有排序和查找考试中也经常会涉及到二叉树遍历结点），还有排序和查找考试中也经常会涉及到。念、二叉树遍历、结点），还有排序和查找考试中也经常会涉及到。第4页算法的基本概念算法的定义算法是程序设计的核心对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，定义明确的规则。通俗点说，就是计算机解题的过计算的方法在这个过程中，程计算的方法。在这个过程中，无论是形成解题思路推理实现的算法还是编写程序思路推理实现的算法还是编写程序操作实现的算都是在实施某种算法。法，都是在实施某种算法。个数从大到小进行排序。例N个数从大到小进行排序。个数从大到小进行排序常用的有冒泡排序、选择排序等。有多种排序方法，常用的有冒泡排序、选择排序等。第5页2算法的基本特征一个算法应该具有以下五个重要的特征一个算法应该具有以下五个重要的特征有穷性确定性输入输出可行性一个算法必须保证执行有限步之后结束；算法的每一步骤必须有确切的定义；一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成第6页3算法的表示一个算法的表示需要使用一些语言形式。一个算法的表示需要使用一些语言形式。传统的算法图形法，如“流程图”和NS图图形法，传统的算法图形法流程图”图目前常用的方法使用伪码描述算法。使用伪码描述算法。目前常用的方法使用伪码描述算法算法与计算机程序算法是一组逻辑步骤算法是一组逻辑步骤程序用计算机语言描述的算法程序用计算机语言描述的算法问题输入园的半径，计算园的面积INPUTRS314RRPTINTS开始输入R输入RS314RR输出S输出S结束第7页算法举例个数排序算法举例N个数排序冒泡排序的方法冒泡排序的方法1扫描整个线性表，逐次对扫描整个线性表，扫描整个线性表相邻的两个元素进行比较，相邻的两个元素进行比较，若为逆序，则交换；若为逆序，则交换；第一趟扫描的结果使最大的元素排到表的最后；2除最后一个元素，对剩余除最后一个元素，除最后一个元素的元素重复上述过程，的元素重复上述过程，将次大的数排到表的倒数第二个位置；位置；3重复上述过程；重复上述过程；重复上述过程对于长度为N的线性表，对于长度为的线性表，冒泡的线性表排序需要对表扫描N1遍。排序需要对表扫描遍第8页4算法的两个基本要素算法的两个基本要素一是对数据对象的运算和操作；二是算法的控制结构。基本运算和操作算术运算关系运算逻辑运算数据传输控制结构顺序选择循环算法基本设计方法列举法、归纳法、递推、递归、减斗递推技术、回溯法第9页5算法评价评价一个算法优劣的主要标准是算法的执行效率和存储需求评价一个算法优劣的主要标准是算法的执行效率和存储需求时间复杂度执行这个算法所需要的计算工作量时间复杂度执行这个算法所需要的计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量空间复杂度执行这个算法所需要的内存空间空间复杂度执行这个算法所需要的内存空间算法在执行过程中临时占用的存储空间时间复杂度它大致等于计算机执行一种简单操作所需的平均时间时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法它大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积简单操作的次数的乘积。中进行简单操作的次数的乘积。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法中的输入输出数据所占用的存储空间和的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个部分临时占用的存储空间这三个部分第10页一、算法对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。算法不等于程序，也不等计算机方法，程序的编制不算法不等于程序，也不等计算机方法，可能优于算法的设计。可能优于算法的设计。算法评价时间复杂度时间复杂度执行这个算法所需要的计算工作量空间复杂度空间复杂度执行这个算法所需要的内存空间第11页算法习题1在计算机中，算法是指在计算机中，算法是指。A查询方法B加工方法CC解题方案的准确而完整的描述D排序方法2下列叙述中正确的是（07年4月）下列叙述中正确的是年月A算法的效率只与问题的规模有关，而与数据的存储结构无关算法的效率只与问题的规模有关，算法的效率只与问题的规模有关B算法的时间复杂度是指执行算法所需要的计算工作量算法的时间复杂度是指执行算法所需要的计算工作量C数据的逻辑结构与存储结构是一一对应的数据的逻辑结构与存储结构是一一对应的BD算法的时间复杂度与空间复杂度一定相关算法的时间复杂度与空间复杂度一定相关3算法的有穷性是指08年4月算法的有穷性是指年月A）算法程序的运行时间是有限的）AB）算法程序所处理的数据量是有限的）C）算法程序的长度是有限的）D）算法只能被有限的用户使用）第12页4算法的时问复杂度是指2010年3月年月A算法的执行时间算法的执行时间B算法所处理的数据量算法所处理的数据量C算法程序中的语句或指令条数算法程序中的语句或指令条数D算法在执行过程中所需要的基本运算次数算法在执行过程中所需要的基本运算次数5算法的空间复杂度是指09年9月年月A）算法在执行过程中所需要的计算机存储空间）B）算法所处理的数据量）C）算法程序中的语句或指令条数）D）算法在执行过程中所需要的临时工作单元数）6下列叙述中正确的是06年9月年月D计算工作量ADA）一个算法的空间复杂度大，则其时间复杂度也必定大）一个算法的空间复杂度大，B）一个算法的空间复杂度大，则其时间复杂度必定小）一个算法的空间复杂度大，C）一个算法的时间复杂度大，则其空间复杂度必定小）一个算法的时间复杂度大，D）上述三种说法都不对）第13页二、数据结构程序算法数据结构程序算法数据结构算法计算机在进行数据处理时，计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量很多，而这些大量的数据元素都需要存放在计算机中，因此，数据元素在计算机中如何组织，以便提高数据处理的效率，的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。节省计算机的存储空间，这是进行数据处理的关键问题。数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。一般情况下，在具有相同特征的数据元素集合中，一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），），这种关系反映了该集元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。合中的数据元素所固有的一种结构。第14页二数据结构数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。数据结构是研究数据和数据之间关系的一门学科，它包括三个方面。学科，它包括三个方面。（1）数据集合中各数据元素之间所固有的逻）辑关系，即数据的逻辑结构；辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计）在对数据进行处理时，算机中的存储关系，即数据的存储结构；算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。）对各种数据结构进行的运算。第15页1逻辑结构数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构包含数据的逻辑结构包含（1）表示数据元素的信息；）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。）表示各数据元素之间的前后件关系。例1一年四季的数据结构BD,RD春，夏，秋，冬春R春，夏,夏，秋,秋，冬春夏秋2家庭成员的数据结构BD,RD父亲，儿子，女儿父亲，父亲儿子，女儿R父亲，儿子,父亲，女儿父亲，父亲，父亲儿子父亲女儿春数据结构的图形表示夏父亲秋冬儿子女儿第16页常见的逻辑结构有线性结构、树形结构和图形结构。线性结构、树形结构和图形结构。图形结线性结构树形结构构线性结构结构的的的树形结构结构的图形结构结构的线形结构。线形结构。图形。的。结构第17页结构的树形结构和图形结构2存储结构（物理结构）存储结构（计算机在实际进行数据处理时，计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。它们的逻辑关系不一定是相同的，而且一般也不可能相同。如一年四季家庭成员计算机存储空间怎样存放存储结构指数据结构在计算机存储空间中的具体实现。存储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有常见的存储结构有顺序存储结构链式存储结构索引存储结构存储结构只抽象地反映数据元素之间的关系的结构，系的结构，而不管其存储方式的数据结构称为逻辑结构。数据结构称为逻辑结构。一种数据结构可以根据需要表示一种数据结构可以根据需要表示成一种或多种存储结构。成一种或多种存储结构。第18页通常，一个数据结构中的元素结点可能是动态变化的。通常，一个数据结构中的元素结点可能是动态变化的。根据需要或在处理过程中，据需要或在处理过程中，可以在一个数据结构中增加一个新结插入运算），也可以删除某个结点（删除运算），），也可以删除某个结点），除此之点（插入运算），也可以删除某个结点（删除运算），除此之对数据结构的运算还有查找、分类、合并、分解、外，对数据结构的运算还有查找、分类、合并、分解、复制和修改。修改。在对数据结构的处理过程中，在对数据结构的处理过程中，不仅数据结构中结点的个数在动态变化，而且，在动态变化，而且，各数据元素之间的关系也有可能在动态地变化。变化。如无序表变有序表3数据的运算检索插入删除更新排序数据结构是研究数据和数据之间关系的一门学科，关系的一门学科，研究以下三方面内容内容数据的逻辑结构数据的存储结构数据的运算第19页常见的数据结构1线性表线性表2栈和队列栈和队列3树树上一页下一页停止放映第20|92页20|92页|92线性表（LINEARLIST）线性表（LIST）线性表是由N（线性表是由（N0）个数据元素A1，A2，AI，AN组成的一个有限序列。，组成的一个有限序列。简单的线性表春夏秋冬复杂的线性表记录1记录记录2记录记录3记录记录4记录第21页02011001张三男李四女02011003线性表的存储结构线性表的存储结构有两种线性表的存储结构有两种顺序存储结构链式存储结构存储地址20002004A1A2AIAN占4个字节个字节线性表的顺序存储结构顺序存储结构把逻辑上相邻的顺序存储结构把逻辑上相邻的逻辑上相邻数据元素存储在物理上相邻物理上相邻的存数据元素存储在物理上相邻的存储单元里，顺序存储结构只存储储单元里，顺序存储结构只存储结点的值，不存储结点间的关系，结点的值，不存储结点间的关系，结点间的关系由存储单元的邻接关系来体现。关系来体现。20004I120004N1LOA（LOA（AI）LOA（A1）L（I1）LOA（L（第I个数的地址第一个数的地址L为该类型数所占的字节第22页顺序表的插入和删除运算线性表的顺序存储结构称为顺序表。线性表的顺序存储结构称为顺序表。顺序表的插入运算顺序表的删除运算在线性表顺序存储情况下，在线性表顺序存储情况下，要插入或删除一个元素，都会由于数据元素的移动而消耗大量的处理时间，都会由于数据元素的移动而消耗大量的处理时间，所以这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的。常变动的线性表是合适的。第23页线性表的链式存储结构线性表的链式存储结构称为线性链表。线性表的链式存储结构称为线性链表。链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且各数据元素的存储顺序也是任意的。置也相邻，而且各数据元素的存储顺序也是任意的。各数据元素的先后关系是由各结点的指针域指示。各数据元素的先后关系是由各结点的指针域指示。链式存储结构的每一个存储结点不仅存储结点的值，链式存储结构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系而且存储结点之间的关系数据域指针域第24页线性链表的物理状态线性链表的物理状态应用举例应用举例线性链表的存储结构线性链表的存储结构设线性表为（A1，A2，A3，A4，A5）1A1线性表的顺线性表的顺序存储结构序存储结构HEAD123456789103A2A1A491102A23A34A45A56731注意123此类编号不代表所在的地址单元的地址编码A3A5105095HEADA1A2A3A4A5第25页线性链表的逻辑状态线性链表的插入和删除运算单链表的插入运算单链表的删除运算采用链式存储结构，存储空间开销较大，采用链式存储结构，存储空间开销较大，但是进行插入和删除运算不会造成大量元素的移动。入和删除运算不会造成大量元素的移动。循环链表是加一种形式的链式存储结构。循环链表是加一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点。表中最后一个结点的指针域指向头结点。3HEAD19510A1A2A3A4A5第26页双向链表的存储结构提问单向链表的缺点是什么提示如何寻找结点的直接前趋。双向链表可以克服单链表的单向性的缺点。在双向链表的结点中有两个指针域，在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。直接后继，另一指向直接前趋。3HEAD1510A1A2A3A4双向循环链表第27页线性表A1，A2，A3，A4，A5，注意注意数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的。不一定是相同的。一个逻辑数据结构可以有多种存储结构，可以有多种存储结构，且不同的存储结构影响数据处理的效率。线性表的存储结构有两种顺序存储结构1A12A23A34A45A567HEAD3链式存储结构12345678910A3A550A410A11A29第28页2栈和队列栈和队列都是特殊的线性表。栈和队列都是特殊的线性表。栈（STACK）及其基本运算STACK）队列（QUEUE）及其基本运算队列（QUEUE）循环队列及其基本运算第29页栈（STACK）是一种特殊的线性表。其特点是插入和删STACK）是一种特殊的线性表线性表。除运算都只能在线性表的一端进行。除运算都只能在线性表的一端进行。栈是按照“先进后出”后进先出”栈是按照“先进后出”或“后进先出”的原则组织数据的线性表。据的线性表。栈的物理存储结构可以用顺序结构，栈的物理存储结构可以用顺序结构，也可以用链表结构。下面讨论顺序存储结构中栈元素的插入和删除运算。下面讨论顺序存储结构中栈元素的插入和删除运算。顺序栈的进栈和出栈运算栈的基本运算有三种入栈、栈的基本运算有三种入栈、退栈和读栈顶元素在顺序栈中插入和删除运算不需要移动表中其他数据元素。移动表中其他数据元素。第30页队列（QUEUE）是一种特殊的线性表。其特点是所有的队列（QUEUE）是一种特殊的线性表。插入都在表的一端进行所有的删除运算都在表的另进行，删除运算都在表的插入都在表的一端进行，所有的删除运算都在表的另一端进行进行。一端进行。队列是按照“先进先出”后进后出”队列是按照“先进先出”或“后进后出”的原则组织数据的线性表。数据的线性表。队列的物理存储结构可以用顺序结构，也可以用链式队列的物理存储结构可以用顺序结构，结构。结构。顺序队列的运算栈有三种操作入栈出栈栈有三种操作入栈出栈读栈顶元素队列有三种操作入队出队队列有三种操作入队出队读队首元素例有入栈元素序列ABCD，求可能的出栈序列有入栈元素序列，求可能的出栈序列如是队列又是什么情况呢如是队列又是什么情况呢第31页循环队列把队列的存储空间在逻辑上看作一个环，把队列的存储空间在逻辑上看作一个环，当R指向存指向存储空间的末端后，就把它重新置于始端。储空间的末端后，就把它重新置于始端。循环队列的运算队列中进行插入的一端称做队尾REAR,进行删除的一端进行删除的一端队列中进行插入的一端称做队尾称做队首FRONT。称做队首。习题数据结构分为逻辑结构和存储结构，习题数据结构分为逻辑结构和存储结构，循环队列属于【结构。（。（2005年9月）列属于【】结构。（年月答案存储结构。答案存储结构。第32页常见数据结构的逻辑结构线性表栈队列也是一种操作受限的特殊的线性表线性结构是特殊的线性表树型结构）树（树型结构）是一种重要的非线形数据结构第33页数据存储结构方面的考题1数据的存储结构是指（2005年4月）年月A存储在外存中的数据C数据在计算机中的顺序存储方式2下列叙述中正确的是（2009年3月）年月A）栈是“先进先出”的线性表）栈是“先进先出”B）队列是“先进后出”的线性表）队列是“先进后出”C）循环队列是非线性结构）D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构）有序线性表既可以采用顺序存储结构，B数据所占的存储空间量D数据的逻辑结构在计算机中的表示答案D。答案。答案D。答案。3数据结构分为线性结构和非线性结构，带链的队列属于数据结构分为线性结构和非线性结构，带链的队列属于4下列数据结构中，属于非线性结构的是下列数据结构中，A）循环队列）C二叉树B带链队列D）带链栈）。答案线性结构。答案线性结构。答案答案C第34页5。下列叙述中正确的是（）。（2008年9月）。下列叙述中正确的是（年月答案。答案A。A）顺序存储结构的存储一定是连续的，链式存储结构的存储空）顺序存储结构的存储一定是连续的，间不一定是连续的B）顺序存储结构只针对线性结构，链式存储结构只针对非线性）顺序存储结构只针对线性结构，结构C）顺序存储结构能存储有序表，链式存储结构不能存储有序表）顺序存储结构能存储有序表，D）链式存储结构比顺序存储结构节省存储空间）答案。6。下列关于栈的叙述正确的是（2008年4月）年月栈按“先进先出”B栈按先进后出”栈按“A）栈按“先进先出”组织数据B栈按“先进后出”组织数据C）只能在栈底插入数据D）不能删除数据答案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第35页8。假设用一个长度为50的数组（数组元索的下标从。假设用一个长度为的数组数组元索的下标从0的数组（到49）作为栈的存储空间，栈底指针）作为栈的存储空间，栈底指针BOTTOM指间栈底指间栈底元素，栈顶指针TOP指向栈顶元素，如果BOTTOM49，元素，栈顶指针指向栈顶元素，如果，指向栈顶元素TOP30（数组下标），则栈中具有【】个元素。），则栈中具有个元素。（数组下标），则栈中具有【（2009年3月）年月答案答案199设某循环队列的容量为，如果头指针设某循环队列的容量为50，如果头指针FRONT45指向指向队头元素的前一位置，尾指针REAR10指向队尾元素，指向队尾元素，队头元素的前一位置，尾指针指向队尾元素则该循环队列中共有【2】个元素。（2010年3月）】个元素。年月答案答案15第36页线性结构与非线性结构线性表、线性表、栈和队列都是线性结构一个数据结构不是线性结构，则称其为非线性结一个数据结构不是线性结构，则称其为非线性结构。一个非空的数据结构若满足下面的两个条件，一个非空的数据结构若满足下面的两个条件，则这种数据结构即为线性结构线性结构。构即为线性结构。有且仅有一个根结点；有且仅有一个根结点；除第一个结点外，每一个结点最多有一个直接前驱结点；除第一个结点外，每一个结点最多有一个直接前驱结点；除最后一个结点外，每一个结点最多有一个直接后继结点。除最后一个结点外，每一个结点最多有一个直接后继结点。3HEAD19510A1A2A3A4A5第37页线性链表的逻辑状态3树与二叉树树型结构是一种重要的非线性结构。树型结构是一种重要的非线性结构。树的概念二叉树的概念二叉树的存储二叉树的遍历第38页树的概念树的定义个结点的有限集。（N0）个结点的有限集。（树的定义N个结点的有限集。（）根ONLYONE若N0，则称为空树；，则称为空树；否则，否则，当N1时，其余结时点被分成M（点被分成（M0）个互不）相交的子集T1，相交的子集，T2，TM，每个子集又是一棵树。，每个子集又是一棵树。由此可以看出，由此可以看出，树的定义是递归的。递归的。QUESTION如何辨别根如何辨别根第39页EBFJACGKDHMI只有一个结点的树A树型结构的常用术语结点的度一个结点的子树的个数；结点A、的度数的度数个数；Q结点、G的度数树的度树中所有结点度的最大值；右图中树的度大值；Q右图中树的度终端结点度为的结点；度为0的结点的结点；Q图中叶子结点有几个7图中叶子结点有几个非终端结点度不为的结点；度不为0的结点的结点；Q图中非终端结点有几个5图中非终端结点有几个孩子结点、双亲结点、兄弟结点、结点的子孙、孩子结点、双亲结点、兄弟结点、结点的子孙、结点的祖先第40页BEFJACGKDHMI树型结构的常用术语结点的层次树中根结点的层次为1，根结点子树的根为第2层次为，根结点子树的根为第层，以此类推；以此类推；Q图中结点F的层次图中结点的层次的层次EABFJCGKDHMI树的深度树中所有结点层次的最大值；图中树的深度的最大值；Q图中树的深度有序树、无序树如果树中每有序树、棵子树从左向右的排列拥有一定的顺序，不得互换，的顺序，不得互换，则称为有序否则称为无序树。树，否则称为无序树。第41页二叉树的概念定义二叉树是一种有序的树形结构。定义二叉树是一种有序的树形结构。它与一般树形结构的区别是树形结构的区别是每个结点最多有两棵子树；每个结点最多有两棵子树；子树有左右之分，次序不能任意颠倒。子树有左右之分，次序不能任意颠倒。二叉树的5种基本形态二叉树的种基本形态第42页二叉树的性质【性质1】在二叉树的第层上最多有I1个结点（I1）在二叉树的第I层上最多有个结点（）层上最多有2ABEFGH第43页CD【性质2】深度为的二叉树最多有2H1个结点（H1）深度为H的二叉树最多有个结点（）深度为的二叉树最多有个结点满二叉树如果一个深度为的二叉树拥有满二叉树如果一个深度为H的二叉树拥有H1个结的二叉树拥有2个结点，则将它称为满二叉树。则将它称为满二叉树。满二叉树完全二叉树有一棵深度为，具有个结点的二叉树，完全二叉树有一棵深度为H，具有N个结点的二叉树，个结点的二叉树若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1N的结点位置的结点位置的每个结点分别与满二叉树中编号为一一对应，则称这棵二叉树为完全二叉树。一一对应，则称这棵二叉树为完全二叉树。完全二叉树第44页满二叉树满二叉树也是完满全二二叉树完全二叉树第45页完全二叉树是叉树非完全二叉树深度为4的深度为的完全二叉树第46页【性质3】二叉树上叶子结点数比度为的结点数多二叉树上叶子结点数比度为2的结点数多二叉树上叶子结点数比度为的结点数多1ABEFGHCD叶子结点度为2的结点第47页【性质4】具有个结点的完全二叉树的深度为LOG2N1具有N个结点的完全二叉树的深度为具有其中，其中，LOG2N的结果是不大于的结果是不大于LOG2N的最大整数的最大整数深度为4的深度为的满二叉树深度为4的深度为的完全二叉树LOG281LN9/IN24LOG2151IN16/IN24深度为3的完全二叉树具有4深度为的完全二叉树具有7深度为4的完全二叉树具有8深度为的完全二叉树具有15深度为5的完全二叉树具有15深度为的完全二叉树具有31深度为6的完全二叉树深度为的完全二叉树深度为7的完全二叉树深度为的完全二叉树深度为8的完全二叉树深度为的完全二叉树深度为9的完全二叉树深度为的完全二叉树深度为10的完全二叉树深度为的完全二叉树深度为11的完全二叉树深度为的完全二叉树具有32具有63具有64具有127具有128255具有具有256511具有具有5121023具有具有10242047具有第48页树型结构方面的考题1在深度为7的满二叉树中,叶子结点的个数为（2006年4月）在深度为7的满二叉树中,叶子结点的个数为（2006年A32A32B31B31C64C64D63D631答案C。答案。答案2在深度为7的满二叉树中，度为2的结点个数为【在深度为7的满二叉树中，度为2的结点个数为【07年】。07年4月）2答案63。答案。答案一棵二叉树中共有70个叶子结点与80个度为1的结点，70个叶子结点与80个度为3一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总07年结点数为（07年9月）A）219B）221C）2293答案A。答案。答案D）231个叶子结点。】个叶子结点。】个。（20054答案19。答案。答案某二叉树中度为2的结点有1818个4某二叉树中度为2的结点有18个，则该二叉树中有【（2005年4月）2005年年9月）一棵二叉树第六层（根结点为第一层）的结点数最多为【5一棵二叉树第六层（根结点为第一层）的结点数最多为【5答案32。答案。答案第49页二叉树的存储在计算机中，二叉树通常采用链式存储结构。在计算机中，二叉树通常采用链式存储结构。LLINKINFORLINKT二叉树的存储结点的结构ABDGACBFCEDGEF第50页二叉树的遍历遍历指不重复地访问二叉树中的所有结点。遍历指不重复地访问二叉树中的所有结点。不重复地访问二叉树中的所有结点二叉树的遍历的次序与树型结构上的大多数运算有联系。数运算有联系。遍历的方式有三种序遍历（1）先（前）序遍历（DLR）（2）中序遍历（LDR）中序遍历（）（3）后序遍历（LRD）后序遍历（）H第51页ACFGDBE二叉树的遍历遍历指不重复地访问二叉树中的所有结点。遍历指不重复地访问二叉树中的所有结点。不重复地访问二叉树中的所有结点序遍历（1）先（前）序遍历（DLR）若二叉树为空，则结束遍历操作；若二叉树为空，则结束遍历操作；否则访问根结点；访问根结点；先序遍历左子树；先序遍历左子树；遍历左子树先序遍历右子树。先序遍历右子树。遍历右子树GEBFACD先序遍历的结果先序遍历的结果ABECFGHDH第52页（2）中序遍历（LDR）中序遍历（）若二叉树为空，则结束遍历操作；若二叉树为空，则结束遍历操作；否则中序遍历左子树；中序遍历左子树；访问根结点；访问根结点；中序遍历右子树。中序遍历右子树。中序遍历的结果中序遍历的结果EBAFHGCD（3）后序遍历（LRD）后序遍历（）若二叉树为空，则结束遍历操作；若二叉树为空，则结束遍历操作；否则后序遍历左子树；后序遍历左子树；后序遍历右子树；后序遍历右子树；访问根结点。访问根结点。后序遍历的结果后序遍历的结果EBHGFDCA第53页ABEFGHCD练习练习下图所示的二叉树经过三种遍历得到的顺序分别为下图所示的二叉树经过三种遍历得到的顺序分别为ABDGEHCF先序序列先序序列ABDGCEFH中序序列中序序列DGBAECHF后序序列后序序列GDBEHFCA根据先序遍历序列，根据先序遍历序列，建立二叉树第54页树型结构方面的考题21设二叉树如下设二叉树如下设二叉树如下（2010年3月）年月对该二叉树进行后序遍历的结果为【3】EDBGHFCAABCFEGHD2对如下二叉树（2006年4月）对如下二叉树（年月进行后序遍历的结果为AABCDEFBDBEAFCDCABDECFDDEBFCA第55页查找技术查找是数据处理的重要内容。查找是数据处理的重要内容。查找指在一个给定的数据结构中查找指定的元素，查找指在一个给定的数据结构中查找指定的元素，该元素也称关键字。该元素也称关键字。若找到了满足条件的结点，称查找成功；若找到了满足条件的结点，称查找成功；否则称查找失败。找失败。衡量一个查找算法的主要标准是查找过程中对关键字进行的平均比较次数。字进行的平均比较次数。通常根据不同的数据结构，采用不同的查找方法通常根据不同的数据结构，采用不同的查找方法顺序查找二分查找第56页顺序查找线性表中最简单的查找方法。线性表中最简单的查找方法。方法从线性表的第一个元素开始，方法从线性表的第一个元素开始，依次将线性表中的元素与关键字进行比较，若相等，则查找成功；中的元素与关键字进行比较，若相等，则查找成功；若将所有元素都与关键字进行了比较但不相等，则若将所有元素都与关键字进行了比较但不相等，查找失败。查找失败。顺序查找法的适用场合顺序查找法的适用场合对线性表中元素的排列次序没有要求；对线性表中元素的排列次序没有要求；对线性表的存储结构没有要求，对线性表的存储结构没有要求，链式结构和顺序结构均可。序结构均可。第57页二分查找折半查找是一种效率较高的查找方法，但是只适合顺序存储是一种效率较高的查找方法，但是只适合顺序存储的有序表。的有序表。二分查找的方法二分查找的方法首先将关键字与线性表中间位置的结点比较，相等则查找成功；不相等则根据比较的结点比较，相等则查找成功；结果确定下一步查找应在哪个子表中进行；结果确定下一步查找应在哪个子表中进行；重复上述过程，直至查找成功或子表长度为0。述过程，直至查找成功或子表长度为。二分查找法的适用场合二分查找法的适用场合线性表中的元素按关键字值递增或递减的次序排列；线性表采用顺序存储结构。线性表采用顺序存储结构。第58页折半查找算法举例对给定数列（有序）3，11，17，21，23，28，对给定数列（有序）3，5，11，17，21，23，28，30，32，50，按折半查找算法，查找关键字值为3030，32，50，按折半查找算法，查找关键字值为30的数据元素。的数据元素。A1A2A3A4A5A6A7A8A9A103，11，17，21，23，28，30，32，第1次3，5，11，17，21，23，28，30，32，50K30MID1（110）MID1（110）/25LOWMIDHIGHKAMID1A52123，28，30，32，第2次23，28，30，32，50LOW上一页下一页停止放映HIGHMIDMID2（610）/28610）KAMID2A830第59|92页59|92页|92练习假设待查有序（升序）顺序表中数据元素的关键字序列为（8,18,27,42,47,50,56,68,95,120），用折半查找方法查找关键字值为27的数据元素对于长度为N的有序线性表，最坏情况只需比较LOG2N次对于长度为N的有序线性表，最坏情况只需比较LOG2N次。LOG2N第60页排序技术排序指将一个无序序列整理成按关键字值递增或递减排列的有序排序指将一个无序序列整理成按关键字值递增或递减排列的有序序列。序列。顺序存储的线性表排序方法中其排序对象一般是顺序存储的线性表。排序方法中其排序对象一般是顺序存储的线性表。根据排序序列的规模以及数据处理的要求，根据排序序列的规模以及数据处理的要求，可以采用不同的排序方法交换类排序法冒泡排序快速排序插入类排序法简单插入排序希尔排序选择类排序法简单选择排序堆排序第61页冒泡排序冒泡排序的方法冒泡排序的方法扫描整个线性表，扫描整个线性表，逐次对相邻的两个元素进行比若为逆序，则交换；较，若为逆序，则交换；第一趟扫描的结果使最或最小的元素排到表的最后或最前大或最小的元素排到表的最后或最前；或最小的元素排到表的最后或最前除最后或最前一个元素除最后或最前一个元素，对剩余的元素重复上或最前一个元素，述过程，将次大或次小的数排到表的倒数或正或次小的数排到表的倒数述过程，将次大或次小的数排到表的倒数或正第二个位置；数第二个位置；第二个位置重复上述过程；重复上述过程；对于长度为N的线性表，对于长度为的线性表，冒泡排序需要对表扫描的线性表N1遍。遍第62页冒泡排序的方法设待排数据元素的关键字为（，设待排数据元素的关键字为（18，20，15，32，4，25），第一趟冒泡排序后的序列状），第一趟，），第一趟冒泡排序后的序列状态如图所示181818181818上一页下一页停止放映201532420153241520324152032415204321520425252525252532最大数第63|92页63|92页|92第二趟冒泡排序Q第二趟冒泡排序后的结果是什么样的达到第二趟冒泡排序后的结果是什么样的了最终的排序目标吗了最终的排序目标吗一共需要多少次能够最后成为有序序列后成为有序序列Q你觉得冒泡排序的效率如何如果是你，你你觉得冒泡排序的效率如何如果是你，会用什么方法来排序会用什么方法来排序冒泡排序比较简单，当初始序列基本有序时，冒泡排序比较简单，当初始序列基本有序时，冒泡排序有较高的效率，反之效率较低。冒泡排序有较高的效率，反之效率较低。冒泡排序终止条件冒泡排序终止条件本趟排序未发生交换，本趟排序未发生交换，终止排序算法上一页下一页停止放映第64|92页64|92页|92设待排数据元素的关键字为（26,18,32,54,47,9,15初始序列第一趟排序后第二趟排序后第三趟排序后第四趟排序后第五趟排序后2618325447915上一页下一页停止放映182632479155418263291547182691532189152691518冒泡排序法，需要比较的次数为NN1/2；冒泡排序法，需要比较的次数为NN1/2；NN第65|92页65|92页|92选择排序选择排序的方法选择排序的方法扫描整个线性表，从中找出最小的元素，扫描整个线性表，从中找出最小的元素，与第一个元素交换；一个元素交换；除第一个元素，对剩下的子表采用相同的方法除第一个元素，找出次小的数，与第二个数交换；找出次小的数，与第二个数交换；重复上述过程；重复上述过程；对于长度为N的线性表，对于长度为的线性表，选择排序需要对表扫的线性表描N1遍。遍简单选择排序法,最坏情况需要NN1/2次比较NN次比较；简单选择排序法,最坏情况需要NN1/2次比较；第66页例设待排数据元素的关键字为（15，14，22，30，设待排数据元素的关键字为（，37，11），每一趟排序后的序列状态如图所示），每一趟排序后的序列状态如图所示，），每一趟排序后的序列状态如图所示初态初态15，14，22，30，37，15，11，第一趟第一趟1114，22，30，37，15，15，第二趟第二趟11，1422，30，37，15，15，第三趟11，14，30，37，22，第三趟11，14，1530，37，22，15第四趟11，14，15，1537，22，30第四趟，第五趟第五趟11，14，15，15，2237，30，上一页下一页停止放映第六趟第六趟11，14，15，15，22，3037，有序序列第67|92页67|92页|92排序法小结排序法小结简单选择排序法,最坏情况需要NN1/2次比较；次比较；简单选择排序法最坏情况需要次比较冒泡排序法,冒泡排序法希尔排序法,希尔排序法堆排序法,堆排序法最坏情况需要NN1/2次比较；次比较；最坏情况需要次比较最坏情况需要ON15次比较；次比较；最坏情况需要次比较最坏情况需要ONLOG2N次比较；次比较；最坏情况需要次比较第68页排序查找方面的考题排序查找方面的考题1对于长度为的线性表，在最坏情况下，下列各排序法所对应的比较对于长度为N的线性表，在最坏情况下，的线性表次数中正确的是（次数中正确的是（2005年4月）年月DA冒泡排序为冒泡排序为N/2B冒泡排序为冒泡排序为NC快速排序为快速排序为ND快速排序为快速排序为NN1/22在长为的有序线性表中进行顺序查找，最坏情况下需要比较的次数在长为64的有序线性表中进行顺序查找在长为的有序线性表中进行顺序查找，为。（06年9月）。年月A）、）、63）、B）、）、64）、C）、）、6）、D）、）、7）、B3下列数据结构中，能用二分法进行查找的是（2005年9月）下列数据结构中，能用二分法进行查找的是（年月A）顺序存储的有序线性表B）线性链表）AC）二叉链表D）有序线性链表）4下列排序方法中，最坏情况下比较次数最少的是（09年3月）下列排序方法中，最坏情况下比较次数最少的是（年月A）冒泡排序B）简单选择排序）DC）直接插入排序）D）堆排序）第69页第二章程序设计基础内容内容1程序设计方法与风格。程序设计方法与风格。结构化程序设计。2结构化程序设计。面向对象的程序设计方法，对象，3面向对象的程序设计方法，对象，方属性及继承与多态性。法，属性及继承与多态性。第70页1结构化程序设计结构化程序设计方法的四条原则是1234自顶向下；逐步求精；模块化；限制使用GOTO语句。结构化程序的基本结构和特点结构化程序的基本结构和特点（1）顺序结构）顺序结构简单的程序设计，最基本、最常用的结构；（2）选择结构（分支结构）选择结构（分支结构）包括简单选择和多分支选择结构，（3）重复结构（循环结构）重复结构（循环结构）可根据给定条件，判断是否需要重复执行某一相同程序段。第71页2面向对象的程序设计对象是面向对象方法中最基本的概念。对象是面向对象方法中最基本的概念。对象是系统中用来描述客观事物的一个实对象是系统中用来描述客观事物的一个实是构成系统的一个基本单位，体，是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成。操作组成。属性即对象所包含的信息属性即对象所包含的信息操作描述了对象执行的功能，操作也称为方操作描述了对象执行的功能，描述了对象执行的功能法或服务。法或服务。第72页类是指具有共同属性、共同方法的对象的集合。是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象，对象是对应类的一个实例是对应类的一个实例。所以类是对象的抽象，对象是对应类的一个实例。消息是一个实例与另一个实例之间传递的信息是一个实例与另一个实例之间传递的信息。消息是一个实例与另一个实例之间传递的信息。消息的组成包括（1）接收消息的对象的名称；）接收消息的对象的名称；（2）消息标识符，也称消息名；）消息标识符，也称消息名；（3）零个或多个参数。）零个或多个参数。继承是指能够直接获得已有的性质和特征是指能够直接获得已有的性质和特征，继承是指能够直接获得已有的性质和特征，而不必重复定义他们。复定义他们。单继承指一个类只允许有一个父类多重继承指一个类允许有多个父类。多重继承指一个类允许有多个父类。多态性是指同样的消息被不同的对象接受时可导致完多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。全不同的行动的现象。第73页程序设计基础方面的考题1符合结构化原则的三种基本控制结构是选择结构、循环结构和【】符合结构化原则的三种基本控制结构是选择结构、循环结构和【2009年3月年月2下列选项中不属于结构化程序设计原则的是（2009年9月）下列选项中不属于结构化程序设计原则的是（年月A可封装D自顶向下（顺序结构）顺序结构）AC模块化D逐步求精3以下叙述中正确的是。（以下叙述中正确的是。（。（2010年3月）年月A）程序设计的任务就是编写程序代码并上机调试）B）程序设计的任务就是确定所用数据结构）C）程序设计的任务就是确定所用算法）D）以上三种说法都不完整）D对象4在面向对象方法中，类的实例称为【】。（在面向对象方法中，在面向对象方法中】。（2005年4月）年月5在面向对象方法中【】描述的是具有相似属性与操作的一组对象。在面向对象方法中,在面向对象方法中】描述的是具有相似属性与操作的一组对象。类（2006年4月）第74页第三章软件工程基础计算机软件是包括程序、计算机软件是包括程序、数据及相关文档的完整集合。档的完整集合。软件按功能分为应用软件、系统软件、软件按功能分为应用软件、系统软件、支撑软件（或工具软件）。支撑软件（或工具软件）。第75页1软件工程概念软件工程概念软件工程是应用于计算机软件的定义、软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。一整套方法、工具、文档、实践标准和工序。软件工程包括3个要素方法、工具和过程。个要素软件工程包括个要素方法、工具和过程。软件周期软件产品从提出、实现、软件周期软件产品从提出、实现、使用维护到停止使用退役的过程。使用退役的过程。软件生命周期三个阶段软件定义软件开发、软件定义、软件生命周期三个阶段软件定义、软件开发、运行维护，主要活动阶段是维护，主要活动阶段是（1）可行性研究与计划制定；可行性研究与计划制定；可行性研究与计划制定（2）需求分析；）需求分析；（3）软件设计；）软件设计；（4）软件实现；）软件实现；（5）软件测试；）软件测试；（6）运行和维护。）运行和维护。第76页2结构化分析方法结构化分析方法着眼于数据流，自顶向下，结构化分析方法着眼于数据流，自顶向下，着眼于数据流逐层分解，建立系统的处理流程，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具,建立系统的逻辑模型。和数据字典为主要工具建立系统的逻辑模型。建立系统的逻辑模型结构化分析的常用工具（1）数据流图；）数据流图；（2）数据字典；）数据字典；（3）判定树；判定表。）判定树；判定表。（4）软件需求规格说明书）第77页3结构化设计方法软件设计包括软件设计包括总体设计与详细设计在程序结构中各模块的内聚性越强，在程序结构中各模块的内聚性越强，则耦合性越弱。优秀软件应高内聚，低耦合。越弱。优秀软件应高内聚，低耦合。常见的过程设计工具有常见的过程设计工具有图形工具（程序流程图,NS,PAD）图形工具（程序流程图）表格工具（判定表）表格工具（判定表）语言工具（伪码）语言工具（PDL伪码）伪码第78页程序流程图NS图图P