数据结构二级PPT讲义

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

2、0分8分2007年9月12分4分8分6分2008年4月10分2分8分10分2008年9月10分2分8分10分2009年3月10分2分8分10分2009年9月10分2分8分10分2010年3月10分0分10分10分第4页 算法的基算法的基本概念本概念 2.2.算法复杂算法复杂度的概念和度的概念和意义意义 数据结构的概念数据结构的概念 线性表线性表 栈和队列栈和队列 树与二叉树树与二叉树 查找技术查找技术 排序技术排序技术 对于等级考试，这个部分的考核对于等级考试，这个部分的考核重点主要重点主要在在算法和数据结构的基本概算法和数据结构的基本概念念、二叉树二叉树(遍历、结点），遍历、结点），还有还有

3、排序和查找排序和查找考试中也经常会涉及到。考试中也经常会涉及到。第5页算法的定义算法的定义算法是程序设计的核心算法是程序设计的核心 算法是在有限步骤内求解某一问题所使用的一组定义明确的算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机规则。通俗点说，就是计算机解题的过程解题的过程( (计算的方法计算的方法) )。在。在这个过程中，无论是形成解题思路这个过程中，无论是形成解题思路( (推理实现的算法推理实现的算法) )还是编还是编写程序写程序( (操作实现的算法操作实现的算法) )，都是在实施某种算法。，都是在实施某种算法。例：例： n个数从大到小进行排序。个数从大到

4、小进行排序。 有多种排序方法有多种排序方法 ，常用的有冒泡排序、选择排序等。，常用的有冒泡排序、选择排序等。讲课讲课说课说课第6页 2 . 算法的基本特征算法的基本特征一个算法应该具有以下五个重要的特征：一个算法应该具有以下五个重要的特征：n 有穷性有穷性n 确定性确定性n 输入输入n 输出输出n 可行性可行性一个算法必须保证执行有限步之后结束；算法的每一步骤必须有确切的定义；一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；算法原则上能够精确地运行，而且人们用笔和纸做

5、有限次运算后即可完成 拥有足够的情报拥有足够的情报第7页u 算法与计算机程序算法与计算机程序 算法算法_是一组逻辑步骤是一组逻辑步骤 程序程序用计算机语言描述的算法用计算机语言描述的算法INPUT rS=3.14 * r*rPTINT S开始开始输入输入R RS=3.14 * R*R输出输出S S结束结束问题：输入园的半径，计算园的面积 一个算法的表示需要使用一些语言形式。一个算法的表示需要使用一些语言形式。传统的算法传统的算法-图形法，如图形法，如“流程图流程图”和和N-S图图目前常用的方法目前常用的方法-使用伪码描述算法。使用伪码描述算法。第8页冒泡排序的方法：冒泡排序的方法：1.1.扫描

6、整个线性表，逐次对相扫描整个线性表，逐次对相邻的两个元素进行比较，若为邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的逆序，则交换；第一趟扫描的结果使最大的元素排到表的最结果使最大的元素排到表的最后后 ；2.2.除最后一个元素，对剩余的除最后一个元素，对剩余的元素重复上述过程，将次大的元素重复上述过程，将次大的数排到表的倒数第二个位置；数排到表的倒数第二个位置；3.3.重复上述过程；重复上述过程；对于长度为对于长度为n n的线性表，冒泡排的线性表，冒泡排序需要对表扫描序需要对表扫描n-1n-1遍。遍。 算法举例：算法举例：n个数排序个数排序第9页4. 算法的两个基本要素：算法的两个基本要素

7、：n 算术运算算术运算n 关系运算关系运算n 逻辑运算逻辑运算n 数据传输数据传输n 顺序顺序n 选择选择n 循环循环u一是对数据对象的运算和操作；u二是算法的控制结构。u算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法 第10页 评价一个算法优劣的主要标准是算法的执行效率和存储需求：评价一个算法优劣的主要标准是算法的执行效率和存储需求：n 时间复杂度：执行这个算法所需要的时间复杂度：执行这个算法所需要的计算工作量计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量n 空间复杂度：执行这个算

8、法所需要的空间复杂度：执行这个算法所需要的内存空间内存空间 算法在执行过程中临时占用的存储空间算法在执行过程中临时占用的存储空间 时间复杂度时间复杂度它大致等于计算机它大致等于计算机执行一种简单操作所需的平均时间执行一种简单操作所需的平均时间与算法与算法中进行中进行简单操作的次数的乘积简单操作的次数的乘积。 一个算法在计算机存储器上所占用的存储空间，包括一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用存储算法本身所占用的存储空间的存储空间、算法中的输入输出数据所占用的存储空间算法中的输入输出数据所占用的存储空间和和算法在运行过程中算法在运行过程中临时占用的存储空间临时占用的存储

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

10、法的时间复杂度与空间复杂度一定相关(3)算法的有穷性是指算法的有穷性是指 (08年年4月月)A）算法程序的运行时间是有限的）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的）算法程序所处理的数据量是有限的 C）算法程序的长度是有限的）算法程序的长度是有限的 D）算法只能被有限的用户使用）算法只能被有限的用户使用(c)(B)算法习题:(A)第12页(4) 算法的时问复杂度是指算法的时问复杂度是指 (2010年年3月月)A)算法的执行时间算法的执行时间B)算法所处理的数据量算法所处理的数据量C)算法程序中的语句或指令条数算法程序中的语句或指令条数D)算法在执行过程中所需要的基本运算次

