第二章数据结构与算法精选PPT.ppt

《第二章数据结构与算法精选PPT.ppt》由会员分享，可在线阅读，更多相关《第二章数据结构与算法精选PPT.ppt（111页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章数据结构与算第二章数据结构与算法法第1页，本讲稿共111页2考试方式考试方式v1、考试形式、考试形式v无纸化考试全部采用上机考试的方式进行考试，取消原来的纸质试卷。考生只参加一次考试，合格即可拿到证书。无纸化考试因为不需要再分笔试和机试，因此不再有补考。考生若未能通过考试，则下次必须全部重考。从整体上来说，无纸化考试相对于传统考试，难度有所降低。第2页，本讲稿共111页考试方式考试方式v2、考试题型、考试题型v全国计算机等级考试二级无纸化考试中，共有4个大题。第一个大题为单项选择题；其余三个大题为上机操作题。单选题为四选一或三选一，共40分，考40个小题。v二级考试各科上机操作题均考3个

2、大题，共60分。3第3页，本讲稿共111页4考试内容：第一章考试内容：第一章1.数据库的基本概念：数据库，数据库管理系统，数据库系统。2.数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。3.关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。4.数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。第4页，本讲稿共111页5考试内容：第二章考试内容：第二章1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3.线性表的定义；线性表的顺序

3、存储结构及其插入与删除运算。4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5.线性单链表、双向链表与循环链表的结构及其基本运算。6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。第5页，本讲稿共111页6考试内容：第三章考试内容：第三章1.程序设计方法与风格。2.结构化程序设计。3.面向对象的程序设计方法，对象，方法，属性及继承与多态性。第6页，本讲稿共111页7考试内容：第四章考试内容：第四章1.软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。2.结构化分析方法，数

4、据流图，数据字典，软件需求规格说明书。3.结构化设计方法，总体设计与详细设计。4.软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。5.程序的调试，静态调试与动态调试。第7页，本讲稿共111页8学习方法学习方法v基本概念要理解v理解的基础上适当记忆一些概念v多做练习，从练习中总结v与所学的知识结合起来，以增加对知识的理解能力第8页，本讲稿共111页第二章第二章数据结构与算法数据结构与算法9第9页，本讲稿共111页本章主要内容本章主要内容v算法算法算法算法v数据结构数据结构数据结构数据结构 数据结构研究的主要内容数据结构研究的主要内容数据结构研究的主

5、要内容数据结构研究的主要内容 基本概念和术语基本概念和术语基本概念和术语基本概念和术语 数据结构类型数据结构类型数据结构类型数据结构类型 线性结构和非线性结构线性结构和非线性结构线性结构和非线性结构线性结构和非线性结构 顺序存储与链式存储顺序存储与链式存储顺序存储与链式存储顺序存储与链式存储 线性表线性表线性表线性表 栈和队列栈和队列栈和队列栈和队列 线性链表线性链表线性链表线性链表 树与二叉树树与二叉树树与二叉树树与二叉树 查找和排序查找和排序查找和排序查找和排序 图图图图第10页，本讲稿共111页2.1 2.1 算法算法v算法的基本概念算法的基本概念算法：解题方案的准确而完整的描述。算法：

6、解题方案的准确而完整的描述。算法的基本特征：算法的基本特征：是一组严谨地定义运算顺序的规则，每一个是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。规则都是有效的，是明确的，此顺序将在有限的次数下终止。算法不算法不等于程序，程序不可能优于算法。等于程序，程序不可能优于算法。基本特性基本特性可行性：根据实际问题设计的算法，执行得到满意结果可行性：根据实际问题设计的算法，执行得到满意结果确定性：每一步骤必须有明确定义，不允许有多义性。确定性：每一步骤必须有明确定义，不允许有多义性。有穷性：算法必须能在有限的时间内做完。有穷性：算法必须能在有限的时间内做完。

7、输入和输出：拥有足够的情报，方可执行。输入和输出：拥有足够的情报，方可执行。第11页，本讲稿共111页2.1 2.1 算法算法v算法的基本要素算法的基本要素1.1.对数据对象的运算和操作对数据对象的运算和操作算术运算：、算术运算：、等运算等运算逻辑运算：逻辑运算：and and、oror、notnot等运算等运算关系运算：关系运算：、=、=、!=!=等运算等运算数据传输：赋值、输入、输出等操作数据传输：赋值、输入、输出等操作2.2.算法的控制结构算法的控制结构算法中各操作之间的执行顺序算法中各操作之间的执行顺序描述算法的工具通常有描述算法的工具通常有传统流程图传统流程图、N-SN-S结构化流程

