计算机等级考试 二级C 之一 公共基础数据结构.ppt

《计算机等级考试 二级C 之一 公共基础数据结构.ppt》由会员分享，可在线阅读，更多相关《计算机等级考试 二级C 之一 公共基础数据结构.ppt（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、公共基础知识内容与考点公共基础知识内容与考点基本要求基本要求基本要求基本要求 掌握算法的基本概念。掌握算法的基本概念。掌握算法的基本概念。掌握算法的基本概念。掌握基本数据结构及其操作。掌握基本数据结构及其操作。掌握基本数据结构及其操作。掌握基本数据结构及其操作。掌握基本排序和查找算法。掌握基本排序和查找算法。掌握基本排序和查找算法。掌握基本排序和查找算法。掌握逐步求精的结构化程序设计方法。掌握逐步求精的结构化程序设计方法。掌握逐步求精的结构化程序设计方法。掌握逐步求精的结构化程序设计方法。掌握软件工程的基本方法，具有初步应用相关技术进行掌握软件工程的基本方法，具有初步应用相关技术进行掌握软件工

2、程的基本方法，具有初步应用相关技术进行掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。软件开发的能力。软件开发的能力。软件开发的能力。掌握数据库的基本知识，了解关系数据库的设计。掌握数据库的基本知识，了解关系数据库的设计。掌握数据库的基本知识，了解关系数据库的设计。掌握数据库的基本知识，了解关系数据库的设计。考试方式考试方式1 1公共基础知识的考试方式为笔试，与公共基础知识的考试方式为笔试，与公共基础知识的考试方式为笔试，与公共基础知识的考试方式为笔试，与C C语言程序设语言程序设语言程序设语言程序设计计计计(C+(C+语言程序设计、语言程序设计、语言程序设计、语言程序设计、J

3、avaJava语言程序设计、语言程序设计、语言程序设计、语言程序设计、Visual Visual BasicBasic语言程序设计、语言程序设计、语言程序设计、语言程序设计、Visual FoxProVisual FoxPro数据库程序设计或数据库程序设计或数据库程序设计或数据库程序设计或AccessAccess数据库程序设计数据库程序设计数据库程序设计数据库程序设计)的笔试部分合为一张试卷，公的笔试部分合为一张试卷，公的笔试部分合为一张试卷，公的笔试部分合为一张试卷，公共基础知识部分占全卷的共基础知识部分占全卷的共基础知识部分占全卷的共基础知识部分占全卷的3030分。分。分。分。2 2公共基

4、础知识有公共基础知识有公共基础知识有公共基础知识有l0l0道选择题和道选择题和道选择题和道选择题和5 5道填道填道填道填第第 1 1 章章 数据结构与算法数据结构与算法 考试内容考试内容 算法算法算法算法 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念 线性表及顺序存储结构线性表及顺序存储结构线性表及顺序存储结构线性表及顺序存储结构 栈和队列栈和队列栈和队列栈和队列 树与二叉树树与二叉树树与二叉树树与二叉树 线性链表线性链表线性链表线性链表(单、双、循环）的结构及基本运算单、双、循环）的结构及基本运算单、双、循环）的结构及基本运算单、双、循环）的结构及基本运算 查找技

5、术查找技术查找技术查找技术 排序技术排序技术排序技术排序技术选择题：选择题：4545填空题：填空题：1212考点考点1：算法的基本概念算法的基本概念考点考点考点考点1 1：算法的基本概念：算法的基本概念：算法的基本概念：算法的基本概念 解题方案的准确而完善的描述解题方案的准确而完善的描述解题方案的准确而完善的描述解题方案的准确而完善的描述考点考点考点考点1 1在笔试考试中考核的几率为在笔试考试中考核的几率为在笔试考试中考核的几率为在笔试考试中考核的几率为30%30%，主要是以填空，主要是以填空，主要是以填空，主要是以填空题的形式出现，分值为题的形式出现，分值为题的形式出现，分值为题的形式出现，

6、分值为2 2分，此考点为识记内容，读者分，此考点为识记内容，读者分，此考点为识记内容，读者分，此考点为识记内容，读者还应该了解算法中对数据的基本运算。还应该了解算法中对数据的基本运算。还应该了解算法中对数据的基本运算。还应该了解算法中对数据的基本运算。20052005年年3 3月：填空题月：填空题（5 5）问题处理方案的正确而完整的描述称为）问题处理方案的正确而完整的描述称为 。算法算法 算法的基本特征：算法的基本特征：算法的基本特征：算法的基本特征：可行性可行性可行性可行性、确定性确定性确定性确定性、有穷性有穷性有穷性有穷性、拥有足够的情报拥有足够的情报拥有足够的情报拥有足够的情报。2005

7、2005年年3 3月：选择题月：选择题（1111）算法具有五个特性，以下选项不属于算法特性的是：）算法具有五个特性，以下选项不属于算法特性的是：A A）有穷性）有穷性 B B）简洁性）简洁性 C C）可行性）可行性 D D）确定性）确定性B B考试链接考试链接算法的基本要素：算法的基本要素：（1 1）算法中对数据的运算和操作）算法中对数据的运算和操作）算法中对数据的运算和操作）算法中对数据的运算和操作 一是对数据对象的运算和操作；二是算法的控制结一是对数据对象的运算和操作；二是算法的控制结一是对数据对象的运算和操作；二是算法的控制结一是对数据对象的运算和操作；二是算法的控制结构。构。构。构。在

8、一般的计算机系统中，基本的运算和操作有以下在一般的计算机系统中，基本的运算和操作有以下在一般的计算机系统中，基本的运算和操作有以下在一般的计算机系统中，基本的运算和操作有以下4 4类：算术运算、逻辑运算、关系运算和数据传输。类：算术运算、逻辑运算、关系运算和数据传输。类：算术运算、逻辑运算、关系运算和数据传输。类：算术运算、逻辑运算、关系运算和数据传输。（2 2）算法的控制结构：算法的控制结构：算法的控制结构：算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。算法中各操作之间的执行顺序称为算法的控制结构。算法中各操作之间的执行顺序称为算法的控制结构。算法中各操作之间的执行顺序称为算

9、法的控制结构。描述算法的工具通常有传统流程图、描述算法的工具通常有传统流程图、描述算法的工具通常有传统流程图、描述算法的工具通常有传统流程图、N-SN-S结构化流程结构化流程结构化流程结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选图、算法描述语言等。一个算法一般都可以用顺序、选图、算法描述语言等。一个算法一般都可以用顺序、选图、算法描述语言等。一个算法一般都可以用顺序、选择、循环择、循环择、循环择、循环3 3种基本控制结构组合而成。种基本控制结构组合而成。种基本控制结构组合而成。种基本控制结构组合而成。考点考点2：算法的复杂度：算法的复杂度 算法复杂度的基本概念算法复杂度的基本概念

10、算法复杂度的基本概念算法复杂度的基本概念 执行算法所需要的计算工作量执行算法所需要的计算工作量执行算法所需要的计算工作量执行算法所需要的计算工作量 算法的计算工作量用算法所执行的算法的计算工作量用算法所执行的算法的计算工作量用算法所执行的算法的计算工作量用算法所执行的基本运算次数基本运算次数表示表示表示表示 算法的算法的算法的算法的基本运算次数基本运算次数表示是问题规模的函数表示是问题规模的函数表示是问题规模的函数表示是问题规模的函数算法的工作量算法的工作量算法的工作量算法的工作量=f(nf(n)n n是问题的规是问题的规是问题的规是问题的规模模模模在同一问题规模下，如果算法所需的基本运算次数

11、取决在同一问题规模下，如果算法所需的基本运算次数取决在同一问题规模下，如果算法所需的基本运算次数取决在同一问题规模下，如果算法所需的基本运算次数取决于某一特定输入时，可用平均性态或最坏情况复杂性分于某一特定输入时，可用平均性态或最坏情况复杂性分于某一特定输入时，可用平均性态或最坏情况复杂性分于某一特定输入时，可用平均性态或最坏情况复杂性分析算法的工作量析算法的工作量析算法的工作量析算法的工作量平均性态平均性态 各种特定输入下基本运算次数的加权平均值来衡量算法各种特定输入下基本运算次数的加权平均值来衡量算法各种特定输入下基本运算次数的加权平均值来衡量算法各种特定输入下基本运算次数的加权平均值来衡

12、量算法 其中其中其中其中x x是所有可能输入中的某个特定输入，是所有可能输入中的某个特定输入，是所有可能输入中的某个特定输入，是所有可能输入中的某个特定输入，p(xp(x)是是是是x x出现的概率，出现的概率，出现的概率，出现的概率，t(xt(x)是在输入为是在输入为是在输入为是在输入为x x时所执行的基本运算时所执行的基本运算时所执行的基本运算时所执行的基本运算次数，次数，次数，次数，DnDn表示当问题规模为表示当问题规模为表示当问题规模为表示当问题规模为n n时，算法所有可能输时，算法所有可能输时，算法所有可能输时，算法所有可能输入的集合。入的集合。入的集合。入的集合。最坏情况复杂性最坏情

13、况复杂性 在规模为在规模为在规模为在规模为n n n n时，算法所执行的基本运算的最大次数时，算法所执行的基本运算的最大次数时，算法所执行的基本运算的最大次数时，算法所执行的基本运算的最大次数算法的空间复杂度算法的空间复杂度包括算法程序所占的空间、输入数据所占的空间，以及包括算法程序所占的空间、输入数据所占的空间，以及包括算法程序所占的空间、输入数据所占的空间，以及包括算法程序所占的空间、输入数据所占的空间，以及算法执行过程中所需要的额外空间算法执行过程中所需要的额外空间算法执行过程中所需要的额外空间算法执行过程中所需要的额外空间 执行这个算法所需要的内存空间执行这个算法所需要的内存空间执行这

14、个算法所需要的内存空间执行这个算法所需要的内存空间 如果额外空间量相对于问题规模来说是常数，则称该如果额外空间量相对于问题规模来说是常数，则称该如果额外空间量相对于问题规模来说是常数，则称该如果额外空间量相对于问题规模来说是常数，则称该算法是算法是算法是算法是原地的原地的真题实例真题实例考点考点考点考点2 2在笔试考试中，是一个经常考查的内容，在笔试在笔试考试中，是一个经常考查的内容，在笔试在笔试考试中，是一个经常考查的内容，在笔试在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为考试中出现的几率为考试中出现的几率为考试中出现的几率为70%70%，主要是以选择的形式出现，主要是以选择

15、的形式出现，主要是以选择的形式出现，主要是以选择的形式出现，分值为分值为分值为分值为2 2分，此考点为重点识记内容，读者还应该识记分，此考点为重点识记内容，读者还应该识记分，此考点为重点识记内容，读者还应该识记分，此考点为重点识记内容，读者还应该识记算法时间复杂度及空间复杂度的概念。算法时间复杂度及空间复杂度的概念。算法时间复杂度及空间复杂度的概念。算法时间复杂度及空间复杂度的概念。20102010年年3 3月：选择题月：选择题（2 2）算法的时间复杂度指：）算法的时间复杂度指：A A）算法的执行时间）算法的执行时间 B B）算法所处理的数据量）算法所处理的数据量C C）算法指令中的语句或指令

16、条数）算法指令中的语句或指令条数D D）算法在执行过程中所需要的基本运算次数）算法在执行过程中所需要的基本运算次数20092009年年9 9月：选择题月：选择题（4 4）算法的空间复杂度指：）算法的空间复杂度指：A A）算法的执行过程中所需要的计算机存储空间）算法的执行过程中所需要的计算机存储空间B B）算法所处理的数据量）算法所处理的数据量C C）算法指令中的语句或指令条数）算法指令中的语句或指令条数D D）算法在执行过程中所需要的临时工作单元数）算法在执行过程中所需要的临时工作单元数D DA A考点考点3：数据结构的基本概念：数据结构的基本概念考点考点考点考点3 3在笔试考试中，是一个经常

17、考查的内容，在笔试在笔试考试中，是一个经常考查的内容，在笔试在笔试考试中，是一个经常考查的内容，在笔试在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为考试中出现的几率为考试中出现的几率为考试中出现的几率为70%70%，主要是以选择的形式出现，主要是以选择的形式出现，主要是以选择的形式出现，主要是以选择的形式出现，分值为分值为分值为分值为2 2分，此考点为识记内容，读者还应该识记数据分，此考点为识记内容，读者还应该识记数据分，此考点为识记内容，读者还应该识记数据分，此考点为识记内容，读者还应该识记数据的逻辑结构和存储结构的概念。的逻辑结构和存储结构的概念。的逻辑结构和存储结构的概念。

18、的逻辑结构和存储结构的概念。在数据结构中，从逻辑上可以把数据结构分成在数据结构中，从逻辑上可以把数据结构分成_。A A）内部结构和外部结构）内部结构和外部结构 B B）线性结构和非线性结构）线性结构和非线性结构C C）紧凑结构和非紧凑结构）紧凑结构和非紧凑结构 D D）动态结构和静态结构）动态结构和静态结构解析：逻辑结构反映数据元素之间的逻辑关系，解析：逻辑结构反映数据元素之间的逻辑关系，线性结构表示数据元素之间为一对一的关系，线性结构表示数据元素之间为一对一的关系，非线性结构表示数据元素之间为一对多或者多对一的关系，非线性结构表示数据元素之间为一对多或者多对一的关系，所以答案为所以答案为B

19、B）。）。考点考点3：数据结构的基本概念：数据结构的基本概念 数据元素数据元素数据元素数据元素 每一个需要处理的对象都可以抽象成每一个需要处理的对象都可以抽象成每一个需要处理的对象都可以抽象成每一个需要处理的对象都可以抽象成数据元素数据元素一般情况下，在具有相同特征的数据元素集合中，各个一般情况下，在具有相同特征的数据元素集合中，各个一般情况下，在具有相同特征的数据元素集合中，各个一般情况下，在具有相同特征的数据元素集合中，各个元素之间有某种关系，这个关系反映了该集合中的数据元素之间有某种关系，这个关系反映了该集合中的数据元素之间有某种关系，这个关系反映了该集合中的数据元素之间有某种关系，这个

20、关系反映了该集合中的数据元素之间固有的一种结构。在数据处理领域中，统常把元素之间固有的一种结构。在数据处理领域中，统常把元素之间固有的一种结构。在数据处理领域中，统常把元素之间固有的一种结构。在数据处理领域中，统常把数据元素之间的这种固有的关系简单的用前后件关系来数据元素之间的这种固有的关系简单的用前后件关系来数据元素之间的这种固有的关系简单的用前后件关系来数据元素之间的这种固有的关系简单的用前后件关系来描述描述描述描述 数据结构数据结构数据结构数据结构 带有带有带有带有结构结构结构结构的数据元素的集合的数据元素的集合的数据元素的集合的数据元素的集合数据元素之间的前后件关系数据元素之间的前后件

21、关系数据元素之间的前后件关系数据元素之间的前后件关系(数据的逻辑结构数据的逻辑结构 (数据的存储结构数据的存储结构 (数据的运算数据的运算数据的逻辑结构数据的逻辑结构 数据的逻辑结构是反映数据之间逻辑关系的结构数据的逻辑结构是反映数据之间逻辑关系的结构数据的逻辑结构是反映数据之间逻辑关系的结构数据的逻辑结构是反映数据之间逻辑关系的结构数据结构的两要素：数据结构的两要素：数据结构的两要素：数据结构的两要素：Data-Structure Data-Structure Data-Structure Data-Structure (D,R)(D,R)(D,R)(D,R)其中：其中：其中：其中：D D

22、D D是数据元素的集合，是数据元素的集合，是数据元素的集合，是数据元素的集合，R R R R是是是是D D D D上关系的集合上关系的集合上关系的集合上关系的集合例例1。1 一年四季的数据结构可表示成一年四季的数据结构可表示成B=B=B=B=（D D D D，R R R R）D=D=D=D=春，夏，秋，冬春，夏，秋，冬春，夏，秋，冬春，夏，秋，冬 R=R=R=R=（春，夏），（夏，秋），（秋，冬）（春，夏），（夏，秋），（秋，冬）（春，夏），（夏，秋），（秋，冬）（春，夏），（夏，秋），（秋，冬）数据的存储结构数据的存储结构 数据的逻辑结构在计算机存储空间内的存放形式数据的逻辑结构在计算机存储

23、空间内的存放形式数据的逻辑结构在计算机存储空间内的存放形式数据的逻辑结构在计算机存储空间内的存放形式20052005年年3 3月：选择题月：选择题（1 1）数据的存储结构是指）数据的存储结构是指A A）存储在外存的数据）存储在外存的数据B B）数据所占的存储空间量）数据所占的存储空间量C C）数据在计算机中的顺序存储方式）数据在计算机中的顺序存储方式D D）数据的逻辑结构在计算机中的表示）数据的逻辑结构在计算机中的表示D D数据结构的图形表示数据结构的图形表示 数据结构的图形表示数据结构的图形表示数据结构的图形表示数据结构的图形表示数据元素：数据元素：数据元素：数据元素：R R R R关系的二

24、元组：一条有向线段从前件指向后件关系的二元组：一条有向线段从前件指向后件关系的二元组：一条有向线段从前件指向后件关系的二元组：一条有向线段从前件指向后件 没有前件的结点称为没有前件的结点称为没有前件的结点称为没有前件的结点称为“根结点根结点”没有后件的结点称为没有后件的结点称为没有后件的结点称为没有后件的结点称为“叶子结点叶子结点”除了根结点和叶子结点的其它结点称为除了根结点和叶子结点的其它结点称为除了根结点和叶子结点的其它结点称为除了根结点和叶子结点的其它结点称为“内部结点内部结点”考点考点4：线性表：线性表a1a2a3an-1an线性表的逻辑结构是线性表的逻辑结构是n n个数据元素的有限序

25、列个数据元素的有限序列:(a(a1 1,a,a2 2,a,a3 3,a,an n)n n为线性表的长度为线性表的长度(n0)(n0)，n=0n=0的表称为空表的表称为空表数据元素呈线性关系数据元素呈线性关系.必存在唯一的称为必存在唯一的称为“第一个第一个”的的数据元素数据元素;必存在唯一的称为必存在唯一的称为“最后一个最后一个”的数据元素；的数据元素；除第一个元素外，每个元素都有且只有一个前驱元素；除第一个元素外，每个元素都有且只有一个前驱元素；除除最后一个元素外，每个元素都有且只有一个后继元素。最后一个元素外，每个元素都有且只有一个后继元素。所有数据元素所有数据元素a ai i在同一个线性表

26、中必须具有相同的数据类型在同一个线性表中必须具有相同的数据类型 线性表按其存储结构可分为顺序表和链表线性表按其存储结构可分为顺序表和链表。用顺序存储结构存。用顺序存储结构存储的线性表称为顺序表储的线性表称为顺序表顺序表顺序表顺序表顺序表；顺序表顺序表线性表的存储结构线性表的存储结构线性表的存储结构线性表的存储结构 线性表中所有元素所占的存储空间是线性表中所有元素所占的存储空间是线性表中所有元素所占的存储空间是线性表中所有元素所占的存储空间是“连续的连续的”线性表中各元素在存储空间中是按逻辑次序存放的线性表中各元素在存储空间中是按逻辑次序存放的线性表中各元素在存储空间中是按逻辑次序存放的线性表中

27、各元素在存储空间中是按逻辑次序存放的a1a2a3an-1an前后件存储空间是连续的，且前件元素一定前后件存储空间是连续的，且前件元素一定前后件存储空间是连续的，且前件元素一定前后件存储空间是连续的，且前件元素一定存储在后件元素前面。存储在后件元素前面。存储在后件元素前面。存储在后件元素前面。考点考点4：线性表：线性表考点考点考点考点4 4在笔试考试中，虽然说不是考试经常考查的内容，在笔试考试中，虽然说不是考试经常考查的内容，在笔试考试中，虽然说不是考试经常考查的内容，在笔试考试中，虽然说不是考试经常考查的内容，但读者还是对此考点有所了解，在笔试考试中出现的几但读者还是对此考点有所了解，在笔试考

28、试中出现的几但读者还是对此考点有所了解，在笔试考试中出现的几但读者还是对此考点有所了解，在笔试考试中出现的几率为率为率为率为30%30%。20092009年年9 9月：选择题月：选择题（1 1）下列数据结构中，属于非线性结构的是：）下列数据结构中，属于非线性结构的是：A A）循环队列）循环队列B B）带链队列）带链队列C C）二叉树）二叉树D D）带链栈）带链栈C C考点考点5：栈：栈栈栈(STACK)(STACK)也是一种特殊的线性表，是也是一种特殊的线性表，是一种一种“后进先出后进先出后进先出后进先出(LIFO(LIFO(LIFO(LIFO)”的结构，它的的结构，它的运算规则受到一些约束和

29、限定，故又称运算规则受到一些约束和限定，故又称限定性数据结构限定性数据结构栈是限定仅在表尾进行插入和删除运算的线栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为性表，表尾称为栈顶栈顶栈顶栈顶(top)(top)，表头称为表头称为栈底栈底栈底栈底(bottom)(bottom)栈的物理存储可以用顺序存储结构，也可以栈的物理存储可以用顺序存储结构，也可以用链式存储结构用链式存储结构l栈的结构特点栈的结构特点栈的结构特点栈的结构特点anan-1.6a1a2a0LIFO-Last In First Out栈顶栈顶栈底栈底进栈出栈考点考点5：栈：栈考点考点考点考点5 5在笔试考试中，是一个必考的内容

30、，在笔试考试在笔试考试中，是一个必考的内容，在笔试考试在笔试考试中，是一个必考的内容，在笔试考试在笔试考试中，是一个必考的内容，在笔试考试中出现的几率为中出现的几率为中出现的几率为中出现的几率为100%100%，主要是以选择的形式出现，分，主要是以选择的形式出现，分，主要是以选择的形式出现，分，主要是以选择的形式出现，分值为值为值为值为2 2分，此考点为重点掌握内容，读者应该掌握栈的分，此考点为重点掌握内容，读者应该掌握栈的分，此考点为重点掌握内容，读者应该掌握栈的分，此考点为重点掌握内容，读者应该掌握栈的运算运算运算运算 。20052005年年3 3月：选择题月：选择题（2 2）下列关于栈的

31、描述中错误的是：）下列关于栈的描述中错误的是：A A）栈是后进先出的线性表）栈是后进先出的线性表B B）栈只能顺序存储）栈只能顺序存储C C）栈具有记忆作用）栈具有记忆作用D D）在栈的插入删除操作中，不需要改变栈底指针）在栈的插入删除操作中，不需要改变栈底指针B B20092009年年9 9月：选择题月：选择题（2 2）下列数据结构中，能够按照）下列数据结构中，能够按照“后进先出后进先出”原则存取数据的是：原则存取数据的是：A A）循环队列）循环队列B B）栈）栈C C）队列）队列D D）二叉树）二叉树B B栈的顺序存储栈的顺序存储用一位数组用一位数组用一位数组用一位数组s(1,m)s(1,

32、m)s(1,m)s(1,m)作栈的顺序存储空间作栈的顺序存储空间作栈的顺序存储空间作栈的顺序存储空间 mm是是是是“最大容量最大容量”通常栈底指针指向栈空间的低地址一端通常栈底指针指向栈空间的低地址一端通常栈底指针指向栈空间的低地址一端通常栈底指针指向栈空间的低地址一端top=0top=0top=0top=0，表示栈空，表示栈空，表示栈空，表示栈空top=mtop=mtop=mtop=m，表示栈满，表示栈满，表示栈满，表示栈满FEDCBAbottombottomS(10)S(10)10987654321toptop栈运算图示栈运算图示FEDCBAbottombottomS(10)S(10)10

33、987654321toptopYXFEDCBAbottombottomS(10)S(10)10987654321toptopXFEDCBAbottombottomS(10)S(10)10987654321toptop6 6 个元素的栈个元素的栈加入加入X X、Y Y后的栈后的栈退出一个元退出一个元素后的栈素后的栈真题实例真题实例20092009年年3 3月：选择题月：选择题（2 2）支持子程序调用结构的是）支持子程序调用结构的是A A）栈）栈B B）树）树C C）队列）队列D D）二叉树）二叉树A AB B20092009年年3 3月：填空题月：填空题（1 1）假设用一个长度为）假设用一个长度

34、为5050的数组（数组元素的下标从的数组（数组元素的下标从0 0到到4949）作为栈的存储空间，栈顶指针作为栈的存储空间，栈顶指针toptop指向栈顶元素，如果指向栈顶元素，如果bottom=49,top=30bottom=49,top=30（数组下标），则栈中共有（数组下标），则栈中共有个元素。个元素。2020考点考点6：队列：队列队列队列(Queue)(Queue)限定所有的插入只能在表的一端进行，而所有的限定所有的插入只能在表的一端进行，而所有的删除都在表的另一端进行的线性表删除都在表的另一端进行的线性表表中允许插入的一端称为队尾表中允许插入的一端称为队尾(Rear)(Rear)，允许删

35、除的一端称为队允许删除的一端称为队头头(Front)(Front)队列的操作是按先进先出的原则进行的队列的操作是按先进先出的原则进行的队列的物理存储可以用顺序存储结构，也可以用链式存储结构。队列的物理存储可以用顺序存储结构，也可以用链式存储结构。队列的结构特点队列的结构特点队列的顺序存储结构队列的顺序存储结构队列的顺序存储结构一般采用循环队列的形式队列的顺序存储结构一般采用循环队列的形式队列的顺序存储结构一般采用循环队列的形式队列的顺序存储结构一般采用循环队列的形式frontfrontQ(1:m)Q(1:m)m21rearrear 将队列存储空间的最后一个位置绕到底一个位置将队列存储空间的最后

36、一个位置绕到底一个位置将队列存储空间的最后一个位置绕到底一个位置将队列存储空间的最后一个位置绕到底一个位置存储空间的第一个位存储空间的第一个位存储空间的第一个位存储空间的第一个位置为队尾。置为队尾。置为队尾。置为队尾。队列空队列空队列空队列空s=0s=0s=0s=0队列满队列满队列满队列满front=rearfront=rearfront=rearfront=rear且且且且s=1s=1s=1s=1队列的插入删除图示队列的插入删除图示FEDCBAfrontfrontQ(1Q(1：8)8)87654321rearrearXFEDCBAYfrontfrontQ(1Q(1：8)8)87654321r

37、earrearXFEDCBYfrontfrontQ(1Q(1：8)8)87654321rearrear6 6 个元素循个元素循环队列环队列加入加入X X、Y Y后的循环队后的循环队列列退出一个元退出一个元素后的循环素后的循环队列队列真题实例真题实例20102010年年3 3月：填空题月：填空题（）设某循环队列的容量为（）设某循环队列的容量为50,50,如果头指针如果头指针front=45front=45（指向队头（指向队头元素的前一个位置），尾指针元素的前一个位置），尾指针rear=10rear=10（指向队尾元素），则该（指向队尾元素），则该循环队列中共有循环队列中共有个元素。个元素。151

38、520092009年年9 9月：选择题月：选择题（3 3）对于循环队列，下列叙述中正确的是：）对于循环队列，下列叙述中正确的是：A A）队头指针是固定不变的）队头指针是固定不变的B B）队头指针一定大于队尾指针）队头指针一定大于队尾指针C C）队头指针一定小于队尾指针）队头指针一定小于队尾指针D D）队头指针可以大于队尾指针，也可以小于队尾指针）队头指针可以大于队尾指针，也可以小于队尾指针D D线性链表线性链表 用一组任意的用一组任意的用一组任意的用一组任意的(连续或不连续连续或不连续连续或不连续连续或不连续)存储单元来存放线性表的存储单元来存放线性表的存储单元来存放线性表的存储单元来存放线性

39、表的数据元素数据元素数据元素数据元素d1d2d3dn hh h头指针 链表的一个重要特点是插入、删除运算灵活方便，不链表的一个重要特点是插入、删除运算灵活方便，不需移动结点，只要改变结点中指针域的值即可需移动结点，只要改变结点中指针域的值即可最后一个结点没有后继结点，指向最后一个结点没有后继结点，指向它的指针域为空它的指针域为空(记为记为N NULLULLULLULL 或或)。另外还需要设置一个头指针另外还需要设置一个头指针headhead，指向单链表的第指向单链表的第一个结点一个结点(称为头指针称为头指针h)h)缺点：第一个和空表单独处理缺点：第一个和空表单独处理循环链表循环链表 循环链表增

40、加了一个表头结点，其数据域为任意或根据循环链表增加了一个表头结点，其数据域为任意或根据循环链表增加了一个表头结点，其数据域为任意或根据循环链表增加了一个表头结点，其数据域为任意或根据需要设置，指针域指向第一个结点，循环链表的头指针指需要设置，指针域指向第一个结点，循环链表的头指针指需要设置，指针域指向第一个结点，循环链表的头指针指需要设置，指针域指向第一个结点，循环链表的头指针指向标头结点。向标头结点。向标头结点。向标头结点。循环链表最后一个结点的指针域指向表头结点循环链表最后一个结点的指针域指向表头结点循环链表最后一个结点的指针域指向表头结点循环链表最后一个结点的指针域指向表头结点d1d2d

41、3dn hh h表头结点表头结点表头结点表头结点优点：实现了空表与非空表的运算统一优点：实现了空表与非空表的运算统一Head=0 Head=0 Head=0 Head=0 空表空表空表空表考点考点7：队列、栈与链表：队列、栈与链表考点考点考点考点7 7在笔试考试中，队列与栈换着考，经常与链表结在笔试考试中，队列与栈换着考，经常与链表结在笔试考试中，队列与栈换着考，经常与链表结在笔试考试中，队列与栈换着考，经常与链表结合在一起，出现概率很高。合在一起，出现概率很高。合在一起，出现概率很高。合在一起，出现概率很高。20052005年年3 3月：选择题月：选择题（5 5）下列对于线性链表描述正确的是

42、：）下列对于线性链表描述正确的是：A A）存储空间不一定是连续，且各元素存储顺序是任意的）存储空间不一定是连续，且各元素存储顺序是任意的B B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面）存储空间不一定是连续，且前件元素一定存储在后件元素的前面C C）存储空间必须连续，且前件元素一定存储在后件元素的前面）存储空间必须连续，且前件元素一定存储在后件元素的前面D D）存储空间必须连续，且各元素存储顺序是任意的）存储空间必须连续，且各元素存储顺序是任意的A A20092009年年3 3月：选择题月：选择题（1 1）下列叙述中正确的是）下列叙述中正确的是A A）栈是）栈是“先进先出先进先

43、出”的线性表的线性表B B）队列是）队列是“先进后出先进后出”的线性表的线性表C C）循环队列是非线性结构）循环队列是非线性结构D D）有序线性表可以采用顺序存储结构，也可以采用链式存储结构）有序线性表可以采用顺序存储结构，也可以采用链式存储结构D D真题实例真题实例20102010年年3 3月：填空题月：填空题（1 1）一个队列初始状态为空，现将元素）一个队列初始状态为空，现将元素A,B,C,D,E,F,5,4,3,2,1A,B,C,D,E,F,5,4,3,2,1依次入队然后再依次退队，则元素退队的顺序为依次入队然后再依次退队，则元素退队的顺序为。A,B,C,D,E,F,5,4,3,2,1A

44、,B,C,D,E,F,5,4,3,2,1考点考点8：树与二叉树的基本性质：树与二叉树的基本性质考点考点考点考点8 8在笔试考试中，是一个必考的内容，在笔试考试在笔试考试中，是一个必考的内容，在笔试考试在笔试考试中，是一个必考的内容，在笔试考试在笔试考试中，是一个必考的内容，在笔试考试中出现的几率为中出现的几率为中出现的几率为中出现的几率为100%100%，主要是以选择的形式出现，有，主要是以选择的形式出现，有，主要是以选择的形式出现，有，主要是以选择的形式出现，有时也有出现在填空题中，分值为时也有出现在填空题中，分值为时也有出现在填空题中，分值为时也有出现在填空题中，分值为2 2分，此考点为重

45、点掌分，此考点为重点掌分，此考点为重点掌分，此考点为重点掌握内容。重点识记树及二叉树的性质。握内容。重点识记树及二叉树的性质。握内容。重点识记树及二叉树的性质。握内容。重点识记树及二叉树的性质。考点考点8：树与二叉树的基本性质：树与二叉树的基本性质 数据元素之间有明显的层次关系数据元素之间有明显的层次关系数据元素之间有明显的层次关系数据元素之间有明显的层次关系树树(Tree)(Tree)是由一个或多个结点组成的有限集合是由一个或多个结点组成的有限集合T T，其中有一个特定其中有一个特定的称为根的结点；其余结点可分为的称为根的结点；其余结点可分为m(m0)m(m0)个互不相交的有限集个互不相交的

46、有限集T T1 1,T,T2 2,T,T3 3,T,Tm m，每一个集合本身又是一棵树，且称为根的子树。每一个集合本身又是一棵树，且称为根的子树。树的形式化定义树的形式化定义树的形式化定义树的形式化定义：树的表示：树的表示：树的表示：树的表示：(A(B(E,F),C(G),D(H,I,J)度度度度：结点子树个数为结点的度,结点度的最大值为该树的度 森林森林森林森林：0棵或多棵不相交的树的集合称为森林森林ABCDEFGHI根结点叶子分支结点C C是G G的父结点，G G是C C的子结点，H H和I I是兄弟结点结点的度：子树个数树的度：度的最大值结点的层次：为父结点层数加1（根结点层数为1）树的

47、深度：结点最大层数森林：删去根结点典型应用：文件管理无前趋的结点无后继的结点有前趋和后继的结点结点B的度为2，层次为2，树的度为3，树的深度为4二叉树二叉树二叉树：二叉树：二叉树：二叉树：二叉树二叉树(Binary Tree)(Binary Tree)是是n(n0)n(n0)个结点的有限集，它或为空个结点的有限集，它或为空树树(n=0)(n=0)，或由一个根结点和两棵分别称为根的左子树和右子或由一个根结点和两棵分别称为根的左子树和右子树的互不相交的二叉树组成树的互不相交的二叉树组成。二叉树的逻辑结构：二叉树的逻辑结构：二叉树的逻辑结构：二叉树的逻辑结构：二叉树的结点的子树要区分左子树和右子树，

48、即使在结二叉树的结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。右子树。ABCDEFHG满二叉树满二叉树除了最后一层外，每一层上的所有结点都有两个子结点。除了最后一层外，每一层上的所有结点都有两个子结点。除了最后一层外，每一层上的所有结点都有两个子结点。除了最后一层外，每一层上的所有结点都有两个子结点。163459781021112131415深度为深度为4 4的满二叉树的满二叉树完全二叉树完全二叉树除了最后一层外，每一层上结点数都达到最大值除了最后一层外，每一层上结点数都达到最大值除了最后

49、一层外，每一层上结点数都达到最大值除了最后一层外，每一层上结点数都达到最大值16345978102深度为深度为4 4的完全二叉树的完全二叉树二叉树的基本性质二叉树的基本性质 二叉树有下面一些重要数学性质:性质一：性质一：在二叉树中，第i层的节点个数 最多为2i-1 个，i1；性质二：性质二：性质二：性质二：深度为k的二叉树的节点总数最 大为2k-1,k1。性质三：性质三：对任一棵二叉树T如果其叶子节点个数为n0,度为2的节点个数为n2,则n0=n2+1。性质四：性质四：具有n个节点的二叉树的深度至少为 log2n+1。性质五：性质五：具有n个节点的完全二叉树的深度为 log2n+1。完全二叉树

50、完全二叉树性质六：性质六：若一棵有n个节点(即深度为 log2n+1)的完全二叉树是按层序编号(从第一层到第 log2n+1层，每层从左到右)则对任一节点i（1in),我们有：如果i=1，则结点i是二叉树的根，无双亲，如果i1，则其双亲节点parent(i)是结点int(i/2)。如果2in，则其左孩子lchild(i)是2i；若2in,则i无左孩子(结点i为叶子结点)。如 果 2i+1 n，则其右孩子rchild(i)是2i+1；若2i+1n，则i无右孩子。完全二叉树完全二叉树 i-1 ii+12i2i+12i+22i+3lchild(ilchild(i)rchild(irchild(i)l