11、数算法在执行过程中所需要的基本运算次数(5) 算法的空间复杂度是指算法的空间复杂度是指 (09年年9月月) A）算法在执行过程中所需要的计算机存储空间）算法在执行过程中所需要的计算机存储空间B）算法所处理的数据量）算法所处理的数据量C）算法程序中的语句或指令条数）算法程序中的语句或指令条数D）算法在执行过程中所需要的临时工作单元数）算法在执行过程中所需要的临时工作单元数(6) 下列叙述中正确的是下列叙述中正确的是 (06年年9月月)A）一个算法的空间复杂度大，则其时间复杂度也必定大）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小）一个算法的空间复

12、杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间复杂度必定小）一个算法的时间复杂度大，则其空间复杂度必定小 D）上述三种说法都不对）上述三种说法都不对(D)计算工作量(A)(D)u 算法的时间复杂度是指算法的时间复杂度是指A) 执行算法程序所需要的时间执行算法程序所需要的时间 B) 算法程序的长度算法程序的长度C) 算法执行过程中所需要的基本运算次数算法执行过程中所需要的基本运算次数 D) 算法程序中的指令条数算法程序中的指令条数u 算法的基本特征是可行性、确定性、算法的基本特征是可行性、确定性、 【1】 和拥有足够的情报。和拥有足够的情报。u 算法的空间复杂度是指算法的空间复

13、杂度是指 A) 算法程序的长度算法程序的长度 B) 算法程序中的指令条数算法程序中的指令条数 C) 算法程序所占的存储空间算法程序所占的存储空间 D) 执行过程中所需要的存储空间执行过程中所需要的存储空间u 在计算机中，算法是指在计算机中，算法是指 A) 加工方法加工方法B) 解题方案的准确而完整的描述解题方案的准确而完整的描述 C) 排序方法排序方法D) 查询方法查询方法例题讲解例题讲解有穷性有穷性u算法分析的目的是算法分析的目的是 A) 找出数据结构的合理性找出数据结构的合理性 B) 找出算法中输入和输找出算法中输入和输出之间的关系出之间的关系 C) 分析算法的易懂性和可靠性分析算法的易懂

14、性和可靠性 D) 分析算法的效率分析算法的效率以求改进以求改进u算法的工作量大小和实现算法所需的存储单元多少算法的工作量大小和实现算法所需的存储单元多少分别称为算法的分别称为算法的 【1】 。时间复杂度和空间复杂度时间复杂度和空间复杂度第15页 计算机在进行数据处理时，实际需要处理的数据元素一般有计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的的数据元素在计算机中如何组织，以便提高数据处理的效率，并且数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空

15、间，节省计算机的存储空间，这是进行数据处理的关键问题。这是进行数据处理的关键问题。程序程序=算法算法+数据结构数据结构数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。 一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。一般情况下，在具有相同特征的数据元素集合中，各个数据一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。合中的数据元素所固有的一种结构。超市的物

16、品如何超市的物品如何存放才好找且节存放才好找且节省空间呢？省空间呢？第16页二二. 数据结构数据结构数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。数据结构是研究数据和数据之间关系的一门学科，它数据结构是研究数据和数据之间关系的一门学科，它包括三个方面。包括三个方面。（1）数据集合中各数据元素之间所固有的逻辑关系，）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；的存储关系，即数据的存储结构；（3）对各种数据结构进行

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