8、图结构化流程图、算法描述语言算法描述语言等等算法可以用算法可以用顺序、选择、循环顺序、选择、循环三种基本结构组合而成。三种基本结构组合而成。第12页，本讲稿共111页2.1 2.1 算法算法v算法设计基本方法算法设计基本方法（1 1）列举法：）列举法：根据问题，列举所有可能的情况，并用问题中给定根据问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。的条件检验哪些是需要的，哪些是不需要的。（2 2）归纳法：）归纳法：通过列举少量的特殊情况，经过分析，最后找通过列举少量的特殊情况，经过分析，最后找出一般的关系。出一般的关系。（3 3）递推：）递推：是指从已知的初始条件

9、出发，逐次推出所要求的各是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。中间结果和最后结果。（4 4）递归：）递归：将问题逐层分解的过程。将问题逐层分解的过程。（5 5）减半递推技术：）减半递推技术：“减半减半”，是指将问题规模减半，而问题，是指将问题规模减半，而问题性质不变；性质不变；“递推递推”，是指重复，是指重复“减半减半”过程。过程。（6 6）回溯法：）回溯法：分析问题，找出一个解决总线索，然后沿着这个线索分析问题，找出一个解决总线索，然后沿着这个线索逐步试探。逐步试探。第13页，本讲稿共111页2.1 2.1 算法算法v算法的复杂度：时间复杂度、空间复杂度算法的复杂度

10、：时间复杂度、空间复杂度算法的时间复杂度算法的时间复杂度算法时间复杂度是指执行算法所需要的算法时间复杂度是指执行算法所需要的计算工作量计算工作量。工作量用算法所执行的工作量用算法所执行的基本运算次数基本运算次数来度量，而算法所来度量，而算法所执行的基本运算次数是问题规模的函数，即执行的基本运算次数是问题规模的函数，即 算法的工作量算法的工作量=f(n)=f(n)O(1)常量级 O(n)线性级 O(n2)平方级第14页，本讲稿共111页时间复杂度举例举例举例1X=X+1 S=0执行次数：执行次数：2时间复杂度：时间复杂度：O(1)此算法的基本操作是赋值语句。执行两条语句各一此算法的基本操作是赋值

11、语句。执行两条语句各一次，共次，共2次次,与规模无关。时间复杂度为与规模无关。时间复杂度为(1)，即常，即常量阶。量阶。第15页，本讲稿共111页时间复杂度举例举例举例2For i=1 to n x=x+1 s=s+xNext i v执行次数为：执行次数为：2nv其时间复杂度为：其时间复杂度为：O(n)v即时间复杂度为线性阶。即时间复杂度为线性阶。第16页，本讲稿共111页时间复杂度举例举例举例3For i=1 to n For j=1 to n x=x+1 s=s+x next jNext i v执行次数执行次数2n2v其时间复杂度为：其时间复杂度为：O(n2)v即时间复杂度为平方阶。即时间

12、复杂度为平方阶。基本语句基本语句第17页，本讲稿共111页例，例，for (j=1 1；j=n；j+)X=X+1 1；for (i=1 1；i=n；i+)(c)for (i=1 1；i=n；i+)X=X+1 1；(b)X=X+1 1；(a)基本操作重复执行的次数分别为基本操作重复执行的次数分别为1，n，n2第18页，本讲稿共111页2.1 2.1 算法算法算法空间复杂度算法空间复杂度算法空间复杂度是指执行这个算法所需要的算法空间复杂度是指执行这个算法所需要的内存空间内存空间。存储空间包括：存储空间包括：算法程序所占的空间算法程序所占的空间输入数据所占的空间输入数据所占的空间算法执行过程中所需要

13、的额外空间。算法执行过程中所需要的额外空间。第19页，本讲稿共111页2.2.1 2.2.1 数据结构研究的主要内容数据结构研究的主要内容v当今计算机应用的特点当今计算机应用的特点所处理的数据量大且具有一定的关系；所处理的数据量大且具有一定的关系；对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。管理和检索。应用举例应用举例1 1学籍档案管理学籍档案管理 假设一个学籍档案管理系统应包含如下表所示的学生信息。假设一个学籍档案管理系统应包含如下表所示的学生信息。第20页，本讲稿共111页v特点特点每个学生的信息占据一行，

