全国计算机二级辅导-公共基础部分.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为循环队列的容量）；若frontrear，队列中有rear-front个元素；若front=rear，队列中有n个或0个元素。,例：设某循环队列的容量为50，如果头指针front=45（指向队头元素的前一位置），尾指针rear=10（指向队尾元素），则该循环队列中共有 个元素。,答案：15,例：下列叙述中正确的是（）。A）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B）在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况C）在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D）循环队列中元素的个数是由队头指针和队尾指针共同决定,答案：D,七、线性链表,线性链表的基本概念 在线性链表中，各数据元素之间的前后件关系是由各结点的指针域来指示的，指向线性表中第一个结点的指针HEAD称为头指针，当HEAD=NULL（或0）时称为空表。,线性链表的运算主要有：线性链表的插入、删除、查找、合并、分解、逆转、复制、排序等。,在线性链表中查找指定元素 在非空线性链表中寻找包括指定元素x的前一个结点p的基本方法如下：从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为x为止。当线性链表中不存在包含元素x的结点时，则找到的p为线性链表中的最后一个节点号。,线性链表的插入 为了在线性链表中插入一个新元素，首先要给该元素分配一个新节点，它可以从可利用栈中取得。然后将存放新元素值的结点链接到线性链表中指定的位置。,线性链表的删除 为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，然后将要删除结点放回到可利用栈。,例：下列关于线性链表的叙述中，正确的是。A）各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致B）各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续C）进行插入与删除时，不需要移动表中的元素D）以上三种说法都不对,答案：C,八、树,树-是一种简单的非线性结构，是层次结构。树结构中，每一个结点只有一个前件，称为父结点。没有前件的结点只有一个，称为树的根结点。在树结构中，每一个结点可以有多个后件，它们称为该结点的子结点。没有后件的结点称为叶子结点。一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。,（1）二叉树的定义,二叉树具有以下两个特点：非空二叉树只有一个根结点每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域。,（2）二叉树的基本性质,二叉树具有以下几个性质：性质1：在二叉树的第k层上，最多有2k-1（k1）个结点。性质2：深度为m的二叉树最多有2m-1个结点。性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。如果叶子结点n0，度为2的结点数为n2，则n0n21。性质4：具有n个结点的二叉树，其深度至少为log2n+1，其中log2n表示取log2n 的整数部分。,（3）满二叉树和完全二叉树,满二叉树-除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。节点数达到最大值。完全二叉树-除最后一层外，其它各层的结点数都达到最大个数，最后一层所有的节点都连续集中在最左边。,具有n个结点的完全二叉树的深度为 log2n+1。设完全二叉树共有n个结点。如果从根结点开始，从上到下、从左到右用自然数1,2,3,n给结点进行编号，则对于编号为k的结点有以下结论：若k=1，则该结点为根结点，它无父结点；若k 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,【例】设一棵二叉树的中序遍历为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+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的满二叉树的总结点个数为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.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的有序线性表，在最坏情况下，二分查找只需要比较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(n 1)/2次的比较。（2）希尔排序法将整个无序序列分割成若干小的子序列分别进行插入排序。长度为n的线性表，在最坏的情况下，希尔排序所需要的比较次数为：O(n1.5),（二）插入类排序,（三）选择类排序,（1）简单选择排序扫描整个线性表，从选出最小的元素，将它交换到最前面；对剩下的子表采用同样的方法，直到子表为空。长度为n的序列，在最坏的情况下，简单选择排序法需要经过n(n 1)/2次的比较。（2）堆排序法长度为n的序列，在最坏的情况下，堆排序的比较次数为O(nlog2n)。,假设线性表的长度为n，则：冒泡排序和简单插入排序的比较次数（时间复杂度）为n(n-1)/2；希尔排序的比较次数为O(n1.5)；简单选择排序的比较次数为n(n-1)/2；堆排序的比较次数为O(nlog2n)。,例：冒泡排序在最坏的情况下的比较次数是。A.n(n+1)/2 B.nlog2nC.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）程序调试通常也称为DebugD）软件测试应严格执行测试计划，排除测试的随意性,软件测试的目的是为了发现错误，而改正错误属于程序调试的范畴。,答案：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、关系模型 关系的数据结构 关系模型采用二维表来表示 二维表由表的框架及表的元组组成 二维表一般满足