1、 全国计算机等级考试全国计算机等级考试辅导教程辅导教程 公共基础知识公共基础知识考试大纲考试大纲考试方式考试方式1 笔试笔试，与程序设计语言（，与程序设计语言（C、VB、VF等）笔试等）笔试部分合为一张试卷。部分合为一张试卷。2 公共基础知识占笔试试卷的公共基础知识占笔试试卷的30分分。3 10道选择题、道选择题、5道填空题道填空题。基本要求基本要求1 掌握算法的基本概念掌握算法的基本概念2 掌握基本数据结构及其操作掌握基本数据结构及其操作3 掌握基本排序和查找算法掌握基本排序和查找算法4 掌握逐步求精的结构化程序设计方法掌握逐步求精的结构化程序设计方法5 掌握软件工程的基本方法，具有初步应用
2、相关技掌握软件工程的基本方法，具有初步应用相关技术进行软件开放的能力术进行软件开放的能力6掌握数据库的基本知识，了解关系数据库的设计掌握数据库的基本知识，了解关系数据库的设计考试内容考试内容数据结构与算法数据结构与算法1 1 算法的基本概念：算法的基本概念：时间复杂度、时间复杂度时间复杂度、时间复杂度2 2 数据结构的基本概念：数据结构的基本概念：逻辑结构、存储结构、图形表示逻辑结构、存储结构、图形表示 线性结构与非线性结构线性结构与非线性结构3 3 线性表的定义：线性表的定义：顺序存储结构、插入与删除操作顺序存储结构、插入与删除操作4 4 栈和队列：栈和队列：顺序存储结构、基本运算顺序存储结
3、构、基本运算5 5 线性链表：线性链表：结构、基本运算结构、基本运算6 6 树的基本概念：树的基本概念：二叉树、遍历二叉树、遍历7 7 查找技术：查找技术：顺序、二分查找顺序、二分查找8 8 排序技术：排序技术：交换、选择、插入排序交换、选择、插入排序第一章：数据结构与算法第一章：数据结构与算法第一节第一节 算法的基本概念算法的基本概念1 定义定义 算法是指解题方案的准确而完整的描述算法是指解题方案的准确而完整的描述。算法不等于程序算法不等于程序,当然程序也可以作为算法的描述当然程序也可以作为算法的描述,但程序还需考虑但程序还需考虑很多与方法和分析无关的细节问题。很多与方法和分析无关的细节问题
4、。2 算法的基本特征算法的基本特征（1）可行性可行性 同一个算法在不同精度的计算机上应得到相同的结果同一个算法在不同精度的计算机上应得到相同的结果（2）确定性确定性 算法中的每一步必须有明确的定义，不允许有多义性。算法中的每一步必须有明确的定义，不允许有多义性。（3）有穷性有穷性 执行有限步骤后终止，应包括合理的执行时间。执行有限步骤后终止，应包括合理的执行时间。（4）拥有足够的情报拥有足够的情报 算法的结果与输入的数据有关，不同的输入算法的结果与输入的数据有关，不同的输入有不同的结果。当输入错误时，算法可能无法执行。当算法拥有足有不同的结果。当输入错误时，算法可能无法执行。当算法拥有足够多的
5、情报时（考虑的输入可能性越多），出错的可能越小。够多的情报时（考虑的输入可能性越多），出错的可能越小。综上所述，所谓算法，是一组严谨地定义运算综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止是明确的，此顺序将在有限的次数下终止3 3 算法的基本要素算法的基本要素 一对数据对象的运算和操作一对数据对象的运算和操作;二算法的控制结构。二算法的控制结构。（1 1）对数据对象的运算和操作）对数据对象的运算和操作算术、关系、逻辑运算和数据传输（赋值、输入、输出）算术、关系、逻辑运算和数据传输（赋值
6、、输入、输出）（2 2）算法的控制结构）算法的控制结构 控制结构控制结构一般可分为一般可分为顺序、选择、循环顺序、选择、循环三种基本结构。三种基本结构。描述算法有传统流程图、描述算法有传统流程图、N-SN-S结构化流程图、算法描结构化流程图、算法描述语言等述语言等。4 算法复杂度算法复杂度 算法复杂度主要包括时间和空间复杂度。算法复杂度主要包括时间和空间复杂度。（1）时间复杂度（次数）时间复杂度（次数）指算法的运算次数。指算法的运算次数。（注意：不是指运算的时间）（注意：不是指运算的时间）（2）空间复杂度（空间复杂度（内存空间）内存空间）执行算法需要的内存空间。执行算法需要的内存空间。包括：程
7、序所占的空间包括：程序所占的空间 输入的数据所占的空间输入的数据所占的空间 运算时所需的空间运算时所需的空间算法的时间复杂度是指（）算法的时间复杂度是指（）A A 执行算法程序所需要的时间执行算法程序所需要的时间 B B 算法程序的长度算法程序的长度C C 算法执行过程中所需要的基本运算次数算法执行过程中所需要的基本运算次数 D D 算法程序中的指令条数算法程序中的指令条数 算法的空间复杂度是指（）算法的空间复杂度是指（）A A 算法程序的长度算法程序的长度 B B 算法程序中的指令条数算法程序中的指令条数C C 算法程序所占的存储空间算法程序所占的存储空间 D D 算法执行过程中所需要的存储
8、空间算法执行过程中所需要的存储空间 第第2节节 数据结构的基本概念数据结构的基本概念计算机处理数据，主要考虑两个方面：计算机处理数据，主要考虑两个方面：一一 提高数据处理的速度？提高数据处理的速度？二二 节省存储空间？节省存储空间？数据结构主要研究三个方面的问题：数据结构主要研究三个方面的问题：（1）数据的）数据的逻辑结构逻辑结构：各数据元素间所固有的逻辑关系：各数据元素间所固有的逻辑关系（2）数据的）数据的存储结构存储结构（物理结构物理结构）：各数据元素在计算机中的存）：各数据元素在计算机中的存储关系储关系（3）对各种数据结构进行的运算。）对各种数据结构进行的运算。1 数据结构的概念数据结构
9、的概念数据数据需要处理的数据元素的集合需要处理的数据元素的集合结构结构关系，是集合中各个数据元素之间存在的关系关系，是集合中各个数据元素之间存在的关系数据结构是指反映数据元素之间关系的数据元素集合的表示数据结构是指反映数据元素之间关系的数据元素集合的表示（1）逻辑结构）逻辑结构 反映数据元素之间逻辑关系的数据结构。反映数据元素之间逻辑关系的数据结构。例如：春、夏、秋、冬，主要指前件、后件的关系例如：春、夏、秋、冬，主要指前件、后件的关系（2）存储结构）存储结构(物理结构物理结构)在计算机存储空间的存放形式（数据的逻辑结构在计算机中在计算机存储空间的存放形式（数据的逻辑结构在计算机中的存放方式）
10、的存放方式）春不一定存储在夏的后面春不一定存储在夏的后面数据的存储结构是指数据的存储结构是指（）（）A A 存储在外存中的数据存储在外存中的数据B B 数据所占的存储空间量数据所占的存储空间量C C 数据在计算机中的顺序存储方式数据在计算机中的顺序存储方式D D 数据的逻辑结构在计算机中的表示数据的逻辑结构在计算机中的表示 2 数据结构的图形表示数据结构的图形表示父亲父亲儿子儿子女儿女儿d1d2d3名词解释：名词解释：（1）结点）结点（2）前件结点）前件结点（3）后件结点）后件结点（4）根结点）根结点春春夏夏秋秋冬冬3 线性结构和非线性结构线性结构和非线性结构一个数据结构中一个数据元素都没有，
11、称该数据结构为一个数据结构中一个数据元素都没有，称该数据结构为空空的数据结构的数据结构。根据数据元素之间前后件关系的复杂程度，将数据结构分根据数据元素之间前后件关系的复杂程度，将数据结构分为为线性结构和非线性结构线性结构和非线性结构线性结构线性结构 必须满足以下两个条件：必须满足以下两个条件：（1）有且只有一个根结点。有且只有一个根结点。（2）每个结点最多有一个前件，也最多一个后件。每个结点最多有一个前件，也最多一个后件。非线性结构非线性结构 不必须满足以上两个条件不必须满足以上两个条件d1d2d3春夏秋冬在数据结构中，从逻辑上可以把数据结构分成（）在数据结构中，从逻辑上可以把数据结构分成（）
12、A 动态结构和静态结构动态结构和静态结构B 紧凑结构和非紧凑结构紧凑结构和非紧凑结构C 线性结构和非线性结构线性结构和非线性结构D 内部结构和外部结构内部结构和外部结构 第第3节线性表和顺序存储结构节线性表和顺序存储结构1 线性表的基本概念线性表的基本概念线由一组数据元素组成。是最简单、最常用的一种数据结构线由一组数据元素组成。是最简单、最常用的一种数据结构.线性表是一种线性结构。线性表是一种线性结构。非空线性表有如下结构特征：非空线性表有如下结构特征：（1）有且只有一个根结点有且只有一个根结点（2）有且只有一个终结节点有且只有一个终结节点（3）除以上二结点外，每个结点有且只有一个前件，也有除
13、以上二结点外，每个结点有且只有一个前件，也有且只有一个后件且只有一个后件。d1d2d3春春夏夏秋秋冬冬姓名姓名性别性别数学数学英语英语张三张三女女7070李四李四男男6590王五王五女女68802 线性表的顺序存储结构线性表的顺序存储结构具有如下特点具有如下特点逻辑相临，物理相临逻辑相临，物理相临（1）线性表中所有元素所占的存储空间是连续的。）线性表中所有元素所占的存储空间是连续的。（2）数据元素在存储空间中是按逻辑顺序依次存）数据元素在存储空间中是按逻辑顺序依次存放的。放的。姓名姓名数学数学英语英语张三张三7070李四李四6590王五王五6880张三7070李四6590王五6880线性表的顺
14、序存储结构是一种随机存取的存储结构线性表的顺序存储结构是一种随机存取的存储结构。可随机访问任意一个结点可随机访问任意一个结点3 线性表的插入运算线性表的插入运算2597143、线性表的插入运算、线性表的插入运算2597143、线性表的插入运算、线性表的插入运算2597143、线性表的插入运算、线性表的插入运算2597143、线性表的插入运算、线性表的插入运算214597结论：结论：（1）如果在线性表的末尾进行，即在第）如果在线性表的末尾进行，即在第n个元个元素之后插入新元素，则只要增加素之后插入新元素，则只要增加一个一个元素即可，元素即可，不需要移动元素不需要移动元素（2）如果要在线性表的第）
15、如果要在线性表的第1个元素之前插入，个元素之前插入，则需要移动表中则需要移动表中n个个的元素。的元素。（3）在一般情况下，如果在第）在一般情况下，如果在第i个元素之前进个元素之前进行，则第行，则第i个元素之后的所有元素都必须移动。个元素之后的所有元素都必须移动。在平均情况下，需要移动表中一半的元素。在平均情况下，需要移动表中一半的元素。因此算法的平均时间复杂度为因此算法的平均时间复杂度为O(n).4、线性表的删除运算、线性表的删除运算2145974、线性表的删除运算、线性表的删除运算25974、线性表的删除运算、线性表的删除运算25974、线性表的删除运算、线性表的删除运算25974、线性表的
16、删除运算、线性表的删除运算2597注意：注意：如果为线性表开辟的存储空间已经满了，不如果为线性表开辟的存储空间已经满了，不能再插入元素，否则会造成能再插入元素，否则会造成“上溢上溢”错误错误1 如果删除如果删除第第n个个元素，则不需要移动其他元素；元素，则不需要移动其他元素；2 如果删除如果删除第第1个个元素，则需要移动所有的元素。元素，则需要移动所有的元素。3 在一般情况下，若要删除第在一般情况下，若要删除第i个元素，则原来第个元素，则原来第i个元素之后的所有元素都必须依次往前移动一个个元素之后的所有元素都必须依次往前移动一个位置。位置。平均要移动表中一半的元素。平均要移动表中一半的元素。算
17、法的平均时间复杂度为算法的平均时间复杂度为O(n).结论：结论：线性表顺序存储，插入或删除一个元素，效率很低，线性表顺序存储，插入或删除一个元素，效率很低，特别是线性表比较大的情况，由于数据元素的移动而消耗特别是线性表比较大的情况，由于数据元素的移动而消耗较多的处理时间。较多的处理时间。线性表的顺序存储结构对于小线性表或者元素不常变线性表的顺序存储结构对于小线性表或者元素不常变动的线性表来说是合适的，因为顺序存储结构比较简单。动的线性表来说是合适的，因为顺序存储结构比较简单。对线性表，描述的是（）对线性表，描述的是（）A 存储空间不一定连续，且各元素的存储顺序是任意的存储空间不一定连续，且各元
18、素的存储顺序是任意的B存储空间不一定连续，存储空间不一定连续，且前件元素一定存储在后件元素前面且前件元素一定存储在后件元素前面C存储空间必须连续，存储空间必须连续，且前件元素一定存储在后件元素后面且前件元素一定存储在后件元素后面D存储空间存储空间必须必须连续，且各元素的存储顺序是任意的连续，且各元素的存储顺序是任意的 第第4节节 栈和队列栈和队列1 栈及其运算栈及其运算 栈是限定在一端进行插入与删除的线性表。栈是限定在一端进行插入与删除的线性表。入栈原则：先进后出，后进先出。入栈原则：先进后出，后进先出。597栈顶栈顶栈底栈底64入栈（插入数据）入栈（插入数据）4597栈顶栈底664597栈顶
19、栈底入栈（插入数据）入栈（插入数据）64597栈顶栈底出栈（删除数据）出栈（删除数据）4597栈顶栈底出栈（删除数据）出栈（删除数据）597栈顶栈底出栈（删除数据）出栈（删除数据）2 栈的特点栈的特点1 栈顶元素总是最后被插入的元素，也是最早被删除栈顶元素总是最后被插入的元素，也是最早被删除的元素。的元素。2 栈底元素总是最早被插入的元素，也是最晚被删除栈底元素总是最早被插入的元素，也是最晚被删除的元素。的元素。3 栈具有记忆作用。栈具有记忆作用。4 在顺序存储结构下，栈的插入与删除运算不需要移在顺序存储结构下，栈的插入与删除运算不需要移动表中其他数据。动表中其他数据。5 栈顶指针，栈顶指针，
20、top动态反映了栈中元素的变化情况。动态反映了栈中元素的变化情况。6 栈和线性表实现方法类似栈和线性表实现方法类似顺序和链接顺序和链接下列关于栈的描述正确的是（）下列关于栈的描述正确的是（）A 在栈中只能插入元素而不能删除元素在栈中只能插入元素而不能删除元素B 在栈中只能删除元素而不能插入元素在栈中只能删除元素而不能插入元素C 栈是特殊的线性表，只能在一端插入或删除元素栈是特殊的线性表，只能在一端插入或删除元素D 栈是特殊的线性表，只能在一端插入元素，而在另一栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素端删除元素 下列关于栈的描述中错误的是（）下列关于栈的描述中错误的是（）A A
21、栈是先进后出的线性表栈是先进后出的线性表B B 栈只能顺序存储栈只能顺序存储C C 栈具有记忆作用栈具有记忆作用D D 对栈的插入与删除操作中，不需要改变栈底指针对栈的插入与删除操作中，不需要改变栈底指针 0809：一个栈的初始状态为空，现将元素一个栈的初始状态为空，现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则出依次入栈，然后再依次出栈，则出栈序列是栈序列是_。A)12345ABCDEB)EDCBA54321C)ABCDE12345D)54321EDCBA1 若进栈序列为若进栈序列为1，2，3，4，进栈过程中可以出栈，则，进栈过程中可以出栈，则下列不可能的一个出栈
22、序列是（下列不可能的一个出栈序列是（）A 1，4，3，2 B 2，3，4，1 C 3，1，4，2 D 3，4，2，12 若进栈序列是若进栈序列是1，2，3，4，假定进栈和出栈可以穿插，假定进栈和出栈可以穿插进行，则可能的出栈序列是（）进行，则可能的出栈序列是（）A 2，4，1，3 B 3，1，4，2 C 3，4，1，2 D 1，2，3，42 队列及其运算队列及其运算 允许在允许在一端一端进行插入、而在进行插入、而在另一端另一端进行删除的进行删除的线性表。线性表。即即“先进选出，后进后出先进选出，后进后出”的原则的原则DCBA frontrear入队（插入数据）入队（插入数据）EDCBA fro
23、ntrear2 队列及其运算队列及其运算 允许在允许在一端一端进行插入、而在进行插入、而在另一端另一端进行删除的进行删除的线性表。线性表。即即“先进选出，后进后出先进选出，后进后出”的原则的原则入队（插入数据）入队（插入数据）FEDCB Afrontrear2 队列及其运算队列及其运算 允许在允许在一端一端进行插入、而在进行插入、而在另一端另一端进行删除的进行删除的线性表。线性表。即即“先进选出，后进后出先进选出，后进后出”的原则的原则入队（插入数据）入队（插入数据）FEDCBfrontrear2 队列及其运算队列及其运算 允许在允许在一端一端进行插入、而在进行插入、而在另一端另一端进行删除的
24、进行删除的线性表。线性表。即即“先进先出，后进后出先进先出，后进后出”的原则的原则出队（删除数据）出队（删除数据）FEDCfrontrear2 队列及其运算队列及其运算 允许在允许在一端一端进行插入、而在进行插入、而在另一端另一端进行删除的进行删除的线性表。线性表。即即“先进选出，后进后出先进选出，后进后出”的原则的原则出队（删除数据）出队（删除数据）下列叙述中正确的是（）下列叙述中正确的是（）FEDCfrontrear栈和队列的共同点是（栈和队列的共同点是（）A 都是先进先出都是先进先出 B 都是后进先出都是后进先出 C 只允许在端点处插入和删除元素只允许在端点处插入和删除元素 D 没有共同
25、点没有共同点一个队列的入队序列是一个队列的入队序列是1，2，3，4，则队列的输出序，则队列的输出序列是列是A 4，3，2，1 C 1，4，3，2 D 3，2，4，1B 1，2，3，4FEDfrontrear下列叙述中正确的是（）下列叙述中正确的是（）B B 栈与队列是非线性结构栈与队列是非线性结构 C C 线性链表是非线性结构线性链表是非线性结构 D D 二叉树是线性结构二叉树是线性结构 下列关于队列的叙述中正确的是（）下列关于队列的叙述中正确的是（）A A 在队列中只能插入数据在队列中只能插入数据 B B 在队列中只能删除数据在队列中只能删除数据 D D 队列是先进后出的线性表队列是先进后出
26、的线性表 出队（删除数据）出队（删除数据）C C 队列是先进先出的线性表队列是先进先出的线性表A A 线性表是线性结构线性表是线性结构 第5节：线性链表线性表的顺序结构的主要缺点（1）插入或删除时要移动大量的数据元素。（2）分配空间后，如果存储空间已满，会出现“上溢”错误。（3）多个线性表同时工作时，需要大量的连续空间。假设每个数据结点对应一个存储单元，这种存储单元称为存储结点，简称结点。在链式存储方式中，要求每个结点由两部组成：一部分用于存放数据元素值，称为数据区；另一部分用于存放指针，称为指针域。数据域指针域第第5节：线性链表节：线性链表 在链式存储结构中，在链式存储结构中，存储空间可以不
27、连续存储空间可以不连续。链式存储。链式存储方式既可以用于线性结构，也可以用于非线性结构。在用方式既可以用于线性结构，也可以用于非线性结构。在用于非线性结构时，其指针的个数要多一些。于非线性结构时，其指针的个数要多一些。数据数据指针指针数据数据指针指针数据数据 指针指针数据数据NULLHEAD0数数据据指指针针指指针针数数据据指指针针指指针针数数据据指指针针指指针针数数据据0单向链表示意图单向链表示意图双向链表示意图双向链表示意图1 1 链式存储方法链式存储方法存储地址存储地址200 101 300 390 500 809200 101 300 390 500 809存储内容存储内容 a a h
28、 h d d o o b b m m c c后继地址后继地址101101300300390390500500809809340340nullnull 链式存储结构不要求逻辑上相邻的数据物理链式存储结构不要求逻辑上相邻的数据物理上也相邻上也相邻,结点间的关系由附加的地址结点间的关系由附加的地址(指针指针)为实为实现现.每个结点由两部组成：一部分用于存放数据元素值称为数每个结点由两部组成：一部分用于存放数据元素值称为数据区；另一部分用于存放指针称为指针域。据区；另一部分用于存放指针称为指针域。数据域数据域指针域指针域 105105 h h 110110 100100 a a 105105 1101
29、10 d d 308308 308308 o o 500500 500500 b bnullnull headhead 100100 101 102 103 104 105 106 107 108101 102 103 104 105 106 107 108存储内容存储内容 a a b b c c d d e e f f g g h h顺序存储顺序存储(1)(1)在逻辑上相邻的元素在物理可以不相邻在逻辑上相邻的元素在物理可以不相邻(2)(2)存储时不用事先准备存储时不用事先准备,这样会节约存储空间这样会节约存储空间(3)(3)对增加对增加,删除接点操作简单删除接点操作简单,不必移动结点不必移动
30、结点,只要改结点中指针值只要改结点中指针值 优点：优点：除存储本身信息外，还除存储本身信息外，还有表示有表示其直接后继信息其直接后继信息的指针域的指针域,因此其存储因此其存储密度小密度小,存储空间利用率低。存储空间利用率低。缺点：缺点：105105 h h 110110 100100 a a 105105 110110 d d 308308 308308 o o 500500 500500 b bnullnull headhead 100100 105 h 110 100 a 105 110 d 308 308 o 500 500 bnull head 100m 105 h 110 100 a
31、 105 210 m 110 d 308 308 o500 head 100 500 bnull2 2 插入元素插入元素 210110 105 h 210 100 a 105 210 m 110 110 d 308 308 o500 head 100 500 bnull3 3 删除元素删除元素 105 h 210 100 a 105 110 d 308 308 o 500 500 bnull head 1001101 1 下列对于线性链表的描述中正确的是下列对于线性链表的描述中正确的是 A A 存储空间不一定是连续，且各元素的存储顺序是任意的存储空间不一定是连续，且各元素的存储顺序是任意的B
32、B 存储空间不一定是连续，且前件元素一定存储在后件元素的前面存储空间不一定是连续，且前件元素一定存储在后件元素的前面C C 存储空间必须连续，且前件元素一定存储在后件元素的前面存储空间必须连续，且前件元素一定存储在后件元素的前面D D 存储空间必须连续，且各元素的存储顺序是任意的存储空间必须连续，且各元素的存储顺序是任意的 2 链表不具备的特点是（）链表不具备的特点是（）B 插入和删除不需要移动任何元素插入和删除不需要移动任何元素C 不必事先估计存储空间不必事先估计存储空间 D 所需要空间与其长度成正比所需要空间与其长度成正比3 下列叙述中正确的是（）下列叙述中正确的是（）A 线性链表是线性表
33、的链式存储结构线性链表是线性表的链式存储结构B 栈和队列是非线性结构栈和队列是非线性结构C 双向链表是非线性结构双向链表是非线性结构D 只有根结点的二叉树是线性结构只有根结点的二叉树是线性结构A 可随机访问任意一个结点可随机访问任意一个结点第第6节节 树和二叉树树和二叉树1 树树 树是一种非线性结构。树是一种非线性结构。南昌工程学院信息系水利系机电系软件应用网络应电供电通信2 树基本术语树基本术语ABCDEFG结点结点表示树中的元素表示树中的元素,包括数据项及若干指向其子树的分支包括数据项及若干指向其子树的分支结点的度结点的度结点拥有的子树数结点拥有的子树数叶子叶子度为度为0的结点的结点双亲双
34、亲孩子结点的上层结点叫该结点的双亲孩子结点的上层结点叫该结点的双亲兄弟兄弟同一双亲的孩子同一双亲的孩子树的度树的度-一棵树中最大的结点度数一棵树中最大的结点度数结点的层次结点的层次从根结点算起从根结点算起,根为第一层根为第一层,它的孩子为第二层它的孩子为第二层树的高度树的高度树中结点的最大层次数（树中结点的最大层次数（树的深度树的深度）森林森林m(m 0)棵互不相交的树的集合棵互不相交的树的集合ABCDEFGHIJKLM结点结点A的度：的度：3结点结点B的度：的度：2结点结点M的度：的度：0叶子：叶子：K，L，F，G，M，I，J结点结点I的双亲：的双亲：D结点结点L的双亲：的双亲：E树的度：树
35、的度：3结点结点A的层次：的层次：1结点结点M的层次：的层次：4树的深度：树的深度：4ABCDEFHIJK结点结点B的孩子：的孩子：结点结点F的双亲：的双亲：树的高度树的高度结点结点K的层次的层次树的度树的度叶子：叶子：结点结点A的度：的度：互为兄弟的结点：互为兄弟的结点：2E,I,J,K,HD,ECB,C D,E F,H I,J244下列关于树的概念错误的是（下列关于树的概念错误的是（）A一棵树中只有一个无前驱的结点一棵树中只有一个无前驱的结点B一棵树的度为树中各个结点的度数之和一棵树的度为树中各个结点的度数之和C一棵树中，每个结点的度数之和等于结点总数减一棵树中，每个结点的度数之和等于结点
36、总数减1D一棵树中每个结点的度数之和与边的条数相等一棵树中每个结点的度数之和与边的条数相等二叉树二叉树RKQBNOW二叉树具有以下两个特点二叉树具有以下两个特点:(1)非空二叉树只有一个根结点。非空二叉树只有一个根结点。(2)每个结点最多有二个子树每个结点最多有二个子树,且分别且分别称左子树和右子树。称左子树和右子树。二叉树不是树的特殊情况，主要区别是区分左子树和右二叉树不是树的特殊情况，主要区别是区分左子树和右子树，即使是在只有一棵树的情况下，也要指明是左子子树，即使是在只有一棵树的情况下，也要指明是左子树或右子树。树或右子树。NBOWBACACBABOWBAC 3 二叉树二叉树两棵不同的二
37、叉树两棵不同的二叉树RKQBNOW二叉树的基本性质：二叉树的基本性质：(1)第第k层上最多有层上最多有2k-1个结点个结点(2)深度为深度为m二叉树的最多有二叉树的最多有2m-1个结点个结点(3)在任意一个二叉树中在任意一个二叉树中,度为度为0的结点（即叶子结点）总的结点（即叶子结点）总比度为比度为2的点多一个。的点多一个。(4)具有具有n个结点的二叉树，其深度至少为个结点的二叉树，其深度至少为log2n+1例例:在深度为在深度为5 5的二叉树中，结点的个数最多为的二叉树中，结点的个数最多为 A A）32 B32 B）31 C31 C）16 D16 D）15154 满二叉树：满二叉树：除最后一
38、层外，每一层上除最后一层外，每一层上的所有结点都有两个子结点。的所有结点都有两个子结点。RKQBNRKQBNOWRKQB5 完全二叉树：完全二叉树：是除最后一层外，每是除最后一层外，每一层上的结点数均达到最大值；在最一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。后一层上只缺少右边的若干结点。RKQBNOWQRKBW一棵二叉树第六层的结点数最多为一棵二叉树第六层的结点数最多为 （）个个 某二某二叉叉树中，度为树中，度为2 2的结点有的结点有1818个，则个，则有（有（）个叶子结点。个叶子结点。一棵完全二叉树有一棵完全二叉树有700700个结点，该二叉树中有个结点，该二叉树中有（）
39、个叶个叶子结点子结点 3219350N0+N2+N1=700 N1=1 N0=N2+1 2*N2+N1+1=700N2=349 N0=3506 二叉树的遍历二叉树的遍历遍历是指不重复地访问二叉树中所有结点。遍历是指不重复地访问二叉树中所有结点。C遍历分三种方式：遍历分三种方式：前序、中序和后序遍历前序、中序和后序遍历。前序遍历法前序遍历法首先访问首先访问根结点根结点,再访问再访问左子树左子树,最后访问最后访问右子树右子树，并且在，并且在访问左子树和右子树时访问左子树和右子树时,仍然是先访问根，再左子树，最仍然是先访问根，再左子树，最后右子树。后右子树。例：用前序法访问：例：用前序法访问：FCA
40、DBEGHPFAPHEDGBACBDFEHGP 中序遍历法中序遍历法首先访问历首先访问历左子树左子树，再访问，再访问根结点根结点，最后中序，最后中序右子树右子树。并且在访问左子树和右子树时并且在访问左子树和右子树时,仍然是先访问左子树，再仍然是先访问左子树，再访问根，最后是右子树。访问根，最后是右子树。CFAPHEDGB例：用中序法访问：例：用中序法访问：后序遍历后序遍历首先后序遍历首先后序遍历左子树左子树，再，再右子树右子树，最后访问，最后访问根结点根结点，并且，并且在访问左子树和右子树时在访问左子树和右子树时,仍然是先访问左子树，再访问仍然是先访问左子树，再访问右子树，最后是根。右子树，最
41、后是根。ABDCHPGEFCFAPHEDGB例：用后序法访问：例：用后序法访问：A bdcF HPGe实例：已知二叉树后序遍历序列是实例：已知二叉树后序遍历序列是dabec，中序遍历序列是，中序遍历序列是debac，它的，它的前序遍历序列是前序遍历序列是_。A.cedbaB.acbedC.decabD.deabcceadb实例：已知二叉树后序遍历序列是实例：已知二叉树后序遍历序列是dabec，中序遍历序列是，中序遍历序列是debac，它的，它的前序遍历序列是前序遍历序列是_。A.cedbaB.acbedC.decabD.deabc由后序由以知道根节点是由后序由以知道根节点是C；而而C又在中序的
42、最后，说明又在中序的最后，说明没有右子树。没有右子树。ceadb实例：已知二叉树后序遍历序列是实例：已知二叉树后序遍历序列是dabec，中序遍历序列是，中序遍历序列是debac，它的，它的前序遍历序列是前序遍历序列是_。A.cedbaB.acbedC.decabD.deabcceadb设一棵二叉树的中序遍历结果为设一棵二叉树的中序遍历结果为DBEAFC,DBEAFC,前序遍前序遍历结果为历结果为ABDECF,ABDECF,则后序遍历结果为则后序遍历结果为_。如图所示的二叉树，其中序遍历的结果为（如图所示的二叉树，其中序遍历的结果为（）A abcdef B abdefcA abcdef B ab
43、defcC dbefac D defbcaC dbefac D defbcaabcefd第第7节节 查找技术查找技术1 顺序查找顺序查找 以下以下2种情况只能采用顺序查找种情况只能采用顺序查找 （1）无序表）无序表 （2）有序线性表，如果采用链式存储结构。）有序线性表，如果采用链式存储结构。最坏情况下所需要的比较次数为最坏情况下所需要的比较次数为n,平均查找次数为平均查找次数为(n+1)/2 1 8 12 2 6 7 10 3 91 1 在长度为在长度为n n的有序线性表中进行二分查找，需要的比较次数的有序线性表中进行二分查找，需要的比较次数为为_。2 2 对长度为对长度为n n的线性表进行顺
44、序查找，在最坏情况下所需要的的线性表进行顺序查找，在最坏情况下所需要的比较次数为比较次数为_。A n+1 B n C(n+1)/2 D n/2 A n+1 B n C(n+1)/2 D n/2 2 2 二分法查找二分法查找 只适用于只适用于顺序存储的有序表顺序存储的有序表。对长度为对长度为n n的有序线性表，在最坏情况下，二分查找的有序线性表，在最坏情况下，二分查找只需比较只需比较loglog2 2n n次，而顺序查找要比较次，而顺序查找要比较n n次。次。1 2 3 4 5 6 7 8 9第第8节节 排序技术排序技术 交换类排序法、插入类排序法和选择类排序法。交换类排序法、插入类排序法和选择
45、类排序法。1 交换类排序法交换类排序法 借助元素之间的互相交换进行排序的一种方法。借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。）冒泡排序法。51731695173169第第8节节 排序技术排序技术 交换类排序法、插入类排序法和选择类排序法。交换类排序法、插入类排序法和选择类排序法。1 交换类排序法交换类排序法 借助元素之间的互相交换进行排序的一种方法。借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。）冒泡排序法。1573169第第8节节 排序技术排序技术 交换类排序法、插入类排序法和选择类排序法。交换类排序法、插入类排序法和选择类排序法。1 交换类排序法交换类排序法
46、 借助元素之间的互相交换进行排序的一种方法。借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。）冒泡排序法。1573169第第8节节 排序技术排序技术 交换类排序法、插入类排序法和选择类排序法。交换类排序法、插入类排序法和选择类排序法。1 交换类排序法交换类排序法 借助元素之间的互相交换进行排序的一种方法。借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。）冒泡排序法。1573169第第8节节 排序技术排序技术 交换类排序法、插入类排序法和选择类排序法。交换类排序法、插入类排序法和选择类排序法。1 交换类排序法交换类排序法 借助元素之间的互相交换进行排序的一种方法。借助元素
47、之间的互相交换进行排序的一种方法。（1）冒泡排序法。）冒泡排序法。1537169第第8节节 排序技术排序技术 交换类排序法、插入类排序法和选择类排序法。交换类排序法、插入类排序法和选择类排序法。1 交换类排序法交换类排序法 借助元素之间的互相交换进行排序的一种方法。借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。）冒泡排序法。1537169第第8节节 排序技术排序技术 交换类排序法、插入类排序法和选择类排序法。交换类排序法、插入类排序法和选择类排序法。1 交换类排序法交换类排序法 借助元素之间的互相交换进行排序的一种方法。借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。
48、）冒泡排序法。1531769第第8节节 排序技术排序技术 交换类排序法、插入类排序法和选择类排序法。交换类排序法、插入类排序法和选择类排序法。1 交换类排序法交换类排序法 借助元素之间的互相交换进行排序的一种方法。借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。）冒泡排序法。1531769第第8节节 排序技术排序技术 交换类排序法、插入类排序法和选择类排序法。交换类排序法、插入类排序法和选择类排序法。1 交换类排序法交换类排序法 借助元素之间的互相交换进行排序的一种方法。借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。）冒泡排序法。1531679第第8节节 排序技术排序
49、技术 交换类排序法、插入类排序法和选择类排序法。交换类排序法、插入类排序法和选择类排序法。1 交换类排序法交换类排序法 借助元素之间的互相交换进行排序的一种方法。借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。）冒泡排序法。1531679第第8节节 排序技术排序技术 交换类排序法、插入类排序法和选择类排序法。交换类排序法、插入类排序法和选择类排序法。1 交换类排序法交换类排序法 借助元素之间的互相交换进行排序的一种方法。借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。）冒泡排序法。1531679第第8节节 排序技术排序技术 交换类排序法、插入类排序法和选择类排序法。交换
50、类排序法、插入类排序法和选择类排序法。1 交换类排序法交换类排序法 借助元素之间的互相交换进行排序的一种方法。借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。）冒泡排序法。1531679第第8节节 排序技术排序技术 交换类排序法、插入类排序法和选择类排序法。交换类排序法、插入类排序法和选择类排序法。1 交换类排序法交换类排序法 借助元素之间的互相交换进行排序的一种方法。借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。）冒泡排序法。1531679第第8节节 排序技术排序技术 交换类排序法、插入类排序法和选择类排序法。交换类排序法、插入类排序法和选择类排序法。1 交换类排序