18、=(父亲，儿子父亲，儿子) ,(父亲，女儿父亲，女儿)春夏秋冬数据结构的图形表示数据结构的图形表示父亲儿子女儿第18页u常见的常见的逻辑结构逻辑结构有：有：线性结构、树形结构和图形结构。线性结构、树形结构和图形结构。线性结构线性结构树形结构树形结构图形结构图形结构u 线性结构线性结构 结构中的每个元素之间存在一个对一个的关系；结构中的每个元素之间存在一个对一个的关系；u 树形结构树形结构 结构中的每个元素之间存在一个对多个的关系；结构中的每个元素之间存在一个对多个的关系；u 图形结构或网状结构图形结构或网状结构 结构中的每个元素之间存在多个对多个的关系。结构中的每个元素之间存在多个对多个的关系

19、。其中，其中，树形结构和图形结构统称为非线形结构树形结构和图形结构统称为非线形结构。数据的逻辑结构可以。数据的逻辑结构可以用二元关系表示，也可以直观地用图形来表示。用二元关系表示，也可以直观地用图形来表示。第19页u 2. 存储结构（物理结构存储结构（物理结构） 计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。它们的逻辑关系不一定是相同的，而且一般也不可

20、能相同。如：如：一年四季 家庭成员 计算机存储空间怎样存放？ 存储结构指数据结构在计算机存储空间中的具体实现。存储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有：常见的存储结构有：n 顺序存储结构顺序存储结构n 链式存储结构链式存储结构n 索引存储结构索引存储结构只抽象地反映数据元素之间的关系的结构，只抽象地反映数据元素之间的关系的结构，而不管其存储方式的数据结构称为逻辑结而不管其存储方式的数据结构称为逻辑结构。构。一种一种数据结构可以根据需要表示成一种或数据结构可以根据需要表示成一种或多种存储结构多种存储结构。第20页u 3. 数据的运算数据的运算n 检索检索n 插入插入n 删

21、除删除n 更新更新n 排序排序 通常，一个数据结构中的元素结点可能是动态变化的。根据需要通常，一个数据结构中的元素结点可能是动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结点（插入运或在处理过程中，可以在一个数据结构中增加一个新结点（插入运算），也可以删除某个结点（删除运算），除此之外，对数据结构算），也可以删除某个结点（删除运算），除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改。的运算还有查找、分类、合并、分解、复制和修改。 在对数据结构的处理过程中，不仅数据结构中结点的个数在动态在对数据结构的处理过程中，不仅数据结构中结点的个数在动态变化，而且，各数据

22、元素之间的关系也有可能在动态地变化。变化，而且，各数据元素之间的关系也有可能在动态地变化。如：无序表变有序表数据结构是研究数据和数据之数据结构是研究数据和数据之间关系的一门学科，研究以下三间关系的一门学科，研究以下三方面内容：方面内容：n 数据的逻辑结构数据的逻辑结构n 数据的存储结构数据的存储结构n 数据的运算数据的运算父亲儿子女儿第第21 21|92|92页页常见的数据结构常见的数据结构u 数据结构分类数据结构分类 线性结构与非线性结构线性结构与非线性结构两大类型线性结构：一个非空的数据结构若满足下面的两个条件，则一个非空的数据结构若满足下面的两个条件，则这种数据结构即为这种数据结构即为。

23、 有且仅有一个根结点；有且仅有一个根结点； 除第一个结点外，每一个结点最多有一个前件；除第一个结点外，每一个结点最多有一个前件； 除最后一个结点外，每一个结点最多有一个后件。除最后一个结点外，每一个结点最多有一个后件。常见的线性结构有：常见的线性结构有：第第2222|92|92页页a1a2a5a3a4HEAD319510线性链表的逻辑状态线性链表的逻辑状态常见的非线性结构有树、常见的非线性结构有树、非线性结构一个数据结构不是线性结构。一个数据结构不是线性结构。第23页 线性表是由线性表是由n（n0）个数据元素）个数据元素 a1，a2，ai，an组成的一个有限序列。组成的一个有限序列。春春夏夏秋

24、秋冬冬记录记录1 02011001 张三张三 男男记录记录2 02011003 李四李四 女女 记录记录3记录记录4第24页特点：特点： 顺序存储结构把顺序存储结构把逻辑上相逻辑上相邻邻的数据元素存储在的数据元素存储在物理上相邻物理上相邻的存储单元里，顺序存储结构的存储单元里，顺序存储结构只只存储结点的值存储结点的值，不存储结点间的，不存储结点间的关系，结点间的关系由存储单元关系，结点间的关系由存储单元的邻接关系来体现。的邻接关系来体现。a1a2aian存储地址存储地址200020042000+4*(i-1)2000+4*(n-1)占占4个字节个字节第i个数的地址第一个数的地址L为该类型数所占

