计算机2级C公共基础知识课件.ppt

计算机等级考试计算机等级考试公共基础知识公共基础知识1第2页计算机二级考试公共基础知识计算机二级考试公共基础知识大纲大纲q数据结构与算法数据结构与算法q程序设计基础程序设计基础q软件工程基础软件工程基础q数据库设计基础数据库设计基础这四个方面在试卷中出现的情况是：选择题10个（20分），填空题5个（10分），总分值占到了试卷卷面分的30，是一个不小的比例。2第3页计算机二级考试公共基础知识试卷分析计算机二级考试公共基础知识试卷分析章节章节考试时间考试时间数据结构数据结构与算法与算法程序设计程序设计基础基础软件工程软件工程基础基础数据库设计数据库设计基础基础2007年4月10分2分10分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分3第4页算法算法算法的基算法的基本概念本概念2.2.算法复杂算法复杂度的概念和度的概念和意义意义一、基本数据结构与算法一、基本数据结构与算法数据结构数据结构数据结构的概念数据结构的概念线性表线性表栈和队列栈和队列树与二叉树树与二叉树查找技术查找技术排序技术排序技术对于等级考试，这个部分的考核对于等级考试，这个部分的考核重点主要重点主要在在算法和数据结构的基本概算法和数据结构的基本概念念、二叉树二叉树(遍历、结点），遍历、结点），还有还有排序和查找排序和查找考试中也经常会涉及到。考试中也经常会涉及到。4第5页算法的定义算法的定义u对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。算法是程序设计的核心算法是程序设计的核心算法的基本概念算法的基本概念 算法是在有限步骤内求解某一问题所使用的一组定义明确的算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机规则。通俗点说，就是计算机解题的过程解题的过程(计算的方法计算的方法)。在。在这个过程中，无论是形成解题思路这个过程中，无论是形成解题思路(推理实现的算法推理实现的算法)还是编还是编写程序写程序(操作实现的算法操作实现的算法)，都是在实施某种算法。，都是在实施某种算法。例：例：n个数从大到小进行排序。个数从大到小进行排序。有多种排序方法有多种排序方法，常用的有冒泡排序、选择排序等。，常用的有冒泡排序、选择排序等。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。讲课讲课说课说课5第6页2.算法的基本特征算法的基本特征一个算法应该具有以下五个重要的特征：一个算法应该具有以下五个重要的特征：n有穷性有穷性n确定性确定性n输入输入n输出输出n可行性可行性一个算法必须保证执行有限步之后结束；算法的每一步骤必须有确切的定义；一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成拥有足够的情报拥有足够的情报6第7页u算法与计算机程序算法与计算机程序算法算法_是一组逻辑步骤是一组逻辑步骤程序程序用计算机语言描述的算法用计算机语言描述的算法3.3.算法的表示算法的表示算法的表示算法的表示INPUT rINPUT rS=3.14*r*rS=3.14*r*rPTINT SPTINT S开始开始输入输入R RS=3.14 S=3.14*R*RR*R输出输出S S结束结束问题：输入园的半径，计算园的面积一个算法的表示需要使用一些语言形式。一个算法的表示需要使用一些语言形式。传统的算法传统的算法-图形法，如图形法，如“流程图流程图”和和N-S图图目前常用的方法目前常用的方法-使用伪码描述算法。使用伪码描述算法。7第8页冒泡排序的方法：冒泡排序的方法：1.1.扫描整个线性表，逐次对相扫描整个线性表，逐次对相邻的两个元素进行比较，若为邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的逆序，则交换；第一趟扫描的结果使最大的元素排到表的最结果使最大的元素排到表的最后后 ；2.2.除最后一个元素，对剩余的除最后一个元素，对剩余的元素重复上述过程，将次大的元素重复上述过程，将次大的数排到表的倒数第二个位置；数排到表的倒数第二个位置；3.3.重复上述过程；重复上述过程；对于长度为对于长度为n n的线性表，冒泡排的线性表，冒泡排序需要对表扫描序需要对表扫描n-1n-1遍。遍。算法举例：算法举例：n个数排序个数排序8第9页4.算法的两个基本要素：算法的两个基本要素：基本运算和操作基本运算和操作基本运算和操作基本运算和操作n算术运算算术运算n关系运算关系运算n逻辑运算逻辑运算n数据传输数据传输控制结构控制结构控制结构控制结构 n顺序顺序n选择选择n循环循环u一是对数据对象的运算和操作；u二是算法的控制结构。u算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法9第10页5.算法的复杂度算法的复杂度评价一个算法优劣的主要标准是算法的执行效率和存储需求：评价一个算法优劣的主要标准是算法的执行效率和存储需求：n时间复杂度：执行这个算法所需要的时间复杂度：执行这个算法所需要的计算工作量计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量n空间复杂度：执行这个算法所需要的空间复杂度：执行这个算法所需要的内存空间内存空间算法在执行过程中临时占用的存储空间算法在执行过程中临时占用的存储空间时间复杂度时间复杂度它大致等于计算机它大致等于计算机执行一种简单操作所需的平均时间执行一种简单操作所需的平均时间与算法中与算法中进行进行简单操作的次数的乘积简单操作的次数的乘积。一个算法在计算机存储器上所占用的存储空间，包括一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用存储算法本身所占用的存储空间的存储空间、算法中的输入输出数据所占用的存储空间算法中的输入输出数据所占用的存储空间和和算法在运行过程中算法在运行过程中临时占用的存储空间临时占用的存储空间这三个部分这三个部分10第11页(1)在计算机中，算法是指在计算机中，算法是指_。A.查询方法查询方法B.加工方法加工方法C.解题方案的准确而完整的描述解题方案的准确而完整的描述D.排序方法排序方法(2)下列叙述中正确的是下列叙述中正确的是（07年年4月月）A)算法的效率只与问题的规模有关，而与数据的存储结构无关算法的效率只与问题的规模有关，而与数据的存储结构无关B)算法的时间复杂度是指执行算法所需要的计算工作量算法的时间复杂度是指执行算法所需要的计算工作量C)数据的逻辑结构与存储结构是一一对应的数据的逻辑结构与存储结构是一一对应的D)算法的时间复杂度与空间复杂度一定相关算法的时间复杂度与空间复杂度一定相关(3)算法的有穷性是指算法的有穷性是指(08年年4月月)A）算法程序的运行时间是有限的）算法程序的运行时间是有限的B）算法程序所处理的数据量是有限的）算法程序所处理的数据量是有限的C）算法程序的长度是有限的）算法程序的长度是有限的D）算法只能被有限的用户使用）算法只能被有限的用户使用(c)(B)算法习题:(A)11第12页(4)算法的时问复杂度是指算法的时问复杂度是指(2010年年3月月)A)算法的执行时间算法的执行时间B)算法所处理的数据量算法所处理的数据量C)算法程序中的语句或指令条数算法程序中的语句或指令条数D)算法在执行过程中所需要的基本运算次数算法在执行过程中所需要的基本运算次数(5)算法的空间复杂度是指算法的空间复杂度是指(09年年9月月)A）算法在执行过程中所需要的计算机存储空间）算法在执行过程中所需要的计算机存储空间B）算法所处理的数据量）算法所处理的数据量C）算法程序中的语句或指令条数）算法程序中的语句或指令条数D）算法在执行过程中所需要的临时工作单元数）算法在执行过程中所需要的临时工作单元数(6)下列叙述中正确的是下列叙述中正确的是(06年年9月月)A）一个算法的空间复杂度大，则其时间复杂度也必定大）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小）一个算法的空间复杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间复杂度必定小）一个算法的时间复杂度大，则其空间复杂度必定小D）上述三种说法都不对）上述三种说法都不对(D)计算工作量(A)(D)12u算法的时间复杂度是指算法的时间复杂度是指A)执行算法程序所需要的时间执行算法程序所需要的时间B)算法程序的长度算法程序的长度C)算法执行过程中所需要的基本运算次数算法执行过程中所需要的基本运算次数D)算法程序中的指令条数算法程序中的指令条数u算法的基本特征是可行性、确定性、算法的基本特征是可行性、确定性、【1】和拥有足够的情报。和拥有足够的情报。u算法的空间复杂度是指算法的空间复杂度是指A)算法程序的长度算法程序的长度B)算法程序中的指令条数算法程序中的指令条数C)算法程序所占的存储空间算法程序所占的存储空间D)执行过程中所需要的存储空间执行过程中所需要的存储空间u在计算机中，算法是指在计算机中，算法是指A)加工方法加工方法B)解题方案的准确而完整的描述解题方案的准确而完整的描述C)排序方法排序方法D)查询方法查询方法例题讲解例题讲解有穷性有穷性13u算法分析的目的是算法分析的目的是A)找出数据结构的合理性找出数据结构的合理性B)找出算法中输入和输出找出算法中输入和输出之间的关系之间的关系C)分析算法的易懂性和可靠性分析算法的易懂性和可靠性D)分析算法的效率分析算法的效率以求改进以求改进u算法的工作量大小和实现算法所需的存储单元多少算法的工作量大小和实现算法所需的存储单元多少分别称为算法的分别称为算法的【1】。时间复杂度和空间复杂度时间复杂度和空间复杂度14第15页计算机在进行数据处理时，实际需要处理的数据元素一般有很计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，省计算机的存储空间，这是进行数据处理的关键问题。这是进行数据处理的关键问题。二、数据结构二、数据结构程序程序=算法算法+数据结构数据结构数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。一般情况下，在具有相同特征的数据元素集合中，各个数据一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即元素之间存在有某种关系（即联系）联系），这种关系反映了该集，这种关系反映了该集合中的数据元素所固有的一种结构。合中的数据元素所固有的一种结构。超市的物品如何超市的物品如何存放才好找且节存放才好找且节省空间呢？省空间呢？15第16页二二.数据结构数据结构数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。数据结构是研究数据和数据之间关系的一门学科，它数据结构是研究数据和数据之间关系的一门学科，它包括三个方面。包括三个方面。（1）数据集合中各数据元素之间所固有的逻辑关系，）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。）对各种数据结构进行的运算。16第17页u1.逻辑结构逻辑结构数据的逻辑结构是指反映数据元素之间逻辑关系的数据结数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。构。数据的逻辑结构包含：数据的逻辑结构包含：（1）表示数据元素的信息；）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。）表示各数据元素之间的前后件关系。例：例：1.一年四季的数据结构一年四季的数据结构B=(D,R)D=春，夏，秋，冬春，夏，秋，冬R=(春，夏春，夏),(夏，秋夏，秋),(秋，冬秋，冬)2.家庭成员的数据结构家庭成员的数据结构B=(D,R)D=父亲，儿子，女儿父亲，儿子，女儿R=(父亲，儿子父亲，儿子),(父亲，女儿父亲，女儿)春夏秋冬数据结构的图形表示数据结构的图形表示父亲儿子女儿17第18页u常见的常见的逻辑结构逻辑结构有：有：线性结构、树形结构和图形结构。线性结构、树形结构和图形结构。线性结构线性结构树形结构树形结构图图形形结结构构u线性结构线性结构结构中的每个元素之间存在结构中的每个元素之间存在一个对一个的关系一个对一个的关系；u树形结构树形结构结构中的每个元素之间存在结构中的每个元素之间存在一个对多个的关系一个对多个的关系；u图形结构或网状结构图形结构或网状结构结构中的每个元素之间存在结构中的每个元素之间存在多个对多个的关系多个对多个的关系。其中，其中，树形结构和图形结构统称为非线形结构树形结构和图形结构统称为非线形结构。数据的逻辑结构可以用。数据的逻辑结构可以用二元关系表示，也可以直观地用图形来表示。二元关系表示，也可以直观地用图形来表示。18第19页u2.存储结构（物理结构存储结构（物理结构）计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。们的逻辑关系不一定是相同的，而且一般也不可能相同。如：如：一年四季家庭成员计算机存储空间怎样存放？存储结构指数据结构在计算机存储空间中的具体实现。存储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有：常见的存储结构有：n顺序存储结构顺序存储结构n链式存储结构链式存储结构n索引存储结构索引存储结构只抽象地反映数据元素之间的关系的结构，只抽象地反映数据元素之间的关系的结构，而不管其存储方式的数据结构称为逻辑结而不管其存储方式的数据结构称为逻辑结构。构。一种一种数据结构可以根据需要表示成一种或数据结构可以根据需要表示成一种或多种存储结构多种存储结构。19第20页u3.数据的运算数据的运算n检索检索n插入插入n删除删除n更新更新n排序排序通常，一个数据结构中的元素结点可能是动态变化的。根据需要通常，一个数据结构中的元素结点可能是动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结点（插入运或在处理过程中，可以在一个数据结构中增加一个新结点（插入运算），也可以删除某个结点（删除运算），除此之外，对数据结构算），也可以删除某个结点（删除运算），除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改。的运算还有查找、分类、合并、分解、复制和修改。在对数据结构的处理过程中，不仅数据结构中结点的个数在动态在对数据结构的处理过程中，不仅数据结构中结点的个数在动态变化，而且，各数据元素之间的关系也有可能在动态地变化。变化，而且，各数据元素之间的关系也有可能在动态地变化。如：无序表变有序表数据结构是研究数据和数据之数据结构是研究数据和数据之间关系的一门学科，研究以下三间关系的一门学科，研究以下三方面内容：方面内容：n数据的逻辑结构数据的逻辑结构n数据的存储结构数据的存储结构n数据的运算数据的运算父亲儿子女儿20第第21 21|92|92页页常见的数据结构常见的数据结构u 数据结构分类数据结构分类 线性结构与非线性结构线性结构与非线性结构两大类型线性结构：一个非空的数据结构若满足下面的两个条件，则一个非空的数据结构若满足下面的两个条件，则这种数据结构即为这种数据结构即为线性结构线性结构线性结构线性结构。有且仅有一个根结点；有且仅有一个根结点；除第一个结点外，每一个结点最多有一个前件；除第一个结点外，每一个结点最多有一个前件；除最后一个结点外，每一个结点最多有一个后件。除最后一个结点外，每一个结点最多有一个后件。常见的线性结构有：常见的线性结构有：线性表、栈、队列、线性链表等线性表、栈、队列、线性链表等线性表、栈、队列、线性链表等线性表、栈、队列、线性链表等21 21第第2222|92|92页页a1a2a5a3a4HEAD319510线性链表的逻辑状态线性链表的逻辑状态常见的非线性结构有树、常见的非线性结构有树、二叉树、图等二叉树、图等二叉树、图等二叉树、图等非线性结构：一个数据结构不是线性结构。一个数据结构不是线性结构。2222第23页 线性表（线性表（线性表（线性表（LinearListLinearList）线性表是由线性表是由n（n0）个数据元素）个数据元素a1，a2，ai，an组成的一个有限序列。组成的一个有限序列。简单的线性表简单的线性表简单的线性表简单的线性表春春夏夏秋秋冬冬复杂的线性表复杂的线性表复杂的线性表复杂的线性表记录记录102011001张三张三男男记录记录202011003李四李四女女记录记录3记录记录423第24页线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构特点：特点：顺序存储结构把顺序存储结构把逻辑上相逻辑上相邻邻的数据元素存储在的数据元素存储在物理上相邻物理上相邻的的存储单元里，顺序存储结构存储单元里，顺序存储结构只存储只存储结点的值结点的值，不存储结点间的关系，不存储结点间的关系，结点间的关系由存储单元的邻接关结点间的关系由存储单元的邻接关系来体现。系来体现。a1a2aian存储地址存储地址200020042000+4*(i-1)2000+4*(n-1)占占4个字节个字节LoaLoa（a ai i）=Loa=Loa（a a1 1）+L*+L*（i-1i-1）第i个数的地址第一个数的地址L为该类型数所占的字节线性表的存储结构线性表的存储结构线性表的存储结构有两种：线性表的存储结构有两种：u顺序存储结构顺序存储结构u链式存储结构链式存储结构24第25页u顺序表的插入运算顺序表的插入运算u顺序表的删除运算顺序表的删除运算顺序表的插入和删除运算顺序表的插入和删除运算顺序表的插入和删除运算顺序表的插入和删除运算在线性表顺序存储情况下，要插入或删除一个元在线性表顺序存储情况下，要插入或删除一个元素，都会由于数据元素的移动而消耗大量的处理时间，素，都会由于数据元素的移动而消耗大量的处理时间，所以这种存储方式对于小线性表或其中数据元素不经所以这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的。常变动的线性表是合适的。线性表的顺序存储结构称为顺序表。线性表的顺序存储结构称为顺序表。25第26页插入运算插入运算ai-1.a2a1alengthai+1aixai-1.a2a1alengthai+1aiX 插入算法的分析插入算法的分析:假设线性表中含有假设线性表中含有n n个数据元素，在进行插入操作时，若假定个数据元素，在进行插入操作时，若假定在在n+1n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：个位置上插入元素的可能性均等，则平均移动元素的个数为：26第27页删除运算删除运算ai-1.a2a1alengthai+1aiai-1.a2a1alengthai+1删除算法的分析删除算法的分析:在进行删除操作时，若假定删除每个元素的可能性均等，则平在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：均移动元素的个数为：总结总结:顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。插入或删除操作时，这一点需要值得考虑。27第28页线性表的链式存储结构线性表的链式存储结构线性表的链式存储结构线性表的链式存储结构u线性表的链式存储结构称为线性链表。线性表的链式存储结构称为线性链表。u链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且各数据元素的存储顺序也是任意的。各数据元素的先后而且各数据元素的存储顺序也是任意的。各数据元素的先后关系是由各结点的指针域指示。关系是由各结点的指针域指示。u链式存储结构的每一个存储结点不仅存储结点的值，而且存链式存储结构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系：储结点之间的关系：u链式存储结构分为单链表、双向链表、循环链表链式存储结构分为单链表、双向链表、循环链表u线性链表不能随机存取线性链表不能随机存取数据域数据域指针域指针域28第29页设线性表为设线性表为（a1，a2，a3，a4，a5）1a2923a1145a4106789a3510a50HEAD3a1a2a5a3a4HEAD319510线性链表的逻辑状态线性链表的逻辑状态线性链表线性链表的物理状态的物理状态1 a12 a23 a34 a45 a567线性表的线性表的线性表的线性表的顺顺顺顺序存储序存储序存储序存储结构结构结构结构注意:123此类编号不代表所在的地址单元的地址编码线性表的链式存储结构线性表的链式存储结构及其插入与删除操作及其插入与删除操作29第30页zhaoqiansunlizhouwuzhengwang/H存储地址存储地址数据数据17131925313743liqiansunwangwuzhaozhengzhou指针指针43131null377192531头指针头指针单链表单链表30第31页单链表的插入运算单链表的插入运算在在P所指向的结点之后插入所指向的结点之后插入新的结点新的结点单链表单链表删除运算删除运算PbaxSbaPLaaian ai-1ai+1要求要求:删除结点删除结点ai。31第32页循环链表循环链表:首尾相接的链表。首尾相接的链表。将将最最后后一一个个结结点点的的空空指指针针改改为为指指向向头头结结点点，从从任任一一结结点点出出发发均均可可找找到到其其它结点它结点。a1a2ana3L.带头结点的单链表带头结点的单链表a1a2ana3L.循环单链表循环单链表特点特点:可以从任何一个结点开始访问链表的所有结点可以从任何一个结点开始访问链表的所有结点.32第33页双向链表的存储结构双向链表的存储结构在在每每个个结结点点中中设设置置两两个个指指针针，一一个个指指向向后后继继，一一个个指指向向前前驱驱。可可直直接接确定一个结点的前驱和后继结点。可提高效率。确定一个结点的前驱和后继结点。可提高效率。HEAD31510a2a3a4a1提问：单向链表的缺点是什么？提示：如何寻找结点的直接前趋。双向链表可以克服单链表的单向性的缺点。在双向链表的结点中有两个指针域，其一指向直接后继，另一在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。指向直接前趋。双向循环链表双向循环链表33第34页u线性表的应用：应用最广的数据结构。线性表的应用：应用最广的数据结构。u.高级语言中的数组；高级语言中的数组；u计算机的文件系统；计算机的文件系统；u计算机的目录系统；计算机的目录系统；u电话号码查询系统（可采用顺序表或单链表结构电话号码查询系统（可采用顺序表或单链表结构）；）；u各种事务处理（各种事务处理（可采用顺序表或单链表结构可采用顺序表或单链表结构）;34第35页2.栈和队列栈和队列栈和队列栈和队列是两种特殊的线性表，它们是运算时要是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为受到某些限制的线性表，故也称为限定性的数限定性的数据结构据结构。uu 栈（栈（栈（栈（StackStack）及其基本运算）及其基本运算）及其基本运算）及其基本运算uu 队列（队列（队列（队列（QueueQueue）及其基本运算）及其基本运算）及其基本运算）及其基本运算uu 循环队列及其基本运算循环队列及其基本运算循环队列及其基本运算循环队列及其基本运算35第36页1.栈栈栈栈是限定仅在表尾进行插入或删除操作的线性表。是限定仅在表尾进行插入或删除操作的线性表。栈顶栈顶表尾。表尾。栈底栈底表头。表头。空栈空栈不含元素的空表。不含元素的空表。a1a2an栈底栈底栈顶栈顶进栈进栈出栈出栈栈栈s=(a1,a2,an)后进先出或先后进先出或先进后出进后出（LIFO）36第37页u栈的物理存储结构可以用顺序结构，也可以用链表结栈的物理存储结构可以用顺序结构，也可以用链表结构。构。u下面讨论顺序存储结构中栈元素的插入和删除运算。下面讨论顺序存储结构中栈元素的插入和删除运算。n顺序栈的进栈和出栈运算顺序栈的进栈和出栈运算n栈的基本运算有三种：入栈、退栈和读栈顶元素栈的基本运算有三种：入栈、退栈和读栈顶元素在顺序栈中插入和删除运算不需要在顺序栈中插入和删除运算不需要移动表中其他数据元素。移动表中其他数据元素。37第38页2.栈的顺序存储结构及其基本运算栈的顺序存储结构及其基本运算a2a1a1a2top用顺序存储结构表示的栈用顺序存储结构表示的栈:顺序栈用一组连续的存储单元存放自栈底到栈顶的数据顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量元素，一般用一维数组表示，设置一个简单变量top指示栈顶指示栈顶位置，称为位置，称为针栈顶指针栈顶指，它始终指向待插入元素的位置。它始终指向待插入元素的位置。基本运算：基本运算：压（进）栈：压（进）栈：PUSH出栈：出栈：POP读栈顶元素：读栈顶元素：gettop38第39页例子：例子：topbaseEDCBAtopbaseCBAbasetopAbasetop空桟：空桟：topbase非空桟：非空桟：top始终在桟顶元素的后一个位置始终在桟顶元素的后一个位置桟的元素个数：桟的元素个数：top-base上溢上溢下溢下溢39第40页2 2、队列、队列定义：定义：一种特殊的线性结构，限定只能在表的一端进行插入，一种特殊的线性结构，限定只能在表的一端进行插入，在在表的另一端进行删除的线性表表的另一端进行删除的线性表。此种结构称为。此种结构称为先进先出先进先出（FIFO）表。）表。a1,a2,a3,a4,an-1,an队队列列示示意意图图队队头头队队尾尾先进先出先进先出后进后出后进后出（LIFO）40第41页e3e4 (c)(c)e1,e2出队，出队，e4入队入队 队队满满rear=3fronte1e2e3 (b)rearfront(b)e1,e2,e3入队入队队列的顺序存储结构及其基本运算队列的顺序存储结构及其基本运算 3210 (a)rear=front=-1(队空）队空）rearfront空队列空队列:非空队列非空队列:队列元素个数队列元素个数:rear=front=-1front始终指向队头元素前一个位置，而始终指向队头元素前一个位置，而rear始终指向队始终指向队尾元素的位置尾元素的位置rear-front41第42页队列的物理存储结构可以用顺序结构，也可以用链式结队列的物理存储结构可以用顺序结构，也可以用链式结构。构。u顺序队列的运算顺序队列的运算栈有三种操作：栈有三种操作：入栈出栈读栈顶元素入栈出栈读栈顶元素队列有三种操作：入队出队读队首元素队列有三种操作：入队出队读队首元素例：有入栈元素序列：例：有入栈元素序列：ABCD，求可能的出栈序列，求可能的出栈序列如是队列又是什么情况呢？如是队列又是什么情况呢？42第43页uu 循环队列循环队列循环队列循环队列 把队列的存储空间在逻辑上看作一个环，当把队列的存储空间在逻辑上看作一个环，当R指向存指向存储空间的末端后，就把它重新置于始端。储空间的末端后，就把它重新置于始端。u循环队列的运算循环队列的运算进行删除的一端称做队首进行删除的一端称做队首(front)。队列中进行插入的一端称做队列中进行插入的一端称做队尾队尾(rear),习题：数据结构分为逻辑结构和存储结构，循环队习题：数据结构分为逻辑结构和存储结构，循环队列属于列属于【】结构。（结构。（2005年年9月）月）答案：答案：存储结构。存储结构。43第44页frontrearMaxsize-101e3e4 rear=3front44第45页0012345frontABCDEFrear上溢上溢0012345frontrear下溢下溢front=rear队满队满front=rear队空队空45第46页数据存储结构方面的考题数据存储结构方面的考题1：数据的存储结构是指：数据的存储结构是指（2005年年4月）月）A)存储在外存中的数据存储在外存中的数据B)数据所占的存储空间量数据所占的存储空间量C)数据在计算机中的顺序存储方式数据在计算机中的顺序存储方式D)数据的逻辑结构在计算机中的表示数据的逻辑结构在计算机中的表示2.下列叙述中正确的是下列叙述中正确的是（2009年年3月）月）A）栈是）栈是“先进先出先进先出”的线性表的线性表B）队列是）队列是“先进后出先进后出”的线性表的线性表C）循环队列是非线性结构）循环队列是非线性结构D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构3.数据结构分为线性结构和非线性结构，带链的队列属于数据结构分为线性结构和非线性结构，带链的队列属于。4.下列数据结构中，属于非线性结构的是下列数据结构中，属于非线性结构的是A）循环队列）循环队列B)带链队列带链队列C)二叉树二叉树D）带链栈）带链栈答案：答案：D。答案：答案：D。答案：线性结构。答案：线性结构。答案：答案：c46第47页5。下列叙述中正确的是（下列叙述中正确的是（）。）。（2008年年9月）月）A）顺顺序序存存储储结结构构的的存存储储一一定定是是连连续续的的，链链式式存存储储结结构构的的存存储储空空间不一定是连续的间不一定是连续的B）顺顺序序存存储储结结构构只只针针对对线线性性结结构构，链链式式存存储储结结构构只只针针对对非非线线性性结构结构C）顺序存储结构能存储有序表，链式存储结构不能存储有序表）顺序存储结构能存储有序表，链式存储结构不能存储有序表D）链式存储结构比顺序存储结构节省存储空间）链式存储结构比顺序存储结构节省存储空间答案：答案：A。6 6。下列关于栈的叙述正确的是。下列关于栈的叙述正确的是 （2008年年4月）月）A A）栈按）栈按“先进先出先进先出”组织数据组织数据 B)B)栈按栈按“先进后出先进后出”组织数据组织数据 C C）只能在栈底插入数据）只能在栈底插入数据 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，147第48页9.设某循环队列的容量为设某循环队列的容量为50，如果头指针，如果头指针front=45(指向指向队头元素的前一位置队头元素的前一位置)，尾指针，尾指针rear=10(指向队尾元素指向队尾元素)，则该循环队列中共有，则该循环队列中共有【2】个元素。个元素。（2010年年3月）月）8。假设用一个长度为。假设用一个长度为50的数组（数组元索的下标从的数组（数组元索的下标从0到到49）作为栈的存储空间，栈底指针）作为栈的存储空间，栈底指针bottom指间栈底指间栈底元素，栈顶指针元素，栈顶指针top指向栈顶元素，如果指向栈顶元素，如果bottom=49，top=30（数组下标），则栈中具有（数组下标），则栈中具有【】个元素。个元素。（2009年年3月）月）答案：答案：19答案：答案：15465011048u链表不具有的特点是链表不具有的特点是A)不必事先估计存储空间不必事先估计存储空间B)可随机访问任一元素可随机访问任一元素C)插入删除不需要移动元素插入删除不需要移动元素D)所需空间与线性表长度成正比所需空间与线性表长度成正比u数据结构分为逻辑结构与存储结构，线性链表属于数据结构分为逻辑结构与存储结构，线性链表属于【1】。u数据结构中，与所使用的计算机无关的是数据的数据结构中，与所使用的计算机无关的是数据的A)存储结构存储结构B)物理结构物理结构C)逻辑结构逻辑结构D)物理和存储结构物理和存储结构u数据的逻辑结构有线性结构和数据的逻辑结构有线性结构和【1】两大类。两大类。u数据的存储结构是指数据的存储结构是指A）数据所占的存储空间）数据所占的存储空间B）数据的逻辑结构在计算机中的表示）数据的逻辑结构在计算机中的表示C）数据在计算机中的顺序存储方式）数据在计算机中的顺序存储方式D）存储在外存中的数据）存储在外存中的数据例题讲解例题讲解存储结构存储结构 非线性结构非线性结构49u顺序存储方法是把逻辑上相邻的结点存储在物理位置顺序存储方法是把逻辑上相邻的结点存储在物理位置【2】的存储单元的存储单元中。中。u数据处理的最小单位是数据处理的最小单位是A)数据数据B)数据元素数据元素C)数据项数据项D)数据结构数据结构u数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及据结构进行的运算，以及A)数据的存储结构数据的存储结构 B)计算方法计算方法C)数据映象数据映象D)逻辑存储逻辑存储u线性表的顺序存储结构和线性表的链式存储结构分别是线性表的顺序存储结构和线性表的链式存储结构分别是A)顺序存取的存储结构、顺序存取的存储结构顺序存取的存储结构、顺序存取的存储结构B)随机存取的存储结构、顺序存取的存储结构随机存取的存储结构、顺序存取的存储结构C)随机存取的存储结构、随机存取的存储结构随机存取的存储结构、随机存取的存储结构D)任意存取的存储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构相邻相邻50u根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成构分成A)动态结构和静态结构动态结构和静态结构B)紧凑结构和非紧凑结构紧凑结构和非紧凑结构C)线性结构和非线性结构线性结构和非线性结构D)内部结构和外部结构内部结构和外部结构u数据结构包括数据的逻辑结构、数据的数据结构包括数据的逻辑结构、数据的【2】以及对数据的操作运算。以及对数据的操作运算。u数据的基本单位是数据的基本单位是【5】。u下列叙述中，错误的是下列叙述中，错误的是A)数据的存储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率密切相关B)数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关C)数据的存储结构在计算机中所占的空间不一定是连续的数据的存储结构在计算机中所占的空间不一定是连续的D)一种数据的逻辑结构可以有多种存储结构一种数据的逻辑结构可以有多种存储结构存储结构存储结构数据元素数据元素51u链表不具有的特点是链表不具有的特点是A)不必事先估计存储空间不必事先估计存储空间B)可随机访问任一元素可随机访问任一元素C)插入删除不需要移动元素插入删除不需要移动元素D)所需空间与线性表长度成正比所需空间与线性表长度成正比u顺序