14、所有学生的信息每个学生的信息占据一行，所有学生的信息按学号顺序按学号顺序依次排依次排列构成一张表格；列构成一张表格；表中每个学生的信息依据学号的大小存在着一种表中每个学生的信息依据学号的大小存在着一种前后关系前后关系.对它的操作通常是对它的操作通常是插入插入某个学生的信息，某个学生的信息，删除删除某个学生的信息，某个学生的信息，更新更新某个学生的信息，按条件某个学生的信息，按条件检索检索某个学生的信息等等。某个学生的信息等等。2.2.1数据结构研究的主要内容数据结构研究的主要内容第21页，本讲稿共111页应用举例应用举例2 2制定教学计划制定教学计划 在制定教学计划时，需要考虑在制定教学计划时

15、，需要考虑各门课程的开设顺序各门课程的开设顺序。有些课程需要先。有些课程需要先导课程，有些则不需要导课程，有些则不需要;而有些课程又是其他课程的先导课程。比如，计而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示：算机专业课程的开设情况如下表所示：2.2.1数据结构研究的主要内容数据结构研究的主要内容第22页，本讲稿共111页课程先后关系的图形描形式课程先后关系的图形描形式课程先后关系的图形描形式课程先后关系的图形描形式c1c9c4c2c12c10c11c5c3c6c7c82.2.1数据结构研究的主要内容数据结构研究的主要内容v特点特点特点特点课程的先后关系用课程的先后

16、关系用图结构描述；图结构描述；通过实施创建图结构，通过实施创建图结构，按要求将图结构中的按要求将图结构中的顶点进行线性排序。顶点进行线性排序。第23页，本讲稿共111页v 数据结构主要研究以下三个方面的问题：数据结构主要研究以下三个方面的问题：数据的逻辑结构：数据的逻辑结构：数据集合中各元素的信息，及元素之间所固数据集合中各元素的信息，及元素之间所固有的逻辑关系（有的逻辑关系（前后件关系前后件关系）数据的存储结构：数据的存储结构：各数据元素在计算机中的存储关系各数据元素在计算机中的存储关系对各种数据结构进行的运算对各种数据结构进行的运算 主要目的是为了提高数据的效率。主要目的是为了提高数据的效

17、率。所谓提高数据处理的所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数效率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占用的计算机存储空间。据处理过程中所占用的计算机存储空间。2.2.1数据结构研究的主要内容数据结构研究的主要内容数据结构研究的主要内容数据结构研究的主要内容第24页，本讲稿共111页数据结构是一门研究数据结构是一门研究数据数据组织组织、存存储储和和运算运算的一般方法的学科。的一般方法的学科。是相互有关联的是相互有关联的数据元素的集合。数据元素的集合。2.2.22.2.2基本概念和术语基本概念和术语第25页，本讲稿共

18、111页能输入到计算机中能输入到计算机中并能被计算机程序处理的并能被计算机程序处理的符号的集合。符号的集合。整数整数(1,2)(1,2)、实数、实数(1.1,1.2)(1.1,1.2)字符串字符串(Beijing)(Beijing)、图形、声音。图形、声音。数据结构是一门研究数据结构是一门研究数据数据组织组织、存存储储和和运算运算的一般方法的学科。的一般方法的学科。2.2.2基本概念和术语基本概念和术语第26页，本讲稿共111页计计算机管理算机管理算机管理算机管理图书问题图书问题 图书馆里有各种卡片：有按里有各种卡片：有按书名名编排的、有按作者排的、有按作者编排排的、有按分的、有按分类编排。排

19、。如何将如何将查询图书的的这些信息存入些信息存入计算机中既要考算机中既要考虑查询时间短，又要考短，又要考虑节省空省空间 数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。2.2.2基本概念和术语基本概念和术语第27页，本讲稿共111页 最最简单的的办法之一是建立一法之一是建立一张表表，每一本，每一本书的信息在的信息在表中占一行，如表中占一行，如 数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。2.2.2基本概念和术语基本概念和术语第28页，本讲稿共111页 如何将如何将0,