25、的字节线性表的存储结构有两种：线性表的存储结构有两种：u 顺序存储结构顺序存储结构u 链式存储结构链式存储结构第25页u 顺序表的插入运算顺序表的插入运算u 顺序表的删除运算顺序表的删除运算 在线性表顺序存储情况下，要插入或删除一个元在线性表顺序存储情况下，要插入或删除一个元素，都会由于数据元素的移动而消耗大量的处理时间，素，都会由于数据元素的移动而消耗大量的处理时间，所以这种存储方式对于小线性表或其中数据元素不经所以这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的。常变动的线性表是合适的。线性表的顺序存储结构称为顺序表。线性表的顺序存储结构称为顺序表。第26页插入运算插入运算

26、ai-1.a2a1alengthai+1ai xai-1.a2a1alengthai+1ai X 插入算法的分析插入算法的分析: : 假设线性表中含有假设线性表中含有n n个数据元素，在进行插入操作时，若假个数据元素，在进行插入操作时，若假定在定在n+1n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：个位置上插入元素的可能性均等，则平均移动元素的个数为：1n1iis2n1)i(n1n1E第27页 删除运算删除运算ai-1.a2a1alengthai+1aiai-1.a2a1alengthai+1删除算法的分析删除算法的分析: : 在进行删除操作时，若假定删除每个元素的可能性均等，则

27、在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：平均移动元素的个数为：总结总结: : 顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。插入或删除操作时，这一点需要值得考虑。n1idl21ni)(nn1E第28页u 线性表的链式存储结构称为线性链表。线性表的链式存储结构称为线性链表。u 链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，

28、链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且各数据元素的存储顺序也是任意的。各数据元素的先后而且各数据元素的存储顺序也是任意的。各数据元素的先后关系是由各结点的指针域指示。关系是由各结点的指针域指示。u 链式存储结构的每一个存储结点不仅存储结点的值，而且存链式存储结构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系：储结点之间的关系：u 链式存储结构分为单链表、双向链表、循环链表链式存储结构分为单链表、双向链表、循环链表u 线性链表不能随机存取线性链表不能随机存取数据域数据域指针域指针域第29页设线性表为设线性表为（a1，a2，a3，a4，a5）1a2923a1145a4

29、106789a3510a50HEAD3a1a2a5a3a4HEAD319510线性链表的逻辑状态线性链表的逻辑状态线性链表线性链表的物理状态的物理状态1 a12 a23 a34 a45 a567注意:1 2 3 此类编号不代表所在的地址单元的地址编码线性表的链式存储结构线性表的链式存储结构及其插入与删除操作及其插入与删除操作第30页zhaoqiansunlizhouwuzhengwang /H存储地址存储地址数据数据17131925313743liqiansunwangwuzhaozhengzhou指针指针43131null377192531头指针头指针单链表单链表第31页单链表的插入运算单链

30、表的插入运算在在P所指向的结点之后插入所指向的结点之后插入新的结点新的结点单链表单链表删除运算删除运算PbaxSbaPLaaian ai-1ai+1要求要求:删除结点删除结点ai。第32页循环链表循环链表: 首尾相接的链表。首尾相接的链表。 将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点它结点。a1a2ana3L.带头结点的单链表带头结点的单链表a1a2ana3L.循环单链表循环单链表特点特点: 可以从任何一个结点开始访问链表的所有结点可以从任何一个结点开始访问链表的所有结点.第33页双向链表的存储结构双向链表

31、的存储结构 在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的前驱和后继结点。可提高效率。确定一个结点的前驱和后继结点。可提高效率。HEAD31510 a2 a3 a4 a1提问：单向链表的缺点是什么？ 提示：如何寻找结点的直接前趋。 双向链表可以克服单链表的单向性的缺点。 在双向链表的结点中有两个指针域，其一指向直接后继，另一在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。指向直接前趋。 双向循环链表双向循环链表 第34页u 线性表的应用：应用最广的数据结构。线性表的应用：应用最广的数据结

32、构。u .高级语言中的数组；高级语言中的数组；u 计算机的文件系统；计算机的文件系统；u 计算机的目录系统；计算机的目录系统；u 电话号码查询系统（可采用顺序表或单链表结电话号码查询系统（可采用顺序表或单链表结构构）；）；u 各种事务处理（各种事务处理（可采用顺序表或单链表结构可采用顺序表或单链表结构）;第35页栈和队列栈和队列是两种特殊的线性表，它们是运算时是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为要受到某些限制的线性表，故也称为限定性限定性的数据结构的数据结构。第36页1 .栈栈栈栈是限定仅在表尾进行插入或删除操作的线性表。是限定仅在表尾进行插入或删除操作的线性表。栈

33、顶栈顶表尾。表尾。栈底栈底表头。表头。空栈空栈不含元素的空表。不含元素的空表。a1a2an栈底栈底栈顶栈顶进栈进栈出栈出栈栈栈s=(a1,a2,an)后进先出或先后进先出或先进后出（进后出（LIFO）第37页u栈的物理存储结构可以用顺序结构，也可以用链表栈的物理存储结构可以用顺序结构，也可以用链表结构。结构。u下面讨论顺序存储结构中栈元素的插入和删除运算。下面讨论顺序存储结构中栈元素的插入和删除运算。n 顺序栈的进栈和出栈运算顺序栈的进栈和出栈运算 n栈的基本运算有三种：入栈、退栈和读栈顶元素栈的基本运算有三种：入栈、退栈和读栈顶元素 在顺序栈中插入和删除运算不需要在顺序栈中插入和删除运算不需

34、要移动表中其他数据元素移动表中其他数据元素。第38页2. 栈的顺序存储结构及其基本运算栈的顺序存储结构及其基本运算 a2 a1 a1 a2 top 用顺序存储结构表示的栈用顺序存储结构表示的栈: 顺序栈用一组连续的存储单元存放自栈底到栈顶的顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量数据元素，一般用一维数组表示，设置一个简单变量top指示指示栈顶位置，栈顶位置，称为称为针栈顶指针栈顶指，它始终指向待插入元素的位置。它始终指向待插入元素的位置。基本运算：基本运算：压（进）栈：压（进）栈：PUSH出栈：出栈：POP读栈顶元素：读栈顶元素：gettop第

35、39页例子：例子：topbaseEDCBAtopbaseCBAbasetopAbasetop空桟：空桟：topbase非空桟：非空桟：top始终在桟顶元素的后一个位置始终在桟顶元素的后一个位置桟的元素个数：桟的元素个数：top-base上溢上溢下溢下溢第40页2 2、队列、队列定义：一种特殊的线性结构，限定只能在表的一端进行插入，定义：一种特殊的线性结构，限定只能在表的一端进行插入，在在 表的另一端进行删除的线性表表的另一端进行删除的线性表 。此种结构称为先进先出。此种结构称为先进先出（FIFO）表。）表。 a1 , a2 , a3 , a4 , an-1 , an 队队 列列 示示 意意 图

36、图队头队头队尾队尾先进先出先进先出后进后出后进后出（LIFO）第41页 e3 e4 (c)(c) e1,e2出队，出队，e4入队入队 队队 满满rear =3front e1 e2 e3 (b)rearfront(b)e1,e2,e3入队入队队列的顺序存储结构及其基本运算队列的顺序存储结构及其基本运算 3 2 1 0 (a)rear=front=-1(队空）队空）rearfront空队列空队列:非空队列非空队列:队列元素个数队列元素个数:rear=front=-1front始终指向队头元素前一个位置，而始终指向队头元素前一个位置，而rear始终指向队始终指向队尾元素的位置尾元素的位置rear-

37、front第42页 队列的物理存储结构可以用顺序结构，也可以用链式结队列的物理存储结构可以用顺序结构，也可以用链式结构。构。u 顺序队列的运算顺序队列的运算 栈有三种操作：栈有三种操作： 入栈出栈读栈顶元素入栈出栈读栈顶元素队列有三种操作：入队出队读队首元素队列有三种操作：入队出队读队首元素例：有入栈元素序列：例：有入栈元素序列：ABCD，求可能的出栈序列，求可能的出栈序列如是队列又是什么情况呢？如是队列又是什么情况呢？第43页 把队列的存储空间在逻辑上看作一个环，当把队列的存储空间在逻辑上看作一个环，当R指向存指向存储空间的末端后，就把它重新置于始端。储空间的末端后，就把它重新置于始端。u

38、循环队列的运算循环队列的运算队列中进行插入的一端称做队尾队列中进行插入的一端称做队尾(rear),进行删除的一端进行删除的一端称做队首称做队首(front)。 习题：数据结构分为逻辑结构和存储结构，循环队习题：数据结构分为逻辑结构和存储结构，循环队列属于列属于【 】结构。（结构。（2005年年9月）月）答案：存储结构。答案：存储结构。第44页frontrearMaxsize-101 e3 e4 rear =3front第45页0012345frontABCDEFrear上溢上溢0012345frontrear下溢下溢front=rear队满队满front=rear队空队空第46页数据存储结构方

39、面的考题数据存储结构方面的考题 1：数据的存储结构是指：数据的存储结构是指 （2005年年4月）月）A) 存储在外存中的数据存储在外存中的数据 B) 数据所占的存储空间量数据所占的存储空间量C) 数据在计算机中的顺序存储方式数据在计算机中的顺序存储方式 D) 数据的逻辑结构在计算机中的表示数据的逻辑结构在计算机中的表示2. 下列叙述中正确的是下列叙述中正确的是 （2009年年3月）月） A）栈是）栈是“先进先出先进先出”的线性表的线性表 B）队列是）队列是“先进后出先进后出”的线性表的线性表 C）循环队列是非线性结构）循环队列是非线性结构 D）有序线性表既可以采用顺序存储结构，也可以采用链式存

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

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

