全国计算机等级考试二级公共基础知识

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