20、1,2,3,4,5,6,7,8,90,1,2,3,4,5,6,7,8,9这这1010个数存放在个数存放在计算机中能最快地达到你所需要的目的？算机中能最快地达到你所需要的目的？目的不同，目的不同，最佳最佳的存的存储方方法就不同。方方法就不同。从大到小排列：从大到小排列：9,8,7,6,5,4,3,2,1,09,8,7,6,5,4,3,2,1,0输出偶数：出偶数：0,2,4,6,8,1,3,5,7,90,2,4,6,8,1,3,5,7,9 数据元素在数据元素在计算机中的表示算机中的表示 数据结构是一门研究数据结构是一门研究数据数据组织组织、存存储储和和运算运算的一般方法的学科。的一般方法的学科。2

21、.2.22.2.2基本概念和术语基本概念和术语基本概念和术语基本概念和术语第29页，本讲稿共111页对数据数据结构中的构中的节点点进行操作行操作处理理(插入、插入、删除、修改、除、修改、查找、排序找、排序)数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。2.2.2基本概念和术语基本概念和术语第30页，本讲稿共111页数据元素数据元素数据元素数据元素(Data Element)(Data Element)数据元素数据元素是数据的是数据的基本单位基本单位，即数据集合中的个体。，即数据集合中的个体。有时一个数据元素可由若干有时一个数据元素

22、可由若干数据项数据项(Data Item)(Data Item)组成。组成。数据项数据项是数据的最小单位。是数据的最小单位。数据元素亦称数据元素亦称节点节点或或记录记录。2.2.2基本概念和术语基本概念和术语第31页，本讲稿共111页数据结构可描述为数据结构可描述为 Group=Group=（D D，R R）有限个数据元素的集合有限个数据元素的集合有限个节点间关系的集合有限个节点间关系的集合2.2.2基本概念和术语基本概念和术语第32页，本讲稿共111页 1数据的逻辑结构数据的逻辑结构 2、数据的存储结构、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。、数据的运算：检索、排序、

23、插入、删除、修改等。A线性结构线性结构B非线性结构非线性结构A 顺序存储顺序存储 B 链式存储链式存储线性表线性表栈栈队队树形结构树形结构图形结构图形结构数数据据结结构构的的三三个个方方面面2.3数据结构类型数据结构类型第33页，本讲稿共111页2.3.1线性结构和非线性结构线性结构和非线性结构线性结构和非线性结构线性结构和非线性结构v 线性结构条件线性结构条件线性结构条件线性结构条件（1 1）有且只有一个根结点；）有且只有一个根结点；（2 2）每一个结点最多有一个前件（前驱），也最多有一个后件（后）每一个结点最多有一个前件（前驱），也最多有一个后件（后驱）。驱）。（3 3）首节点无前件，尾节

24、点无后件。）首节点无前件，尾节点无后件。v非线性结构：非线性结构：非线性结构：非线性结构：不满足线性结构条件的数据结构不满足线性结构条件的数据结构v注意：注意：在一个线性结构中插入或删除任何一个节点后还应是线性结在一个线性结构中插入或删除任何一个节点后还应是线性结构；否则，不能称为线性结构。构；否则，不能称为线性结构。学学学学 生生生生 成成成成 绩绩绩绩 表表表表8686胡孝臣胡孝臣986110398611039595刘忠刘忠赏98611079861107100100张卓卓98611099861109成成绩姓名姓名学号学号第34页，本讲稿共111页2.3.12.3.1线性结构和非线性结构线性

25、结构和非线性结构全校学生档案管理的树形结构的组织方式全校学生档案管理的树形结构的组织方式全校学生档案管理的树形结构的组织方式全校学生档案管理的树形结构的组织方式非线性非线性结构结构v 树形结构树形结构第35页，本讲稿共111页ABCDEFGH树形结构树形结构树形结构树形结构 结点间具有分层次的连接关系结点间具有分层次的连接关系结点间具有分层次的连接关系结点间具有分层次的连接关系HBCDEFGA2.3.1线性结构和非线性结构线性结构和非线性结构v 树形结构树形结构第36页，本讲稿共111页2.3.12.3.1线性结构和非线性结构线性结构和非线性结构v 图形结构：节点间的连接任意图形结构：节点间的

26、连接任意图形结构：节点间的连接任意图形结构：节点间的连接任意1423 D=1,2,3,4 R=(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)无向图无向图213 D=1,2,3 R=,有向图有向图第37页，本讲稿共111页Lo+（n-1)*m元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*m存储地址存储地址存储内容存储内容Loc(a)=Lo+（i-1)*m每个元每个元素所占素所占用的存用的存储单元储单元个数个数2.3.2顺序存储与链式存储顺序存储与链式存储v 顺序存储顺序存储顺序存储顺序存储常用于线性数据结构，常用于线性数据结构，将