42、在栈底插入数据 D 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第48页9. 设某循环队列的容量为设某循环队列的容量为50，如果头指针，如果头指针front=45(指向指向队头元素的前一位置队头元素的前一位置)，尾指针，尾指针rear=10(指向队尾元素指向队尾元素)，则该循环队列中共有则该循环队列

43、中共有 【2】 个元素。个元素。 （2010年年3月）月） 8。假设用一个长度为。假设用一个长度为50的数组（数组元索的下标从的数组（数组元索的下标从0到到49）作为栈的存储空间，栈底指针）作为栈的存储空间，栈底指针bottom指间栈底指间栈底元素，栈顶指针元素，栈顶指针top指向栈顶元素，如果指向栈顶元素，如果bottom=49，top=30（数组下标），则栈中具有（数组下标），则栈中具有【 】个元素。个元素。 （2009年年3月）月） 答案：答案：19答案：答案：154650110u链表不具有的特点是链表不具有的特点是A) 不必事先估计存储空间不必事先估计存储空间 B) 可随机访问任一元素

44、可随机访问任一元素C) 插入删除不需要移动元素插入删除不需要移动元素D) 所需空间与线性表长度成正比所需空间与线性表长度成正比u数据结构分为逻辑结构与存储结构，线性链表属于数据结构分为逻辑结构与存储结构，线性链表属于 【1】 。 u数据结构中，与所使用的计算机无关的是数据的数据结构中，与所使用的计算机无关的是数据的 A) 存储结构存储结构B) 物理结构物理结构 C) 逻辑结构逻辑结构D) 物理和存储结构物理和存储结构 u数据的逻辑结构有线性结构和数据的逻辑结构有线性结构和 【1】 两大类。两大类。u数据的存储结构是指数据的存储结构是指A）数据所占的存储空间）数据所占的存储空间B）数据的逻辑结构

