全国计算机二级辅导-公共基础部分.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个元素的地址+(i1)每个元素的长度,四、栈,栈-是限定在一端进行插入与删除的线性表，一端封闭，另一端开口。在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。其操作原则是“先进后出”。栈的运算有入栈、退栈、读栈顶元素。在顺序存储结构下，对这种类型线性表的插入与删除运算是不需要移动表中其他数据元素的。,例：下列关于栈的叙述正确的是。A.栈按“先进先出”组织数据B.栈按“先进后出”组织数据C.只能在栈底插入数据D.不能删除数据,答案：B,例：一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（）。A）12345ABCDEB）EDCBA54321C）ABCDE12345D）54321EDCBA,答案：B,例：一个栈的入栈序列是1,2,3,n，其出栈序列是P1,P2,P3,Pn。如果P1=n，那么Pi为_。,ni+1,分析：栈是先进后出的线性表。当P1=n，即n是最先出栈的，n必定是最后入栈的。那么，进栈顺序是：1,2,3,n，则出栈的顺序是：n,n1,n2,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为循环队列的容量）；若front1，则该结点的父结点编号为INT(k/2)。若2kn，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（显然也无右子结点）。若2k+1n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。,完全二叉树的两个性质,（4）二叉树的遍历,二叉树的遍历是指不重复地访问二叉树中的所有结点。前序遍历：根节点-遍历左子树-遍历右子树中序遍历：遍历左子树-根节点-遍历右子树后序遍历：遍历左子树-遍历右子树-根节点,例：对下列二叉树进行前序遍历的结果为。A.DYBEAFCZXB.DEBFZXCAC.ABDYECFXZD.ABCDEFXYZ,答案：C,例：对下列二叉树进行中序遍历的结果。,答案：DBXEAYFZC,【例】设一棵二叉树的前序遍历结果为A、B、D、E、C、F，中序遍历结果为D、B、E、A、F、C。则其后序遍历的结果为_。,D、E、B、F、C、A,【例】设一棵二叉树的中序遍历为CDBAFEHG，后序遍历为DCBFHGEA。则其前序遍历的结果为_。,ABCDEFGH,【例】设一棵二叉树的前序遍历结果为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,例：深度为5的满二叉树有_个叶子结点。,根据二叉树的性质：二叉树第i（i1）层上至多有2i-1个结点。得到第5层的节点数最多是16。,答案：16,例：某二叉树有n个度为2的结点，则该二叉树的叶子结点为个。A.n+1B.n-1C.2nD.n/2,据二叉树性质3，在任意一棵二叉树中，度为0的节点（即叶子节点）总比度为2的节点多一个，即n0=n2+1。,答案：A,例：一棵二叉树有10个度为1的结点，7个度为2的结点，则该二叉树共有个结点。,答案：25,例：某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在第1层）A.3B.4C.6D.7,答案：D,例：在深度为7的满二叉树中，度为2的结点个数为。,答案：63,分析：根据二叉树性质1，该深度为7的满二叉树的叶子结点个数为2(7-1)个。根据二叉树性质2，该深度为7的满二叉树的总结点个数为27-1个。故深度为2的结点个数为：n2=27-1-2(7-1)=63,分析：根据二叉树性质1，满二叉第7层的叶子结点数为27-1个，即64个。根据二叉树的叶子结点总比度为2的结点数多1个的结论，故度为2的结点个数为：64-1=63,例：一棵二叉树共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为。A.219B.221C.229D.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）因此该树的叶子结点为：168=8,【例】设一棵完全二叉树共有700个结点，则在该二叉树中有_叶子结点。,350,分析：根据完全二叉树的性质6（P36）可知：（1）编号700的叶子结点（即最后一个叶子结点），其父结点编号为：INT(700/2)=350（2）编号为350的结点为最后一个树结点，即：编号1至350均为父结点，计350个；编号351至700均为叶子结点。（3）所以叶子结点的个数为：700350=350,九、查找技术,（一）顺序查找顺序查找一般指在线性表中查找指定的元素。在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中的一半元素进行比较。最大查找次数为n次。,（二）二分法查找二分法查找只适用于顺序查找的有序表。有序表元素按值非递减排列的线性表。对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。,例：有序线性表能进行二分查找的前提是该线性表必须是存储的。,答案：升序,例：在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为。A）63B）64C）6D）7,答案：B,例：在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（）。A）O(n)B）O(n2)C）O(log2n)D）O(nlog2n),二分查找的效率要比顺序查找高得多。对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。,答案：C,十、排序技术,（一）交换类排序交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。（1）冒泡排序法冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2。（2）快速排序法快速排序过程中，随着对各子表不断地进行分割，划分出的子表会越来越多，但一次又只能对一个子表进行再分割处理，需要将暂时不分割的子表记忆起来，这就要用一个栈来实现。,（1）简单插入排序将无序序列中的各个数据元素依次插入到已经有序的线性表中。长度为n的线性表，在最坏的情况下，简单插入排序需要经过n(n1)/2次的比较。（2）希尔排序法将整个无序序列分割成若干小的子序列分别进行插入排序。长度为n的线性表，在最坏的情况下，希尔排序所需要的比较次数为：O(n1.5),（二）插入类排序,（三）选择类排序,（1）简单选择排序扫描整个线性表，从选出最小的元素，将它交换到最前面；对剩下的子表采用同样的方法，直到子表为空。长度为n的序列，在最坏的情况下，简单选择排序法需要经过n(n1)/2次的比较。（2）堆排序法长度为n的序列，在最坏的情况下，堆排序的比较次数为O(nlog2n)。,假设线性表的长度为n，则：冒泡排序和简单插入排序的比较次数（时间复杂度）为n(n-1)/2；希尔排序的比较次数为O(n1.5)；简单选择排序的比较次数为n(n-1)/2；堆排序的比较次数为O(nlog2n)。,例：冒泡排序在最坏的情况下的比较次数是。A.n(n+1)/2B.nlog2nC.n(n-1)/2D.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）程序调试通常也称为DebugD）软件测试应严格执行测试计划，排除测试的随意性,软件测试的目的是为了发现错误，而改正错误属于程序调试的范畴。,答案：A,例：软件测试可分为白盒测试和黑盒测试。基本路径测试属于测试。,白盒测试的主要方法有逻辑覆盖、基本路径测试等。,答案：白盒测试,例：程序流程图中带箭头的线段表示的是。A图元关系B数据流C控制流D调用关系,详细设计阶段的主要描述工具分为图形、语言和表格描述工具。程序流程图是常用的图形描述工具之一，流程图中包含的主要元素有方框：表示一个处理步骤；菱形框：表示一个逻辑条件；箭头：表示控制流向。,答案：C,例：下图所示的流程控制结构称为。,答案：分支结构（选择结构或条件结构）,例：某系统总体结构图如下图所示：该系统总体结构图的深度是A)7B)6C)3D)2,答案：C,例：在结构化分析使用的数据流图（DFD）中，利用对其中的图形元素进行确切解释。,数据字典的作用是对DFD中出现的被命名的图形元素的确切解释。,答案：数据字典,第四章数据库设计基础,【本章考试要点】,数据库的基本概念：数据库、数据库管理系统、数据库系统。数据模型、实体联系模型及ER图，从ER图导出关系数据模型。关系代数运算：集合运算及选择、投影、联接运算。数据库规范化理论。数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。,1、数据、数据库数据库管理系统数据数据库长期存储在计算机内的、有组织的、可共享的数据集合。数据库是由一个互相关联的数据的集合和一组用以访问这些数据的程序组成。数据库管理系统数据库管理员数据库系统数据库应用系统,一、数据库系统的基本概念,2、数据库系统的发展人工管理阶段文件系统阶段数据库统阶段3、数据库系统的基本特点数据的集成性数据的高共享性与低冗余性数据的独立性（物理独立性与逻辑独立性）数据统一管理与控制,4、数据库系统的内部结构体系三级模式概念模式内模式外模式两级映射概念模式到内模式的映射外模式到概念模式的映射,1、数据模型的基本概念数据模型的定义数据模型所描述内容的三个部分数据结构、数据操作、数据约束数据模型的类型概念模型面向用户的模型逻辑模型（数据模型）面向数据库系统的模型，只有转换成数据模型后才能在数据库中得以表示。物理模型面向计算机的物理表示,二、数据模型,2、ER模型长期以来被广泛使用的概念模型是ER模型ER模型的基本概念实体属性联系（1:1、1:m、m:n）ER模型三个基本概念之间的连接关系实体集（联系）与属性之间的连接关系实体（集）与联系,ER模型的图示法实体集表示法（矩形）属性表示法（椭圆形）联系表示法（菱形）实体集（联系）与属性之间的连接关系实体集与联系之间的连接关系,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。,T,R,S,【例】关系R和S如下图，它们按DE进行连接后得到T。,T,R,S,1、数据库设计概述数据库设计一般采用生命周期法。数据库应用系统的开发分为若干个阶段需求分析阶段（需求说明书）概念设计阶段（概念数据模型）逻辑设计阶段（逻辑数据模型）物理设计阶段（数据库内模式）编码阶段测试阶段运行阶段进一步修改阶段,数据库设计,四、数据库设计与管理,2、数据库设计的需求分析需求分析是设计数据库的起点需求分析的任务需求分析的主要工具是数据流图数据字典是进行详细的数据收信和数据分析所获得的主要结果，包括五个部分：数据项（数据的最小单位）数据结构数据流（可以是数据项或数据结构）数据存储处理过程,3、数据库的概念设计数据库概念设计的目的数据库概念设计的方法集中式模式设计法视图集成设计法数据库概念设计的过程（使用ER图）4、数据库的逻辑设计逻辑设计是在概念设计的基础上，将与数据库管理系统无关的ER图转换成以数据库管理系统的逻辑数据模型表示的逻辑模式（关系数据模型）逻辑设计的过程,5、数据库的物理设计数据库在物理设备上的存储结构与存取方法称为数据库的物理结构，它依赖于给定的数据库管理系统和计算机系统物理设计的主要目标物理设计的内容索引设计集簇设计分区设计,数据库的建立。数据库的调整。数据库的重组。数据库安全性控制与完整性控制。数据库的故障恢复。数据库监控。,数据库管理,例：在数据库系统中，用户所见的数据模式为_。A）概念模式B）外模式C）内模式D）物理模式,外模式是用户的数据视图，就是用户所见到的数据模式。,答案：B,例：数据库设计的四个阶段是：需求分析、概念设计、逻辑设计和。A）编码设计B）测试阶段C）运行阶段D）物理设计,数据库设计主要分四个步骤：需求分析，概念结构设计，逻辑结构设计，物理结构设计。,答案：D,例：有三个关系R、S和T如下：则由关系R和S得到关系T的操作是。A)自然连接B)交C)除D)并,答案：C,例：设有如三个关系表下列操作中正确的是A）T=RSB）T=RSC）T=RSD）T=R/S,答案：C(笛卡尔积),例：数据库技术的根本目标是要解决数据的。A）存储问题B）共享问题C）安全问题D）保护问题,答案：B,例：下列实体的联系中，属于多对多联系的是。A）学生与课程B）学校与校长C）住院的病人与病床D）职工与工资,答案：A,例：在关系运算中，投影运算的含义是。A）在基本表中选择满足条件的记录组成一个新的关系B）在基本表中选择需要的字段（属性）组成一个新的关系C）在基本表中选择满足条件的记录和属性组成一个新的关系D）上述说法均是正确的,答案：B,例：SQL的含义是。A）结构化查询语言B）数据定义语言C）数据库查询语言D）数据库操纵与控制语言,答案：A,例：一个关系表的行称为。,答案：记录,例：在下列关系运算中,不改变关系表中的属性个数但能减少元组个数的是。A.并B.交C.投影D.笛卡儿乘积,答案：B,关系运算包括：常用的集合运算有交、并、差和专门的关系运算选择、投影、连接，这其中只有交、选择运算能够在不改变基本表中的属性个数但能减少元组个数。,例：在E-R图中,用来表示实体之间联系的图形是_。A.矩形B.椭圆形C.菱形D.平行四边形,在E-R图中，有三个基本的抽象概念：实体、联系和属性。E-R图示E-R模型的图形表示法，在E-R图中，用矩形框表示实体，菱形框表示联系，椭圆形框表示属性。,答案：C,例：在关系数据中,能够惟一地标识一个记录的属性或属性的结合,称为。A.关键字B.属性C.关系D.域,在关系数据库中，能够唯一标识一个记录的属性或属性的组合称为关键字。,答案：A,例：在现实世界中,每个人都有自己的出生地，实体“人”与实体”出生地”之间的联系是。A.一对一联系B.一对多联系C.多对多联系D.无联系,答案：B,例：在数据库系统中，实现各种数据管理功能的核心软件称为。,答案：数据库管理系统,例：如果表中一个字段不是本表的主关键字，而另外一个表的主关键字或候选关键字，这个字段称为_。,答案：外部关键字,例：实体完整性约束要求关系数据库中元组的属性值不能为空。,答案：关键字,例：在关系A（S,SN,D）和关系B（D,CN,NM）中，A的主关键字是S，B的主关键字是D，则称_是关系A的外码。,答案：D,例：在SQL的Select命令中用短语对查询的结果进行排序。,答案：ORDERBY,例：在关系运算中，要从关系模式中指定若干属性组成新的关系，该关系运算称为。,答案：投影,例：下列叙述中正确的是。A.为了建立一个关系，首先要构造数据的逻辑关系B.表示关系的二维表中各元组的每一个分量还可以分成若干个数据项C.一个关系的属性名表称为关系模式D.一个关系可以包括多个二维表,答案：C,例：用二维表来表示实体及实体之间联系的数据模型是。A.实体-联系模型B.层次模型C.网状模型D.关系模型,关系数据模型用二维表的形式来表示实体间的联系。,答案：D,例：在企业中，职工的“工资级别”与职工个人“工资”的联系是。A.一对一联系B.一对多联系C.多对多联系D.无联系,每个人的个人工资都对应有一个工资级别，但一个工资级别可对应多个人的个人工资，所以工资级别与工资之间的联系是一对多。,答案：B,例：假设一个书店用（书号，书名，作者，出版社，出版日期，库存数量.）一组属性来描述图书，可以作为“关键字”的是。A.书号B.书名C.作者D.出版社,关键字的定义为：若一个属性或多个属性的组合可以起到唯一识别元组的作用，即可被选取为关键字。,答案：A,例：在教师表中，如果找出职称为“教授”的教师，所采用的关系运算是。A选择B投影C联接D自然联接,选择运算是根据给定的条件选择符合条件的记录，投影运算是从关系表中选择部分属性进行显示，连接运算是把多个表进行连接显示，自然连接是连接运算的一种，自然连接的条件是共有属性对应相等进行连接。要找出职称为教授的教师是一种选择运算。,答案：A,例：在数据库管理系统提供的数据定义语言、数据操纵语言和数据控制语言中，负责数据的模式定义与数据的物理存取构建。,数据定义语言。数据定义语言用于定义数据库的所有特性和属性，尤其是行布局、列定义、键列（有时是选键方法）、文件位置和存储策略。数据库操纵语言用于查询和操纵模式对象中的数据，数据库控制语言控制用户对数据库的存取能力，控制数据库的安全性。,答案：数据定义语言,例：在数据管理技术发展的三个阶段中，数据共享最好的是（）。A）人工管理阶段B）文件系统阶段C）数据库系统阶段D）三个阶段相同,人工管理阶段：无共享，冗余度大；文件系统阶段：共享性差、冗余度大；数据库系统阶段：共享性大，冗余度小。,答案：C,例：有三个关系R、S和T如下：由关系R和S通过运算得到关系T，则所使用的运算为（）。A）笛卡尔积B）交C）并D）自然连接,答案：D,自然连接：当连接属性具有相同属性名，连接条件取值相等条件时，去掉重复属性的等值连接称为自然连接。自然连接满足下面的条件：两关系间有公共域；通过公共域的相等值进行连接。,例：数据库设计包括概念设计、和物理设计。,数据设计的四个阶段：需求分析、概念设计、逻辑设计、物理设计。,答案：逻辑设计,例：在二维表中，元组的不能再分成更小的数据项。,答案：分量,例：数据库应用系统中的核心问题是（）。A）数据库设计B）数据库系统设计C）数据库维护D）数据库管理员培训,答案：A,例：在关系数据库中，基本的关系运算有三种，它们是选择、投影和。,答案：连接,例：有两个关系R，S如下：由关系R通过运算得到关系S，则所使用的运算为（）。A）选择B）投影C）插入D）连接,答案：B,例：将E-R图转换为关系模式时，实体和联系都可以表示为（）。A）属性B）键C）关系D）域,从E-R图到关系模式的转换是比较直接的，实体与联系都可以表示成关系，E-R图中属性也可以转换成关系的属性。实体集也可以转换成关系。,答案：C,例：按数据的组织形式，数据库的数据模型可分为三种模型，它们是（）。A）小型、中型和大型B）网状、环状和链状C）层次、网状和关系D）独享、共享和实时,答案：C,数据模型是数据库管理系统用来表示实体及实体间联系的方法。一个具体的数据模型应当正确地反映出数据之间存在的整体逻辑关系。任何一个数据库管理系统都是基于某种数据模型的。数据库管理系统所支持的传统数据模型有3种：层次数据模型、网状数据模型和关系数据模型。,例：数据库中有A、B两表，均有相同字段C