27、将逻辑上相邻的数据元素存储逻辑上相邻的数据元素存储在物理上相邻的存储单元里。在物理上相邻的存储单元里。v三个弱点三个弱点三个弱点三个弱点插入或删除操作时，需移动插入或删除操作时，需移动大量元数。大量元数。长度变化较大时，需按最大长度变化较大时，需按最大空间分配。空间分配。表的容量难以扩充表的容量难以扩充第38页，本讲稿共111页每个每个节点节点都由两部分组成：数据域和指针域。都由两部分组成：数据域和指针域。数据域：数据域：存放元素本身的数据，存放元素本身的数据，指针域：指针域：存放指针，体现存放指针，体现数据元素之间的逻辑联系数据元素之间的逻辑联系2.3.22.3.2顺序存储与链式存储顺序存储

28、与链式存储顺序存储与链式存储顺序存储与链式存储1536元素元素2 21400元素元素1 11346元素元素3 3元素元素4 4head1345v链接存储结构特点链接存储结构特点链接存储结构特点链接存储结构特点比顺序存储结构的存储密度小比顺序存储结构的存储密度小 (每个节点都由数据域和指针愈组成每个节点都由数据域和指针愈组成)。逻辑上相邻的节点物理上不必相邻。逻辑上相邻的节点物理上不必相邻。插入、删除灵活插入、删除灵活(不必移动节点，仅改变节点中的指针不必移动节点，仅改变节点中的指针)。v链接存储结构链接存储结构链接存储结构链接存储结构第39页，本讲稿共111页 1346 1346 元素元素3

29、3 1536 1536 .1536 1536 元素元素2 2 1400 1400 .元素元素4 4 1346 1346 1400 1400 元素元素1 1 1345 1345 指指针 存存储内容内容存存储地址地址1536元素元素2 21400元素元素1 11346元素元素3 3元素元素4 4head13452.3.2顺序存储与链式存储顺序存储与链式存储链式链式链式链式存储存储存储存储的地的地的地的地址映址映址映址映射表射表射表射表第40页，本讲稿共111页1 1、链表不具有的特点是（）、链表不具有的特点是（）A)A)不必事先估计存储空间不必事先估计存储空间 B)B)插入删除不需要移动元素插入删

30、除不需要移动元素 C)C)可随机访问任一元素可随机访问任一元素 D)D)所需空间与线性表长度成正比所需空间与线性表长度成正比2 2、数据结构中，与所使用的计算机无关的是数据的（）、数据结构中，与所使用的计算机无关的是数据的（）A)A)存储结构存储结构B)B)物理结构物理结构 C)C)逻辑结构逻辑结构D)D)物理和存储结构物理和存储结构 3 3、根据数据结构中各数据元素之间前后件关系的复杂程度，一般将、根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成（）数据结构分成（）A)A)动态结构和静态结构动态结构和静态结构 B)B)紧凑结构和非紧凑结构紧凑结构和非紧凑结构 C)C)线性

31、结构和非线性结构线性结构和非线性结构 D)D)内部结构和外部结构内部结构和外部结构4 4、数据处理的最小单位是（）、数据处理的最小单位是（）A)A)数据数据 B)B)数据元素数据元素 C)C)数据项数据项 D)D)数据结构数据结构过关练习过关练习第41页，本讲稿共111页5 5、下列叙述中，错误的是（）、下列叙述中，错误的是（）A)A)数据的存储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率密切相关 B)B)数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关 C)C)数据的存储结构在计算机中所占空间不一定是连续的数据的存储结构在计算机中所占空间不一定是连续的 D)

32、D)一种数据的逻辑结构可以有多种存储结构一种数据的逻辑结构可以有多种存储结构6 6、线性表的顺序存储结构和线性表的链式存储结构分别是、线性表的顺序存储结构和线性表的链式存储结构分别是 A)A)顺序存取的存储结构、顺序存取的存储结构顺序存取的存储结构、顺序存取的存储结构 B)B)随机存取的存储结构、顺序存取的存储结构随机存取的存储结构、顺序存取的存储结构 C)C)随机存取的存储结构、随机存取的存储结构随机存取的存储结构、随机存取的存储结构 D)D)任意存取的存储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构7 7、数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各、数据结

