二级公共基础知识ppt课件

*,二 级 公 共 基 础 知 识,考试需知,:,考试内容及安排,第一章,算法与数据结构,第二章,程序设计基础,第三章,软件工程基础,第四章,数据库设计基础,1,一、涉及面广，但难度小,你应该知道,公共基础知识考题特点及复习建议,计算机等级二级理论考试中有关公共知识部分的题目共有15道，涉及,算法及数据结构,、,程序设计基础,、,软件工程基础,和,数据库设计基础,等四门学科，但是从整体上分析，考试中的考核内容的难度不大，考点也相对集中些。,2,二、考核重点为基本概念、基本方法,和基本运算,你应该知道,计算机等级二级理论考试中涉及的题目都是,基本概念,、,基本方法,和,基本运算,，考核以概念和认识性内容为主，理解性、应用性内容极少。,3,三、考核重点是数据结构和算法,你应该知道,以下是对以往二级理论考试的大概统计：,算法及数据结构,： 50%,程序设计基础,：12.5%,软件,工程基础,：18.75%,数据库设计基础,：18.75%,4,四、六点复习及应试建议,复习的关键是,考生必须准确判断和掌握常见考点,公共基础知识部分的知识点多、杂，考生在学习过程中应理,清其中的,脉络关系（即框架提纲）,，才能有效地组织和记住,各知识点,考生,不要太追求灵活掌握该部分的内容,，最好经历一个“,先死,后活、熟能生巧,”的过程，这是多数考生常犯的另一种错误,最后给大家一个,答题技巧,：“,会就会，不会就不会,”，,不要拖,时间，要考虑成本/效果的关系，为后面的题目提供时间,。,5,你应该知道,共讲授,20,个学时，具体安排如下：,第 周 （ 月 日）：,算法、数据结构,（上）,（地点：,）,第 周 （ 月 日）：,数据结构,(,下）、软件工程、程序设计基础,（地点：,）,第 周 （ 月 日）：,数据库系统、真题讲解,（地点：,）,本 课 程 授 课 安 排,6,1、了解算法的基本概念和一些,常用的算法,，学会计算算法的,时间复杂度,；,2、掌握数据结构的基本概念，并了解数据的,逻辑结构,和,存储结构,，学会利,用图形的方式表示数据结构 ；,学,习,目,标,与,要,求,算法与数据结构：,3、了解线性表的基本概念，并掌握线性表的顺序存储结构以及顺序存储的,线性表的基本运算；,4、了解栈和队列的基本概念，并掌握它们的基本运算；,5、了解线性链表的基本概念，并掌握线性链表的基本运算，同时，了解循,环链表的基本概念和基本操作；,6、理解树的概念，尤其是二叉树的基本概念和相关性质，掌握二叉树的存,储结构和遍历技术；,7、掌握查找技术，学会利用顺序查找和二分查找在数列中查找指定的数据；,8、学会利用相关的排序技术实现无序数列的排序操作。,7,1、了解软件工程的基本概念；,2、了解软件工程过程与软件的生命周期，以及软件工程的目标和原则；,学,习,目,标,与,要,求,软件工程,：,3、了解利用结构化分析法进行软件工程中的需求分析的方法，并了解需,求分析的方法和需要完成的任务；,4、了解数据流图的使用方法；,5、了解如何利用结构化设计方法进行软件设计，并了解软件设计的一些,常用工具；,6、了解软件测试的目的和方法，以及软件测试的准则，了解常用的软件,测试方法的区别和各自的功能与特点；,7、了解程序调试的方法和原则 。,8,1、了解程序设计的方法，以及程序设计风格确立的一些因素，掌握程序,设计的基本规则；,2、了解结构化程序设计的基本原则，掌握结构化程序设计的基本结构与特点;,学,习,目,标,与,要,求,程序设计基础,：,3、了解面向对象的程序设计方法，并理解面向对象方法的一些基本概念。,数据库系统,：,1、了解数据库系统的基本概念，以及数据库系统的发展；,2、了解数据模型的基本概念，并对,E-R,模型、层次模型、网状模型和关系模型,进行了解，并掌握关系模型的数据结构、关系的操作和数据约束等知识；,3、了解关系模型的基本操作，掌握关系模型的基本运算及扩充运算；,4、了解数据库的设计与管理，掌握数据库设计的几个阶段的方法和特点。,9,程,序,设,计,基,本,概,念,一、 计算机工作原理,通过工作原理了解，熟悉计算机内部执行功能的基本意义。为理解程序打下基础，特别理解计算机是机器。,二、 程序的定义,指令的集合。（解释指令）,通过硬件控制系统自动完成某一功能。,通过一系列代码实现。,10,程,序,设,计,基,本,概,念,三、 程序怎样执行、如何编写程序,计算机本身仅能识别二进制代码,“,0,”,、,“,1,”,。,编程最直接、最低级的就是机器语言。,为解决机器语言难理解、记忆等问题。出现符号语言。,为使编程接近自然语言，出现高级语言。如,C、PASCAL、FORTRAN,等。,为配合高级语言编程，出现了开发工具，提高效率、减轻劳动量。如,VB、VC、PB、Delphi、VFP,等。因此,VFP,不是编程语言。,11,程,序,设,计,基,本,概,念,不管什么形式编写代码，最终都应将代码翻译成机器语言，,这就是编译程序的工作。不同的语言有不同的编译器。,程序控制是一种逻辑控制。因此，严谨的逻辑思维是一个,程序员必备的基本素质。,用程序实现某一功能。有许多方法。具体用哪种完全取决,于程序员个人的思维方式。因此，程序是脑力劳动的结晶，,从某种意义上，编程又是一门艺术。,程序的特殊性决定了程序的复杂性，且与实现功能的复杂,性密切相关成正比。因此为使复杂的、智力的编程工作规,范化、科学化，便出现了各种编程设计方法。如结构化编,程方法、面向对象的程序设计方法等。,12,程,序,设,计,基,本,概,念,不管用什么方法编程，不管编程者智力程度如何，不管,采用什么样的编程语言和方法，程序最终完成的功能稳,定、可靠、实用、易维护和安全等是程序的最终目标，,也是程序员的追求。,程序设计是一个复杂艰巨的过程。编写代码仅是程序设,计的一部分。必须先有思想，再有方法，然后才是编写,代码，且要经过许多反复，不可急功近利。,13,程,序,设,计,基,本,概,念,四、 程序设计语言或工具,程序设计语言指的是用来编写程序的语言。,人与计算机交流要使用语言，以便让计算机工作，计算,机也通过语言把结果告诉用计算机的人“人机对,话”。,人与计算机交流的语言非平常人与人之间交流的语言，,是专门的语言程序设计语言。,程序设计语言是计算机系统软件的重要组成部分。,14,程,序,设,计,基,本,概,念,执行程序设计的语言有很多，可分高级语言和低级语言，,区别在于接近自然语言的程度,高级语言一般与具体的计算机硬件无关，比较接近人类,自然语言的语法习惯及数学表达形式。,用高级语言编写的源程序不能被机器直接执行，需通过,编译成解释程序的翻译才可被机器执行（机器语言）。,四、 程序设计语言或工具（续）,15,第一章 算法与数据结构,二级公共基础知识,返回,16,算,法,与,数,据,结,构,一、算法,1、算法的基本概念,算法,是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。它是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。,算法具有,有穷性,、,确定性,、,可行性,、,输入,和,输出,（拥有足够的情报）等个重要特性。,17,学,习,目,标,与,要,求,2、算法的基本要素,对数据对象的,运算,和,操作,：,算术运算、逻辑运算、关系运算、数据传输,算法中各操作之间的执行顺序；,描述算法的工具通常有传统流程图、,N-S,结构化流程,图、算法描述语言等；,一个算法一般可以用,顺序,、,选择,、,循环,三种基本结构,组合而成。,算法的,控制结构,：,18,算,法,与,数,据,结,构,3、算法设计的基本方法,列举法,归纳法,递推,递归（以简洁的形式设计和描述算法）,减半递推技术,回溯法,19,算,法,与,数,据,结,构,二、算法的复杂度,1、时间复杂度,依据算法编制的程序在计算机上运行时所消耗的时间,来度量。通常有,事后统计法,和,事前分析估算法,。,一个算法是由,控制结构,（顺序、分支和循环）和,原操,作,构成的，算法时间取决于两者的综合效果。,算法中基本操作重复执行次数,n,和算法执行时间同步,增长，称作算法的,时间复杂度,。,20,算,法,与,数,据,结,构,2、空间复杂度,一般是指执行这个算法所需要的,内存空间,。,一个算法所占用的存储空间包括,算法程序,所占的空间、,输入的初始数据,所占的存储空间以及,某种数据结构,所需,要的附加存储空间。,一个上机执行的程序除了需要存储空间来寄存本身所用,指令、常数、变量和输入数据外，也需要一些对数据进,行操作的工作单元和存储一些为实现计算所需信息的辅,助空间。,21,算,法,与,数,据,结,构,3、例题讲解,算法的时间复杂度是指(,C,),A、,执行算法程序所需要的时间,B、,算法程序的长度,C、,算法执行过程中所需要的基本运算次数,D、,算法程序中的指令条数,算法的基本特征是可行性、确定性、,【1】,和拥有足够,的情报。,【答案】,:,有穷性,算法的空间复杂度是指(,D,),A),算法程序的长度,B),算法程序中的指令条数,C),算法程序所占的存储空间,D),执行过程中所需要的存储空间,22,算,法,与,数,据,结,构,在计算机中，算法是指（,B,）,A),加工方法,B),解题方案的准确而完整的描述,C),排序方法,D),查询方法,算法分析的目的是(,D,),A),找出数据结构的合理性,B),找出算法中输入和输出之间的关系,C),分析算法的易懂性和可靠性,D),分析算法的效率以求改进,算法的工作量大小和实现算法所需的存储单元多少分别称,为算法的,【 1 】,。,【答案】,:,时间复杂度和空间复杂度,23,算,法,与,数,据,结,构,三、数据结构（,Data Structure,）,1、数据结构研究的主要内容,当今计算机应用的,特点,：,1、所处理的数据量大且具有一定的关系；,2、对其操作不再是单纯的数值计算，而更多地是需,要对其进行组织、管理和检索。,对数据的讨论不单是数据本身，还要包括数据与数据之间的关系。,24,特点：,每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；,表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的,线性结构,；,对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等。,应用举例,1学籍档案管理,假设一个学籍档案管理系统应包含如下表所示的学生信息。,25,应用举例,2,家庭血缘关系图,表示家庭成员的辈分关系，,使用下图1-1所示的形式描述。,图 1-1,家庭血缘关系图,特点：,在求解过程中，所处理的数据之间具有层次关系，这是我们,所说的,树形结构,；,对它的操作有：建立树形结构，输出终结点内容等。,26,应用举例,3,制定教学计划,在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示：,27,这种数据可以用下面的图来表示：,27,课程先后关系的图形描形式：,c1,c9,c4,c2,c12,c10,c11,c5,c3,c6,c7,c8,图 1-2 计算机专业必修课程开设先后关系,28,28,1、数据的,逻辑结构,2、数据的,存储结构,3、数据的,运算,：检索、排序、插入、删除、修改等。,A,线性结构,B,非线性结构,A,顺序存储,B,链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(亦称物理结构),数据结构的主要研究问题：,29,29,2、基本概念和术语,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,例：,整数,(1,2)、,实数,(1.1,1.2),字符串,(,Beijing)、,图形,、,声音,。,计算机管理图书问题 ：,在图书馆里有各种卡片：有按书名编排的、有按作,者编排的、有按分类编排。如何将查询图书的这些信息,存入计算机中既要考虑查询时间短，又要考虑节省空间。,最简单的办法之一是建立一张表，每一本书的信息在表,中占一行，如：,30,30,数据元素在计算机中的表示,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,如何将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,对数据结构中的节点进行操作处理,（插入、删除、修改、查找、排序）,31,31,数据元素(,Data Element),数据元素是数据的基本单位，即数据集合中的个体。,有时一个数据元素可由若干,数据项,(,Data Item,),组成。数据项是数据的最小单位。,数据元素亦称,节点,或,记录,。,数据结构可描述为,Group=（D，R）,有限个数据元素的集合,有限个节点间关系的集合,32,32,数据结构可描述为,Group=（D，R）,例,1,：一年四季的数据结构可表示成,B=,（,D,，,R,）,D=,春，夏，秋，冬,R=,（春，夏），（夏，秋），（秋，冬）,例,2,：家庭成员数据结构可表示成,B=,（,D,，,R,）,D=,父亲，儿子，女儿,R=,（父亲，儿子），（父亲，女儿）,冬,春,夏,秋,父亲,儿子,女儿,33,数据结构也可用图形表示,一年四季的数据结构可表示成,家庭成员数据结构可表示成,冬,春,夏,秋,父亲,儿子,女儿,（ 概念：结点、前件、后件、根结点、叶子 ）,34,树形结构,全校学生档案管理的组织方式,计算机程序管理系统也是典型的,树形结构,。,35,H,G,F,E,C,D,B,A,树形结构 结点间具有分层次的连接关系,H,B,C,D,E,F,G,A,36,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),图形结构节点间的连结是任意的,1,4,2,3,37,3、例题讲解,数据处理的最小单位是(,C,),A),数据,B),数据元素,C),数据项,D),数据结构,数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及(,A,),A),数据的存储结构,B),计算方法,C),数据映象,D),逻辑存储,数据结构包括数据的逻辑结构、数据的,【4】,以及对数据的操作运算。,【答案,】,物理结构（或存储结构）,38,线性结构与非线性结构：,线性结构：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。,如：一年四季，,26,个英文字母,非线性结构：线性以外的数据结构。,如：反映家庭成员间辈分关系的数据结构,算,法,与,数,据,结,构,39,4,、线性表,（,Linear List）,学 生 成 绩 表,(,按成绩排列,),86,胡孝臣,9861103,95,刘忠赏,9861107,100,张卓,9861109,成 绩,姓 名,学 号,线性表结点间是以线性关系联结：,线性表,：具有线性结构的有限序列。,数据元素在线性表中的位置只取决于它们自己的序号，,即数据元素之间的相对位置是线性的。,40,线性表的定义:,线性表,是,n,个元素的有限序列，它们之间的关系可以排成,一个线性序列：,a1，a2， ，,ai,， ，an,其中,n,称作表的,长度,，当,n=0,时，称作,空表,。,线性表的特点：,1、线性表中所有元素的性质相同。,2、除第一个和最后一个数据元素之外，其它数据元素有且,仅有一个前驱和一个后继。第一个数据元素无前驱，最,后一个数据元素无后继。,3、数据元素在表中的位置只取决于它自身的序号。,在线性表上常用的运算有：,初始化、求长度、取元素、修改、前插、删除、检索、排序,41,41,线性表的,顺序存储结构,及其,插入,与,删除,操作,特点：,1、线性表中数据元素类型一致，只有,数据域,，存储空间,利用率高。,2、所有元素所占的存储空间是连续的。,3、各数据元素在存储空间中是按,逻辑顺序,依次存放的,（,a）,做插入、删除时需移动大量元素。,（,b）,空间估计不明时，按最大空间分配。,算,法,与,数,据,结,构,42,顺序存储,存储地址,存储内容,元素,n,.,元素,i,.,元素2,元素1,L,o,L,o,+,m,L,o,+(i-1),m,Lo+（n-1),m,Loc(,元素,i)=L,o,+（i-1),m,每个元素所占用,的存储单元个数,线性表的,顺序存储结构,：,首地址,起始地址,基地址,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,45,在进行删除操作时，若假定删除每个元素的可能性均等，,则平均移动元素的个数为：,分析结论,顺序存储结构表示的线性表，在做插入或删除操作时，平,均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。,删除算法的分析,46,46,线性表的例题讲解,顺序存储方法是把逻辑上相邻的结点存储在物理位置,【1】,的存储单元中。,【答案,】,相邻,长度为,n,的顺序存储线性表中，当在任何位置上插入一个元,素概率都相等时，插入一个元素所需移动元素的平均个数,为,【2】,。,【答案,】,n/2,线性表,L=(a1,a2,a3,ai,，an)，,下列说法正确的是（,D,）,A),每个元素都有一个直接前件和直接后件,B),线性表中至少要有一个元素,C),表中诸元素的排列顺序必须是由小到大或由大到小,D),除第一个元素和最后一个元素外，其余每个元素都有一,个且只有一个直接前件和直接后件,47,47,数据结构中，与所使用的计算机无关的是数据的(,C,),A),存储结构,B),物理结构,C),逻辑结构,D),物理和存储结构,下列叙述中，错误的是（,B,）,A),数据的存储结构与数据处理的效率密切相关,B),数据的存储结构与数据处理的效率无关,C),数据的存储结构在计算机中所占的空间不一定是连续的,D),一种数据的逻辑结构可以有多种存储结构,数据的存储结构是指（,B,）,A）,数据所占的存储空间,B）,数据的逻辑结构在计算机中的表示,C）,数据在计算机中的顺序存储方式,D）,存储在外存中的数据,48,根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成(,C,),A),动态结构和静态结构,B),紧凑结构和非紧凑结构,C),线性结构和非线性结构,D),内部结构和外部结构,数据的逻辑结构有线性结构和,【2】,两大类。,非线性结构,当线性表采用顺序存储结构实现存储时，其主要特点是,【1】,。,【答案,】,逻辑结构中相邻的结点在存储结构中仍相邻。,49,49,5、堆栈和队列,堆栈和队列的定义,栈和队列,是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为,限定性的数据结构。,堆栈的定义,堆栈：,限定只能在表的一端进行插入和删除的特殊的线性表,此种,结构称为,后进先出。,设栈,s=（a,1,，a,2,，a,i,， ，a,n,）,其中,a,1,是,栈底,元素，,a,n,是,栈顶,元素。,栈顶（,top)：,允许插入和删除的一端；,约定,top,始终指向新数据元素将存放的位置。,栈底,（,bottom):,不允许插入和删除的一端。,a,1,a,2,.,a,n,进栈,出栈,栈顶,栈底,50,50,a,1,a,2,.,a,n,进栈,出栈,栈顶,栈底,51,51,队列的定义,队列：,一种特殊的线性结构，限定只能在表的一端进行插入，,在表的另一端进行删除的线性表。此种结构称为,先进,先出（,FIFO）,表,。,a,1,a,2,a,3,a,n-1,a,n,队 列 示 意 图,队头,队尾,队列的主要运算,（,1）设置一个空队列；,（2）插入一个新的队尾元素，称为进队；,（3）删除队头元素，称为出队；,（4）读取队头元素。,52,出队,入队,rear,front,52,循环队列及其运算,循环,队列：,将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。,循环队列的元素：,从排头指针指向的后一个位置直到队尾指针指向的位置之间所有的元素。,说明：,为了能够区分队列满与空，设置一个标志,s,。,53,s=,0,表示队列空,1,表示队列非空,队列空与满的条件：,队列空时，,s=0,；,队列满时，,s=1,且,front=rear,。,53,循环队列的运算：,入队运算和退队运算,入队运算：是指在循环队列中的队尾加入一新元素。,具体操作：,（,1,）将队尾指针进一，即,rear=rear+1,。,注：当,rear=m+1,时，重置,rear=1,。,（,2,）将新元素插入到,rear,指向的位置。,注：当,s=1,且,rear=front,时，循环队列满，不能再进行入队运算，称为“上溢”。,退队运算：是指在循环队列的排头位置退出一个元素并赋给指定的变量。,具体操作：,（,1,）将排头指针进一，即,front=front+1,。,注：当,front=m+1,时，重置,front=1,。,（,2,）将排头指针指向位置的后一个元素赋给指定的变量。,注：当,s=0,时，循环队列为空，再不能进行退队运算，称为“下溢”。,54,54,堆栈和队列的例题讲解,栈和队列的共同特点是（,C,）,A),都是先进先出,B),都是先进后出,C),只允许在端点处插入和删除元素,D),没有共同点,如果进栈序列为,e1,e2,e3,e4，,则可能的出栈序列是（,B,）,A) e3,e1,e4,e2,B) e4,e3,e2,e1,C) e3,e4,e1,e2 D),任意顺序,一些重要的程序语言(如,C,语言和,Pascal,语言) 允许过程的递归调用。而实现递归调用中的存储分配通常用（,A,）,A),栈,B),堆,C),数组,D),链表,55,55,栈底至栈顶依次存放元素,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),顺序表,56,56,当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为,【2】,。,答案：,上溢,由两个栈共享一个存储空间的好处是（,B,）,A),减少存取时间，降低下溢发生的机率,B),节省存储空间，降低上溢发生的机率,C),减少存取时间，降低上溢发生的机率,D),节省存储空间，降低下溢发生的机率,下列关于栈的叙述中正确的是（,D,）,)在栈中只能插入数据,B）,在栈中只能删除数据,C）,栈是先进先出的线性表,D）,栈是后进先出的线性表,下列关于队列的叙述中正确的是（,C,）,）在队列中只能插入数据,B）,在队列中只能删除数据,C）,队列是先进先出的线性表,D）,队列是后进先出的线性表,57,57,顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。,顺序存储结构的三个,缺点,：,1.作插入或删除操作时，需移动大量元数。,2.长度变化较大时，需按最大空间分配。,3.表的容量难以扩充。,存储内容,元素,n,.,元素,i,.,元素2,元素1,58,58,6、线性链表,线性链表的基本概念：,线性表的链式存储结构称为,线性链表,。,为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每一小块占若干字节，通常称这些小块为存储结点。,算,法,与,数,据,结,构,59,将存储空间中的每一个存储结点分为两部：,一部分称为,数据域,，用于存储数据元素的值,；,另一部分称为,指针域,，用于存放下一个数据元素的存储序号,（,即存储结点的地址,），,也就是指向后件结点。,线性链表中存储结点的结构如图2.20所示,60,60,1、比顺序存储结构的存储密度小,(每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。,2、逻辑上相邻的节点物理上不必相邻。,3、插入、删除灵活,(不必移动节点，只要改变节点中的指针)。,4,、查找结点时链式存储要比顺序存储慢。,链式存储结构特点：,算,法,与,数,据,结,构,61,线性链表的物理结构,算,法,与,数,据,结,构,线性链表的逻辑结构图,HEAD,：指向线性表中第一个结点的指针，称为,头指针,。,当,HEAD=NULL,（或0）时称为,空表,。,对于线性链表，可以从头指针开始，沿着各个结点的指针扫描到链表中的所有结点。,62,63,为了弥补线性单链表的这个缺点，在某些应用中，对线性链表中的每个结点设置两个指针，一个称为,左指针（,Llink,），,用以指向其前件结点；另一个称为,右指针（,Rlink,），,用以指向其后件的结点。,这样的线性链表称为,双向链表,，其逻辑状态如图,2.23,所示。,63,线性链表的基本运算：,线性链表的运算主要有以下几个：, 在线性链表中包含指定元素的结点之前,插入,一个新元素。, 在线性链表中,删除,包含指定元素的结点。, 将两个线性链表按要求,合并,成一个线性,链表。,64,线性链表的,插入,运算：,线性链表的插入,是指在链式存储结构下,的线性表中插入一个新元素。,为了要在线性链表中插入一个新元素，,首先要给该元素分配一个新结点，然后将存,放新元素值的结点链接到线性链表中指定的,位置。,算,法,与,数,据,结,构,65,66,66,线性链表的删除,指在链式存储结构下的,线性表中删除包含指定元素的结点。,为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，然后将要删除结点放回到可利用栈。,线性链表的,删除,运算：,算,法,与,数,据,结,构,67,68,68,循环链表的结构与前面所讨论的线性链表相比，具有以下,两个特点：, 循环链表的头指针指向表头结点。, 在循环链表中，所有结点的指针构成了一个环状链。,图2.29是循环链表的示意图。,循环链表：,69,69,在实际应用中，循环链表与线性单链表相比主要有以下两个方面的优点：, 在循环链表中，只要指出表中任何一个结点 的位置，就可以从它出发访问到表中其他所有的结点。, 由于在循环链表中设置了一个表头结点，因 此，在任何情况下，循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。,算,法,与,数,据,结,构,70,链表不具有的特点是（,B,）,A),不必事先估计存储空间,B),可随机访问任一元素,C),插入删除不需要移动元素,D),所需空间与线性表长度成正比,数据结构分为逻辑结构与存储结构，线性链表属于,【1】,。,【答案,】,存储结构,线性表的顺序存储结构和线性表的链式存储结构分别是,(,B,),A),顺序存取的存储结构、顺序存取的存储结构,B),随机存取的存储结构、顺序存取的存储结构,C),随机存取的存储结构、随机存取的存储结构,D),任意存取的存储结构、任意存取的存储结构,线性链表的例题讲解,71,71,7、树与二叉树：,树的基本概念：,前面我们讨论的线性表，栈、队列和数组等都是,线性结构,。而,树,是一种,非线性数据结构,，它的每一个结点，都可以有不止一个直接后继，除根外的所有结点，都有且只有一个直接前趋。这些数据结点按分支关系组织起，清晰地反映了数据元素之间的层次关系。,72,算,法,与,数,据,结,构,现实世界中，能用树的结构表示的例子,：,学校的行政关系（,P31,）、书的层次结构（,P32,）、人类的家族血缘关系等。,73,74,例：下图是一个有,13,个结点的树，其中,A,是根，其余结点为分三个互不相交的子集：,T1,B,E,F,K,L,T2,F,G,T3,D,H,I,J,M,T1,、,T2,和,T3,都是根,A,的子树。,74,75,树结构的基本术语：,结点的度,：结点所拥有子树的个数，图中,A,的度为,3,，,C,的度为,1,，,F,的度为,0,。,叶子结点：,树中度为,0,的结点，图中的,K,、,L,、,F,、,G,、,M,、,I,、,J,均称为叶子结点（或终端结点）。,子结点与父结点：,把每一个结点的一个或多个后件称为该点的子结点；反之，这个结点称为其子结点的父结点，同一个父结点的子结点之间互称为兄弟。,树的度：,树中各结点的度的最大值，度不为,0,的结点为非终端结点同，又叫分支结点。,森林：,N0,或,N=0,棵互不相交的树的集合组成森林。图中将根结点,A,去掉，其中三棵子树就组成一个森林。,树的深度,：树中结点的最大层次称为树的深度或高度。图中树的深度为,4,。,75,二叉树,是一种很有用的非线性结构。,二叉树具有以下两个特点：,（1）非空二叉树只有一个根结点；,（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。,二叉树（,Binary Tree）：,因为树的每个结点的度不同，存储困难，使得对树的处理算法很复杂。所以引出二叉树的讨论。,76,76,77,77,性质1,：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。,例子1,：某二叉树中度为2的结点有18个，则该二叉树中有,19,个叶子结点。,二叉树的性质：,特别要注意：,二叉树不是,树的特殊情况。,a,a,b,b,两棵不同的二叉树,78,78,性质2,：二叉树的第,i,层上至多有2,i-1,（i,1）,个结点,二叉树的性质：,4,2,3,1,6,7,8,9,10,11,12,13,14,15,5,第一层(,i=1)，,有2,1-1,=1,个节点。,第二层(,i=2)，,有2,2-1,=2,个节点。,第三层(,i=3)，,有2,3-1,=4个节点。,第四层(,i=4)，,有2,4-1,=8个节点。,79,二叉树的性质：,性质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个节点。,1+2+4+2,m-1,=2,m-1,(,等比数列前,M,项和,),80,满二叉树与完全二叉树,满二叉树,是指除最后一层外，每一层上的所有结点都有两个子结点。,完全二叉树,是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。,注意：,满二叉树是完全二叉树，完全二叉树不一定是满二叉树。,算,法,与,数,据,结,构,81,满二叉树的特点：,每一层上都含有最大结点数。,82,82,完全二叉树的特点：,除最后一层外，每一层都取最大 结点数，最后一层结点都集中在该层最左边的若干位置,83,83,84,84,对于,完全二叉树,而言,如果它的结点个数为,偶,数，则该二叉树中：,叶子结点的个数=非叶子结点的个数,如果它的结点个数为,奇,数，则该二叉树中：,叶子结点的个数=非叶子结点的个数+1,（即叶子结点数比非叶子结点数,多一个,）,规律总结：,算,法,与,数,据,结,构,1,2,3,4,1,2,3,4,5,2,叶子结点,3,2,非叶子结点,2,85,例题讲解,1、设一棵完全二叉树共有700个结点，则在该二叉树中有,350,个叶子结点。,2、在深度为5的满二叉树中，叶子结点的个数为（,C,）,A) 32 B) 31,C) 16,D) 15,算,法,与,数,据,结,构,86,二叉树的遍历,二叉树的遍历,是指不重复地访问二叉树中的所有结点。,二叉树的遍历可以分为三种：,前序,遍历、,中序,遍历、,后序,遍历。,设访问根结点记作,V；,遍历根的左子树记作,L；,遍历根的右子树记作,R；,前序：,VLR（,即根左右）,中序：,LVR（,即左根右）,后序：,LRV（,即左右根）,87,87,88,4 10 8 9 5 2 6 7 3 1,例：结合下图所示的二叉树，写出该二叉树的前序、中序及后序遍历结果。,后序遍历：,中序遍历：,前序遍历：,1 2 4 5 8 10 9 3 6 7,4 2 10 8 5 9 1 6 3 7,88,1、设一棵二叉树的中序遍历结果为,DBEAFC,前序遍历结果为,ABDECF，,则后序遍历结果为：,DEBFCA,例题讲解,2、已知一棵二叉树前序遍历和中序遍历分别为,ABDEGCFH,和,DBGEACHF，,则该二叉树的后序遍历为（,B,）,A) GEDHFBCA,B) DGEBHFCA,C) ABCDEFGH D) ACBFEDHG,89,具有3个结点的二叉树有（,D,）,A) 2,种形态,B) 4,种形态,C) 7,种形态,D) 5,种形态,设有下列二叉树：,对此二叉树前序遍历的结果为（,B,）,A) ZBTTCPXA,B) ATBZXCTP,C) ZBTACTXP D) ATBZXCPT,90,90,8、查找和排序：,查找又称为,检索,查找算法的评价主要考虑算法的时间复杂性，既可以采用数量级的形式表示，也可以采用平均检索（查找）长度，即在查找成功情况下的平均比较次数来表示。,查找可分为,顺序查找,和,二分法查找,两种。,算,法,与,数,据,结,构,91,（,a）,顺序查找：,顺序查找,又称,线性查找,。它是一种最简单、最基本的查找方法。基本思想是：从表中第一条记录开始，逐个进行记录的关键字和给定值的比较。若某个记录的关键字和给定值相等，则查找成功；否则，若直至最后一个记录，其关键字和给定值都不相等，则表明表中没有所查记录，查找不成功。,算,法,与,数,据,结,构,92,二分查找,又称,折半查找,。作为二分查找对象的表必须是顺序存储的有序表，即各记录的次序是按其关键字的大小顺序（以下假定按从小到大的顺序）排列的表。,（,b）,二分查找：,算,法,与,数,据,结,构,93,二分查找的,具体做法,是: 先取表,中间,位置的记录关键字与给定值比较。若相等, 则查找成功；否则, 若给定值比该记录的关键字小，则给定值必在表的前半部分。在这前半部分中再取中间位置记录的关键字进行比较，就又可以排除这部分的一半。依次反复进行，直到找到给定值或找完全表而找不到为止。,对于,n,较大时，查找长度可以近似地表示为,算,法,与,数,据,结,构,94,排序,是将一组杂乱无章的数据按一定的规律顺次排列起来。,通常数据对象有多个属性域，即由多个数据成员组成, 其中有一个属性域可用来区分对象,作为排序依据。该域称为,关键字（,key）,。,排序的时间开销是衡量算法好坏的最重要的标志。对于长度为,n,的有序线性表，查找时最坏情况只需比较,n,次。,排序（,sort）,95,（,a）,交换类排序：,交换类排序法：,冒泡排序法,：需要比较的次数为,n(n-1)/2,快速排序法,：是对冒泡排序的改进，是目,前内部排序中速度最快的一种。,算,法,与,数,据,结,构,96,（,b）,插入类排序：,插入类排序的,基本方法,是：每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止,。,简单插入排序法：,最坏情况需要,n(n-1)/2,次比较；,希尔排序法：,最坏情况需要,O（n,1.5,）,次比较。,算,法,与,数,据,结,构,97,（,c）,选择类排序：,选择类排序的,思想,是：每一趟（例如，第,i,趟，,i=0，1，n2）,在后面,ni,个待排序对象中选,出关键字最小（升序，若为降序，选出最大关键,字）的对象，作为有序对象序列的第,i,个对象。待,到第,n2,趟作完，待排序对象只剩下1个，不用再,选了，结束排序。,简单选择排序法,，最坏情况需要,n(n-1)/2,次比较；,堆排序法,，最坏情况需要,O（nlog,2,n）,次比较。,98,第二章 程序设计基础,二级公共基础知识,返回,99,内容,1,、程序设计方法与风格,2,、结构化程序设计,3,、面向对象的程序设计方法，对象、方法、属性及继承与多态性。,程,序,设,计,基,础,100,程,序,设,计,基,础,（一）程序设计方法与风格,如何形成良好的程序设计风格：,1、源程序内部文档化；,选择标识符的名字,注释（,序言性,和,功能性,注释）,程序的视觉组织,一般位于模块的首部，用于说明模块的相关信息,位于源程序,模块内部,风格：,清晰第一，效率第二。,101,显式地说明一切变量,数据说明的次序应该规范化,便于查找变量（按顺序排列）,对复杂数据结构应注释说明,2、数据说明,程,序,设,计,基,础,3、语句的结构,每条语句简单明了,限制,GOTO,语句的使用,(,尽量不用或少用,),尽量只采用3种基本控制结构编程,102,4、输入和输出,对所有输入数据进行校验和合理性检查,输入输出格式保持一致,设计良好的输出报表,输入方式,应力求简单，尽量避免给用户带来不必要的麻烦；,交互式输入数据时应有必要的提示信息; 程序应对输入数据的,合法性进行检查;若用户输入某些数据后可能产生严重后果,应,给用户输出必要的提示并要求用户确认；应根据系统的特点和,用户的习惯设计出令用户满意的输入方式。,输出数据的格式,应清晰，美观；输出数据时要加上必要的,提示信息。,103,103,主要思想：,对大型的程序设计，使用一些基本的结构来设计程序，无论多复杂的程序，都可以使用这些基本结构按一定的顺序组合起来。这些基本结构的特点都是只有一个入口、一个出口。由这些基本结构组成的程序就避免了任意转移、阅读起来需要来回寻找的问题。,程,序,设,计,基,础,（二）结构化程序设计,三种基本结构的特点,只有一个入口,只有一个出口,基本结构中的每一部分都有机会执行到,结构内不存在“死循环”,三种基本结构,顺序结构,选择结构,循环结构,104,程,序,设,计,基,础,设计原则,自顶向下,逐步求精,模块化,限制使用,goto,语句,（二）结构化程序设计,结构化程序设计方法,1,、要求把程序的结构规定为顺序、选择和循环三种基本机构，并提出了自顶向下、逐步求精、模块化程序设计等原则。,2,、结构化程序设计是把模块分割方法作为对大型系统进行分析的手段，使其最终转化为三种基本结构，其目的是为了解决由许多人共同开发大型软件时，如何高效率地完成可靠系统的问题。,3,、程序的可读性好、可维护性好成为评价程序质量的首要条件。,4,、缺点：程序和数据结构松散地耦合在一起。解决此问题的方法就是采用面向对象的程序设计方法,(OOP),。,105,（三）面向对象的程序设计方法,面向对象的程序设计（,Object-Oriented,Programming，OOP,）,是一种把面向对象的,思想应用于软件开发过程中，指导开发活动,的系统方法，简称,OOP,方法，它是建立在对,象概念（对象、类和继承）基础上的方法。,程,序,设,计,基,础,106,面向对象程序设计方法的优点,1,、与人类习惯的思维方法一致,2,、稳定性好,3,、可重用性好,4,、易于开发大型软件产品,5,、可维护性好,程,序,设,计,基,础,107,基本概念,对象,(Object),对象是基本的运行时认得实体，它既包括数据（属性），也包括作用于数据的操作（行为）。,一个对象把属性和行为封装为一个整体。,一个对象通常可由对象名、属性和操作,3,部分组成。,属性,：通常是一些数据，有时它也可以是另一个对象。,事件,：是由对象识别的一个动作，用户可以编写相应代码对此动作进行响应，如单击、双击、移动等。,方法,：对象中的属性只能通过该对象所提供的操作来存取或修改。,面向对象,(Object Oriented, OO),从该问题所涉及的对象入手来研究问题。,108,消息,(Message),对象之间进行通信的一种构造,类（,Class,）,：,类是一组具有相同属性和相同操作的对象的集合。,一个类定义了一组大体上相似的对象。,一个类所包含的方法和数据描述一组对象的共同行为和属性。,类是在对象之上的抽象，对象是类的具体化，是类的实例。,基类,：,用来生成新类的类。,派生类,：,由已存在的类派生出来的新类，也叫子类。,继承,：,是指能够直接获得已有的性质和特征，而不必重复定义他们。继承分单继承和多重继承。,109,水上交通工具,陆上交通工具,水陆两用交通工具,多 重 继 承 图,程,序,设,计,基,础,单继承,指一个类只允许有一个父类，,多重继承,指一个类允许有多个父类。,110,程,序,设,计,基,础,封装,(Encapsulation),将数据和操作数据的函数衔接在一起，构成一个具有类类型的对象的描述。,对象的内部实现受保护，外界不能访问,封装简化了程序员对对象的使用,多态性,(Polymorphism),不同的对象收到同一消息可以产生完全不同的结构，这一现象叫做多态性,多态的实现受到继承的支持,111,四、例题讲解：,程,序,设,计,基,础,结构化程序设计的3种结构是（,D,）,A),顺序结构、选择结构、转移结构,B),分支结构、等价结构、循环结构,C),多分支结构、赋值结构、等价结构,D),顺序结构、选择结构、循环结构,在设计程序时，应采纳的原则之一是（,D,）,A),不限制,goto,语句的使用,B),减少或取消注解行,C),程序越短越好,D),程序结构应有助于读者理解,112,程序设计语言的基本成分是数据成分、运算成分、控制成,分和（,D,）,A),对象成分,B),变量成分,C),语句成分,D),传输成分,程,序,设,计,基,础,结构化程序设计主要强调的是（,D,）,A),程序的规模,B),程序的效率,C),程序设计语言的先进性,D),程序易读性,以下不属于对象的基本特点的是（,C,）,A),分类性,B),多态性,C),继承性,D),封装性,113,对建立良好的程序设计风格，下面描述正确的是（,A,）,A),程序应简单、清晰、可读性好,B),符号名的命名只要符合语法,C),充分考虑程序的执行效率,D),程序的注释可有可无,在结构化程序设计思想提出之前，在程序设计中曾强调程序,的效率，现在，与程序的效率相比，人们更重视程序的（,C,）,A),安全性,B),一致性,C),可理解性,D),合理性,程,序,设,计,基,础,114,下列叙述中，不属于结构化程序设计方法的主要原则的是（,B,）,A),自顶向下,B),由底向上,C),模块化,D),限制使用,goto,语句,对象实现了数据和操作的结合，是指对数据和数据的操作进行（,C,）,A),结合,B),隐藏,C),封装,D),抽象,在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送（,D,）,A）,调用语句,B）,命令,C）,口令,D）,消息,程,序,设,计,基,础,115,信息屏蔽的概念与下述哪一种概念直接相关（,B,）,A）,软件结构定义,B）,模块独立性,C）,模块类型划分,D）,模块耦合度,下列对对象概念描述错误的是（,A,）,A）,任何对象都必须有继承性,B）,对象是属性和方法的封装体,C）,对象间的通讯靠消息传递,D）,操作是对象的动态属性,程,序,设,计,基,础,116,面向对象的设计方法与传统的面向过程的方法有本质的不同,它的基本原理是（,C,）,A),模拟现实世界中不同事物之间的联系,B),强调模拟现实世界中的算法而不强调概念,C),使用现实世界的概念抽象地思考问题从而自然地解决问题,D),鼓励开发者在软件开发的绝大部分中都用实际领域的概念去思考,在面向对象的程序设计中，类描述的是具有相似性质的一组,【1】,。,【答案,】,对象,在面向对象方法中，类之间共享属性和操作的机制称为,【2】,。,【答案,】,继承,一个类可以从直接或间接的祖先中继承所有属性和方法。采用这个方法提高了软件的,【3】,。,【答案,】,可重用性,117,在面向对象的模型中，最基本的概念是对象和,【4】,。,【答案】：,类,在面向对象的设计中，用来请求对象执行某一处理或回答某些信息的要求称为,【5】,。,【答案】：,消息,在程序设计阶段应该采取,【6】,和逐步求精的方法，把一个模块的功能逐步分解，细化为一系列具体的步骤，进而用某种程序设计语言写成程序。,【答案】,：,自顶向下,程,序,设,计,基,础,118,【7】,是一种信息隐蔽技术，目的在于将对象的使用者和对象的设计者分开。,【答案】,：