全国计算机二级辅导-公共基础部分.ppt

,全国计算机二级考试,公共基础知识,（1）笔试：90分钟，满分100分，其中含公共基础知识部分的30分。,（2）上机操作：90分钟，满分100分。,上机操作包括：,基本操作,简单应用,综合应用,全国计算机二级考试形式,第一章 数据结构与算法,【本章考试要点】,算法的基本概念；算法复杂度的概念和意义（时间复杂度和空间复杂度）。,数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构。,线性表的定义；线性表的顺序存储结构及其插入与删除。,栈和队列的定义；栈和队列的顺序存储结构有其基本运算。,线性单链表、双向链表与循环链表的结构及其基本运算。,树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。,顺序查找与二分法查找算法；基本排序算法（交换类排序、选择类排序、插入类排序）。,【本章考试要点】（续）,一、算法,算法,-,是一组严谨地定义运算顺序的规则,算法的,5,个特性,-,可行性、确定性、有穷性、拥有足够的情报。,算法的基本要素,-,一是对数据对象的运算和操作，,二是算法的控制结构,算法设计基本方法,-,列举法、归纳法、递推、递归、,减半递推,算法的复杂度,-,包括时间复杂度和空间复杂度,时间复杂度,-,执行算法所需的计算工作量,空间复杂度,-,执行算法所需的内存空间,例：下列叙述中正确的是,。,A）一个算法的空间复杂度大，则其时间复杂度也必定大,B）一个算法的空间复杂度大，则其时间复杂度必定小,C）一个算法的时间复杂度大，则其空间复杂度必定小,D）上述三种说法都不对,答案：D,例：算法的时间复杂度是指_。,A）算法的执行时间,B）算法所处理的数据量,C）算法程序中的语句或指令条数,D）算法在执行过程中所需要的基本运算次数,答案：D,例：算法的有穷性是指,。,A 算法程序的运行时间是有限的,B 算法程序所处理的数据量是有限的,C 算法程序的长度是有限的,D 算法只能被有限的用户使用,算法的基本特征：可行性，确定性，有穷性，拥有足够的情报。算法的有穷性是指算法必须能在执行有限个步骤之后终止，即算法程序运行的时间是有限的。,答案：A,二、数据结构,数据结构,-,相互有关联的数据元素的集合。,如春、夏、秋、冬；,18,、,11,、,35,、,23,、,16,；父亲、儿子、女儿等都是数据元素。,前件,-,数据元素之间的关系，如父亲是儿子和女儿的前件,后件,-,如儿子是父亲的后件,结构,-,指数据元素之间的前后件关系,数据的逻辑结构,是指反映数据元素之间逻辑关系，而与它们在计算机中的存储位置无关。,数据的存储结构（物理结构）,-,数据的逻辑结构在计算机存储空间中的存放形式，数据元素在计算机存储空间的位置关系可能与逻辑关系不同。,例：下列叙述中正确的是,。,A.数据的逻辑结构与存储结构必定是一一对应的,B.由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构,C.程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构,D.以上三种说法都不对,答案：D,数据的逻辑结构可以表示成多种存储结构，如：线性表就可用顺序存储结构或链式存储结构。,三、线性表,根据数据结构中各数据元素之间前后件关系的复杂程度，可将数据结构分两类,-,线性结构与非线性结构。,线性结构（线性表）,-,满足下列两个条件：,（,1,）有且只有一个根结点。,（,2,）每一个结点最多有一个前件和后件。,则称该数据结构为线性结构，否则为非线性结构。,线性表是最简单、最常用的一种数据结构，其数据元素之间的相对位置是线性的，其存储方式为顺序存储的，如数组。,线性表的顺序存储结构具有以下两个基本特点：,线性表中所有元素所占的存储空间是连续的；,线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。,基本操作：插入,/,删除元素。,在平均情况下，在线性表中插入,/,删除一个元素，需要移动表中一半的元素。,例：如果一个线性表第1个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是_。,108,分析：,数据元素的存储地址取决于第1个元素的存储地址，即：第i个元素的存储地址=,第1个元素的地址+(i 1)每个元素的长度,四、栈,栈,-,是限定在一端进行插入与删除的线性表，一端封闭，另一端开口。,在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。,其操作原则是“先进后出”。,栈的运算有入栈、退栈、读栈顶元素。,在顺序存储结构下，对这种类型线性表的插入与删除运算是不需要移动表中其他数据元素的。,例：下列关于栈的叙述正确的是,。,A.栈按“先进先出”组织数据,B.栈按“先进后出”组织数据,C.只能在栈底插入数据,D.不能删除数据,答案：B,例：一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E 依次入栈，然后再依次出栈，则元素出栈的顺序是（）。,A）12345ABCDE,B）EDCBA54321,C）ABCDE12345,D）54321EDCBA,答案：B,例：一个栈的入栈序列是1,2,3,n，其出栈序列是P1,P2,P3,Pn。如果P1=n，那么Pi为_,。,n i+1,分析：,栈是先进后出的线性表。当P1=n，即n是最先出栈的，n必定是最后入栈的。那么，进栈顺序是：1,2,3,n，则出栈的顺序是：n,n 1,n 2,1。,例：假设用一个长度为50 的数组（数组元素的下标从0 到49）作为栈的存储空间，栈底指针bottom 指向栈底元素，栈顶指针top 指向栈顶元素，如果bottom=49，top=30（数组下标），则栈中具有_个元素。,答案：20,五、队列,队列,-,是指在一端进行插入（称为队尾）而在另一端进行删除（称为队头）的线性表。,尾指针（,rear,）总是指向最后被插入的元素。,排头指针（,front,）指向排头元素的前一个位置。,其操作规则是“先进先出”。,其运算有入队和退队。,循环队列,-,就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。,循环队列主要有两种基本运算：,（,1,）入队运算：,rear=,rear,+1,（,2,）退队运算：,front=,front,+1,例：线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的,存储结构。,答案：顺序,例：下列对队列的叙述正确的是,A.队列属于非线性表,B.队列按“先进后出”原则组织数据,C.队列在队尾删除数据,D.队列按“先进先出”原则组织数据,答案：D,例：设某循环队列的容量为50，头指针front=5（指向队头元素的前一位置），尾指针rear=29（指向队尾元素），则该循环队列中共有,个元素。,考察数据结构的循环队列的知识。队列元素数为：rear-front=29-5=24个。,答案：24,在循环队列中:,若frontrear，队列中有n-front+rear个元素（其中n为循环队列的容量）；,若front 1,，则该结点的父结点编号为,INT(k/2),。,若,2kn,，则编号为,k,的结点的左子结点编号为,2k,；否则该结点无左子结点（显然也无右子结点）。,若,2k+1n,，则编号为,k,的结点的右子结点编号为,2k+1,；否则该结点无右子结点。,完全二叉树的两个性质,（4）二叉树的遍历,二叉树的遍历是指不重复地访问二叉树中的所有结点。,前序遍历：根节点-遍历左子树-遍历右子树,中序遍历：遍历左子树-根节点-遍历右子树,后序遍历：遍历左子树-遍历右子树-根节点,例：对下列二叉树进行前序遍历的结果为,。,A.DYBEAFCZX,B.DEBFZXCA,C.ABDYECFXZ,D.ABCDEFXYZ,答案：C,例：对下列二叉树进行中序遍历的结果,。,答案：DBXEAYFZC,【例】设一棵二叉树的前序遍历结果为A、B、D、E、C、F，中序遍历结果为D、B、E、A、F、C。则其后序遍历的结果为 _。,D,、,E,、,B,、,F,、,C,、,A,A,B,C,D,F,E,【例】设一棵二叉树的中序遍历为CDBAFEHG，后序遍历为DCBFHGEA。则其前序遍历的结果为 _。,ABCDEFGH,A,B,E,C,F,G,D,H,【例】设一棵二叉树的前序遍历结果为A、B、D、H、E、C、F、I、J、G，中序遍历结果为D、H、B、E、A、I、F、J、C、G。则其后序遍历的结果为 _ _ _ _。,H,、,D,、,E,、,B,、,I,、,J,、,F,、,G,、,C,、,A,A,D,H,F,G,J,I,E,B,C,例：深度为5的满二叉树有_个叶子结点。,根据二叉树的性质：二叉树第i（i1）层上至多有2,i-1,个结点。得到第5层的节点数最多是16。,答案：16,例：某二叉树有n个度为2的结点，则该二叉树的叶子结点为,个。,A.n+1 B.n-1,C.2n D.n/2,据二叉树性质3，在任意一棵二叉树中，度为0的节点（即叶子节点）总比度为2的节点多一个，即n0=n2+1。,答案：A,例：一棵二叉树有10个度为1的结点，7个度为2的结点，则该二叉树共有,个结点。,答案：25,例：某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在第1层）,A.3 B.4 C.6 D.7,答案：D,例：在深度为7的满二叉树中，度为2的结点个数为,。,答案：63,分析：根据二叉树性质1，该深度为7的满二叉树的叶子结点个数为2,(7-1),个。根据二叉树性质2，该深度为7的满二叉树的总结点个数为2,7,-1个。故深度为2的结点个数为：n2=2,7,-1-2,(7-1),=63,分析：,根据二叉树性质1，满二叉第7层的叶子结点数为2,7,-1个，即64个。根据二叉树的叶子结点总比度为2的结点数多1个的结论，故度为2的结点个数为：64-1=63,例：一棵二叉树共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为,。,A.219 B.221,C.229 D.231,二叉树性质3：度为0的结点比度为2的结点多一个。故总结点数为：,M=n0+n1+n2,=n0+n1+(n0-1),=2n0+n1-1,=2*70+80-1=219,答案：A,【例】设树T的度为4，其中度为1,2,3,4的结点个数分别为：4,2,1,1。则这棵树中的叶子结点有 _。,8,分析：,（1）此树的结点数（含根结点和叶子结点）共计：,14+22+31+41+1=16,（2）此树的子树共计：4+2+1+1=8,（3）因此该树的叶子结点为：16 8=8,【例】设一棵完全二叉树共有700个结点，则在该二叉树中有 _ 叶子结点。,350,分析：,根据完全二叉树的性质6（P36）可知：,（1）编号700的叶子结点（即最后一个叶子结点），其父结点编号为：INT(700/2)=350,（2）编号为350的结点为最后一个树结点，即：编号1至350均为父结点，计350个；编号351至700均为叶子结点。,（3）所以叶子结点的个数为：700 350=350,九、查找技术,（一）顺序查找,顺序查找一般指在线性表中查找指定的元素。,在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中的一半元素进行比较。最大查找次数为,n,次。,（二）二分法查找,二分法查找只适用于顺序查找的有序表。,有序表,元素按值,非递减,排列的线性表。,对于长度为,n,的有序线性表，在最坏情况下，二分查找只需要比较,log,2,n,次，而顺序查找需要比较,n,次。,例：有序线性表能进行二分查找的前提是该线性表必须是,存储的。,答案：升序,例：在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为,。,A）63B）64,C）6D）7,答案：B,例：在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（）。,A,）,O(n)B,）,O(n,2,),C,）,O(log,2,n)D,）,O(nlog,2,n),二分查找的效率要比顺序查找高得多。对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log,2,n次，而顺序查找需要比较n次。,答案：C,十、排序技术,（一）交换类排序,交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。,（1）冒泡排序法,冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2。,（2）快速排序法,快速排序过程中，随着对各子表不断地进行分割，划分出的子表会越来越多，但一次又只能对一个子表进行再分割处理，需要将暂时不分割的子表记忆起来，这就要用一个栈来实现。,（1）简单插入排序,将无序序列中的各个数据元素依次插入到已经有序的线性表中。,长度为,n,的线性表，在最坏的情况下，简单插入排序需要经过,n(n 1)/2,次的比较。,（,2,）希尔排序法,将整个无序序列分割成若干小的子序列分别进行插入排序。,长度为,n,的线性表，在最坏的情况下，希尔排序所需要的比较次数为：,O(n,1,.,5,),（二）插入类排序,（三）选择类排序,（1）简单选择排序,扫描整个线性表，从选出最小的元素，将它交换到最前面；对剩下的子表采用同样的方法，直到子表为空。,长度为,n,的序列，在最坏的情况下，简单选择排序法需要经过,n(n 1)/2,次的比较。,（,2,）堆排序法,长度为,n,的序列，,在最坏的情况下，堆排序的比较次数为,O(nlog,2,n),。,假设线性表的长度为n，则：,冒泡排序和简单插入排序的比较次数（时间复杂度）为n(n-1)/2；,希尔排序的比较次数为O(n,1.5,)；,简单选择排序的比较次数为n(n-1)/2；,堆排序的比较次数为O(nlog,2,n)。,例：冒泡排序在最坏的情况下的比较次数是,。,A.n(n+1)/2,B.nlog,2,n,C.n(n-1)/2,D.n/2,答案：C,例：对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-1)/2的排序方法是_。,A 快速排序,B 冒泡排序,C 直接插入排序,D 堆排序,答案：D,例：按“先进后出”原则组织数据的数据结构是,。,答案：栈,例：数据结构分为线性结构和非线性结构，带链的队列属于,。,答案：线性结构,第二章 程序设计基础,【本章考试要点】,程序设计方法与风格。,结构化程序设计。,面向对象的程序设计方法，掌握并理解对象、方法、属性，以及继承与多态性的概念。,程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。,当今主导的程序设计风格是著名的：“清晰第一，效率第二”。,一、程序设计方法与风格,要形成良好的程序设计风格，应注重和考虑这些因素：,源程序文档化,数据说明的方法,语句的结构,输入和输出,1.结构化程序设计的原则,结构化程序设计方法的主要原则可以概括为：,自顶向下,逐步求精,模块化,限制使用goto语句,二、结构化程序设计,2.结构化程序设计的三种基本结构分别是：,顺序结构 选择结构循环结构,使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑；,选用的控制结构只准许一个入口和一个出口；,程序语句组成容易识别的块，每块只有一个入口和一个出口；,复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现；,语言中所没有的控制结构，应该采用前后一致的方法来模拟；,严格控制goto语句的使用。,注意：,面向对象方法的优点,与人类习惯的思维方法一致；,稳定性好；,可重用性好；,易于开发大型软件产品；,可维护性好,。,三、面向对象的程序设计,2、面向对象方法的基本概念,1、对象,面向对象程序设计中的最基本的概念。,用来表示客观世界中的任何实体。,它既可以是具体的物理实体，也可以是一个抽象的概念。,对象具有：标识惟一性、分类性、多态性、封装性和模块独立性。,2,、属性,对象所包含的信息。,一般只能通过执行对象的操作来改变。,3、操作（方法）,描述了对象的执行功能，若通过信息传递，还可以为其它对象使用。,操作过程对外是封闭的，用户只能看到这一操作实施后的结果。,4,、类和实例,类是具有共同属性、共同方法的对象的集合。,类的对象的抽象，它描述了属于该对象类型的所有对象的性质；而一个对象则是其对应类的一个实例。,5、消息（事件）,面向对象的世界是通过对象与对象间彼此的相互合作来推动的，对象间的这种相互合作需要一个机制协助进行，这样的机制称为“消息”。,6、继承,继承是使用已有的类定义作为基础建立新类的定义技术。已有的类可当做基类来引用，则新类相应地可当做派生类来引用。,继承是指能够直接获得已有的性质和特征，而不必重复定义它们。,7、多态性,对象根据所接受的消息而做出的动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。,多态性是指子类对象可以像父类对象那样使用，同样的消息既可以发送给父类对象，也可以发送给子类对象。,多态性机制增加了面向对象软件系统的灵活性，进一步减少了信息冗余。,面向对象程序设计中，对象具有以下特征：,继承性,抽象性,封装性,多态性,例：下列选项中不符合良好程序设计风格的是,。,A）源程序要文档化,B）数据说明的次序要规范化,C）避免滥用goto语句,D）模块设计要保证高耦合、高内聚,模块设计要保证低耦合、高内聚,答案：D,例：在结构化程序设计中，模块划分的原则是_。,A各模块应包括尽量多的功能,B各模块的规模应尽量大,C各模块之间的联系应尽量紧密,D模块内有高内聚度，模块间有低耦合度,答案：D,例：下面选项中不属于面向对象程序设计的是_。,A继承性 B.多态性,C.类比性 D.封装性,（面向对象程序设计的特征包括：分类性、多态性、封装性、继承性等。）,答案：C,例：在面向对象方法中，实现信息隐蔽是依靠_。,A.对象的继承,B.对象的多态,C.对象的封装,D.对象的分类,对象的封装性，即从外面只能看到对象的外部特征，而对象的内部状态对外是不可见的。因此对象的信息隐蔽是依靠对象的封装来实现的。,答案：C,例：下列叙述中，不符合良好程序设计风格要求的,是（）。,A.程序的效率第一，清晰第二,B.程序的可读性好,C.程序中要有必要的注释,D.输入数据前要有提示信息,软件在编码阶段，力求程序语句简单、直接，不能只为了追求效率而使语句复杂化。除非对效率有特殊的要求，程序编写要做到,清晰第一、效率第二,。,答案：A,例：在面向对象方法中，不属于“对象”基本特点的,是,。,A）一致性 B）分类性,C）多态性 D）标识唯一性,对象的基本特点：,标识唯一性；,分类性；,多态性；,封装性；,模块独立性好,。,答案：A,例：下列叙述中正确的是,。,A.程序执行的效率与数据的存储结构密切相关,B.程序执行的效率只取决于程序的控制结构,C.程序执行的效率只取决于所处理的数据量,D.以上三种说法都不对,一种数据的逻辑结构根据需要可以表示成多种存储结构，而采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构是很重要的。,答案：A,例：符合结构化原则的三种基本控制结构是：选择结构、循环结构和,。,答案：顺序结构,例：下列选项中不属于结构化程序设计原则的,是（）。,A）可封装 B）自顶向下,C）模块化 D）逐步求精,结构化程序设计方法的主要原则可以概括为自顶向下，逐步求精，模块化，限制使用goto语句等。,答案：A,第三章 软件工程基础,【本章考试要点】,软件工程基本概念；软件生命周期概念；软件工具与软件开发环境。,结构化分析方法、数据流图、数据字典、软件需求规格说明书的概念。,结构化设计方法、总体设计与详细设计。,软件测试方法、白盒测试与黑盒测试、测试用例设计、软件测试的实施、单元测试、集成测试和测试系统。,程序调试、静态调试与动态调试。,一、软件工程基本概念,1、软件定义,（1）软件的定义：软件是与计算机操作相关的计算机程序、规程、规则，以及可能有的文件、文档及数据。,软件的三个要素：,程序,数据,文档,（2）软件分类：软件按功能可分为三大类：,应用软件,系统软件,支撑软件（或工具软件）,（3）软件危机的定义：,软件危机是泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。,（1）软件工程的定义：,软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。软件工程的三个要素：方法、工具和过程。,2、软件工程定义与软件生命周期,（2）软件生命周期就是软件产品从提出、实现、使用维护到停止使用退役的全过程。,软件定义阶段的任务包括可行性研究与计划制定、需求分析；,软件开发阶段的任务包括概要设计、详细设计、软件实现、软件测试；,软件维护阶段的任务包括软件的运行、维护和退役。,（1）软件开发工具,软件开发工具的发展是从单项工具的开发逐步向集成工具发展的，软件开发工具为软件工程方法提供了自动的或半自动的软件支撑环境。,3、软件开发工具与软件开发环境,（2）软件开发环境,软件开发环境或称软件工程环境是全面支持软件开发全过程的软件工具集合。这些软件工具按照一定的方法或模式组合起来，支持软件生命周期内的各个阶段和各项任务的完成。,1、需求分析与需求分析方法,需求分析的定义,需求分析阶段的工作,需求分析方法,结构化分析方法,面向对象的分析方法,二、结构化分析方法,2.关于结构化分析方法,结构化分析方法是结构化程序设计理论在软件需求分析阶段的运用。,结构化分析的常用工具有：,数据流图（,DFD,）,（记住,DFD,图的几个符号）,数据字典（,DD,）,判定树和判定表。,其中最重要的工具是数据流图,。,数据流图是通过对需求的理解构造出逻辑模型的图形表示，它直接支持系统的功能建模。,数据字典是结构化分析方法的核心。数据字典是对所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义，使得用户和系统分析员对输入、输出、存储成分和中间计算结果用共同的理解,。,3.结构化分析的常用工具,软件需求规格说明书（SRS）是需求分析阶段的最后结果，是软件开发中的重要文档之一。,作用,内容,特点,4.软件需求规格说明书,软件设计的基本概念：,软件设计是软件工程的重要阶段，是一个把软件需求转换为软件表示的过程。,软件设计的基础目标是用比较抽象概括的方式确定目标系统如何完成预定的任务，即软件设计是确定系统的物理模型。,三、结构化设计方法,从技术观点看，软件设计包括结构设计、数据设计、接口设计和过程设计。,结构设计是定义软件系统各主要部件之间的关系。,数据设计是将分析时创建的模型转化为数据结构的定义。,接口设计是描述软件内部、软件和协作系统之间以及软件与人之间如何通信。,过程设计是把系统结构部件转换成软件的过程性描述。,软件设计的内容,结构化设计方法的基本思想：将软件设计成相对独立、单一功能的模块组成的结构。,为了提高模块的独立性，应该尽量提高模块的内聚性，降低模块间的耦合性。,概要设计的基本任务：设计软件系统结构、确定数据结构及数据库设计、编写概要设计文档、进行概要设计文档评审。,软件结构设计工具,结构图（,SC,），也称为程序结构图。结构图是描述软件结构的图形工具。,（1）概要设计,a.提高模块独立性；,b.模块规模适中；,c.深度、宽度、扇出和扇入适当；,d.使模块的作用域在该模块的控制域内；,e.应减少模块的接口和界面的复杂性；,f.设计成单入口、单出口的模块；,g.设计功能可预测的模块。,软件设计的准则,详细设计的任务：为软件结构图中的每一个模块确定实现算法的局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。,过程设计的任务：对每个模块规定的功能以及算法的设计，给出适当的算法描述。,（2）详细设计,常见的过程设计工具有：,a.,程序流程图，,N-S,（方框图），,PAD,（问题分析图）；,b.,表格工具：判定表；,c.,语言工具：,PDL,（过程设计语言）。,程序流程图,N-S图,软件测试是保证软件质量的重要手段，其主要过程涵盖了整个软件生命期的过程，包括需求定义阶段的需求测试、编码阶段的单元测试、继承测试以及后期的确认测试、系统测试、验证软件是否合格、能否交付用户使用等。,1、软件测试,四、软件测试及程序的调试,软件测试是为了发现错误而执行程序的过程：,一个好的测试用例是指很可能找到迄今为止尚未发现的错误的用例；,一个成功的测试是发现了至今尚未发现的错误的测试。,（1）软件测试的目的,软件测试过程中应遵循以下准则：,所有测试都有追溯到需求；,严格执行测试计划，派出测试的随意性；,充分注意测试中的群集现象；,程序员应避免监察自己的程序；,穷举测试不可能；,妥善保存测试计划、测试用例、出错统计和最终分析报告。,（2）软件测试的准则,软件测试从是否要执行被测试软件的角度可以分为静态测试和动态测试。,软件测试按照功能划分可分为白盒测试和黑盒测试方法。,（3）软件测试技术与方法综述,白盒测试又称结构测试或逻辑驱动测试，是根据软件产品的内部工作过程，检测内部成分，以确认每种内部操作符合设计规范要求。,白盒测试,a.保证所测模块中每一独立路径至少执行一次；,b.保证所测模块所有判断的每一分支至少执行一次；,c.保证所测模块每一循环都在边界条件和一般条件下至少各执行一次；,d.验证所有内部数据结构的有效性。,白盒测试的基本原则：,a.,逻辑覆盖测试方法,：逻辑覆盖是泛指一系列以程序内部的逻辑结构为基础的测试用例设计技术。逻辑覆盖测试方法有语句覆盖、路径覆盖、判定覆盖、条件覆盖以及判断-条件覆盖。,b.,基本路径测试,：基本路径测试的思想和步骤是，根据软件过程性描述中的控制流程确定程序的环路复杂性度量，用此度量定义基本路径集合，并由此导出一组测试用例对每一条独立执行路径进行测试。,白盒测试的主要方法：,黑盒测试也称功能测试或数据驱动测试，是对软件已经实现的功能是否满足需要进行测试和验证。,黑盒测试,a.,等价类划分法,：将程序的所有可能的输入数据划分成若干部分（及若干等价类），然后从每个等价类中选取数据作为测试用例。,b.,边界值分析法,：边界值分析法是对各种输入、输出范围的边界情况设计测试用例的方法。,c.,错误推测法,：靠经验和直觉推测程序中可能存在的各种错误，从而有针对性地编写检查这些错误的例子的方法。,黑盒测试的方法,软件测试过程一般按4个步骤进行，即：,单元测试,集成测试,验收测试（确认测试）,系统测试。,（4）软件测试的实施,程序调试的任务是诊断和改正程序中的错误，它与软件测试不同，软件测试是尽可能多地发现软件中的错误。软件测试贯穿整个软件生命期，调试主要在开发阶段。,2、程序的调试,程序调试的基本步骤：,第,1,步：错误定位；,第,2,步：修改设计和代码，以排除错误；,第,3,步：进行回归测试，防止引进新的错误。,主要的软件调试方法有：,强行排错法、回溯法、原因排除法。,强行排错法是传统的调试方法，,回溯法适合于小规模的排错，,原因排除法是通过演绎和回归，以及二分法来实现的。,软件调试方法,例：从工程管理角度，软件设计一般分为两步完成，它们是,。,A）概要设计与详细设计,B）数据设计与接口设计,C）软件结构设计与数据设计,D）过程设计与数据设计,从技术观点来看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。从工程管理角度，软件设计分为两步完成：概要设计和详细设计。,答案：A,例：下列选项中不属于软件生命周期开发阶段任务的是,。,A）软件测试B）概要设计,C）软件维护D）详细设计,答案：C,例：_的任务是诊断和改正程序中的错误。,答案：软件调试,例：下列叙述中正确的是,。,A软件测试的主要目的是发现程序中的错误,B软件测试的主要目的是确定程序中错误的位置,C为了提高软件测试的效率，最好由程序编制者自己来完成软件测试的工作,D软件测试是证明软件没有错误,软件测试的主要目的是为了发现软件中还没有被发现的错误；软件调试的目的是定位及改正软件中的错误。,答案：A,例：软件测试分为白箱（盒）测试和黑箱（盒）测试，等阶类划分法属于,测试。,黑箱测试的方法有等价类划分法、错误推测法、边界值分析法等；白箱测试的方法有基本路径测试、逻辑覆盖等。,答案：黑箱（盒）测试,例：软件生命周期可分为多个阶段，一般分为定义阶段、开发阶段和维护阶段。编码和测试属于,阶段。,软件开发阶段可分为：概要设计、详细设计、软件测试，而编码属于详细设计阶段的主要任务。,答案：开发阶段,例：软件是指,。,A.程序,B.程序和文档,C.算法加数据结构,D.程序、数据与相关文档的完整集合,软件是计算机系统中与硬件相互依存的另一部分，是包括程序、数据和相关文档的完整集合。,答案：D,例：软件需求规格说明书应具有完整性、无歧义性、可验证性、可修改性等特性，其中最重要的是,。,无歧义性。作为设计的基础和验收的依据，软件需求规格说明书应该是精确而无二义性的，需求说明书越精确，则以后出现错误、混淆、反复的可能性就越小,。,答案：无歧义性,例：在两种基本测试方法中，,测试的原则之一是保证所测模块中每一个独立路径至少执行一次。,答案：路径覆盖,例：软件设计中模块划分应遵循的准则是,。,A 低内聚低耦合B 高内聚低耦合,C 低内聚高耦合D 高内聚低耦合,答案：B,例：在软件开发中，需求分析阶段产生的主要,文档是,。,A）可行性分析报告,B）软件需求规格说明书,C）概要设计说明书,D）集成测试计划,答案：B,例：在软件开发中，需求分析阶段可以使用的,。,工具是（）。,A）N-S 图,B）DFD 图,C）PAD 图,D）程序流程图,结构化分析常用工具：数据流图（DFD）、数据字典（DD）。详细设计阶段常用的工具：程序流程图，N-S图，PAD图。,答案：B,例：按照软件测试的一般步骤，集成测试应,在,测试之后进行。,软件测试过程一般按4个步骤进行，即单元测试、集成测试、验收测试（确认测试）和系统测试,。,答案：单元,例：软件工程三要素包括方法、工具和过程，,其中，,支持软件开发的各个环节的控制和管理。,软件工程包括3个要素，即方法、工具和过程。方法是完成软件工程项目的技术手段；工具支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理。,答案：过程,例：软件按功能可以分为：应用软件、系统软件和支撑软件（或工具软件）。下面属于应用软件的是,。,A）编译程序 B）操作系统,C）教务管理系统 D）汇编程序,编译程序、操作系统和汇编程序都属于系统软件。而只有教务管理系统是为解决特定领域的应用而开发的软件，属于应用软件的范畴,。,答案：C,例：下面叙述中错误的是,。,A）软件测试的目的是发现错误并改正错误,B）对被调试的程序进行“错误定位”是程序调试的必要步骤,C）程序调试通常也称为Debug,D）软件测试应严格执行测试计划，排除测试的随意性,软件测试的目的是为了发现错误，而改正错误属于程序调试的范畴。,答案：A,例：软件测试可分为白盒测试和黑盒测试。基本路径测试属于,测试。,白盒测试的主要方法有逻辑覆盖、基本路径测试等。,答案：白盒测试,例：程序流程图中带箭头的线段表示的是,。,A 图元关系B 数据流,C 控制流 D 调用关系,详细设计阶段的主要描述工具分为图形、语言和表格描述工具。程序流程图是常用的图形描述工具之一，流程图中包含的主要元素有方框：表示一个处理步骤；菱形框：表示一个逻辑条件；箭头：表示控制流向。,答案：C,例：下图所示的流程控制结构称为,。,答案：分支结构（选择结构或条件结构）,例：某系统总体结构图如下图所示：,该系统总体结构图的深度是,A)7B)6C)3D)2,答案：C,例：在结构化分析使用的数据流图（DFD）中，利用,对其中的图形元素进行确切解释。,数据字典的作用是对DFD中出现的被命名的图形元素的确切解释。,答案：数据字典,第四章 数据库设计基础,【本章考试要点】,数据库的基本概念：数据库、数据库管理系统、数据库系统。,数据模型、实体联系模型及,ER,图，从,ER,图导出关系数据模型。,关系代数运算：集合运算及选择、投影、联接运算。,数据库规范化理论。,数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。,1、数据、数据库数据库管理系统,数据,数据库,长期存储在计算机内的、有组织的、可共享的数据集合。,数据库是由一个互相关联的数据的集合和一组用以访问这些数据的程序组成。,数据库管理系统,数据库管理员,数据库系统,数据库应用系统,一、数据库系统的基本概念,2、数据库系统的发展,人工管理阶段,文件系统阶段,数据库统阶段,3、,数据库系统的基本特点,数据的集成性,数据的高共享性与低冗余性,数据的独立性（物理独立性与逻辑独立性）,数据统一管理与控制,4、数据库系统的内部结构体系,三级模式,概念模式,内模式,外模式,两级映射,概念模式到内模式的映射,外模式到概念模式的映射,1、数据模型的基本概念,数据模型的定义,数据模型所描述内容的三个部分,数据结构、数据操作,、,数据约束,数据模型的类型,概念模型面向用户的模型,逻辑模型（数据模型）,面向数据库系统的模型，只有转换成数据模型后才能在数据库中得以表示。,物理模型面向计算机的物理表示,二、数据模型,2、E R 模型,长期以来被广泛使用的概念模型是E R模型,E R模型的基本概念,实体,属性,联系（1:1、1:m、m:n）,E R模型三个基本概念之间的连接关系,实体集（联系）与属性之间的连接关系,实体（集）与联系,E R模型的图示法,实体集表示法（矩形）,属性表示法（椭圆形）,联系表示法（菱形）,实体集（联系）与属性之间的连接关系,实体集与联系之间的连接关系,E-R图,3、层次模型,是最早发展起来的数据库模型,层次模型的基本结构是树形结构,树结构的特点,4、网状模型,是一个不加任何条件限制的无向图,一般采用分解的方法将一个网络分成若干个二级树,5、关系模型,关系的数据结构,关系模型采用二维表来表示,二维表由表的框架及表的元组组成,二维表一般满足七个性质,关系模型中的重要概念 键（码）,键（二维表中凡能惟一识别元组的最小属性集称该表的键）,候选键,主键,外键,关系操纵,关系模型的数据操纵是建立在关系上的数据操纵，包括：,数据查询,数据删除,数据插入,数据修改,关系中的数据约束,关系模型允许3类数据约束：,实体完整性约束,主键的值不能为空,参照完整性约束,不允许关系引用不存在的元组,用户自定义约束,针对具体数据环境由用户设置的约束,1、关系模型的基本操作,关系是由若干个不同的元组所组成，因此关系可视为元组的集合。,关系模型有插入、删除、修改和查询4种操作,关系的属性指定,关系的元组选择,关系的合并,关系的查询,关系元组的插入,关系元组的删除,三、关系代数,关系是有序组的集合，因此可以将操作看作是集合的运算。,关系模型的基本运算包括：,插入RR,删除R-R,修改(R-R)R （先删后插）,查询,用于查询运算的3个操作需引入新的运算：,投影 （字段）,选择（记录）,笛卡尔儿积 T=RS,2、关系模型的基本运算,3、关系代数中的扩充运算,交运算RS=R-(R-S),除运算T/R=S,连接与自然连接运算,连接是将两个关系按指定的条件合并成一个关系（条件可以是等值或不等值）,自然连接必须满足：,两关系间有公共域,通过公共域的,相等值,进行连接,【例】,关系R和S如下图，它们自然连接后得到T。,A,B,C,D,1,2,3,4,1,5,8,3,2,4,2,6,1,1,4,7,D,E,5,1,6,4,7,3,6,8,A,B,C,D,E,2,4,2,6,4,2,4,2,6,8,1,2,4,7,3,T,R,S,【例】,关系R和S如下图，它们按DE进行连接后得到T。,A,B,C,D,1,2,3,4,3,2,1,8,7,3,1,1,E,F,1,8,7,9,5,2,A,B,C,D,E,F,1,2,3,4,1,8,3,2,1,8,1,8,3,2,1,8,7,9,3,2,1,8,5,2,T,R,S,1、数据库设计概述,数据库设计一般采用生命周期法。,数据库应用系统的开发分为若干个阶段,需求分析阶段（需求说明书）,概念设计阶段（概念数据模型）,逻辑设计阶段（逻辑数据模型）,物理设计阶段（数据库内模式