45、在计算机中的表示）数据的逻辑结构在计算机中的表示C）数据在计算机中的顺序存储方式）数据在计算机中的顺序存储方式D）存储在外存中的数据）存储在外存中的数据 例题讲解例题讲解存储结构存储结构 非线性结构非线性结构u 顺序存储方法是把逻辑上相邻的结点存储在物理位置顺序存储方法是把逻辑上相邻的结点存储在物理位置 【2】 的存储单元的存储单元中。中。 u 数据处理的最小单位是数据处理的最小单位是 A) 数据数据 B) 数据元素数据元素 C) 数据项数据项D) 数据结构数据结构u 数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据

46、结构进行的运算，以及据结构进行的运算，以及 A) 数据的存储结构数据的存储结构 B) 计算方法计算方法 C) 数据映象数据映象 D) 逻辑存储逻辑存储u 线性表的顺序存储结构和线性表的链式存储结构分别是线性表的顺序存储结构和线性表的链式存储结构分别是 A) 顺序存取的存储结构、顺序存取的存储结构顺序存取的存储结构、顺序存取的存储结构 B) 随机存取的存储结构、顺序存取的存储结构随机存取的存储结构、顺序存取的存储结构 C) 随机存取的存储结构、随机存取的存储结构随机存取的存储结构、随机存取的存储结构 D) 任意存取的存储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构 相邻相邻u

47、根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成构分成 A) 动态结构和静态结构动态结构和静态结构 B) 紧凑结构和非紧凑结构紧凑结构和非紧凑结构 C) 线性结构和非线性结构线性结构和非线性结构 D) 内部结构和外部结构内部结构和外部结构 u 数据结构包括数据的逻辑结构、数据的数据结构包括数据的逻辑结构、数据的 【2】 以及对数据的操作运算。以及对数据的操作运算。u 数据的基本单位是数据的基本单位是 【5】 。u 下列叙述中，错误的是下列叙述中，错误的是 A) 数据的存储结构与数据处理的效率密切相关数据的存储结构