33、构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及（）种数据结构进行的运算，以及（）A)A)数据的存储结构数据的存储结构 B)B)计算方法计算方法 C)C)数据映象数据映象 D)D)逻辑存储逻辑存储过关练习过关练习第42页，本讲稿共111页8 8、下列叙述中正确的是（）、下列叙述中正确的是（）A A）程序执行的效率与数据的存储结构密切相关）程序执行的效率与数据的存储结构密切相关B B）程序执行的效率只取决于程序的控制结构）程序执行的效率只取决于程序的控制结构C C）程序执行的效率只取决于所处理的数据量）程序执行的效率只取决于所处理的数据量D D）以上都不对）以上都不

34、对9 9、数据的存储结构是指（）、数据的存储结构是指（）A A）数据所占的存储空间）数据所占的存储空间B B）数据的逻辑结构在计算机中的表示）数据的逻辑结构在计算机中的表示C C）数据在计算机中的顺序存储方式）数据在计算机中的顺序存储方式D D）存储在外存中的数据）存储在外存中的数据 1010、数据（）包括集合、线性结构、树形结构和图、数据（）包括集合、线性结构、树形结构和图4 4种类型。种类型。A)A)算法描述算法描述 B)B)基本运算基本运算 C)C)逻辑结构逻辑结构 D)D)存储结构存储结构过关练习过关练习第43页，本讲稿共111页1111、数据在计算机内存种的表示是指（）、数据在计算机

35、内存种的表示是指（）A A）数据的存储结构）数据的存储结构 B B）数据结构）数据结构C C）数据的逻辑机构）数据的逻辑机构 D D）数据元素间的关系）数据元素间的关系1212、数据结构研究的主要内容包括（）、（）和数据元素之间的、数据结构研究的主要内容包括（）、（）和数据元素之间的三方面联系。三方面联系。1313、顺序存储方法是把逻辑上相邻的结点存储在物理位置（）的存储单、顺序存储方法是把逻辑上相邻的结点存储在物理位置（）的存储单元中。元中。1414、数据结构包括数据的逻辑结构、数据的（）以及对数据的操作运算。、数据结构包括数据的逻辑结构、数据的（）以及对数据的操作运算。1515、数据的基本

36、单位是（）。、数据的基本单位是（）。1616、数据结构分为逻辑结构与存储结构，线性链表属于（）。、数据结构分为逻辑结构与存储结构，线性链表属于（）。1717、数据的逻辑结构有线性结构和、数据的逻辑结构有线性结构和 （）两大类。（）两大类。过关练习过关练习第44页，本讲稿共111页练习参考答案练习参考答案 1 15 5、CCCCB 6CCCCB 61111、BAABCABAABCA 12 12、数据存储结构、数据逻辑结构、数据存储结构、数据逻辑结构 13 13、相邻、相邻 14 14、存储结构、存储结构 15 15、数据元素、数据元素 16 16、非线性结构、非线性结构第45页，本讲稿共111页

37、2.3.3线性表线性表v线性表的基本概念线性表的基本概念 线性表线性表由一组数据元素构成，数据元由一组数据元素构成，数据元素的位置只取决于自己的序号，素的位置只取决于自己的序号，元素之间元素之间的相对位置是线性的。的相对位置是线性的。v非空线性表的结构特征非空线性表的结构特征有且只有一个有且只有一个根结点根结点a1a1，它无前件；，它无前件；有且只有一个有且只有一个终端结点终端结点anan，它无后件；，它无后件；除根结点与终端结点外，其他所有除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只结点有且只有一个前件，也有且只有一个后件。结点个数有一个后件。结点个数n n称为线性表称为线性

38、表的长度，的长度，当当n=0n=0时，称为空表时，称为空表。Lo+（n-1)*m元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*m存储地址存储地址存储内容存储内容Loc(a)=Lo+（i-1)*m第46页，本讲稿共111页v在线性表上常用的运算有在线性表上常用的运算有初始化、求长度、取元素、修改、初始化、求长度、取元素、修改、插入、删除插入、删除、检索、排序。、检索、排序。v线性表的插入操作线性表的插入操作 在线性表在线性表L L中第中第i i个数据元素之前插入数据元素个数据元素之前插入数据元素e e检查插入要求的有关参数的合理性检查插入要求的有关参数

