二级公共基础知识完整版.ppt

1,一、涉及面广，但难度小,你应该知道,公共基础知识考题特点及复习建议,计算机等级二级理论考试中有关公共知识部分的题目共有15道，涉及算法及数据结构、程序设计基础、软件工程基础和数据库设计基础等四门课程，尽管知识面大，但是从整体上分析，考核的内容难度不大，考点也相对集中些。,2,二、考核重点为基本概念、基本方法和基本运算,你应该知道,计算机等级二级理论考试中涉及的题目都是基本概念、基本方法和基本运算，考核以概念和认识性内容为主，理解性、应用性内容偏少。,3,三、考核重点是数据结构和算法,你应该知道,以下是对以往二级理论考试的大概统计：,算法及数据结构：34%程序设计基础：9%软件工程基础：25%数据库设计基础：29%,4,四、几点复习及应试建议,复习的关键是考生必须准确判断和掌握常见考点公共基础知识部分的知识点多、杂，考生在学习过程中应理清其中的脉络关系（即框架提纲），才能有效地组织和记住各知识点考生一开始学习时不要太追求灵活掌握该部分的内容，经历一个“先熟记,再练习、熟能生巧”的过程，这是多数考生常用的一个方法。多做习题，强化知识点学习。,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,一、算法（algorithm）,1、算法的基本概念(汉诺塔的例子),算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。它是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。算法具有可行性、确定性、有穷性、输入和输出（拥有足够的情报）等个重要特性。,汉诺塔,1-b2-c1-c3-b1-a2-b1-b,a,b,c,1,2,3,算法：,算法：对特定问题求解步骤的一种描述。,算法的描述方法：自然语言、专用工具或某种计算机语言。,返回,10,2、算法的基本要素,(1)对数据对象的运算和操作：算术运算、逻辑运算、关系运算、数据传输,算法中各操作之间的执行顺序；描述算法的工具通常有传统流程图、n-s结构化流程图、算法描述语言等；一个算法一般可以用顺序、选择、循环三种基本结构组合而成。,(2)算法的控制结构：,11,3、算法设计的基本方法及例子,列举法（列出所有可能，再逐一检验，得到符合条件的结果）百钱买百鸡归纳法（通过特殊情况，经过分析，最后找出一般关系）递推（从已知的初始条件出发，逐步推算，得到结果）猴子分食桃子递归（将问题逐层分解，最后归结为一些最简单的问题）求年龄问题减半递推（重复将问题的规模减半，而问题性质不变）二分法求方程实根回溯法（以最优方式向前试探，如果失败，则后退再选）八皇后问题,12,3、算法的复杂度,(1)时间复杂度,依据算法编制的程序在计算机上运行时所消耗的时间来度量。通常有事后统计法和事前分析估算法。一个算法是由控制结构（顺序、分支和循环）和原操作构成的，算法时间取决于两者的综合效果。算法中基本操作重复执行次数n和算法执行时间同步增长，称作算法的时间复杂度。,13,(2)空间复杂度,一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及某种数据结构所需要的附加存储空间。一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。,14,3、例题讲解,算法的时间复杂度是指(c)a、执行算法程序所需要的时间b、算法程序的长度c、算法执行过程中所需要的基本运算次数d、算法程序中的指令条数算法的基本特征是可行性、确定性、【1】和拥有足够的情报。【答案】:有穷性算法的空间复杂度是指(d)a)算法程序的长度b)算法程序中的指令条数c)算法程序所占的存储空间d)执行过程中所需要的存储空间,15,在计算机中，算法是指（b）a)加工方法b)解题方案的准确而完整的描述c)排序方法d)查询方法,算法分析的目的是(d)a)找出数据结构的合理性b)找出算法中输入和输出之间的关系c)分析算法的易懂性和可靠性d)分析算法的效率以求改进算法的工作量大小和实现算法所需的存储单元多少分别称为算法的【1】。【答案】:时间复杂度和空间复杂度,16,二、数据结构（datastructure）,1、数据结构研究的主要内容,当今计算机应用的特点：1、所处理的数据量大且具有一定的关系；2、对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。,对数据的讨论不单单是数据本身，还要包括数据与数据之间的关系。下面各例表示不同的数据采用不同的数据结构来组织。,17,特点：每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。,应用举例1学籍档案管理假设一个学籍档案管理系统应包含如下表所示的学生信息。,18,应用举例2家庭血缘关系图表示家庭成员的辈分关系，使用下图1-1所示的形式描述。,图1-1家庭血缘关系图,特点：在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构；对它的操作有：建立树形结构，输出最结点内容等等。,应用举例3制定教学计划在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示：,19,这种数据可以用下面的图来表示：,课程先后关系的图形描形式：,图1-2计算机专业必修课程开设先后关系,20,数据结构的主要研究问题：,21,2、基本概念和术语,数据结构是一门研究数据组织、存储和运算的一般方法的学科。,例：整数(1,2)、实数(1.1,1.2)字符串(beijing)、图形、声音。,计算机管理图书问题：在图书馆里有各种卡片：有按书名编排的、有按作者编排的、有按分类编排。如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间。最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如：,22,数据元素在计算机中的表示,数据结构是一门研究数据组织、存储和运算的一般方法的学科。,如何将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,对数据结构中的节点进行操作处理（插入、删除、修改、查找、排序）,23,数据元素(dataelement),数据元素是数据的基本单位，即数据集合中的个体。有时一个数据元素可由若干数据项(dataitem)组成。数据项是数据的最小单位。,数据元素亦称节点或记录。,数据结构可描述为group=（d，r）,有限个数据元素的集合,有限个节点间关系的集合,24,25,数据结构可描述为group=（d，r）,例1：一年四季的数据结构可表示成b=（d，r）d=春，夏，秋，冬r=（春，夏），（夏，秋），（秋，冬）例2：家庭成员数据结构可表示成b=（d，r）d=父亲，儿子，女儿r=（父亲，儿子），（父亲，女儿）,26,数据结构也可用图形表示,一年四季的数据结构可表示成家庭成员数据结构可表示成,（概念：结点、前件、后件、根结点、叶子）,27,树形结构,全校学生档案管理的组织方式,计算机程序管理系统也是典型的树形结构。,28,d=1,2,3,4r=(1,2),(1,3),(1,4),(2,3),(3,4),(2,4),d=1,2,3r=(1,2),(2,3),(3,2),(1,3),图形结构节点间的连结是任意的,29,3、例题讲解,数据处理的最小单位是(c)a)数据b)数据元素c)数据项d)数据结构数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及(a)a)数据的存储结构b)计算方法c)数据映象d)逻辑存储数据结构包括数据的逻辑结构、数据的【4】以及对数据的操作运算。【答案】物理结构（或存储结构）,30,线性结构与非线性结构：线性结构：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。如：一年四季，26个英文字母非线性结构：线性以外的数据结构。如：反映家庭成员间辈分关系的数据结构,31,结点间是以线性关系联结，如前面提到的：一年四季26个英文字母线性有限序列,4、线性表（linearlist）,线性表：具有线性结构的有限序列。,32,学生成绩表,线性表,33,数据元素、结点、记录,数据项,线性表的定义:线性表是n个元素的有限序列，它们之间的关系可以排成一个线性序列：a1，a2，ai，an其中n称作表的长度，当n=0时，称作空表。,线性表的特点：1、线性表中所有元素的性质相同。2、除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前驱和一个后继。第一个数据元素无前驱，最后一个数据元素无后继。3、数据元素在表中的位置只取决于它自身的序号。在线性表上常用的运算有：初始化、求长度、取元素、修改、前插、删除、检索、排序,34,35,线性表的顺序存储结构及其插入与删除操作,特点：1、线性表中数据元素类型一致，只有数据域，存储空间利用率高。2、所有元素所占的存储空间是连续的。3、各数据元素在存储空间中是按逻辑顺序依次存放的（a）做插入、删除时需移动大量元素。（b）空间估计不明时，按最大空间分配。,36,顺序存储,存储地址,存储内容,元素n,.,元素i,.,元素2,元素1,lo,lo+m,lo+(i-1)m,lo+（n-1)m,loc(元素i)=lo+（i-1)m,每个元素所占用的存储单元个数,线性表的顺序存储结构：,首地址起始地址基地址,插入运算,ai-1,.,a2,a1,alength,ai+1,ai,alength,插入算法的分析假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：,37,x,ai-1,.,a2,a1,alength,ai+1,ai,x,在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：分析结论顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。,删除算法的分析,38,线性表的例题讲解,顺序存储方法是把逻辑上相邻的结点存储在物理位置【1】的存储单元中。【答案】相邻长度为n的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为【2】。【答案】n/2线性表l=(a1,a2,a3,ai，an)，下列说法正确的是（d）a)每个元素都有一个直接前件和直接后件b)线性表中至少要有一个元素c)表中诸元素的排列顺序必须是由小到大或由大到小d)除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件,39,40,数据结构中，与所使用的计算机无关的是数据的(c)a)存储结构b)物理结构c)逻辑结构d)物理和存储结构下列叙述中，错误的是（b）a)数据的存储结构与数据处理的效率密切相关b)数据的存储结构与数据处理的效率无关c)数据的存储结构在计算机中所占的空间不一定是连续的d)一种数据的逻辑结构可以有多种存储结构数据的存储结构是指（b）a）数据所占的存储空间b）数据的逻辑结构在计算机中的表示c）数据在计算机中的顺序存储方式d）存储在外存中的数据,根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成(c)a)动态结构和静态结构b)紧凑结构和非紧凑结构c)线性结构和非线性结构d)内部结构和外部结构数据的逻辑结构有线性结构和【2】两大类。非线性结构当线性表采用顺序存储结构实现存储时，其主要特点是【1】。【答案】逻辑结构中相邻的结点在存储结构中仍相邻。,41,5、堆栈和队列,堆栈和队列的定义,栈和队列是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为限定性的数据结构。,堆栈的定义,堆栈：限定只能在表的一端进行插入和删除的特殊的线性表,此种结构称为后进先出。设栈s=（a1，a2，ai，an）,其中a1是栈底元素，an是栈顶元素。栈顶（top)：允许插入和删除的一端；约定top始终指向新数据元素将存放的位置。栈底（bottom):不允许插入和删除的一端。,42,队列的定义,队列：一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表。此种结构称为先进先出（fifo）表。,a1,a2,a3,a4,an-1,an,队列示意图,队头,队尾,队列的主要运算,（1）设置一个空队列；（2）插入一个新的队尾元素，称为进队；（3）删除队头元素，称为出队；（4）读取队头元素；,43,堆栈和队列的例题讲解,栈和队列的共同特点是（c）a)都是先进先出b)都是先进后出c)只允许在端点处插入和删除元素d)没有共同点如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是（b）a)e3,e1,e4,e2b)e4,e3,e2,e1c)e3,e4,e1,e2d)任意顺序,44,45,a=42+b,8,2,6,b=63+c,c=32+d,d=1+2,=8+b,=2+c,=6+d,=3,8,2,6,一些重要的程序语言(如c语言和pascal语言)允许过程的递归调用。而实现递归调用中的存储分配通常用（a）a)栈b)堆c)数组d)链表,当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为【2】。答案：上溢由两个栈共享一个存储空间的好处是（b）a)减少存取时间，降低下溢发生的机率b)节省存储空间，降低上溢发生的机率c)减少存取时间，降低上溢发生的机率d)节省存储空间，降低下溢发生的机率下列关于栈的叙述中正确的是（d）)在栈中只能插入数据b）在栈中只能删除数据c）栈是先进先出的线性表d）栈是后进先出的线性表下列关于队列的叙述中正确的是（c）在队列中只能插入数据b）在队列中只能删除数据c）队列是先进先出的线性表d）队列是后进先出的线性表,46,两个栈共享只有两个栈都多时才溢出。不共享的话，两个栈只有一个栈多就溢出，,栈底至栈顶依次存放元素a、b、c、d，在第五个元素e入栈前，栈中元素可以出栈，则出栈序列可能是（b）a)abcedb)dcbeac)dbcead)cdabe,47,顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。,顺序存储结构的三个缺点：1.作插入或删除操作时，需移动大量元数。2.长度变化较大时，需按最大空间分配。3.表的容量难以扩充。,存储内容,48,49,6、线性表的链式存储线性链表,线性链表的基本概念：线性表的链式存储结构称为线性链表。为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每一小块占若干字节，通常称这些小块为存储结点。,将存储空间中的每一个存储结点分为两部：一部分称为数据域，用于存储数据元素的值；另一部分称为指针域，用于存放下一个数据元素的存储序号（即存储结点的地址），也就是指向后件结点.,线性链表中存储结点的结构如图2.20所示,50,1536,元素2,1400,元素1,1346,元素3,元素4,head,链式存储,1345,52,指向线性表中第一个结点的指针head称为头指针。当head=null（或0）时称为空表。对于线性链表，可以从头指针开始，沿着各个结点的指针扫描到链表中的所有结点。,线性链表的逻辑结构图所示,53,1、比顺序存储结构的存储密度小(每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。2、逻辑上相邻的节点物理上不必相邻。3、插入、删除灵活(不必移动节点，只要改变节点中的指针)。4、查找结点时链式存储要比顺序存储慢。,链接存储结构特点：,54,54,55,线性链表的基本运算：,线性链表的运算主要有以下几个：在线性链表中包含指定元素的结点之前插入一个新元素。在线性链表中删除包含指定元素的结点。将两个线性链表按要求合并成一个线性链表。,56,线性链表的插入运算：,线性链表的插入是指在链式存储结构下的线性表中插入一个新元素。为了要在线性链表中插入一个新元素，首先要给该元素分配一个新结点，然后将存放新元素值的结点链接到线性链表中指定的位置。,57,57,58,线性链表的删除指在链式存储结构下的线性表中删除包含指定元素的结点。为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，然后将要删除结点放回到可利用栈。,线性链表的删除运算：,59,59,l,.,线性表的链式存储结构可用“结构指针”来描述,带头结点的线性链表,data,next,typedefstructlnodeintdata;structlnode*next;jd;,p,p,单链表的插入运算,s,在p所指向的结点之后插入新的结点,p,p,l,单链表的插入运算,s,单链表的插入运算,voidlbcr(jd*p,intx)/*在p所指向的结点之后插入新的结点*/jd*s;/*定义指向结点类型的指针*/s=(jd*)malloc(sizeof(jd);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;returnok;,p,l,单链表的插入运算,voidlbcr(jd*p,intx)/*在p所指向的结点之后插入新的结点*/jd*s;/*定义指向结点类型的指针*/s=(jd*)malloc(sizeof(jd);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;returnok;,p,l,单链表的插入运算,voidlbcr(jd*p,intx)/*在p所指向的结点之后插入新的结点*/jd*s;/*定义指向结点类型的指针*/s=(jd*)malloc(sizeof(jd);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;returnok;,s,p,l,单链表的插入运算,voidlbcr(jd*p,intx)/*在p所指向的结点之后插入新的结点*/jd*s;/*定义指向结点类型的指针*/s=(jd*)malloc(sizeof(jd);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;returnok;,s,p,l,单链表的插入运算,voidlbcr(jd*p,intx)/*在p所指向的结点之后插入新的结点*/jd*s;/*定义指向结点类型的指针*/s=(jd*)malloc(sizeof(jd);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;returnok;,s,p,l,单链表的插入运算,voidlbcr(jd*p,intx)/*在p所指向的结点之后插入新的结点*/jd*s;/*定义指向结点类型的指针*/s=(jd*)malloc(sizeof(jd);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;returnok;,voidlbsc(jd*p)/*删除p指针指向结点的后一个结点*/jd*q;if(p-next!=null)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/,单链表的删除运算,l,p,voidlbsc(jd*p)/*删除p指针指向结点的后一个结点*/jd*q;if(p-next!=null)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/,单链表的删除运算,l,p,voidlbsc(jd*p)/*删除p指针指向结点的后一个结点*/jd*q;if(p-next!=null)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/,单链表的删除运算,q,l,p,q,voidlbsc(jd*p)/*删除p指针指向结点的后一个结点*/jd*q;if(p-next!=null)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/,单链表的删除运算,l,p,q,voidlbsc(jd*p)/*删除p指针指向结点的后一个结点*/jd*q;if(p-next!=null)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/,单链表的删除运算,l,p,voidlbsc(jd*p)/*删除p指针指向结点的后一个结点*/jd*q;if(p-next!=null)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/,单链表的删除运算,线性链表的查找操作：设无表头结点的线性链表的头指针为h,沿着链表的开始往后找结点x，若找到，则返回该结点在链表中的位置，否则返回空地址。jd*lbcz(jd*h,intx)jd*p;p=h;while(p!=null,2.5.2循环链表:首尾相接的链表。将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。,l,.,带头结点的单链表,l,.,循环单链表,(1)l=p-next;,例题对以下单链表分别执行下列各程序段,并画出结果示意图.,(2)r-data=p-data;,(3)r-data=p-next-data;,(4)p-next-next-next-data=p-data;,(7)p=(jd*)malloc(sizeof(jd);p-data=10;r-link=p;p-link=s;,(7)p=(jd*)malloc(sizeof(jd);p-data=10;r-link=p;p-link=s;,p,(7)p=(jd*)malloc(sizeof(jd);p-data=10;r-next=p;p-next=s;,p,10,(5)p=(jd*)malloc(sizeof(jd);p-data=10;r-next=p;p-next=s;,p,10,(7)p=(jd*)malloc(sizeof(jd);p-data=10;r-next=p;p-next=s;,p,10,(8)t=l;t-next=p-next;free(p);,(9)s-next=l;,如果s-next=l则s所指向的结点为尾结点.,循环链表的结构与前面所讨论的线性链表相比，具有以下两个特点：循环链表的头指针指向表头结点。在循环链表中，所有结点的指针构成了一个环状链。图2.29是循环链表的示意图。,循环链表：,88,89,在实际应用中，循环链表与线性单链表相比主要有以下两个方面的优点：在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点。由于在循环链表中设置了一个表头结点，因此，在任何情况下，循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。,链表不具有的特点是（b）a)不必事先估计存储空间b)可随机访问任一元素c)插入删除不需要移动元素d)所需空间与线性表长度成正比数据结构分为逻辑结构与存储结构，线性链表属于【1】。【答案】存储结构栈通常采用的两种存储结构是（a）a)顺序存储结构和链表存储结构b)散列方式和索引方式c)链表存储结构和数组d)线性存储结构和非线性存储结构,线性链表的例题讲解,90,91,线性表的顺序存储结构和线性表的链式存储结构分别是(c)a)顺序存取的存储结构、顺序存取的存储结构b)顺序存取的存储结构、随机存取的存储结构c)随机存取的存储结构、顺序存取的存储结构d)任意存取的存储结构、任意存取的存储结构,顺序存储结构的地址在内存中是连续的所以可以通过计算地址实现随机存取，而链式存储结构的存储地址不一定连续，只能通过第1个结点的指针顺序存取；,92,7、树与二叉树：,树的基本概念：前面我们讨论的线性表，栈、队列和数组等都是线性结构。而树是一种非线性数据结构，它的每一个结点，都可以有不止一个直接后继，除根外的所有结点，都有且只有一个直接前趋。这些数据结点按分支关系组织起来，清晰地反映了数据元素之间的层次关系。,93,现实世界中，能用树的结构表示的例子：学校的行政关系、书的层次结构、人类的家族血缘关系等。,94,94,95,95,二叉树(binarytree)是一种很有用的非线性结构。二叉树具有以下两个特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。,二叉树（binarytree）：,因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的讨论。,96,97,97,性质1：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。,二叉树的性质：,特别要注意：二叉树是树的特殊情况。,a,a,b,b,两棵不同的二叉树,98,例子1：某二叉树中度为2的结点有18个，则该二叉树中有19个叶子结点。,99,性质2：二叉树的第i层上至多有2i-1（i1）个结点,二叉树的性质：,第三层上(i=3)，有23-1=4个节点。第四层上(i=4)，有24-1=8个节点。,100,二叉树的性质：,性质3：深度为h的二叉树中至多含有2h-1个结点,此树的深度h=4，共有24-1=15个节点。,101,满二叉树与完全二叉树,满二叉树是指除最后一层外，每一层上的所有结点都有两个子结点。完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。注意：满二叉树是完全二叉树，完全二叉树不一定是满二叉树。,102,满二叉树的特点：每一层上都含有最大结点数。,102,103,完全二叉树的特点：除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最左边的若干位置,103,104,对于完全二叉树而言如果它的结点个数为偶数，则该二叉树中：叶子结点的个数=非叶子结点的个数如果它的结点个数为奇数，则该二叉树中：叶子结点的个数=非叶子结点的个数+1（即叶子结点数比非叶子结点数多一个）,规律总结：,105,例题讲解,1、设一棵完全二叉树共有700个结点，则在该二叉树中有350个叶子结点。2、在深度为5的满二叉树中，叶子结点的个数为（c）(即第5层的叶子个数2i-1)a)32b)31c)16d)15,二叉树的遍历,二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。设访问根结点记作v；遍历根的左子树记作l；遍历根的右子树记作r；前序：vlr（即根左右）中序：lvr（即左根右）后序：lrv（即左右根）,106,107,107,108,1、设一棵二叉树的中序遍历结果为dbeafc,前序遍历结果为abdecf，则后序遍历结果为：debfca,例题讲解,2、已知一棵二叉树前序遍历和中序遍历分别为abdegcfh和dbgeachf，则该二叉树的后序遍历为（b）a)gedhfbcab)dgebhfcac)abcdefghd)acbfedhg,前序：abdecf（前序：根最先访问，根必在第一个）中序：dbeafc（由上可知中序根所在，划分出左右子树）前序：abdecf中序：dbeafc前序：abdecf中序：dbeafc,具有3个结点的二叉树有（d）a)2种形态b)4种形态c)7种形态d)5种形态设有下列二叉树：对此二叉树前序遍历的结果为（b）a)zbttcpxab)atbzxctpc)zbtactxpd)atbzxcpt,109,110,8、查找和排序：,查找又称为检索查找算法的评价主要考虑算法的时间复杂性，既可以采用数量级的形式表示，也可以采用平均检索（查找）长度，即在查找成功情况下的平均比较次数来表示。查找可分为顺序查找和二分法查找两种。,111,（a）顺序查找：,顺序查找又称线性查找。它是一种最简单、最基本的查找方法。基本思想是：从表中第一条记录开始，逐个进行记录的关键字和给定值的比较。若某个记录的关键字和给定值相等，则查找成功；否则，若直至最后一个记录，其关键字和给定值都不相等，则表明表中没有所查记录，查找不成功。,112,二分查找又称折半查找。作为二分查找对象的表必须是顺序存储的有序表，即各记录的次序是按其关键字的大小顺序（以下假定按从小到大的顺序）排列的表。,（b）二分查找：,113,二分查找的具体做法是:先取表中间位置的记录关键字与给定值比较。若相等,则查找成功；否则,若给定值比该记录的关键字小，则给定值必在表的前半部分。在这前半部分中再取中间位置记录的关键字进行比较，就又可以排除这部分的一半。依次反复进行，直到找到给定值或找完全表而找不到为止。在最坏情况下，二分查找只需要比较次数:对于n较大时，平均查找长度可以近似地表示为:,例:246791222283645547280,114,排序是将一组杂乱无章的数据按一定的规律顺次排列起来。通常数据对象有多个属性域，即由多个数据成员组成,其中有一个属性域可用来区分象,作为排序依据。该域称为关键字（key）。排序的时间开销是衡量算法好坏的最重要的标志。对于长度为n的有序线性表，查找时最坏情况只需比较n次。,排序（sort）,115,（a）交换类排序：,交换类排序法：冒泡排序法：需要比较的次数为n(n-1)/2快速排序法：是对冒泡排序的改进，是目前内部排序中速度最快的一种。,116,（b）插入类排序：,插入类排序的基本方法是：每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。简单插入排序法：最坏情况需要n(n-1)/2次比较；希尔排序法：最坏情况需要o（n）次比较。,117,（c）选择类排序：,选择类排序的思想是：每一趟（例如，第i趟，i=0，1，n2）在后面ni个待排序对象中选出关键字最小（升序，若为降序，选出最大关键字）的对象，作为有序对象序列的第i个对象。待到第n2趟作完，待排序对象只剩下1个，不用再选了，结束排序。简单选择排序法，最坏情况需要n(n-1)/2次比较；堆排序法，最坏情况需要o（nlog2n）次比较。,118,（一）程序设计方法与风格,如何形成良好的程序设计风格：1、源程序内部文档化；,选择标识符的名字（有含义好理解）注释（序言性和功能性注释）程序的视觉组织（空格空行缩进）,位于源程序模块内部,一般位于模块的首部，用于说明模块的相关信息,119,数据说明的次序应该规范化便于查找变量（按顺序排列）对复杂数据结构应注释说明,2、数据说明,3、语句的结构,每条语句简单明了尽量不用或少用goto语句尽量只采用3种基本控制结构编程,4、输入和输出,对所有输入数据进行校验和合理性检查输入输出格式保持一致设计良好的输出报表,输入方式应力求简单，尽量避免给用户带来不必要的麻烦；交互式输入数据时应有必要的提示信息;程序应对输入数据的合法性进行检查;若用户输入某些数据后可能产生严重后果,应给用户输出必要的提示并要求用户确认；应根据系统的特点和用户的习惯设计出令用户满意的输入方式。输出数据的格式应清晰，美观；输出数据时要加上必要的提示信息。,120,121,结构化程序设计的主要原则是功能分解并逐步求精。当一些任务十分复杂不易描述时，可以将它拆分为一系列较小的功能部件，直到这些子任务小到易于理解和实现的程度。(后面详讲)结构化程序的特点：程序结构仅由顺序、选择和循环3种结构复合而成。,（二）结构化程序设计,122,（三）面向对象的程序设计方法,面向对象与面向过程（晚会的分析过程）面向对象的程序设计（object-orientedprogramming，oop）是一种把面向对象的思想应用于软件开发过程中，指导开发活动的系统方法，简称oo方法，它是建立在对象概念（对象、类和继承）基础上的方法。,123,面向对象程序设计方法的优点：（1）从认知学的角度来看，面向对象方法符合人们对客观世界的认识规律。（2）面向对象方法开发的软件系统易于维护，其体系结构易于理解、扩充和修改。（3）面向对象方法中的继承机制有力地支持软件的复用。,124,几个术语：对象：在现实世界中，每个实体都是对象，例如，大学生、汽车、电视机、空调等都是现实世界中的对象属性：通常是一些数据，有时它也可以是另一个对象事件：是由对象识别的一个动作，用户可以编写相应代码对此动作进行响应方法：对象中的属性只能通过该对象所提供的操作来存取或修改,125,类：类是一组具有相同属性和相同操作的对象的集合。派生类：由已存在的类派生出来的新类，也叫子类。基类：用来生成新类的类。继承是指能够直接获得已有的性质和特征，而不必重复定义他们。继承分单继承和多重继承。单继承指一个类只允许有一个父类，多重继承指一个类允许有多个父类多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。,126,多重继承图,127,四、例题讲解：,结构化程序设计的3种结构是（d）a)顺序结构、选择结构、转移结构b)分支结构、等价结构、循环结构c)多分支结构、赋值结构、等价结构d)顺序结构、选择结构、循环结构在设计程序时，应采纳的原则之一是（d）a)不限制goto语句的使用b)减少或取消注解行c)程序越短越好d)程序结构应有助于读者理解,128,程序设计语言的基本成分是数据成分、运算成分、控制成分和（d）a)对象成分b)变量成分c)语句成分d)传输成分,结构化程序设计主要强调的是（d）a)程序的规模b)程序的效率c)程序设计语言的先进性d)程序易读性以下不属于对象的基本特点的是（c）a)分类性b)多态性c)继承性d)封装性,129,对建立良好的程序设计风格，下面描述正确的是（a）a)程序应简单、清晰、可读性好b)符号名的命名只要符合语法c)充分考虑程序的执行效率d)程序的注释可有可无在结构化程序设计思想提出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人们更重视程序的（c）a)安全性b)一致性c)可理解性d)合理性,130,下列叙述中，不属于结构化程序设计方法的主要原则的是（b）a)自顶向下b)由底向上c)模块化d)限制使用goto语句对象实现了数据和操作的结合，是指对数据和数据的操作进行（c）a)结合b)隐藏c)封装d)抽象在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送（d）a）调用语句b）命令c）口令d）消息,131,信息屏蔽的概念与下述哪一种概念直接相关（b）a）软件结构定义b）模块独立性c）模块类型划分d）模块偶合度下列对对象概念描述错误的是（a）a）任何对象都必须有继承性b）对象是属性和方法的封装体c）对象间的通讯靠消息传递d）操作是对象的动态属性,标识唯一性分类性多态性封装性模块独立性好,面向对象的设计方法与传统的面向过程的方法有本质的不同,它的基本原理是（c）a)模拟现实世界中不同事物之间的联系b)强调模拟现实世界中的算法而不强调概念c)使用现实世界的概念抽象地思考问题从而自然地解决问题d)鼓励开发者在软件开发的绝大部分中都用实际领域的概念去思考在面向对象的程序设计中，类描述的是具有相似性质的一组【1】。【答案】对象在面向对象方法中，类之间共享属性和操作的机制称为【2】。【答案】继承一个类可以从直接或间接的祖先中继承所有属性和方法。采用这个方法提高了软件的【3】。【答案】可重用性,133,在面向对象的设计中，用来请求对象执行某一处理或回答某些信息的要求称为【5】。【答案】：消息在程序设计阶段应该采取【6】和逐步求精的方法，把一个模块的功能逐步分解，细化为一系列具体的步骤，进而用某种程序设计语言写成程序。【答案】：自顶向下类是一个支持集成的抽象数据类型，而对象是类的【12】。【答案】：实例,【7】是一种信息隐蔽技术，目的在于将对象的使用者和对象的设计者分开。【答案】：封装子程序通常分为两类：【9】和函数，前者是命令的抽象，后者是为了求值。【答案】：过程源程序文档化要求程序应加注释。注释一般分为序言性注释和【10】。【答案】：功能性注释,135,（一）基本概念,软件工程：软件工程是指应用计算机科学、数学及管理科学等原理，以工程化的原则和方法来解决软件问题的工程。其目的是提高软件生产率、提高软件质量、降低软件成本。,软件危机：早期的软件主要指程序，采用个体工作方式，缺少相关文档，质量低，维护困难，这些问题称为“软件危机”，软件工程概念的出现源自于软件危机。,软件生命周期将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。分为软件定义、软件开发及软件运行维护3个时期。维护是持续时间最长，花费代价最大的一个时期，软件工程学的一个目的就是提高软件的可维护性，降低维护代价。6个活动阶段：可行性研究与计划制定：确定系统的总体目标。参加人员有用户、项目负责人和系统分析员，产生文档有可行性分析报告、项目计划书等。需求分析：确定系统的逻辑模型。参加人员有用户、项目负责人和系统分析员。产生文档为需求规格说明书，其作用：（1）便于用户、开发人员进行理解交流；（2）反映用户问题的结构，可以作为软件开发工作的基础和依据；（3）作为确认测试和验收的依据。,软件设计(分概要设计和详细设计)：包括软件结构设计、数据设计、接口设计和过程设计。其中结构设计是定义软件系统各部件之间的关系；数据设计是将分析时创建的模型转化为数据结构的定义；接口设计是描述软件内部、软件和操作系统之间及软件与人之间如何通信；过程设计则是把系统结构部件转换成软件的过程性描述。参加人员有系统分析员和高级程序员。产生的文档有设计规格说明书。编码(实现)：编程。高级程序员和程序员产生源程序清单。软件测试：由另一部门的高级程序员或系统分析员产生软件测试计划和软件测试报告。运行维护,软件工程三要素,方法：完成软件工程项目的技术手段。工具：支持软件的开发、管理、文档生成。过程：支持软件开发的各个环节的控制、管理。,软件工程的理论和技术研究的内容软件开发技术和软件工程管理。软件工具和软件开发环境软件工具(case)：用来辅助软件开发、运行、维护、管理、支持等过程中的活动的软件。软件开发环境：支持软件产品开发的软件系统，它由软件工具集和环境集成机制构成,139,软件工程的目标在给定的成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。软件工程鼓励研制和采用各种先进的软件开发方法、工具和环境。,140,（二）结构化分析方法,基本思想将系统分析看成工程项目，有计划、有步骤地进行工作。开发策略自顶向下，逐层分解分析结果一套分层的数据流图(dfd)：用来描述数据流从输入到输出的变换流程一个数据字典(dd)：用来描述dfd中的每个数据流、文件以及组成数据流或文件的数据项(打开实例)一组小说明（加工逻辑说明）：用来描述每个基本加工的加工逻辑,分层数据流图,141,（三）结构化设计方法、总体设计和详细设计,结构化设计方法结构图：基本成分：模块、调用、输入输出数据模块用矩形表示，模块间用线段连接，表示调用关系，输入输出数据可写在调用线段的旁边信息流的类型变换流事务流,142,总体设计设计原则分解协调原则自顶向下的原则信息屏蔽、抽象的原则一致性原则明确性原则模块间的耦合度尽可能小，模块内部组合尽可能紧凑（内聚性高）模块的扇入和扇出系数合理模块的规模适当,143,详细设计根本目标：确定应用怎样具体的实现所要求的系统，不是具体的编写程序，而是要设计程序的“蓝图”自顶向下的原则。,此阶段的结果基本上决定了最终的程序代码的质量。包括内容：,代码设计输入设计输出设计处理过程设计用户界面设计安全控制设计,144,（四）软件测试,意义目的为了