48、与数据处理的效率密切相关 B) 数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关 C) 数据的存储结构在计算机中所占的空间不一定是连续的数据的存储结构在计算机中所占的空间不一定是连续的 D) 一种数据的逻辑结构可以有多种存储结构一种数据的逻辑结构可以有多种存储结构存储结构存储结构数据元素数据元素u链表不具有的特点是链表不具有的特点是A) 不必事先估计存储空间不必事先估计存储空间 B) 可随机访问任一元素可随机访问任一元素C) 插入删除不需要移动元素插入删除不需要移动元素D) 所需空间与线性表长度成正比所需空间与线性表长度成正比u顺序存储方法是把逻辑上相邻的结点存储在物理位置

49、顺序存储方法是把逻辑上相邻的结点存储在物理位置 【2】 的存储单元的存储单元中。中。u长度为长度为n的顺序存储线性表中，当在任何位置上插入一个元素概率都相的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为等时，插入一个元素所需移动元素的平均个数为 【1】 。u线性表若采用顺序存储结构时，要求内存中可用存储单元的地址线性表若采用顺序存储结构时，要求内存中可用存储单元的地址 A) 必须是连续的必须是连续的 B) 部分地址必须是连续的部分地址必须是连续的 C) 一定是不连续的一定是不连续的 D) 连续不连续都可以连续不连续都可以例题讲解例题讲解相邻相邻2

50、nu 线性表线性表L=(a1,a2,a3,ai，an)，下列说法正确的是，下列说法正确的是 A) 每个元素都有一个直接前件和直接后件每个元素都有一个直接前件和直接后件 B) 线性表中至少要有一个元素线性表中至少要有一个元素 C) 表中诸元素的排列顺序必须是由小到大或由大到小表中诸元素的排列顺序必须是由小到大或由大到小 D) 除第一个元素和最后一个元素外，其余每个元素都有一个除第一个元素和最后一个元素外，其余每个元素都有一个 且只有一个直且只有一个直接前件和直接后件接前件和直接后件u 线性表的顺序存储结构和线性表的链式存储结构分别是线性表的顺序存储结构和线性表的链式存储结构分别是 A) 顺序存取

51、的存储结构、顺序存取的存储结构顺序存取的存储结构、顺序存取的存储结构 B) 随机存取的存储结构、顺序存取的存储结构随机存取的存储结构、顺序存取的存储结构 C) 随机存取的存储结构、随机存取的存储结构随机存取的存储结构、随机存取的存储结构 D) 任意存取的存储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构 u 下列叙述中，错误的是下列叙述中，错误的是 A) 数据的存储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率密切相关 B) 数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关 C) 数据的存储结构在计算机中所占的空间不一定是连续的数据的存储结构在计

52、算机中所占的空间不一定是连续的 D) 一种数据的逻辑结构可以有多种存储结构一种数据的逻辑结构可以有多种存储结构 u 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成据结构分成 A) 动态结构和静态结构动态结构和静态结构 B) 紧凑结构和非紧凑结构紧凑结构和非紧凑结构 C) 线性结构和非线性结构线性结构和非线性结构 D) 内部结构和外部结构内部结构和外部结构u 当线性表采用顺序存储结构实现存储时，其主要特点是当线性表采用顺序存储结构实现存储时，其主要特点是 【1】 。随机存取随机存取u链表不具有的特点是链表不具有的特点

53、是A) 不必事先估计存储空间不必事先估计存储空间 B) 可随机访问任一元素可随机访问任一元素C) 插入删除不需要移动元素插入删除不需要移动元素D) 所需空间与线性表长度成正比所需空间与线性表长度成正比u用链表表示线性表的优点是用链表表示线性表的优点是A) 便于随机存取便于随机存取 B) 花费的存储空间较顺序存储少花费的存储空间较顺序存储少C) 便于插入和删除操作便于插入和删除操作 D) 数据元素的物理顺序与逻辑顺序相同数据元素的物理顺序与逻辑顺序相同u长度为长度为n的顺序存储线性表中的顺序存储线性表中,当在任何位置上插入一个元素概率都相等时当在任何位置上插入一个元素概率都相等时,插入一个元素所

54、需移动元素的平均个数为插入一个元素所需移动元素的平均个数为 【1】 。u在单链表中，增加头结点的目的是在单链表中，增加头结点的目的是 A) 方便运算的实现方便运算的实现 B) 使单链表至少有一个结点使单链表至少有一个结点 C) 标识表结点中首结点的位置标识表结点中首结点的位置 D) 说明单链表是线性表的链式存储实现说明单链表是线性表的链式存储实现例题讲解例题讲解2nu 非空的循环单链表非空的循环单链表head的尾结点的尾结点(由由p所指向所指向) ，满足，满足 A) p-next=NULLB) p=NULL C) p-next=head D) p=head u 循环链表的主要优点是循环链表的主