39、的合理性把原来第把原来第n n个数据元素至第个数据元素至第i i个元素（共个元素（共n-i+1)n-i+1)依次后移一个数组元素依次后移一个数组元素的位置。的位置。把新数据元素放在第把新数据元素放在第i i个位置上个位置上修正线性表的数据元素个数。修正线性表的数据元素个数。线性表中含有线性表中含有n n个数据元素，在进行插入操作时，若假定在个数据元素，在进行插入操作时，若假定在n+1n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：个位置上插入元素的可能性均等，则平均移动元素的个数为：n/2n/22.3.3线性表线性表第47页，本讲稿共111页v线性表的插入操作（线性表的插入操作（时

40、间复杂度时间复杂度O(n)）插入前插入前插入插入xlastMaxsize-1aia1a0ai-1ai+1an-1a0a1ai-1aian-1lastMaxsize-1后移后后移后ai1a0a1ai-1ai+1ai+1an xlastMaxsize-1插入后插入后ai+22.3.3线性表线性表第48页，本讲稿共111页v线性表的删除操作（线性表的删除操作（时间复杂度时间复杂度O(n)）2.3.3线性表线性表a0a1ai-1aiai+1an-1删除删除lastmaxsize删除前删除前a0a1ai-1ai+2an-1lastmaxsize删除后删除后ai+1第49页，本讲稿共111页1 1、线性表

41、、线性表L=(a1,a2,a3,L=(a1,a2,a3,aiai，an)an)，下列说法正确的是（），下列说法正确的是（）A)A)每个元素都有一个直接前件和直接后件每个元素都有一个直接前件和直接后件 B)B)线性表中至少要有一个元素线性表中至少要有一个元素 C)C)表中诸元素的排列顺序必须是由小到大或由大到小表中诸元素的排列顺序必须是由小到大或由大到小 D)D)除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件和直接后件2 2、线性表采用链式存储结构时，则内存中可用存储单元地址、线性表采用链式存储结

42、构时，则内存中可用存储单元地址 A)A)必须是连续的必须是连续的 B)B)部分地址必须是连续的部分地址必须是连续的 C)C)一定是不连续的一定是不连续的 D)D)连续不连续都可以连续不连续都可以3 3、在一个长度为、在一个长度为n n的顺行表种，向第的顺行表种，向第i i个元素位置插入一个新元素时，个元素位置插入一个新元素时，需要向后移动（）个元素需要向后移动（）个元素 A)n-i B)i C)n-i-1 D)n-i+1 A)n-i B)i C)n-i-1 D)n-i+14 4、长度为、长度为n n的顺序存储线性表，当在任何位置上插入一个元素概率都相的顺序存储线性表，当在任何位置上插入一个元素

43、概率都相等时，插入一个元素所需移动元素的平均个数为等时，插入一个元素所需移动元素的平均个数为 （）（）。过关练习过关练习第50页，本讲稿共111页练习参考答案练习参考答案 1 1、D 2D 2、C 3C 3、D D 3 3、n/2n/2第51页，本讲稿共111页2.3.4栈和队列栈和队列 栈和队列栈和队列是两种运算时要受到某些特殊限制的线是两种运算时要受到某些特殊限制的线性表，故也称为性表，故也称为限定性的数据结构。限定性的数据结构。v栈：栈：限定限定只能在表的一端进行插入和删除只能在表的一端进行插入和删除的特殊的线性表的特殊的线性表,此种此种结构称为结构称为后进先出。后进先出。设栈设栈s=s

44、=（a1a1，a2a2，,ai,ai，anan）其中其中a1a1是栈底元素，是栈底元素，an an是栈顶元素。是栈顶元素。栈顶（栈顶（top)top)：允许插入和删除的一端；：允许插入和删除的一端；约定约定toptop始终指向新数据元素将存放的位置。始终指向新数据元素将存放的位置。栈底（栈底（bottom):bottom):不允许插入和删除的一端。不允许插入和删除的一端。a1 a2.an进栈进栈出栈出栈栈顶栈顶栈底栈底第52页，本讲稿共111页v队列的主要运算队列的主要运算设置一个空队列；设置一个空队列；插入一个新的插入一个新的队尾（队尾（rearrear）元素，称为进队；元素，称为进队；删除

