资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。谢谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。谢谢,全国计算机等级考试,二级公共基础知识,第1页,第一章 数据结构与算法(30%),考试纲领,1.算法基本概念；算法复杂度概念和意义（时间复杂度与空间复杂度）。2.数据结构定义；数据逻辑结构与存放结构；数据结构图形表示；线性结构与非线性结构概念。3.线性表定义；线性表次序存放结构及其插入与删除运算。4.栈和队列定义；栈和队列次序存放结构及其基本运算。5.线性单链表、双向链表与循环链表结构及其基本运算。6.树基本概念；二叉树定义及其存放结构；二叉树前序、中序和后序遍历。7.次序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。,第2页,知识点归纳,算法基本概念,所谓算法是指解题方案准确而完整描述。严格来说，一个算法必须含有以下五个主要特征：,可行性,确定性,有穷性,输入,输出,综上，所谓算法，是一组严格定义运算次序规则，而且每一个规则都是有效且明确，此次序将在有限次数终止。,第3页,算法基本概念,算法组成要素,算法中对数据运算和操作,算法控制结构,算法设计基本方法,列举法,归纳法,递推,递归,减半递推,回溯法,第4页,算法复杂度,算法复杂度可分为时间复杂度和空间复杂度，是衡量算法优劣量度。,1.,算法时间复杂度,算法时间复杂度是指执行算法所需要工作量。普通情况下，算法中基本操作重复执行次数是问题规模n某个函数,f(n),。,算法时间量度记作：,T(n)=O(f(n),，,表示随问题规模,n,增大，算法执行时间增加率和,f(n),增加率相同，称为算法(渐进)时间复杂度。,第5页,算法复杂度,何估算算法时间复杂度？任何一个算法都是由一个“控制结构”和若干“,原操作,”组成，所以一个算法执行时间能够看成是全部原操作执行时间之和,(原操作(i)执行次数原操作(i)执行时间),则算法执行时间与全部原操作执行次数之和成正比。从算法中选取一个对于所研究问题来说是基本操作原操作，以该基本操作在算法中重复执行次数作为算法时间复杂度依据。这种衡量效率方法所得出不是时间量，而是一个增加趋势量度。它与软硬件环境无关，只暴露算法本身执行效率优劣。,第6页,算法复杂度,算法空间复杂度,算法空间复杂度是指执行这个算法所需要内存空间。空间复杂度作为算法所需存放空间量度，记作：,S(n)=O(g(n),，,其中,n,为问题规模，表示随问题规模增大，算法运行所需存放量增加率与,g(n),增加率相同。,第7页,数据结构,利用计算机进行数据处理是计算机应用一个主要领域。数据结构主要研究和讨论以下三个方面问题：,数据集合中各数据元素之间逻辑关系，即数据逻辑结构。,在对数据进行处理时，各数据元素在计算机中存放关系，即数据存放结构。,对各种数据结构进行运算。,第8页,数据逻辑结构,数据逻辑结构是对数据元素之间存在逻辑关系描述，它能够用一个数据元素集合和定义在此集合上若干关系表示。,与数据在计算机中存放位置无关，是独立于计算机。,第9页,数据存放结构,数据存放结构是数据元素及其关系在计算机存放器中表示。存放结构主要内容是指在存放空间中使用一个存放结点来存放一个数据元素，在存放空间中建立各存放结点之间关联，来表示数据元素之间逻辑关系。,常见存放结构：,次序存放结构,链式存放结构,索引存放结构,散列存放结构,第10页,线性结构和非线性结构,线性结构,在数据元素非空有限集合中，线性结构逻辑特征以下：,存在一个唯一被称为“第一个”数据元素,存在一个唯一被称为“最终一个”数据元素,除第一个之外，集合中每个数据元素都有且只有一个直接前驱,除最终一个之外，集合中每个数据元素都有且只有一个直接后继,非线性结构,非线性结构逻辑特征是：一个结点可能有多个直接前驱和直接后继，树和图都属于非线性结构。,第11页,线性表,通常以以下 n 个数据元素序列”表示,线性表,：,(a,1,a,2,.,a,i,.,a,n,),序列中数据元素个数 n 定义为线性表,表长,；n=0 时线性表被称为,空表,。称 i 为a,i,在线性表中,位序,。,第12页,线性表次序存放,线性表次序存放结构用一组,地址连续,存放单元,依次存放,线性表中数据元素，即以“,存放位置相邻,”表示“位序相继两个数据元素之间前驱和后继关系，并以表中第一个元素存放位置作为线性表起始地址，称作,线性表基地址,。,全部数据元素存放位置均可由第一个数据元素存放位置得到 ADR(a,i,)=,ADR,(a,1,)+(i-1)C,基地址 一个数据元素所占存放量,第13页,线性表插入和删除运算,插入运算是指在线性表某个指定位置增加一个新结点。,普通情况下，要在第i(1in)个元素之前插入一个新元素时，首先要从最终一个元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，然后将新元素插入到第i项。,删除运算是指撤消结构中某个结点。,普通情况，要删除第i(1in)个元素，要从第i+1个元素开始，直到第n个元素，共n-i个元素依次向前移动一个位置。,第14页,栈,栈是限定仅在表一端进行插入和删除操作线性表。允许插入和删除一端称为栈顶，另一端称为栈底。,栈顶元素总是最终被插入元素，从而也是最先被删除元素；栈底元素总是最先被插入，也是最终被删除元素。所以，栈是一个,后进先出,线性表。,通惯用指针top指示栈顶位置，用指针bottom指示栈底位置。,第15页,栈次序存放及运算,用一维数组S(1:m)作为栈次序存放空间，m为栈最大容量。top=0表示栈为空，top=m表示栈满。,栈操作,入栈：在栈顶位置插入一个新元素，栈顶指针top加1。,退栈：取出栈顶元素并赋值给一个指定变量，栈顶指针top减1。,取栈顶元素：将栈顶元素值赋给一个指定变量，不删除栈顶元素，栈顶指针不变。,第16页,队列,队列是一个先进先出线性表，它只允许在表一端插入元素(队尾)，在另一端删除元素(队头)。通常定义头指针front指向队头元素前一个位置，定义尾指针rear指向队尾元素位置。,队列是一个,先进先出,数据结构。,向队尾插入一个元素操作称为入队，从队头删除一个元素操作称为退队。,第17页,循环队列,将队列存放空间最终一个位置绕到第一个位置，形成逻辑上环状空间。,循环队列初始状态为空，即front=rear=m。,入队操作时，rear加1，若rear=m+1，则置rear=1；,退队操作时，front加1，若front=m+1，则置front=1。,在循环队列为空或为满时，都有front=rear，所以需要设置标志s进行区分，定义s=0表示队列为空，s=1表示队列非空。,第18页,单链表,线性表链式存放结构特点是用一组任意存放单元(能够连续，也能够不连续)存放线性表数据元素，为了表示每个数据元素a,i,与其直接后继元素a,i+1,之间逻辑关系，对数据元素a,i,来说，除了存放其本身信息(数据域)之外，还需要存放其后继元素存放位置信息(指针域)。,指针域中存放信息称为指针或链，N个结点链接成一个链表，即为线性表链式存放结构。因为结点中只包含一个指针域，故称为单链表。,第19页,单链表,通常以单链表中第一个数据元素存放地址作为作为单链表地址，称为头指针。整个链表存放必须从头指针开始(次序存取)，头指针指示链表中第一个结点存放位置。最终一个数据元素没有直接后继，其指针域为空。,第20页,单链表插入和删除,第21页,双向链表和循环链表,在双向链表中结点包含两个指针域，其中一个指向直接后继，另一个指向直接前驱。,循环链表特点是表中最终一个结点指针域指向第一个结点，整个链表成为一个由链指针相链接环。据此，从表中任一节点出发均可找到表中其它结点。在循环链表中增加了一个表头结点，其指针域指向第一个元素结点，头指针则指向头结点。,HEAD,HEAD,HEAD,第22页,树及其基本概念,树是一个简单非线性结构，在树中，全部数据元素之间含有显著层次性关系。,树是(n0)个结点有限集合，在任意一棵非空树中：,(1)有且仅有一个特定结点称为根结点。,(2)当n1时，其余结点可分为m个互不相交子集T,1,T,2,T,m,，其中每个有限子集本身又是一棵树，而且称为根子树。,集合为空树简称为空树；树中元素称为结点。,第23页,树主要术语,结点度：结点拥有子树数。,叶节点(终端结点)：度为0结点。,双亲、孩子和弟兄：结点子树根节点称为该结点孩子，该结点称为孩子结点双亲结点。同一个双亲结点孩子互称为弟兄。,层次：结点层次从根开始定义，根为第一层，根孩子为第二层。,深度：树中结点最大层次称为树深度或高度。,第24页,二叉树,二叉树是n(n0)个数据元素有限集，它或为空集,或者含有唯一称为根元素，且其余元素分成两个互不相交子集，每个子集本身也是一棵二叉树，分别称为根左子树和右子树。,二叉树是另一个树型结构，其特点是每个结点至多有两棵子树，而且二叉树子树有左右之分，其次序不能任意颠倒。,第25页,二叉树基本性质,性质1,在二叉树第i层上至多有2,i-1,个结点（i1）,性质2,深度为k二叉树至多有2,k,-1个结点（k1）,性质3,对任何一棵二叉树T，假如其终端结点数为n,0,，度为2结点数为n,2,，则：n,0,=n,2,+1,性质4,含有n个结点二叉树，其深度最少为log,2,n+1,第26页,满二叉树和完全二叉树,满二叉树,除最终一层外，每一层上全部结点都有两个子节点，也就是说每一层上结点数都到达最大值，即在满二叉树第k层上有2,k-1,个结点，且深度为m满二叉树有2,m,-1个结点。,完全二叉树,除最终一层外，每一层上结点数均到达最大值，在最终一层上只缺乏右边若干结点。含有n个结点完全二叉树，其深度为log,2,n+1。,从以上定义可知，满二叉树也是完全二叉树，反之则不然。,满二叉树,最大层结点均向左靠齐,完全二叉树,A,D,C,B,E,F,第27页,二叉树基本性质,性质5,假如对一棵有 n 个结点完全二叉树（其深度为log,2,n+1）结点按层序（从第1层到第log,2,n+1 层，每层从左到右）从1起开始编号，则对任一编号为 i 结点(1in)，则:(1)假如 i=1，则编号为 i 结点是二叉树根，无双亲；假如 i1，则其双亲结点 parent(i)编号是i/2。(2)假如 2in，则编号为 i 结点无左孩子（编号为 i 结点为叶子结点）；不然其左孩子结点 lChild(i)编号是 2i。(3)假如 2i+1n，则编号为 i 结点无右孩子；不然其右孩子结点 rChild(i)编号是结点 2i+1。,第28页,二叉树链式存放结构,在二叉树链式存放结构中，每个结点设置三个域，即数据域，左指针域和右指针域，两个指针域分别存放左右子树根节点存放位置，即指针。,L(i),V(i),R(i),Lchild,value,Rchild,第29页,二叉树链式存放结构,第30页,二叉树遍历,二叉树遍历指不重复地访问二叉树全部结点。从二叉树结构定义得知，二叉树是由根结点、左子树和右子树三部分组成，则遍历二叉树操作可分解为访问根结点、遍历左子树和遍历右子树三个子操作，而且由二叉树递归定义可知，遍历左子树和遍历右子树可如同遍历二叉树一样递归进行。,先序遍历二叉树,中序遍历二叉树,后序遍历二叉树,若二叉树为空，则空操作；不然(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树。,若二叉树为空，则空操作；不然(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树。,若二叉树为空，则空操作；不然(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。,第31页,二叉树遍历,先序遍历：,A,BDEGH,CFIJ,中序遍历：,DBGEH,A,CIJF,后序遍历：,DGHEB,JIFC,A,第32页,查找,查找是指在一个给定数据结构中查找某个指定元素。,次序查找,次序查找普通是指在线性表中查找指定元素，基本方法以下：从线性表第一个元素开始，依次将线性表中元素与被查找元素进行比较，若相等则表示找到，即查找成功；若线性表中全部元素与被查找元素都不相等，则查找失败。,假如线性表为无序表，即表中元素排列是无序，则不论线性表采取次序存放还是链式存放，都必须使用次序查找。,假如线性表有序，但采取链式存放结构，则也必须使用次序查找。,第33页,查找,二分查找(折半查找),二分查找法只适合用于次序存放有序表。先确定待查目标元素所在范围(区间)，然后逐步缩小范围直至找到该元素，或者当查找区间缩小到,0,也没有找到目标元素为止。,查找过程中，给定值首先和处于待查区间中间位置关键字进行比较，若相等，则查找成功，不然将查找区间缩小到前半个区间 或 后半个区间 之后继续进行查找。,第34页,折半查找,二分查找,第35页,排序,排序是指将一个无序序列整理成按值递增或递减(本章均采取递增规则)有序序列。,排序能够在各种不一样存放结构上实现，本章所介绍算法以次序存放线性表为排序对象，在程序设计语言中就是一维数组。,排序算法种类很多，主要包含交换类排序、插入类排序、选择类排序等。,第36页,交换类排序,冒泡排序,基本思想：从表头开始扫描线性表，在扫描过程中依次比较相邻两个元素大小，若前面元素大于后面元素，则交换它们位置。显然，在扫描过程中，不停地将将相邻元素间较大向后移动，最终将线性表中最大元素移到表尾。,然后，从后向前扫描剩下线性表，一样在扫描过程中依次比较相邻两个元素大小，若后面元素小于前面元素，则交换位置。在扫描过程中，不停地将将相邻元素间较小向前移动，最终将线性表中最小元素移到表头。,对剩下线性表重复上述过程，直到剩下线性表为空为止，此时线性表变为有序。,第37页,冒泡排序示例,第一遍(从前向后),第一遍(从后向前),第二遍(从前向后),第二遍(从后向前),第38页,快速排序,基本思想：从线性表中选取一个元素，设为T，将线性表后面小于T元素移动到前面，将前面大于T元素移动到后面，将线性表分为两个部分(子表)，T放到分界限位置，这个过程称为线性表分割，经过一次分割，就以T为分界将线性表分为两个子表，前面子表中全部元素均小于T，而后面子表中元素均大于T。按照上述标准对子表继续进行分割，直到子表为空，则整个线性表有序。,第39页,快速排序,操作步骤：,首先，在表第一个元素、最终一个元素和中间元素中选取一个中值，设为P(k)，并将P(k)赋值给T，再将表中第一个元素移到P(k)位置。设两个指针i，j分别指向表起始和最终位置，重复操作以下两步：,将j逐步减小，并逐次比较P(j)和T，直到发觉一个P(j)T为止，并将P(i)移到 P(j)位置上。,上述两步操作交替进行，直到i和j指向同一个位置，再将T移动到P(i)位置上，完成一次分割。,第40页,31,68,45,90,23,39,54,12,87,76,31,暂存枢轴统计T：,low,high,high,high,12,12,low,68,68,high,high,high,23,23,low,45,45,high,high,31,31,快速排序一次分割过程,31,第41页,插入类排序,简单插入排序,基本思想：将待排序列表分成两部分：已排序部分和未排序部分。每次扫描将未排序列表中第一个元素取出并插入到已排序列表中适当位置。包含n个元素列表最多需要n-1次扫描。,第42页,简单插入排序示例,原始序列,第1趟,第2趟,第3趟,第4趟,第5趟,第43页,希尔排序,基本思想：将整个无序序列分割成若干个小子序列分别进行插入排序。,子序列分割方法：将相隔某个增量h元素组成一个子序列，在排序过程中，逐次减小这个增量，最终当h减到1时，进行一次插入排序，排序完成。,增量序列普通取h,t,=n/2,k,(k=1,2log,2,n),第44页,希尔排序,h=6,h=1,h=3,完成,第45页,选择类排序,简单项选择择排序,基本思想：将待排序列表分成两部分：已排序部分和未排序部分。找到未排序部分中最小元素并把它和未排序部分中第一个元素进行交换。经过一次选择和交换，列表中已排序部分增加一个元素，未排序部分降低一个元素。每次把一个元素从未排序部分移动到已排序部分称为完成一次,分类扫描,或称为,一趟排序,。,一个包含n个元素列表需要进行n-1次扫描完成排序。,第46页,简单项选择择排序示例,原始序列,第1趟,第2趟,第3趟,第4趟,第5趟,第47页,第二章 程序设计基础(15%),考试纲领,1.程序设计方法与格调。2.结构化程序设计。3.面向对象程序设计方法，对象，方法，属性及继承与多态性。,第48页,知识点归纳,程序设计方法,程序设计是一门技术，需要对应理论、方法和工具来支持。就程序设计方法和技术发展而言，主要经历了结构化程序设计和面向对象程序设计阶段。,在程序设计中，通常采取“自顶向下，逐步求精”方法，即把一个模块功效逐步分解，细化为一系列详细步骤，进而转换成一系列用某种程序设计语言编写程序。,第49页,程序设计格调,除了程序设计设计方法和技术之外，程序格调也是非常主要。良好程序设计格调概括起来包含以下及格方面：,源程序文档化,数听说明方法,语句结构,输入和输出,第50页,程序设计格调,源程序文档化,标识符命名,程序注释,序言性注释,功效性注释,程序视觉组织,数据说明,数听说明次序应该规范化,说明语句中变量安排有序化,使用注释说明复杂数据结构,第51页,程序设计格调,语句结构,在一行内只写一条语句,程序编写应优先考虑清楚性,除非对效率有特殊要求，程序编写要做到清楚第一，效率第二,首先要确保程序正确，然后才要求提升速度,防止使用暂时变量而使程序可读性下降,防止无须要转移,尽可能使用库函数,防止使用复杂条件语句,尽可能降低使用“否定”条件条件语句,数据结构要有利于程序简化,要模块化，使模块功效尽可能单一化,利用信息隐蔽，确保每一个模块独立性,从数据出发结构程序,不要修补不好程序，要重写编写,第52页,程序设计格调,输入和输出,对全部输入数据检验正当性,检验输入项各种主要组合正当性,输入格式要简单，以使输入步骤和操作尽可能简单,输入数据时，应允许使用自由格式,应允许缺省值,输入一批数据时，最好使用输入结束标志,在以交互式输入/输出方式进行输入时，要在屏幕上使用提醒符明确提醒输入请求，同时在数据输入结束时，应在屏幕上给出状态信息,当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句一致性；给全部输出加注释，并设计输出报表格式。,第53页,结构化程序设计,结构化程序设计标准,自顶向下。程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始就过多追求细节，先从最上层总目标开始设计，逐步使问题详细化。,逐步求精。对复杂问题，应设计一些子目标过渡，逐步细化。,模块化。一个复杂问题必定是有若干简单问题组成。模块化是把程序要处理总目标分解为分目标，再深入分解为详细小目标，每个小目标成为一个模块。,严格限制GOTO语句使用。,第54页,结构化程序设计基本结构和特点,程序由一些基本结构组成，任何一个程序都能够用三种基本控制结构组成：次序结构、选择结构和循环结构，而且含有以下特点：单入口、单出口、结构中无死循环，程序中三种基本控制结构之间形成次序执行关系。,一个大型程序应按功效分割成一些模块，并把这些模块按层次关系进行组织。,在程序设计时应采取自顶向下、逐步细化实施方法。,第55页,面向对象程序设计,面向对象方法基本概念,1.对象、类和属性,在面向对象程序设计中，对象是程序基本单位。对象能够表示客观世界中任何实体，是对问题域中某个实体抽象。每个对象能够用它本身一组属性和它能够执行一组操作来定义。类是对一组含有共同属性和相同行为对象一个抽象，描述了属于该类全部对象性质。,2.方法,方法有称为操作或服务，它描述了对象执行功效，若经过消息传递，还可为其它对象使用。,第56页,面向对象方法基本概念,3.继承：继承是对象方法一个主要特征。指一个类(子类)直接使用另一个类(父类)全部属性和方法。它能够降低相同类重复说明，从而表达普通性和特殊性标准。,4.多态性：多态性能够用“一个对外界面，多个内部实现”来表示。能够经过方法重载和方法重写来实现多态。重载指一个类中能够有多个含有相同名称方法，由传递给它们不一样个数和类型参数来决定执行那个方法。重写指子类能够重新实现父类一些方法，使其含有自己特征。多态性机制增加了面向对象软件系统灵活性，提升了软件可重用性和可扩充性。,5.消息：面向对象系统中对象之间是经过消息机制彼此相互合作，消息是一个对象与另一个对象之间传递信息，它请求对象执行某一处理或回答某一要求信息。,第57页,面向对象程序设计特点,按照人思维方式对客观世界进行抽象,稳定性好,可重用性好,易于开发大型软件,可维护性好,第58页,第三章 软件工程基础,考试纲领,1.软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。2.结构化分析方法，数据流图，数据字典，软件需求规格说明书。3.结构化设计方法，总体设计与详细设计。4.软件测试方法，白盒测试与黑盒测试，测试用例设计，软件测试实施，单元测试、集成测试和系统测试。5.程序调试，静态调试与动态调试。,第59页,知识点归纳,软件定义和特点,计算机软件式计算机系统中与硬件相互依存另一部分，是包含程序、数据及相关文档完整集合。计算机软件含有以下特点：,软件是一个逻辑实体，含有抽象性,软件生产没有显著制造过程,软件在运行、使用期间不存在磨损、老化问题,软件开发、运行对计算机系统含有依赖性,软件复杂性高，成本昂贵,软件开发包括很多社会原因,第60页,软件危机,所谓软件危机是指在计算机软件开发和维护过程中所碰到一系列严重问题，包含：,软件需求增加得不到满足,软件开发成本和进度无法控制,软件质量难以确保,软件不可维护或可维护性低,软件成本不停提升,软件开发生产率提升赶不上硬件发展和应用需求增加。,第61页,软件工程,为了消除软件危机，提出了软件工程学。软件工程是应用于计算机软件定义、开发和维护一整套方法、工具、文档、实践标准和工序。,软件工程三要素,方法,工具,过程,第62页,软件工程过程,软件工程过程是把输入转化为输出一组彼此相关资源和活动。它包含两方面含义：,1.软件工程过程是指为取得软件产品，在软件工具支持下由软件工程师完成一系列工程活动。通常包含四种基本活动：,P(Plan)：软件规格说明,D(Do)：软件开发,C(Check)：软件确认,A(Action)：软件演进,2.从软件开发观点看，软件工程过程是使用适当资源，为开发软件进行一组开发活动，在活动结束时将输入(用户需求)转化为输出(软件产品)。,第63页,软件生命周期,软件从提出、实现、使用、维护到停顿使用过程称为软件生命周期。普通包含以下几个阶段：,可行性研究与计划制订,需求分析,软件设计,软件实现,软件测试,运行和维护,第64页,软件工程目标与标准,软件工程目标是在给定成本、进度前提下，开发出含有有效性、可靠性、可了解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求软件产品。,为到达上述目标，在软件开发过程中，必须遵照软件工程基本标准：,抽象,信息隐蔽,模块化,局部化,确定性,一致性,完备性,可验证性,第65页,软件开发工具与软件开发环境,软件开发工具对过程和方法提供自动或半自动支持。当这些工具被集成起来使得一个工具产生信息能够被另外一个工具使用时，一个支持软件开发系统就建立起来了，称为计算机辅助软件工程(CASE)。CASE集成了软件、硬件和一个软件工程数据库(包含了相关分析、设计、程序结构和测试主要信息)从而创建了一个软件开发环境。,第66页,结构化分析方法,结构化分析方法大多使用自顶向下、逐层分解系统分析方法来定义系统需求。在结构化分析基础上，完成系统规格说明，建立系统一个自顶向下任务分析模型。结构化分析方法是一个建模技术，模型关键是数据辞典，它描述了全部在目标系统中使用和生成数据对象。结构化分析惯用工具：,数据流图(DFD):描述数据在系统中怎样被传送或变换以及描述怎样对数据流进行变换功效，用于功效建模。,数据字典,判定树,判定表,第67页,数据流图,数据流图是描述数据处理过程工具，它从数据传递和加工角度，来刻画数据流从输入系统到从系统输入移动变换过程。,数据流图基本元素,外部实体,数据流,处理(加工),数据存放,第68页,数据字典,数据字典是关于数据信息集合，对数据流图中各个元素进行完整定义和说明。数据流图和数据字典共同组成系统逻辑模型。,数据字典通常包含信息有：名称、别名、何处使用、怎样使用、内容描述以及补充信息等。,第69页,软件需求,软件需求包含：功效需求、性能需求、环境需求、可靠性需求、安全保密需求、用户界面需求、资源使用需求、成本消耗需求、开发进度需求等。,需求分析应交付主要文档是软件需求规格说明书(SRS)。,第70页,结构化设计,结构化设计就是采取最正确可能方法设计系统各个组成部分以及个成份之间内部联络技术。也就是说，结构化设计是这么一个过程：它决定用哪些方法把哪些部分联络起来，才能处理好某个详细有清楚定义问题。从工程管理角度看，软件设计分两步完成：,1.概要设计，即总体设计。将软件需求转化为数据结构和软件系统结构。惯用软件结构设计工具是结构图(Structure Chart)。,2.详细设计：即过程设计。经过对结构表示进行细化，得到软件详细数据结构和算法。过程设计惯用工含有：程序流程图、N-S图、PAD图、过程设计语言PDL(伪码)。,第71页,软件测试,定义：,使用人工或自动伎俩来运行或测定某个系统过程，其目标在于检验它是否满足要求需求或搞清预期结果与实际结果之间差异。,软件测试是为了发觉错误而执行程序过程。,一个好测试用例是指可能找到迄今为止还未发觉错误用例。,一个成功测试是发觉了至今还未发觉错误测试。,测试不能表明软件中不存在错误，它只能说明软件中存在错误。,第72页,测试技术与方法综述,从是否需要执行被测试软件角度，可将测试分为静态测试和动态测试。,静态测试主要包含代码检验、静态结构分析、代码质量度量等。,动态测试是基于计算机测试，是为了发觉错误而执行程序过程，或者说，是依据软件开发各个阶段规格说明和程序内部结构而精心设计一批测试用例，并利用这些测试用例去运行程序，以发觉程序错误过程。,第73页,测试技术与方法综述,按照功效划分，可将软件测试分为黑盒测试和白盒测试。,黑盒测试将测试对象看作一个黑盒，不考虑程序内部逻辑结构和内部特征，只依据程序需求规格说明，检验程序功效是否符合它功效说明。这种测试又称为功效测试或数据驱动测试。,白盒测试把测试对象看作一个透明盒子，利用程序内部逻辑机构及相关信息，设计或选择测试用例，对程序全部逻辑路径进行测试。经过在不一样点检验程序状态，确定实际状态是否与预期一致。这种测试又称为结构测试或逻辑驱动测试。,第74页,软件测试实施,软件测试按四个步骤进行：,单元测试：对软件设计最小单位模块进行正确性测试，其目标是发觉各模块内部可能存在各种错误。,集成测试：是测试和组装软件过程，它是在把模块按照设计要求组装起来同时进行测试，主要目标是发觉与接口相关错误。,确认测试：任务是验证软件功效和性能以及其它特征是否满足了需求规格说明中确定各种需求，以及软件配置是否完全、正确。,系统测试：将经过确认测试软件，作为整个计算机系统一个元素，与计算机硬件、外设、支持软件、数据以及人员等其它系统元素组合在一起，在实际运行环境中对其进行一系列集成测试和确认测试。,第75页,程序调试,程序调试任务是诊疗和修正程序中错误。,调试方法：,强行排错法,回溯法,原因排除法,第76页,第四章 数据库设计基础,考试纲领,1.数据库基本概念：数据库，数据库管理系统，数据库系统。2.数据模型，实体联络模型及E-R图，从E-R图导出关系数据模型。3.关系代数运算，包含集合运算及选择、投影、连接运算，数据库规范化理论。4.数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计相关策略。,第77页,知识点归纳,数据库定义,1.长久存放在计算机内，有组织、可共享数据集合。数据库中数据按一定数据模型组织、描述和存放，含有较小冗余度、较高数据独立性和易扩展性。,2.数据库是由一个相互关联数据集合和一组用以访问这些数据程序组成。,第78页,数据库管理系统(DBMS),数据库管理系统是一个帮助用户创建和管理数据库应用程序集合。所以，数据库管理系统也就是一个能够帮助完成定义、结构和操纵数据库等处理目标通用软件系统。其主要功效以下：,数据模式定义,数据存取物理构建,数据操纵,数据完整性、安全性定义和检验,数据库并发控制和故障恢复,数据服务,为完成上述功效，DBMS提供了对应语言：,数据定义语言(DDL),数据操纵语言(DML),数据控制语言(DCL),第79页,数据库系统,数据库系统是由数据库、数据库管理系统、数据库管理员、硬件平台和软件平台等几个部分组成完整运行实体。,数据库系统特点,数据集成性,数据高共享性和低冗余性,数据独立性,数据统一管理和控制,第80页,数据库系统内部体系结构,三级模式,概念模式：数据库系统中全局数据逻辑结构描述，全体用户数据视图,外模式：又称为用户模式，是每个用户局部数据描述，用户数据视图,内模式：又称为物理模式，是数据库物理存放结构和物理存取方法描述,二级映射,概念模式到内模式映射,外模式到概念模式映射,第81页,数据模型,数据是现实世界符号抽象，数据模型是现实世界数据特征抽象，它从抽象层次上描述了系统静态特征、动态行为和约束条件，为数据库系统信息表示和操作提供一个抽象框架。数据模型描述内容包含三部分：,数据结构,数据操作,数据约束,数据模型按不一样应用层次分成三种类型：,概念数据模型,逻辑数据模型,物理数据模型,第82页,实体联络(ER)模型,概念模型是面向现实世界，其出发点是有效地模拟显示世界，给出数据概念化结构。实体联络模型是一个广泛使用概念模型，该模型将现实世界要求转化为,实体,、,联络,和,属性,等几个基本概念，并用ER图直观地表示出来。,第83页,ER模型基本概念,实体：概念世界中基本单位，它们是客观存在且能相互区分事物。凡含有共性实体能够组成一个集合称为,实体集,。,属性：属性用来描述实体特征。一个实体能够有多个属性，每个属性能够有值，一个属性取值范围称为该属性,值域,。,联络：联络反应概念世界中实体集之间存在一定关系。,一对一联络(1:1),一对多联络(1:M),多对多联络(M:N),第84页,ER图,ER图是实体联络模型直观图形表示。,实体用矩形表示，并在矩形中标明实体名称。,属性用标有属性名称椭圆表示，而且必须用线将属性与其所属实现相连。,关系用标明关系名称菱形表示，关系名称普通是动词。关系将相关实体连接在一起并在实体旁标注关系基数。,第85页,关系模型,1.关系模型数据结构,在用户观点下，关系模型中数据逻辑结构是一张二维表，它由行和列组成。在关系数据库管理系统中，数据外部视图就是关系或表集合。关系数据库中，每一个关系都有唯一名称。,第86页,关系模型基本概念,属性：关系中每一列都称为属性，每一个属性表示了其下数据含义。表中每一列在关系范围内有唯一名称。,元组：关系中行称为元组。元组定义了一组属性值。,主码：表中某个属性组，它能够唯一确定一个元组。,域：属性取值范围。,分量：元组中一个属性值。,关系模式：对关系描述。,关系名（属性1，属性2，属性n）,比如：学生（学号，姓名，年纪，性别，系，年级）,第87页,关系基本性质,元组个数是有限。,列是同质，即每一列中分量是同一类型数据，来自同一个域。,不一样列能够出自同一个域，称其中每一列为一个属性，不一样属性要给予不一样属性名。,列次序无所谓，即列次序能够任意交换。,任意两个元组不能完全相同。,行次序无所谓，即行次序能够任意交换。,分量必须取原子值，即每一个分量都必须是不可分数据项。,第88页,关系模型,2.关系操纵,关系模型数据操纵即建立在关系上数据操纵，普通有查询、增加、删除及修改四种操作。,3.关系模型约束,实体完整性约束,参考完整性约束,用户自定义完整性约束,第89页,关系模型基本运算,查询,选择、投影、连接、并、交、差,数据更新,插入、删除、更新,关系操作特点,集合操作方式，即操作对象和结果都是集合。,第90页,关系操作：插入、删除、更新,第91页,关系操作：选择,选择操作：应用于一个关系并产生一个新关系，新关系中元组是元关系中元组子集。选择操作依据要求从原关系中选择部分元组，属性数量保持不变。,第92页,关系操作：投影,投影：用于一个关系并产生一个新关系，新关系中属性是原关系中属性子集。投影操作中元组数量保持不变。,第93页,关系操作：连接,连接：基于共有属性将两个关系组合。,第94页,关系操作(集合操作：并、交、差),第95页,数据库设计,数据库设计基本任务是依据用户对象信息需求、处理需求和数据支持环境设计出数据模式。数据库设计通常分为几个阶段：需求分析、概念设计、逻辑设计和物理设计。,第96页,数据库设计,需求分析：经过详细调查现实世界要处理对象，充分了解原系统工作概况，明确用户各种需求，然后在此基础上确定新系统功效。,概念设计：目标是分析数据间内在语义关联，在此基础上建立一个数据库抽象模型。方法有以下两种：,集中式模式设计法,视图集成设计法,第97页,数据库设计,逻辑设计：主要工作是将ER图转换成指定RDBMS中关系模式，并利用规范化理论对逻辑数据模型进行优化。,ER图中实体和联络都能够表示成关系，ER图中属性也能够转换成关系属性。,物理设计：主要目标是对数据内部物理结构作调整并选择合理存取路径，以提升数据库访问速度及有效利用存放空间。,第98页,数据库管理,数据库建立,数据库调整,数据库重组,数据库安全性控制与完整性控制,数据库故障恢复,数据库监控,第99页,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