55、要优点是 A) 不再需要头指针了不再需要头指针了 B) 从表中任一结点出发都能访问到整个链表从表中任一结点出发都能访问到整个链表 C) 在进行插入、删除运算时，能更好的保证链表不断开在进行插入、删除运算时，能更好的保证链表不断开 D) 已知某个结点的位置后，能够容易的找到它的直接前件已知某个结点的位置后，能够容易的找到它的直接前件u 当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为不能进行入队运算。这种情况称为 【2】 。u 用链表表示线性表的突出优点是用链表表示线性表的突出优点是 【1】 。上溢

56、上溢插入、删除灵活插入、删除灵活u栈和队列的共同特点是栈和队列的共同特点是 A)都是先进先出都是先进先出 B) 都是先进后出都是先进后出 C) 只允许在端点处插入和删除元素只允许在端点处插入和删除元素 D) 没有共同点没有共同点u如果进栈序列为如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是，则可能的出栈序列是 A) e3,e1,e4,e2 B) e2,e4,e3,e1 C) e3,e4,e1,e2D) 任意顺序任意顺序u一些重要的程序语言一些重要的程序语言(如如C语言和语言和Pascal语言语言) 允许过程的递归调用允许过程的递归调用。而实现递归调用中的存储分配通常用。而实现递归调用

57、中的存储分配通常用 A) 栈栈B) 堆堆 C) 数组数组 D) 链表链表例题讲解例题讲解u 栈底至栈顶依次存放元素栈底至栈顶依次存放元素A、B、C、D，在第五个元素，在第五个元素E入栈前，栈中元素入栈前，栈中元素可以出栈，则出栈序列可能是可以出栈，则出栈序列可能是 A) ABCED B) DCBEA C) DBCEA D) CDABE u 栈通常采用的两种存储结构是栈通常采用的两种存储结构是 A) 线性存储结构和链表存储结构线性存储结构和链表存储结构B) 散列方式和索引方式散列方式和索引方式 C) 链表存储结构和数组链表存储结构和数组 D) 线性存储结构和非线性存储结构线性存储结构和非线性存储

58、结构u 栈和队列通常采用的存储结构是栈和队列通常采用的存储结构是 【1】 。u 下列数据结构中，按先进后出原则组织数据的是下列数据结构中，按先进后出原则组织数据的是 A) 线性链表线性链表 B) 栈栈 C) 循环链表循环链表 D) 顺序表顺序表当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为入队运算。这种情况称为 【2】 。链表存储结构和数组链表存储结构和数组上溢上溢u 由两个栈共享一个存储空间的好处是由两个栈共享一个存储空间的好处是A) 减少存取时间，降低下溢发生的机率减少存取时间，降低

59、下溢发生的机率 B) 节省存储空间，降低上溢发生的机率节省存储空间，降低上溢发生的机率C) 减少存取时间，降低上溢发生的机率减少存取时间，降低上溢发生的机率 D) 节省存储空间，降低下溢发生的机率节省存储空间，降低下溢发生的机率u 下列关于栈的叙述中正确的是下列关于栈的叙述中正确的是）在栈中只能插入数据）在栈中只能插入数据 B）在栈中只能删除数据）在栈中只能删除数据C）栈是先进先出的线性表）栈是先进先出的线性表 D）栈是后进先出的线性表）栈是后进先出的线性表u 下列关于队列的叙述中正确的是下列关于队列的叙述中正确的是）在队列中只能插入数据）在队列中只能插入数据 B）在队列中只能删除数据）在队列

60、中只能删除数据C）队列是先进先出的线性表）队列是先进先出的线性表 D）队列是后进先出的线性表）队列是后进先出的线性表第60页树型结构是一种重要的非线性结构。树型结构是一种重要的非线性结构。u 树的概念树的概念u 二叉树的概念二叉树的概念u 二叉树的存储二叉树的存储u 二叉树的遍历二叉树的遍历第61页u 树的定义：是一种简单的非线性结构。树的定义：是一种简单的非线性结构。 n个结点的有限个结点的有限集。（集。（n=0） ABDFECGHIJKM没有前件的结点只没有前件的结点只有一个称为根结点。有一个称为根结点。 简称树简称树的根。的根。无结点则称为空树；无结点则称为空树；n 结点的前件称该结结点