45、删除队头（队头（frontfront）元素，称为出队；元素，称为出队；读取队头元素；读取队头元素；a1,a2,a3,a4,an-1,an队队头头队队尾尾2.3.4栈和队列栈和队列v队列：队列：限定限定只能在表的一端进行插入，在表的另一端进行删只能在表的一端进行插入，在表的另一端进行删除除的线性表。此种结构称为的线性表。此种结构称为先进先出（先进先出（FIFOFIFO）表。表。第53页，本讲稿共111页 3210 (a)rear=front=-1(队空）队空）e3 e4 (c)(c)e1,e2出队，出队，e4入入队队rear=4front e1 e2 e3 (b)rearfront(b)e1,e

46、2,e3入入队队2.3.4栈和队列栈和队列v队列的主要运算队列的主要运算队空时，队空时，令令rear=front=-1rear=front=-1当有新元素当有新元素入队时，尾指针加入队时，尾指针加1 1，当有元素，当有元素出队时，头指针加出队时，头指针加1 1。故在非空队列中，头指针始终指向队头元素前一个位置，故在非空队列中，头指针始终指向队头元素前一个位置，而尾指针始终指向队尾元素的位置而尾指针始终指向队尾元素的位置第54页，本讲稿共111页v循环队列元素个数循环队列元素个数=rear-front=rear-fronta1,a2,a3,a4,an-1,an队队头头队队尾尾2.3.4栈和队列栈

47、和队列v循环队列：循环队列：首尾相接首尾相接的队列的队列，逻辑上形成一个环状。，逻辑上形成一个环状。第55页，本讲稿共111页1 1、栈和队列的共同特点是（）、栈和队列的共同特点是（）A)A)都是先进先出都是先进先出 B)B)都是先进后出都是先进后出 C)C)只允许在端点处插入和删除元素只允许在端点处插入和删除元素 D)D)没有共同点没有共同点2 2、如果进栈序列为、如果进栈序列为e1,e2,e3,e4e1,e2,e3,e4，则可能的出栈序列是，则可能的出栈序列是 A)e3,e1,e4,e2 A)e3,e1,e4,e2 B)e2,e4,e3,e1 B)e2,e4,e3,e1 C)e3,e4,e

48、1,e2 C)e3,e4,e1,e2D)D)任意顺序任意顺序3 3、一些重要的程序语言、一些重要的程序语言(如如C C语言和语言和PascalPascal语言语言)允许过程的递归调用。允许过程的递归调用。而实现递归调用中的存储分配通常用（）而实现递归调用中的存储分配通常用（）A)A)栈栈 B)B)堆堆 C)C)数组数组 D)D)链表链表4 4、栈通常采用的两种存储结构是、栈通常采用的两种存储结构是 A)A)线性存储结构和链表存储结构线性存储结构和链表存储结构 B)B)散列方式和索引方式散列方式和索引方式 C)C)链表存储结构和数组链表存储结构和数组 D)D)线性存储结构和非线性存储结构线性存储

49、结构和非线性存储结构过关练习过关练习第56页，本讲稿共111页5 5、下列数据结构中，按先进后出原则组织数据的是（）、下列数据结构中，按先进后出原则组织数据的是（）A)A)线性链表线性链表 B)B)栈栈 C)C)循环链表循环链表 D)D)顺序表顺序表6 6、下列关于栈的叙述中正确的是（）、下列关于栈的叙述中正确的是（）在栈中只能插入数据）在栈中只能插入数据 B B）在栈中只能删除数据）在栈中只能删除数据C C）栈是先进先出的线性表）栈是先进先出的线性表 D D）栈是后进先出的线性表）栈是后进先出的线性表7 7、下列关于队列的叙述中正确的是（）、下列关于队列的叙述中正确的是（）在队列中只能插入数

50、据）在队列中只能插入数据 B B）在队列中只能删除数据）在队列中只能删除数据C C）队列是先进先出的线性表）队列是先进先出的线性表 D D）队列是后进先出的线性表）队列是后进先出的线性表8 8、在顺序栈中进行退栈操作时，（、在顺序栈中进行退栈操作时，（）。）。）谁先谁后都可以）谁先谁后都可以 B B）先移动栈顶指针，后取出元素）先移动栈顶指针，后取出元素C C）不分先后，同时进行）不分先后，同时进行 D D）先取出元素，后移动栈顶指针）先取出元素，后移动栈顶指针过关练习过关练习第57页，本讲稿共111页9 9、假定利用数组、假定利用数组anan顺序存储一个栈，利用顺序存储一个栈，利用topto