分享
分销 收藏 举报 申诉 / 180

类型国家二级计算机access-公共基础知识课件.ppt

  • 上传人:快乐****生活
  • 文档编号:14590501
  • 上传时间:2026-10-17
  • 格式:PPT
  • 页数:180
  • 大小:1.35MB
  • 下载积分:10 金币
  • 配套讲稿:

    如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

    特殊限制:

    部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

    关 键  词:
    国家 二级 计算机 access 公共 基础知识 课件
    资源描述:
    *,*,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,国家二级计算机access 公共基础知识课件,国家二级计算机access 公共基础知识课件国家二级计算机access 公共基础知识课件,一、涉及面广,但难度小,你应该知道,公共基础知识考题特点及复习建议,计算机等级二级理论考试中有关公共知识部分的题目共有15道,涉及,算法及数据结构,、,程序设计基础,、,软件工程基础,和,数据库设计基础,等四门学科,但是从整体上分析,本次考试中的考核内容的难度不大,考点也相对集中些。,2,二、考核重点为基本概念、基本方法,和基本运算,你应该知道,计算机等级二级理论考试中涉及的题目都是,基本概念,、,基本方法,和,基本运算,,考核以概念和认识性内容为主,理解性、应用性内容极少。,3,三、考核重点是数据结构和算法,你应该知道,以下是对以往二级理论考试的大概统计:,算法及数据结构,:50%,程序设计基础,:12.5%,软件工程基础,:18.75%,数据库设计基础,:18.75%,4,1、了解算法的基本概念和一些常用的算法,学会计算算法的时间复杂度;,2、掌握数据结构的基本概念,并了解数据的逻辑结构和存储结构,学会利,用图形的方式表示数据结构;,学,习,目,标,与,要,求,算法及数据结构:,3、了解线性表的基本概念,并掌握线性表的顺序存储结构以及顺序存储的,线性表的基本运算;,4、了解栈和队列的基本概念,并掌握它们的基本运算;,5、了解线性链表的基本概念,并掌握线性链表的基本运算,同时,了解循,环链表的基本概念和基本操作;,6、理解树的概念,尤其是二叉树的基本概念和相关性质,掌握二叉树的存,储结构和遍历技术;,7、掌握查找技术,学会利用顺序查找和二分查找在数列中查找指定的数据;,8、学会利用相关的排序技术实现无序数列的排序操作。,5,1、了解软件工程的基本概念;,2、了解软件工程过程及软件的生命周期,以及软件工程的目标和原则;,学,习,目,标,与,要,求,软件工程,:,3、了解利用结构化分析法进行软件工程中的需求分析的方法,并了解需,求分析的方法和需要完成的任务;,4、了解数据流图的使用方法;,5、了解如何利用结构化设计方法进行软件设计,并了解软件设计的一些,常用工具;,6、了解软件测试的目的和方法,以及软件测试的准则,了解常用的软件,测试方法的区别和各自的功能及特点;,7、了解程序调试的方法和原则。,6,1、了解程序设计的方法,以及程序设计风格确立的一些因素,掌握程序,设计的基本规则;,2、了解结构化程序设计的基本原则,掌握结构化程序设计的基本结构及特点;,学,习,目,标,与,要,求,程序设计基础,:,3、了解面向对象的程序设计方法,并理解面向对象方法的一些基本概念。,数据库系统,:,1、了解数据库系统的基本概念,以及数据库系统的发展;,2、了解数据模型的基本概念,并对,E-R,模型、层次模型、网状模型和关系模型,进行了解,并掌握关系模型的数据结构、关系的操作和数据约束等知识;,3、了解关系模型的基本操作,掌握关系模型的基本运算及扩充运算;,4、了解数据库的设计及管理,掌握数据库设计的几个阶段的方法和特点。,7,程,序,设,计,基,本,概,念,一、计算机工作原理,通过工作原理了解,熟悉计算机内部执行功能的,基本意义。为理解程序打下基础,特别理解计算机是,机器。,二、程序的定义,指令的集合。(解释指令),通过硬件控制系统自动完成某一功能。,通过一系列代码实现。,8,程,序,设,计,基,本,概,念,三、程序怎样执行、如何编写程序,计算机本身仅能识别二进制代码“0”、“1”。,编程最直接、最低级的就是机器语言。,为解决机器语言难理解、记忆等问题。出现符号语言。,为使编程接近自然语言,出现高级语言。如,C、PASCAL、FORTRAN,等。,为配合高级语言编程,出现了开发工具,提高效率、减轻劳动量。如,VB、VC、PB、Delphi、VFP,等。因此,VFP,不是编程语言。,9,程,序,设,计,基,本,概,念,不管什么形式编写代码,最终都应将代码翻译成机器语言,,这就是编译程序的工作。不同的语言有不同的编译器。,程序控制是一种逻辑控制。因此,严谨的逻辑思维是一个,程序员必备的基本素质。,用程序实现某一功能。有许多方法。具体用哪种完全取决,于程序员个人的思维方式。因此,程序是脑力劳动的结晶,,从某种意义上,编程又是一门艺术。,程序的特殊性决定了程序的复杂性,且及实现功能的复杂,性密切相关成正比。因此为使复杂的、智力的编程工作规,范化、科学化,便出现了各种编程设计方法。如结构化编,程方法、面向对象的程序设计方法等。,10,程,序,设,计,基,本,概,念,四、程序设计语言或工具,程序设计语言指的是用来编写程序的语言。,人及计算机交流要使用语言,以便让计算机工作,计算,机也通过语言把结果告诉用计算机的人“人机对,话”。,人与计算机交流的语言非平常人与人之间交流的语言,,是专门的语言程序设计语言。,程序设计语言是计算机系统软件的重要组成部分。,11,程,序,设,计,基,本,概,念,执行程序设计的语言有很多,可分高级语言和低级语言,,区别在于接近自然语言的程度,高级语言一般及具体的计算机硬件无关,比较接近人类,自然语言的语法习惯及数学表达形式。,用高级语言编写的源程序不能被机器直接执行,需通过,编译或解释程序的翻译才可被机器执行(机器语言)。,四、程序设计语言或工具(续),12,算,法,与,数,据,结,构,一、算法(,algorithm,),1、算法的基本概念,算法,是对特定问题求解步骤的一种准确而完整的描述,,,*:算法不等于程序,也不等于计算方法。,算法具有,有穷性,、,确定性,、,可行性,、,输入,和,输出,(拥有足够的情报)等个重要特性。,13,算法的基本特征,(,1,),可行性。,针对实际问题而设计的算法,执行后能够得到满意的结果。(,2,),确定性。,每一条指令的含义明确,无二义性。并且在任何条件下,算法只有唯一的一条执行路径,即,相同的输入只能得出相同的输出。,(,3,),有穷性。,算法必须在有限的时间内完成。有两重含义,一是算法中的操作步骤为有限个,二是每个步骤都能在有限时间内完成。,(,4,),拥有足够的情报。,算法中各种运算总是要施加到各个运算对象上,而这些运算对象又可能具有某种初始状态,这就是算法执行的起点或依据。因此,,一个算法执行的结果总是及输入的初始数据有关,不同的输入将会有不同的结果输出。,当输入不够或输入错误时,算法将无法执行或执行有错。一般说来,当算法拥有足够的情报时,此算法才是有效的;而当提供的情报不够时,算法可能无效。,14,学,习,目,标,与,要,求,2、算法的基本要素,对数据对象的,运算,和,操作,:,算术运算、逻辑运算、关系运算、数据传输,算法中各操作之间的执行顺序;,描述算法的工具通常有传统流程图、,N-S,结构化流程,图、算法描述语言等;,一个算法一般可以用,顺序,、,选择,、,循环,三种基本结构,组合而成。,算法的,控制结构,:,15,算,法,与,数,据,结,构,3、算法设计的基本方法,列举法,归纳法,递推,递归(以简洁的形式设计和描述算法),减半递推技术,回溯法,16,算,法,与,数,据,结,构,二、算法的复杂度(,包括,时间复杂度,和,空间复杂度,),(,1,)算法时间复杂度是指执行算法所需要的计算工作量,,可以用执行算法的过程中所需基本运算的执行次数来度量。,(,2,)算法空间复杂度是指执行这个算法所需要的内存空间,包括算法程序所占空间,输入的初始数据所占空间和执行过程中所需要的额外空间。,17,算,法,与,数,据,结,构,3、例题讲解,算法的时间复杂度是指(,C,),A、,执行算法程序所需要的时间,B、,算法程序的长度,C、,算法执行过程中所需要的基本运算次数,D、,算法程序中的指令条数,算法的基本特征是可行性、确定性、,【1】,和拥有足够,的情报。,【答案】,:,有穷性,算法的空间复杂度是指(,D,),A),算法程序的长度,B),算法程序中的指令条数,C),算法程序所占的存储空间,D),执行过程中所需要的存储空间,18,算,法,与,数,据,结,构,在计算机中,算法是指(,B,),A),加工方法,B),解题方案的准确而完整的描述,C),排序方法,D),查询方法,算法分析的目的是(,D,),A),找出数据结构的合理性,B),找出算法中输入和输出之间的关系,C),分析算法的易懂性和可靠性,D),分析算法的效率以求改进,算法的工作量大小和实现算法所需的存储单元多少分别称,为算法的,【1】,。,【答案】,:,时间复杂度和空间复杂度,19,算,法,与,数,据,结,构,三、数据结构(,Data Structure,),1、数据结构研究的主要内容,当今计算机应用的,特点,:,1、所处理的数据量大且具有一定的关系;,2、对其操作不再是单纯的数值计算,而更多地是需,要对其进行组织、管理和检索。,应用举例,1学籍档案管理,假设一个学籍档案管理系统应包含如下表1-1所示的学生信息。,20,特点:,每个学生的信息占据一行,所有学生的信息按学号顺序依,次排列构成一张表格;,表中每个学生的信息依据学号的大小存在着一种前后关系,,这就是我们所说的线性结构;,对它的操作通常是插入某个学生的信息,删除某个学生的,信息,更新某个学生的信息,按条件检索某个学生的信息,等等。,21,应用举例,2,输出,n,个对象的全排列,输出,n,个对象的全排列可以使用下图1-1所示的形式描述。,图 1-1 3个对象的全排列过程,特点:,在求解过程中,所处理的数据之间具有层次关系,这是我们,所说的,树形结构,;,对它的操作有:建立树形结构,输出最低层结点内容等等。,22,应用举例,3,制定教学计划,在制定教学计划时,需要考虑各门课程的开设顺序。有些课程需要先导课程,有些课程则不需要,而有些课程又是其他课程的先导课程。比如,计算机专业课程的开设情况如下表所示:,23,课程先后关系的图形描形式:,c1,c9,c4,c2,c12,c10,c11,c5,c3,c6,c7,c8,图 1-2 计算机专业必修课程开设先后关系,24,结论:,数据结构主要研究以下三个方面的问题:,数据的逻辑结构,:,数据集合中各数据元素之间所固有的逻辑关系,,包含:,1,)表示数据元素的信息;,2,)表示各数据元素之间的前后件关系,数据的存储结构,:,在对数据进行处理时,各数据元素在计算机中的存储关系,,,数据的存储结构有顺序、链接、索引等,。,对各种数据结构进行的运算,*:数据的逻辑结构反映数据元素之间的逻辑关系,数据的存储结构(也称数据的物理结构)是数据的逻辑结构在计算机存储空间中的存放形式。同一种逻辑结构的数据可以采用不同的存储结构,但影响数据处理效率。,算,法,与,数,据,结,构,25,2、基本概念和术语,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,例:,整数,(1,2)、,实数,(1.1,1.2),字符串,(,Beijing)、,图形,、,声音,。,计算机管理图书问题:,在图书馆里有各种卡片:有按书名编排的、有按作,者编排的、有按分类编排。如何将查询图书的这些信息,存入计算机中既要考虑查询时间短,又要考虑节省空间。,最简单的办法之一是建立一张表,每一本书的信息在表,中占一行,如:,26,数据元素在计算机中的表示,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,如何将0,1,2,3,4,5,6,7,8,9这10个数存放,在计算机中能最快地达到你所需要的目的?,目的不同,,最佳,的存储方方法就不同,。,从大到小排列:,9,8,7,6,5,4,3,2,1,0,输出偶数:,0,2,4,6,8,1,3,5,7,9,对数据结构中的节点进行操作处理(插入、删除、修改、查找、排序),27,数据元素(,Data Element),数据元素是数据的基本单位,即数据集合中的个体。,有时一个数据元素可由若干,数据项,(,Data Item,),组成。数据项是数据的最小单位。,PS:,数据元素是数据的基本单位,数据项是属于数据元素的!数据项是最小单位!,数据元素亦称,节点,或,记录,。,数据结构可描述为,Group=(D,R),有限个数据元素的集合,有限个节点间关系的集合,28,数据结构可描述为,Group=(D,R),1、数据的,逻辑结构,2、数据的,存储结构,3、数据的,运算,:检索、排序、插入、删除、修改等。,A,线性结构,B,非线性结构,A,顺序存储,B,链式存储,线性表,堆栈,队列和线性链表,树形结构,图形结构,数据结构的三个方面,(亦称物理结构),条件:,1,)有且只有一个根结点;,2,)每一个结点最多有一个前件,也最多有一个后件。,不满足线性结构条件的数据结构。,29,线性结构:,例如:,A,B,C,,X,Y,Z,学 生 成 绩 表,86,胡孝臣,95,刘忠赏,100,张卓,成 绩,姓 名,学 号,线性表结点间是以线性关系联结:,算,法,与,数,据,结,构,30,树形结构,全校学生档案管理的组织方式,计算机程序管理系统也是典型的,树形结构,。,31,H,G,F,E,C,D,B,A,树形结构 结点间具有分层次的连接关系,H,B,C,D,E,F,G,A,32,1,4,2,3,D=1,2,3,4,R=(1,2),(1,3),(1,4),(2,3),(3,4),(2,4),2,1,3,D=1,2,3,R=(1,2),(2,3),(3,2),(1,3),图形结构节点间的连结是任意的,33,顺序存储,存储地址,存储内容,元素,n,.,元素,i,.,元素2,元素1,L,o,L,o,+m,L,o,+(i-1)*m,Lo+(n-1)*,m,m,是每个元素所占用,的存储单元个数,顺序存储结构具有两个基本特点:,(,1,)所有元素所占的存储空间是连续的;,(,2,)各数据元素在存储空间中是按逻辑顺序依次存放的,数据的,存储结构,顺序存储,34,链 式 存 储,h,每个节点都由两部分组成:,数据域,和,指针域,。,数据域,存放元素本身的数据,,指针域,存放指针。,数据元素之间逻辑上的联系由指针来体现。,1536,元素2,1400,元素1,1346,元素3,元素4,1345,1345,1346,元素3,1536,.,.,.,1536,元素2,1400,.,.,.,元素4,1346,1400,元素1,1345,指针,存储内容,存储地址,数据的,存储结构,35,1、比顺序存储结构的占用的存储空间要大,(每个节点都由数据域和指针域组成)。,2、逻辑上相邻的节点物理上不必相邻。,3、插入、删除灵活,(不必移动节点,只要改变节点中的指针)。,链式存储结构特点:,算,法,与,数,据,结,构,36,3、例题讲解,链表不具有的特点是(,B,),A),不必事先估计存储空间,B),可随机访问任一元素,C),插入删除不需要移动元素,D),所需空间及线性表长度成正比,数据结构中,与所使用的计算机无关的是数据的(,C,),A),存储结构,B),物理结构,C),逻辑结构,D),物理和存储结构,数据的逻辑结构有线性结构和,【2】,两大类。,非线性结构,37,顺序存储方法是把逻辑上相邻的结点存储在物理位置,【3】,的存储单元中。,【答案,】,相邻,数据处理的最小单位是(,C,),A),数据,B),数据元素,C),数据项,D),数据结构,数据结构作为计算机的一门学科,主要研究数据的逻辑结构、对各种数据结构进行的运算,以及(,A,),A),数据的存储结构,B),计算方法,C),数据映象,D),逻辑存储,线性表的顺序存储结构和线性表的链式存储结构分别是(,B,),A),顺序存取的存储结构、顺序存取的存储结构,B),随机存取的存储结构、顺序存取的存储结构,C),随机存取的存储结构、随机存取的存储结构,D),任意存取的存储结构、任意存取的存储结构,38,根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分成(,C,),A),动态结构和静态结构,B),紧凑结构和非紧凑结构,C),线性结构和非线性结构,D),内部结构和外部结构,数据结构包括数据的逻辑结构、数据的,【4】,以及对数据的操作运算。,【答案,】,物理结构(或存储结构),数据的基本单位是,【5】,。,【答案,】,数据元素,3、例题讲解,39,下列叙述中,错误的是(,B,),A),数据的存储结构及数据处理的效率密切相关,B),数据的存储结构与数据处理的效率无关,C),数据的存储结构在计算机中所占的空间不一定是连续的,D),一种数据的逻辑结构可以有多种存储结构,数据的存储结构是指(,B,),A),数据所占的存储空间,B),数据的逻辑结构在计算机中的表示,C),数据在计算机中的顺序存储方式,D),存储在外存中的数据,3、例题讲解,40,4、线性表(,Linear List),线性表的定义:,线性表,是,n,个元素的有限序列,它们之间的关系可以排成,一个线性序列:,a1,a2,ai,an,其中,n,称作表的,长度,,当,n=0,时,称作,空表,。,线性表的特点:,1、线性表中所有元素的性质相同。,2、除第一个和最后一个数据元素之外,其它数据元素有且,仅有一个前驱和一个后继。第一个数据元素无前驱,最,后一个数据元素无后继。,3、数据元素在表中的位置只取决于它自身的序号。,在线性表上常用的运算有:,初始化、求长度、取元素、修改、前插、删除、检索、排序。,41,线性表的顺序存储结构及其插入及删除操作,特点:,1、线性表中数据元素类型一致,只有数据域,存储空间,利用率高。,2、所有元素所占的存储空间是连续的。,3、各数据元素在存储空间中是按逻辑顺序依次存放的,(,a),做插入、删除时需移动大量元素。插入运算时平均需要移动,n/2,个元素;删除运算时,平均需要移动(,n-1,),/2,个元素。,(,b),空间估计不明时,按最大空间分配。,(,c,),不便于对存储空间的动态分配。,算,法,与,数,据,结,构,42,顺序存储结构示意图(顺序表):,元素,an,.,元素,ai,.,元素,a2,元素,a,1,b,b+m,b+(i-1)*m,b+(maxlen-1)*m,存储地址,内存状态,Loc,(,元素,i,),=b+(i-1)*,m,每个元素所占用,的存储单元个数,首地址,起始地址,基地址,*:由此可以看出,在线性表的顺序存储结构中,其前后件两个元素在存储空间中是紧邻的,且前件元素一定存储在后件元素的前面,可以通过计算机直接确定第,i,个结点的存储地址。,43,元素,a,1,元素,a,2,.,元素,a,i+1,.,0,1,i,线性表的顺序存储结构,可用,C,语言中的一维数组来描述.,第,i,个元素的,a,i,存储地址:,Loc(a,i,)=Loc(a,1,)+(i-1)*m,V,V,Vi,Vm-1,int VM;,其中:,V,是数组的名字,,M,是数组大小,,假设数组中的元素是整型类型,算,法,与,数,据,结,构,44,插入运算,.,a,2,a,1,a,n,.,a,i+1,a,i,0,1,i-1,i,n-1,a,i-1,.,a,2,a,1,a,length,a,i+1,a,i,x,a,i-1,.,a,2,a,1,X,a,i,a,i+1,.,a,length,插入算法的分析,假设线性表中含有,n,个数据元素,在进行插入操作时,若,假定在,n+1,个位置上插入元素的可能性均等,则平均移动元素,的个数为:,45,删除算法的分析,在进行删除操作时,若假定删除每个元素的可能性均等,,则平均移动元素的个数为:,分析结论,顺序存储结构表示的线性表,在做插入或删除操作时,平,均需要移动大约一半的数据元素。当线性表的数据元素量较大,并且经常要对其做插入或删除操作时,这一点需要值得考虑。,46,线性链表 线性表的链式存储结构,线性链表:,线性表的链式存储结构称为线性链表,,是一种物理存储单元上,非连续、非顺序,的存储结构,数据元素的逻辑顺序是通过链表中的指针链接来实现的。因此,在链式存储方式中,每个结点由两部分组成:一部分用于存放数据元素的值,称为,数据域,;另一部分用于存放指针,称为,指针域,,用于指向该结点的前一个或后一个结点(即前件或后件),如下图所示:,47,线性链表的基本运算,(,1,)在线性链表中包含指定元素的结点之前插入一个新元素。,*:,在线性链表中插入元素时,不需要移动数据元素,只需要修改相关结点指针即可,,也不会出现“,上溢,”现象。,(,2,)在线性链表中删除包含指定元素的结点。,*:,在线性链表中删除元素时,也不需要移动数据元素,只需要修改相关结点指针即可,。,(,3,)将两个线性链表按要求合并成一个线性链表。,(,4,)将一个线性链表按要求进行分解。,(,5,)逆转线性链表。,(,6,)复制线性链表。,(,7,)线性链表的排序。,(,8,)线性链表的查找。,*:线性链表不能随机存取。,48,线性链表的插入运算:,线性链表的插入,是指在链式存储结构下的线性表中插入一个新元素。,为了要在线性链表中插入一个新元素,首先要给该元素分配一个新结点,然后将存放新元素值的结点链接到线性链表中指定的位置。,算,法,与,数,据,结,构,49,50,线性链表的删除,指在链式存储结构下的,线性表中删除包含指定元素的结点。,为了在线性链表中删除包含指定元素的,结点,首先要在线性链表中找到这个结点,,然后将要删除结点放回到可利用栈。,线性链表的删除运算:,算,法,与,数,据,结,构,51,52,53,循环链表的结构及前面所讨论的线性链表相比,具有以下,两个特点:,循环链表的头指针指向表头结点。,在循环链表中,所有结点的指针构成了一个环状链。,图2.29是循环链表的示意图。,循环链表:,54,在实际应用中,循环链表及线性单链表相,比主要有以下两个方面的优点:,在循环链表中,只要指出表中任何一个结点,的位置,就可以从它出发访问到表中其他所有的结点。,由于在循环链表中设置了一个表头结点,因,此,在任何情况下,循环链表中至少有一个结点存在,从而使空表与非空表的运算统一。,算,法,与,数,据,结,构,55,线性表的例题讲解,顺序存储方法是把逻辑上相邻的结点存储在物理位置,【1】,的存储单元中。,【答案,】,相邻,长度为,n,的顺序存储线性表中,当在任何位置上插入一个元,素概率都相等时,插入一个元素所需移动元素的平均个数,为,【2】,。,【答案,】,n/2,线性表,L=(a1,a2,a3,ai,an),,下列说法正确的是(,D,),A),每个元素都有一个直接前件和直接后件,B),线性表中至少要有一个元素,C),表中诸元素的排列顺序必须是由小到大或由大到小,D),除第一个元素和最后一个元素外,其余每个元素都有一,个且只有一个直接前件和直接后件,56,57,当线性表采用顺序存储结构实现存储时,其主要特点是,【1】,。,【答案,】,逻辑结构中相邻的结点在存储结构中仍相邻。,线性表若采用链式存储结构时,要求内存中可用存储单,元的地址(,D,),A),必须是连续的,B),部分地址必须是连续的,C),一定是不连续的,D),连续不连续都可以,下列叙述中,错误的是(,B,),A),数据的存储结构及数据处理的效率密切相关,B),数据的存储结构与数据处理的效率无关,C),数据的存储结构在计算机中所占的空间不一定是连续的,D),一种数据的逻辑结构可以有多种存储结构,下列叙述中正确的是,A,)线性链表是线性表的链式存储结构,B,)栈与队列是非线性结构,C,)双向链表是非线性结构,D,)只有根结点的二叉树是线性结构下列对于线性,58,下列叙述中正确的是,A),线性表的链式,存储,结构及顺序存储结构所需要的存储空间是相同的,B),线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构,C),线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构,D),上述三种说法都不对,下列对于线性链表的描述中正确的是,_,。,A,)存储空间不一定是连续,且各元素的存储顺序是任意的,B,)存储空间不一定是连续,且前件元素一定存储在后件元素的前面,C,)存储空间必须连续,且前件元素一定存储在后件元素的前面,D,)存储空间必须连续,且各元素的存储顺序是任意的,下列叙述中正确的是,A,)一个逻辑数据结构只能有一种存储结构,B,)数据的逻辑结构属于线性结构,存储结构属于非线性结构,C,)一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理的效率,D,)一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理的效率,59,5、堆栈和队列,堆栈和队列的定义,栈和队列,是两种特殊的线性表,,它们是运算时要受到某些限制的线性表,故也称为,限定性的数据结构。,堆栈的定义,堆栈:,限定只能在表的一端进行插入和删除的特殊的线性表,此种,结构称为,后进先出。,设栈,s=(a,1,,a,2,,a,i,,a,n,),其中,a,1,是,栈底,元素,,a,n,是,栈顶,元素。,栈顶(,top):,允许插入和删除的一端;,约定,top,始终指向新数据元素将存放的位置。,栈底,(,bottom):,不允许插入和删除的一端。,a,1,a,2,.,a,n,进栈,出栈,栈顶,栈底,60,队列的定义,队列:,一种特殊的线性结构,限定只能在表的一端进行插入,,在表的另一端进行删除的线性表 。此种结构称为,先进,先出(,FIFO),表,。,a,1,a,2,a,3,a,4,a,n-1,a,n,队 列 示 意 图,队头,队尾,队列的主要运算,(,1)设置一个空队列;,(2)插入一个新的队尾元素,称为进队;,(3)删除队头元素,称为出队;,(4)读取队头元素;,61,循环队列及其运算,所谓循环队列,就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。,在循环队列中,用队尾指针,rear,指向队列中的队尾元素,用排头指针,front,指向排头元素的前一个位置,因此,从头指针,front,指向的后一个位置直到队尾指针,rear,指向的位置之间,所有的元素均为队列中的元素。,*:循环队列中元素的个数,=rear-front,。,62,堆栈和队列的例题讲解,栈和队列的共同特点是(,C,),A),都是先进先出,B),都是先进后出,C),只允许在端点处插入和删除元素,D),没有共同点,一些重要的程序语言(如,C,语言和,Pascal,语言)允许过程的递归调用。而实现递归调用中的存储分配通常用(,A,),A),栈,B),堆,C),数组,D),链表,63,栈底至栈顶依次存放元素,A、B、C、D,,在第五个元素,E,入栈前,栈中元素可以出栈,则出栈序列可能是(,B,),A)ABCED,B)DCBEA,C)DBCEA D)CDABE,栈通常采用的两种存储结构是(,A,),A),线性存储结构和链表存储结构,B),散列方式和索引方式,C),链表存储结构和数组,D),线性存储结构和非线性存储结构,栈和队列通常采用的存储结构是,【1】,。,【答案,】,链式存储和顺序存储,下列数据结构中,按先进后出原则组织数据的是(,B,),A),线性链表,B),栈,C),循环链表,D),顺序表,64,下列关于栈的叙述中正确的是(,D,),)在栈中只能插入数据,B),在栈中只能删除数据,C),栈是先进先出的线性表,D),栈是后进先出的线性表,下列关于队列的叙述中正确的是(,C,),)在队列中只能插入数据,B),在队列中只能删除数据,C),队列是先进先出的线性表,D),队列是后进先出的线性表,65,下列叙述中正确的是,A,)在栈中,栈中元素随栈底指针及栈顶指针的变化而动态变化,B,)在栈中,栈顶指针不变,栈中元素随栈底指针的变化而动态变化,C,)在栈中,栈底指针不变,栈中元素随栈顶指针的变化而动态变化,D,)上述三种说法都不对,一个栈的初始状态为空。首先将元素,5,4,3,2,1,依次入栈,然后退栈一次,再将元素,A,B,C,D,依次入栈,之后将所有元素全部退栈,则所有元素退栈(包括中间退栈的元素,),的顺序为,【1】,。,答案:,1DCBA2345,一个队列的初始状态为空。现将元素,A,B,C,D,E,F,5,4,3,2,1,依次入队,然后再依次退队,则元素退队的顺序为,【1】,。,答案:,A,B,C,D,E,F,5,4,3,2,1,下列数据结构中,属于非线性结构的是()。,循环队列,B.,带链队列,C.,二叉树,D.,带链栈,一个栈的初始状态为空。现将元素,1,、,2,、,3,、,4,、,5,、,A,、,B,、,C,、,D,、,E,依次入栈,然后再依次出栈,则元素出栈的顺序是,A,),12345ABCDE,B,),EDCBA54321,C,),ABCDE12345 D,),54321EDCBA,(,2,)下列叙述中正确的是,A,)循环队列有队头和队尾两个指针,因此,循环队列是非线性结构,B,)在循环队列中,只需要队头指针就能反映队列中元素的动态变化情况,C,)在循环队列中,只需要队尾指针就能反映队列中元素的动态变化情况,D,)循环队列中元素的个数是由队头指针和队尾指针共同决定,66,7、树及二叉树:,树的基本概念:,前面我们讨论的线性表,栈、队列和数,组等都是,线性结构,。而,树,是一种,非线性数据,结构,,它的每一个结点,都可以有不止一个,直接后继,除根外的所有结点,都有且只有,一个直接前趋。这些数据结点按分支关系组,织起来,清晰地反映了数据元素之间的层次,关系。,67,算,法,与,数,据,结,构,现实世界中,能用树的结构表示的例子,:,学校的行政关系、书的层次结构、人类的家族血缘关系等。,68,69,70,二叉树具有以下两个特点:,(1)非空二叉树只有一个根结点;,(2)每一个结点最多有两棵子树,且分别称为该结点的左子树及右子树。,*:根据二叉树的概念可知,二叉树的度可以为,0,(叶结点)、,1,(只有一棵子树)或,2,(有,2,棵子树)。,二叉树(,Binary Tree):,因为树的每个结点的度不同,存储困难,使对树的处理算法很复杂。所以引出二叉树的讨论。,71,72,性质1,:在任意一棵二叉树中,度为0的结点,(即叶子结点)总是比度为2的结点多一个。,例子1,:某二叉树中度为2的结点有18个,则,该二叉树中有,19,个叶子结点。,二叉树的性质:,特别要注意:,二叉树不是,树的特殊情况。,a,a,b,b,两棵不同的二叉树,73,例题讲解,1、某二叉树共有,60,个叶子结点及,50,个度为,1,的结点,则该二叉树的总结点数为(,B,),A)148 B)169 C)182 D)198,算,法,与,数,据,结,构,74,性质2,:二叉树的第,i,层上至多有2,i-1,(i,1),个结点。,二叉树的性质:,4,2,3,1,6,7,8,9,10,11,12,13,14,15,5,第三层上(,i=3),,有2,3-1,=4个节点。,第四层上(,i=4),,有2,4-1,=8个节点。,75,二叉树的性质:,性质3,:,深度为,h,的二叉树中至多含有2,h,-1,个结点。,4,2,3,1,6,7,8,9,10,11,12,13,14,15,5,此树的深度,h=4,,共有2,4,-1=15个节点。,76,满二叉树及完全二叉树,满二叉树,是指除最后一层外,每一层上的所,有结点都有两个子结点。,完全二叉树,是指这样的二叉树:除最后一层,外,每一层上的结点数均达到最大值;在最后一,层上只缺少右边的若干结点。,注意:,满二叉树是完全二叉树,完全二叉树,不一定是满二叉树。,算,法,与,数,据,结,构,77,满二叉树的特点:,每一层上都含有最大结点数。,78,完全二叉树的特点:,除最后一层外,每一层都取最大 结点数,最后一层结点都集中在该层最左边的若干位置。,79,对于,完全二叉树,而言,如果它的结点个数为,偶,数,则该二叉树中:叶子结点的个数,=,非叶子结点的个数;如果它的结点个数为,奇,数,则该二叉树中:叶子结点的个数=非叶子结点的个数,+1,,即叶子结点数比非叶子结点数,多一个,。,规律总结:,算,法,与,数,据,结,构,80,例题讲解,1、设一棵完全二叉树共有700个结点,则在该二叉树中有,350,个叶子结点。,2、在深度为5的满二叉树中,叶子结点的个数为(,C,),A)32 B)31,C)16,D)15,3.,一棵二叉树第六层(根结点为第一层)的结点数最多为,【4】,个。,答案:,32,算,法,与,数,据,结,构,81,例题讲解,4,、(,1,)在深度为,7,的满二叉树中,度为,2,的结点个数为,【1】,。,答案:,63,5,、某二叉树中有,n,个度为,2,的结点,则该二叉树中的叶子结点数为,_,。,A,),n+1,B,),n-1C,),2n D,),n/2,6.,某二叉树由,5,个度为,2,的结点以及,3,个度为,1,的结点,则该二叉树中共有,【1】,个结点。,答案:,14,7.,一棵二叉树有,10,个度为,1,的结点,,7,个度为,2,的结点,则该二义树共有,【3】,个结点。,答案:,25,算,法,与,数,据,结,构,82,二叉树的存储结构,在计算机中,二叉树通常采用链式存储结构。,及线性链表类似,用于存储二叉树中各元素的存储结点也由两部分组成:数据域和指针域。但在二叉树中,由于每一个元素可以有两个后件(即两个子结点),因此,用于存储二叉树的存储结点的指针域有两个:一个用于指向该结点的左子结点的存储地址,称为左指针域;另一个用于指向该结点的右子结点的存储地址,称为右指针域。,*:一般二叉树通常采用链式存储结构,对于满二叉树与完全二叉树来说,可以按层序进行顺序存储。这样,不仅节省了存储空间,又能方便地确定每一个结点的父结点与左右子结点的位置,但顺序存储结构对于一般的二叉树不适用。,83,二叉树的遍历,二叉树的遍历,是指不重复地访问二叉树中的所有结点。,二叉树的遍历可以分为三种:,前序,遍历、,中序,遍历、,后序,遍历。,设访问根结点记作,V;,遍历根的左子树记作,L;,遍历根的右子树记作,R;,前序:,VLR(,即,根,左右),中序:,LVR(,即左,根,右),后序:,LRV(,即左右,根,),84,85,1、设一棵二叉树的中序遍历结果为,DBEAFC,前序遍历结果为,ABDECF,,则后序遍历结,果为:,DEBFCA,例题讲解,86,2.,具有3个结点的二叉树有(,D,),A)2,种形态,B)4,种形态,C)7,种形态,D)5,种形态,3.,设有下列二叉树:,对此二叉树前序遍历的结果为(,B,),A)ZBTTCPXA,B)ATBZXCTP,C)ZBTACTXP D)ATBZXCPT,87,例题讲解,5,、,对下列二叉树进行中序遍历的结果是,_,。,A,),ACBDFEG,B,),ACBDFGE,C,),ABDCGEF D,),FCADBEG,6,、,对下列二叉树进行前序遍历的结果为,_,。,A,),DYBEAFCZX B,),YDEBFZXCA,C,),ABDYECFXZ,D,),ABCDEFXYZ,7.,设二叉树如下:,对该二叉树进行后序遍历的结果为,【3】,。,答案:,EDBGHFCA,算,法,与,数,据,结,构,88,8、查找和排序:,查找,又称为,检索,查找算法的评价主要考虑算法的时间复杂,性,既可以采用数量级的形式表示,也可以采,用平均检索(查找)长度,即在查找成功情况,下的平均比较次数来表示。,查找可分为,顺序查找,和,二分法查找,两种。,算,法,与,数,据,结,构,89,(,a),顺序查找:,基本思想:从表中的第一个元素开始,将给定的值及表中逐个元素的关 键字进行比较,直到两者相符,查到所要找的元素为止。否则就是表中没有要找的元素,查找不成功。,在平均情况下,利用顺序查找法在线性表中查找一个元素,大约要与线性表中一半的元素进行比较,最坏情况下需要比较,n,次。,顺序查找一个具有,n,个元素的线性表,其平均复杂度为,O,(,n,)
    展开阅读全文

    开通VIP折扣优惠下载文档

    提示  咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。

    咨信网小贴示:
    1、浏览或下载可查看了解,请点击【咨信网告知】。
    2、下载文件中如有侵权或不适当内容,将立即纠正。
    3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
    4、开具发票登录电脑端申请,请点击【索取发票】。

    咨信网客服组:【微信客服】

    自信AI创作助手
    关于本文
    本文标题:国家二级计算机access-公共基础知识课件.ppt
    链接地址:https://www.zixin.com.cn/doc/14590501.html

    Copyright ©2010-2026   All Rights Reserved  宁波自信网络信息技术有限公司 版权所有   |  客服电话:0574-28810668    微信客服:咨信网客服    投诉电话:18658249818   

    违法和不良信息举报邮箱:help@zixin.com.cn    文档合作和网站合作邮箱:fuwu@zixin.com.cn    意见反馈和侵权处理邮箱:1219186828@qq.com   | 证照中心

    12321jubao.png12321网络举报中心 电话:010-12321  jubao.png中国互联网举报中心 电话:12377   gongan.png浙公网安备33021202000488号  icp.png浙ICP备2021020529号-1 浙B2-20240490   


    关注我们 :微信公众号  抖音  微博  LOFTER               

    自信网络  |  ZixinNetwork