全国计算机二级公共基础知识复习.docx

《全国计算机二级公共基础知识复习.docx》由会员分享，可在线阅读，更多相关《全国计算机二级公共基础知识复习.docx（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、全国计算机二级公共根底学问一, 数据构造及算法数据构造指的是数据之间的相互关系，即数据的组织形式。数据构造用来反映一个数据的内部构成，即一个数据由哪些成分构成, 以什么方式构成, 呈现什么样的构造。数据构造有逻辑上的数据构造和物理上的数据构造之分。逻辑上的数据构造反映数据之间的逻辑关系，而物理上的数据构造反映数据在计算机内部的存储支配。数据构造是数据存在的形式。算法是解题的步骤，是指令的有限序列。它们规定了解决某一特定类型问题的一系列运算，是对解题方案的精确及完整的描述。一个问题的解决方案要以算法为根底。1.1 概念介绍 算法的时间困难度：算法的时间困难度是指执行算法所须要的计算工作量。算法的

2、工作量用算法所执行的根本运算次数来度量，而算法所执行的根本运算次数是问题规模的函数，即 算法的工作量=f(n)其中n是问题的规模。 例如，两个n阶矩阵相乘所须要的根本运算(即两个实数的乘法)次数为n3，即计算工作量为n3，也就是时间困难度为n3。 算法的空间困难度：算法的空间困难度一般是指执行这个算法所须要的内存空间。数据的逻辑构造数据元素相互之间的关系，称为构造。数据的逻辑构造：是指反映数据元素之间逻辑关系的数据构造。数据的存储构造数据的存储构造：是数据的逻辑构造在计算机存储空间中的存放形式。也称数据的物理构造。各数据元素在计算机存储空间中的位置关系及它们的逻辑关系不肯定是一样的。同一种数据

3、的逻辑构造可以依据须要表示成随意一种或几种不同的存储构造。数据的依次存储方式：是将逻辑上相邻的结点存储在物理位置上亦相邻的存储单元里。也就是将全部存储结点相继存入在一个连续相邻的存储区里。数据的链式存储方式：是在存储每个结点信息的同时，增加一个指针来表示结点间的逻辑关系。该方式不要求逻辑上相邻结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。因此，链式存储构造中的每个结点都由两局部组成：一局部用于存储结点本身的信息，称为数据域；另一局部用于存储该结点的后继结点(或前驱结点)的存储单元地址，称为指针域。指针域可以包含一个或多个指针，这由结点之间的关系所确定。线性构造和非线性构造假

4、如在一个线性构造中，一个数据元素都没有，那么称该数据构造为空数据构造。线性构造的逻辑特征：在一个非空的数据构造中，除第一个数据元素只有一个后继没有前驱, 最终一个数据元素只有一个前驱没有后继外，其他的每一个数据元素仅有一个前驱和一个后继。线性构造也称为线性表。注：某个元素干脆相邻的前一个元素称为此元素的前驱, 干脆相邻的后一个元素称为此元素的后继。非线性构造的逻辑特征：在一个非空的数据构造中，某数据元素可能有多于一个前驱或后继。如树型构造等。习题：一选择题(单项选择)1. 算法的时间困难度是指DA) 算法的执行时间B) 算法所处理的数据量C) 算法程序中的语句或指令条数D) 算法在执行过程中所

5、须要的根本运算次数1.2线性表线性表是由同一类型的数据元素构成的一种线性的数据构造。是一种最根本, 最常用的数据构造。线性表常用的存储方式有两种：依次存储方式和链接存储方式。线性表的数学定义：L=(a1,a2,a3,an)说明：线性表是具有一样类型的n(n0)个数据元素组成的有限序列。L：为表的名称。ai(i=1,2, ,n)：为表的元素，也称为线性表中的一个结点。它可以是一个数, 一个字符, 一个字符串，也可以是一条记录，还可以是困难的数据对象。a1是a2的前驱, a2是a1的后继， a2是a3的前驱, a3是a2的后继，依次类推。n：为线性表的长度(元素个数)，当n=0时称线性表为空表。线

6、性表的特点：在非空的线性表中：存在唯一的一个“第一个元素(根结点)。存在唯一的一个“最终一个元素(终端结点)。除第一个元素外，其他的元素均有唯一的前驱。除最终一个元素外，其他的元素均有唯一的后继。1.3栈和队列栈和队列本质上也是线性表，只是它们的操作受到了限制。1.3.1栈栈是限定仅在表尾进展插入和删除操作的线性表。表尾称为栈顶(top)，表头称为栈底(bottom)。栈这种数据构造，类似于子弹夹，底端是封闭的，最终压入的子弹总是最先被弹出，最先压入的子弹只能最终被弹出。栈顶元素总是最终被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最终能被删除的元素。即栈是依

7、据“先进后出或“后进先出的原那么组织数据的。因此，栈也被称为“先进后出表或“后进先出表。由此可以看出，栈具有记忆作用。1.3.2队列队列是指只允许在表的一端插入元素, 在另一端删除元素的线性表。允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。在队列这种数据构造中，最先插入的元素将最先能够被删除，反之最终插入的元素将最终才能被删除。因此，队列又称为“先进先出或“后进后出的线性表。1.4树和二叉树1.4.1树树形构造是数据构造中一种很重要的非线性构造。在树形构造中，全部数据元素之间的关系具有明显的层次特性。树形构造很像自然界中的树，像一棵倒长的树。在现实生活中，能用树形构

8、造表示的例子许多。参见下面的图形：树形构造的根本特征及根本术语：以以下图为例：树的根：在树形构造中，没有前驱的结点只有一个，称为树的根结点，简称为树的根。如：上图中的“R。父结点：在树形构造中，每一个结点(除了树的根结点)只有一个前驱，称为父结点。如：上图中的“R是K, P, Q, D的父结点；“N是X, Y的父结点。子结点：在树形构造中，每个结点可以有多个后继，称为该结点的子结点。如：上图中的K, P, Q, D是“R的子结点；X, Y是“N的子结点。叶子结点：在树形构造中，没有后继的结点称为叶子结点，也称终端结点。如：上图中的C, M, F, E, X, G, S, L, Z, A均为叶子

9、结点。结点的度：在树形构造中，一个结点所拥有的后继个数称为该结点的度。如：上图中根结点R的度是4；结点T的度是3；结点P, Q, D, O, Y, W的度都为1。叶子结点的度为0。树的度：在树形构造中，全部结点中的最大的度称为树的度。如：上图中树的度为4，因为结点R的度最大，是4。树的深度：在树形构造中，树的最大层数称为树的深度(或高度)。如：上图中树的深度是5。说明：树形构造具有明显的层次关系，即树是一种层次构造。在树形构造中一般按如下原那么分层：1) 根结点在第1层。2) 其余结点的层数等于其父结点的层数加1。子树：在树形结中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。如：上图

10、中，结点R有4棵子树，它们分别以K, P, Q, D为根结点；结点P有1棵子树，其根结点为N；结点T有3棵子树，它们分别以W, Z, A为根结点。在树形构造中，子树间互不相交，叶子结点没有子树。森林：森林是M(M0)棵互不相交的树的集合。删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。1.4.2二叉树(1) 二叉树的特点 非空二叉树只有一个根结点。 二叉树中的每个结点，最多有两棵子树，分另称为该结点的左子树及右子树。当一个结点即没有左子树也没有右子树时，该结点就是叶子结点。在下面的图中，左面是只有根结点的二叉树，右面是深度为4的二叉树： (2) 满二叉树及完全二叉树

11、1) 满二叉树：满二叉树是指除最终一层外，每一层上的全部结点都有两个子结点。就是说，在满二叉树中，每一层上的结点数都到达最大值，即在满二叉树的第k层上有2i-1(k1)个结点，且深度为k的满二叉树有2k-1(k1)个结点。在以下图中分别是深度为2, 3, 4的满二叉树：满二叉树中不存在度数为1的结点，每个分支结点均有两棵深度一样的子树，且叶子结点都在最下一层。2) 完全二叉树：假设一棵二叉树最多只有最下面的两层上结点的度数可以小于2，并且最下一层上的全部结点都集中在该层最左边的假设干位置上，那么此二叉树称为完全二叉树。在以下图的4棵二叉树中，分别是深度为3和4的完全二叉树：满二叉树是完全二叉树

12、，完全二叉树不肯定是满二叉树。在满二叉树的最下一层上，从最右边开场连续删去假设干结点后得到的二叉树仍旧是一棵完全二叉树。在完全二叉树中，假设某个结点没有左子结点，那么它肯定没有右子结点，即该结点必是叶子结点。(3) 二叉树的性质假设定义根结点的层数为1(留意：有些资料中规定根结点的层数为0)。性质1：在二叉树的第i层上，最多有2i-1(i1)个结点。性质2：深度为k的二叉树最多有2k-1(k1)个结点。性质3：在随意二叉树中，假设度为0的结点(即叶子结点)的个数为n0，度为2的结点的个数为n2，那么：n0= n2+1(对于完全二叉树还有如下属性)性质4：具有n个结点的完全二叉树，其深度为log

13、2n+1。注：log2n表示取log2n的整数局部。性质5：假如将一棵有n个结点的完全二叉树自顶向下, 同一层自左向右连续给结点编号1, 2, 3, , n，那么对于随意结点i(1in)有如下结论：1) 假如i=1，此结点为根结点，无前驱(即无父结点)；假如i1，那么该结点的父结点编号为Int(i/2)。也可表示成i/2，都表示取整数。2)假如2in，那么结点i无左子结点，明显也没有右子结点，是叶子结点。假如2in，那么结点i的左子结点是编号为2i的结点。3) 假如2i+1n，那么结点i无右子结点。假如2i+1n，那么结点i的右子结点的编号为2i+1。(4) 二叉树的遍历二叉树的遍历就是遵从某

14、种次序，访问二叉树中的全部结点，使得每个结点仅被访问一次。一棵非空二叉树是由根结点, 左子树和右子树三局部组成。因此遍历一棵非空二叉树的问题就可以分解为三项“子任条： 访问根结点(假设用D表示)。 遍历左子树(假设用L表示)。 遍历右子树(假设用R表示)。在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。在先左后右的原那么下，依据访问根结点的次序，二叉树的遍历可分为三种：前序遍历(DLR), 中序遍历(LDR), 后序遍历(LRD)。 以以下图中的二叉树为例： 前序遍历(DLR)： 首先访问根结点，然后遍历左子树，最终遍历右子树。在遍历左, 右子树时，仍旧先访问子树的根结点，然后遍历其

15、左子树，最终遍历其右子树。即，前序遍历是指访问全部的根结点(包括子树的根结点)都在遍历其左, 右子树之前。 前序遍历的操作： 假设二叉树为空，那么完毕反返回。否那么： 访问根结点 前序遍历左子树 前序遍历右子树如，对上图中的二叉树进展前序遍历的结果是：F C A D B E G H P 中序遍历(LDR)： 首先遍历左子树，然后访问根结点，最终遍历右子树。在遍历左, 右子树时，仍旧先遍历其左子树，然后访问子树的根结点，最终遍历其右子树。即，中序遍历是指访问全部的根结点(包括子树的根结点)都在遍历其左子树之后, 在遍历其右子树之前。 中序遍历的操作： 假设二叉树为空，那么完毕反返回。否那么： 中

16、序遍历左子树 访问根结点 中序遍历右子树如，对上图中的二叉树进展中序遍历的结果是：A C B D F E H G P 后序遍历(LRD)： 首先遍历左子树，然后遍历右子树，最终访问根结点。在遍历左, 右子树时，仍旧先遍历其左子树，然后遍历其右子树，最终访问子树的根结点。即，后序遍历是指访问全部的根结点(包括子树的根结点)都在遍历其左, 右子树之后。 后序遍历的操作： 假设二叉树为空，那么完毕反返回。否那么： 后序遍历左子树 后序遍历右子树 访问根结点如，对上图中的二叉树进展后序遍历的结果是：A B D C H P G E F1.5查找查找又称检索。查找是指在一个给定的数据构造中查找某个指定的元

17、素。通常，依据不同的数据构造，应采纳不同的查找方法。1.5.1 依次查找依次查找又称依次搜寻或线性查找。依次查找一般是指在线性表中查找指定的元素。依次查找的根本思想：在n个结点组成的线性表中，从线性表的一端开场，依次将线性表中的元素及被查元素进展比拟，假设相等那么表示找到，即查找胜利；假设线性表中全部的元素都及被查元素进展了比拟但都不相等，那么表示线性表中没有要找的元素，即查找失败。在依次查找中，查找胜利时最多须要比拟n次, 最少比拟1次, 平均比拟次数约为表长的一半。查找失败时比拟n+1次。依次查找的时间困难度为O(n)。对于无序表(即表中的元素的排列是无序的)和链式存储构造的线性表(有序的

18、和无序的)，只能用依次查找。依次查找的优点：算法简洁而适用范围广。对表中元素的排列次序无要求，既可以是按关键字排列的有序表，也可以是无序表；对表的存储构造也无任何要求，既适用于依次存储的依次表，也适用于链接存储的链表。 依次查找的缺点： 查找效率低，平均查找长度较大。当n很大时不宜采纳依次查找。1.5.2 二分查找二分查找又称折半查找。它是一种查找效率较高的查找方法。该方法只适用于依次存储构造的有序表。通常是指有序表中的元素按值升序排列(非递减有序排列)。二分查找不能用于链式存储构造的线性表。 二分查找的根本思想：参见“C语言程序设计或“VB程序设计课件的相应内容动画。 对于长度为n的有序线性

19、表，查找胜利时最多须要比拟log2(n+1)次, 最少比拟1次, 平均查找长度近似log2n。当查找失败时，比拟log2n或log2(n+1)次。 不管二分查找胜利及否，其时间困难度均为O(log2n)。 二分查找的最坏性能和平均性能相当接近。1.6 排序 排序就是将文件中的记录进展整理，使之依据关键字进展递增或递减的依次排列起来，成为一个有序序列的过程。在本节所介绍的排序方法中，其排序的对象一般认为是依次存储的线性表，在程序设计语言中就是一维数组。 这里的排序算法，都是针对升序排序。1.6.1 交换排序 交换排序是两两比拟待排序记录的关键字，假设发觉两个记录关键字的次序相反时即进展交换，直到

20、没有反序的记录为止。下面介绍两种常用的交换排序。(1) 冒泡排序冒泡排序的根本思想：参见“C语言程序设计或“VB程序设计课件的相应内容动画。 对于长度为n的线性表，在最坏状况下，冒泡排序须要经过n/2遍的扫描，比拟次数为n(n-1)/2。 冒泡排序算法的平均时间困难度为O(n2)，空间困难度为O(1)。(2) 快速排序快速排序的根本思想： 参见以下图： 从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，将线性表前面大于T的元素移到后面，结果就把线性表分成了两局部(称为两个子表)，T插入到其分界限的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以T为分界限，将线性表

21、分成了前后两个子表，且前面子表中的全部元素均不大于T，后面子表中的全部元素均不小于T。 假如对分割后的各子表再按上述原那么进展分割，并且这种分割过程可以始终做下去，随着对各子表不断地进展分割，划分出的子表会越来越多(一次只能对一个子表进展再分割处理)，直到全部子表中的元素都排好序为止，那么此时的线性表就变成了有序表。 对于长度为n的线性表：在最坏状况下，快速排序比拟次数为n(n-1)/2。算法的时间困难度为O(n2)，空间困难度为O(n)。 在最好状况下，快速排序算法的时间困难度为O(nlog2n)，空间困难度为O(log2n)。快速排序算法的平均时间困难度是O(nlog2n)，平均比拟次数不

22、大于(n+1)log2n1.6.2 插入排序 插入排序是每次将一个待排序的记录按其关键字大小，插入到前面已排好的序列中的适当位置，直到全部记录插入为止。(1) 干脆插入排序 快速排序的根本思想：请查看相关资料。 对于长度为n的线性表：在最坏状况下，干脆插入排序比拟次数为n(n-1)/2。算法的时间困难度为O(n2)。(2) 希尔排序 希尔排序的根本思想：请查看相关资料。 对于长度为n的线性表：在最坏状况下希尔排序比拟次数为O(n1.5)。1.6.3 选择排序 选择排序的根本思想是：每一遍在n-i+1(i=1,2,n-1)个待排序记录中选取关键字最小的记录作为有序序列中第i个记录，直到全部记录排

23、完为止。(1) 干脆选择排序 选择排序的根本思想：参见“C语言程序设计或“VB程序设计课件的相应内容动画。 在最坏状况下，干脆选择排序比拟次数为n(n-1)/2。(2) 堆排序 希尔排序的根本思想：请查看相关资料。 在最坏状况下，堆排序比拟次数为O(nlog2n)。习题：一选择题(单项选择)1. 以下表达中正确的选项是( D )A栈是“先进先出的线性表B队列是“先进后出的线性表C循环队列是非线性构造D有序线性表既可以采纳依次存储构造，也可以采纳链式存储构造2. 以下关于栈的表达中正确的选项是( A )A) 栈顶元素最先被删除 B) 栈顶元素最终才能被删除C) 栈底元素恒久不能被删除 D) 以上

24、三种说法都不对3. 以下表达中正确的选项是( B )A) 有一个以上根结点的数据构造不肯定是非线性构造B) 只有一个根结点的数据构造不肯定是线性构造C) 循环链表是非线性构造D) 双向链表是非线性构造4. 支持子程序调用的数据构造是( A )A) 栈 B) 树 C) 队列 D) 二叉树5. 某二叉树有5个度为2的结点，那么该二叉树中的叶子结点数是( C )A10 B8 C6 D4提示：在随意二叉树中，假设度为0的结点(即叶子结点)的个数为n0，度为2的结点的个数为n2，那么：n0= n2+1 即 n0(叶子结点数)=5+1=66. 某二叉树共有7个结点，其中叶子结点只有1个，那么该二叉树的深度

25、为(假设根结点在第一层)( D )A) 3 B) 4 C) 6 D)77. 以下排序方法中，最坏状况下比拟次数最少的是( D )A冒泡排序 B简洁项选择择排序 C干脆插入排序 D堆排序8. 以下表达中正确的选项是( A )A) 对长度为n的有序链表进展查找，最坏的状况下须要的比拟次数为nB) 对长度为n的有序链表进展对分查找，最坏的状况下须要的比拟次数为n/2C) 对长度为n的有序链表进展对分查找，最坏的状况下须要的比拟次数为(log2n)D) 对长度为n的有序链表进展对分查找，最坏的状况下须要的比拟次数为(nlog2n)(二) 填空题1. 假设用一个长度为50的数组数组元素的下标从0到49作

26、为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，假如bottom=49,top=30(数组下标)，那么栈中具有_个元素。 答案：202. 一个队列的初始状态为空。现将元素A, B, C, D, E, F, 5, 4, 3, 2, 1一次入队，然后再一次退队，那么元素退队的依次为_。答案：A, B, C, D, E, F, 5, 4, 3, 2, 13. 设某循环队列的容量为50，假如头指针front=45(指向队头元素的前一个位置)，尾指针rear=10指向队尾元素，那么该循环队列中共有_个元素。答案：154. 设二叉树如下：ABCDEFGH对该二叉树进展后序遍历

27、的结果为_。答案：E, D, B, G, H, F, C, A5. 一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，那么后序遍历结果为_。答案：DEBFCA6. 有序线性表能进展二分查找的前提是该线性表必需是_存储。答案：依次二, 软件工程根底计算机软件是计算机系统中及硬件相互依存的另一局部，是包括程序, 数据及相关文档的完整集合。软件由两局部组成：一是机器可执行的程序和数据；二是机器不行执行的，及软件开发, 运行, 维护, 运用等有关的文档。软件的分类 软件按功能可以分为：应用软件, 系统软件, 支撑软件(或工具软件)。 应用软件：是为解决特定领域的应用而开发的软件。 系

28、统软件：是计算机管理自身资源，提高计算机运用效率并为计算机用户供应各种效劳的软件。支撑软件：是介于系统软件和应用软件之间，帮助用户开发软件的工具性软件。软件生命周期通常将软件产品从提出, 实现, 运用维护到停顿运用退役的过程称为软件生命周期。参见以下图： 构造化分析方法构造化分析的常用工具：数据流图(DFD)：是描述数据处理过程的工具，是需求理解的逻辑模型的图形表示，它干脆支持系统的功能建模。数据字典(DD)：是构造化分析方法的核心。判定树判定表构造化设计方法常见的过程设计工具：图形工具：程序流程图，N-S图，PAD图(问题分析图)，HIPO表格工具：判定表。语言工具：PDL(伪码)软件设计的

29、根本原理 1) 抽象：是一种思维工具，就是把事物本质的共同特性提取出来而不考虑其他细微环节。 2) 模块化：是指把一个待开发的软件分解成假设干小的简洁的局部。如高级语言中的过程, 函数, 子程序等。每个模块可以完成一个特定的子功能，各个模块可以按肯定的方法组装起来成为一个整体，从而实现整个系统的功能。 3) 信息隐藏：是指在一个模块内包含的信息(过程或数据)，对于不须要这些信息的其他模块来说是不能访问的。4) 模块独立性：是指每个模块只完成系统要求的独立的子功能，并且及其他模块的联系最少且接口简洁。模块的独立程度是评价设计好坏的重要度量标准。衡量软件的模块独立性运用耦合性和内聚性两个定性的度量

30、标准。内聚性：是一个模块内部各个元素间彼此结合的严密程度的度量。内聚是从功能角度来度量模块内的联系。内聚性是信息隐藏和局部化概念的自然扩展。一个模块的内聚性越强那么该模块的模块独立性越强。作为软件构造设计的设计原那么，要求每一个模块的内部都具有很强的内聚性，它的各个组成局部彼此都亲密相关。耦合性：耦合性是模块间相互连接的严密程度的度量。一个模块及其他模块的耦合性越强那么该模块的模块独立性越弱。原那么上讲，模块化设计总是盼望模块间的耦合表现为非干脆耦合方式。但是，由于问题所固有的困难性和构造化设计的原那么，非干脆耦合往往是不存在的。耦合性及内聚性是模块独立性的两个定性标准，耦合性及内聚性是相互联

31、系的。在程序构造中，各模块的内聚性越强，那么耦合性越弱。一般优秀的软件设计，应尽量做到高内聚，低耦合，即减弱模块之间的耦合性和提高模块内的的内聚性，有利于提高模块的独立性。软件测试软件测试是在软件投入运行前对软件需求, 设计, 编码的最终审核。软件测试是为了发觉错误而执行程序的过程。软件测试应当制定明确的测试方案并按方案执行。软件测试的目的：是发觉错误。软件测试方法和技术：假设从是否须要执行被测软件的角度，可以分为静态测试和动态测试方法。假设依据功能划分可以分为白盒测试和黑盒测试方法。静态测试：包括代码检查, 静态构造分析, 代码质量度量等。静态测试不实际运行软件，主要通过人工进展。动态测试：

32、是基于计算机的测试，是为了发觉错误而执行程序的过程。须要细心设计一批测试用例，并利用这些测试用例去运行程序，以发觉程序错误的过程。测试用例的格式为： (输入值集),(输出值集)白盒测试：也称构造测试或逻辑驱动测试。它是依据软件产品的内部工作过程，检查内部成分，以确认每种内部操作符合设计规格要求。白盒测试把测试对象看作一个翻开的盒子，允许测试人员利用程序内部的逻辑构造及有关信息来设计或选择测试用例，对程序全部的逻辑路径进展测试。通过在不同点检查程序的状态来了解实际的运行状态是否及预期的一样。所以，白盒测试是在程序内部进展，主要用于完成软件内部操作的验证。白盒测试的主要方法有逻辑覆盖, 根本路径测

33、试等。黑盒测试：也称功能测试或数据驱动测试。黑盒测试是对软件已经实现的功能是否满意需求进展测试和验证。黑盒测试完全不考虑程序内部的逻辑构造和内部特征，只依据程序的需求和功能规格说明，检查程序的功能是否符合它的功能说明。所以，黑盒测试是在软件接口处进展，完胜利能验证。黑盒测试只检查程序功能是否依据需求规格说明书的规定正常运用，程序是否能适当地接收输入数据而产生正确的输出信息，并且保持外部信息(如数据库或文件)的完整性。黑盒测试主要诊断功能不对或遗漏, 界面错误, 数据构造或外部数据库访问错误, 性能错误, 初始化和终止条件错误。黑盒测试方法主要有等价类划分法, 边界值分析法, 错误推想法, 因果

34、图等，主要用于软件确认测试。程序调试在对程序进展了胜利的测试之后，将进入程序调试(通常称Debug，即排错)。程序调试的任务是诊断和改正程序中的错误。它及软件测试不同，软件测试是尽可能多地发觉软件中的错误，并找出软件错误的具体位置。软件测试贯穿整个软件生命期，调试主要在开发阶段。习题：一选择题(单项选择)1. 软件按功能可以分为：应用软件, 系统软件和支撑软件或工具软件。下面属于应用软件的是( C )A) 编译程序 B) 操作系统 C) 教务管理系统 D) 汇编程序2. 软件按功能可分为：应用软件, 系统软件, 和支撑软件或工具软件。下面属于系统软件的是( B )A) 编辑软件 B)操作系统

35、C)教务管理系统 D)阅读器, 3. 软件(程序)调试的任务是( A )A) 诊断和改正程序中的错误 B) 尽可能多的发觉程序中的错误C) 发觉并改正程序中的全部错误 D) 确定程序中错误的性质4. 下面表达中错误的选项是( A )A) 软件测试的目的是发觉错误并改正错误B) 对被调试的程序进展“错误定位是程序调试的必要步骤C) 程序调试通常也称为DebugD) 软件测试应严格执行测试方案，解除测试的随意性5. 耦合性和内聚性是对模块独立性度量的两个标准。以下表达中正确的选项是( B )A) 提高耦合性, 降低内聚性有利于提高模块的独立性B) 降低耦合性, 提高内聚性有利于提高模块的独立性C)

36、 耦合性是指一个模块内部各个元素间彼此结合的严密程度D) 内聚性是指模块间相互连接的严密程度6. 数据流图(DFD图)是( C )A) 软件概要设计的工具 B) 软件具体设计的工具C) 构造化方法的需求分析工具 D) 面对对象方法的需求分析工具7. 软件生命周期可分为定义阶段，开发阶段和维护阶段。具体设计属于( B )A) 定义阶段 B) 开发阶段 C) 维护阶段 D) 上述三个阶段8. 在软件开发中，需求分析阶段产生的主要文档是( D )A) 软件集成测试方案 B) 软件具体设计说明书 C) 用户手册 D) 软件需求规格说明书9. 构造化程序所要求的根本构造不包括( B )A) 依次构造 B

37、) GOTO跳转 C) 选择(分支)构造 D) 重复(循环)构造10. 下面描述中错误的选项是( A )A) 系统总体构造图支持软件系统的具体设计B) 软件设计是将软件需求转换为软件表示的过程C) 数据构造及数据库设计是软件设计的任务之一D) PAD图是软件具体设计的表示工具(二) 填空题1. 软件测试可分为白盒测试和黑盒测试。根本路径测试属于_测试。答案：白盒2. 符合构造化原那么的三种根本限制构造是：选择构造, 循环构造和_。答案：依次构造3. 软件是_, 数据和文档的集合。答案：程序4. 对软件设计的最小单位(模块或程序单元)进展的测试通常为_测试。答案：单元 或 模块三, 数据库设计根

38、底计算机应用的三大领域：科学计算, 数据处理, 过程限制。数据库系统的根本概念数据(Data)：就是描述事物的符号记录。数据库(DB)：是数据的集合，它具有统一的构造形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序所共享。数据库中的数据具有“集成, “共享的特点。数据库管理系统(DBMS)：是数据库的机构，是一种系统软件，负责数据库中的数据组织, 数据操纵, 数据维护, 限制及爱护和数据效劳等。数据库管理系统是数据库系统的核心。数据库管理系统一般供应相应的数据语言(Data Language)来完成相应的功能：数据定义语言(DDL)：负责数据的模式定义及数据的物理存取构建

39、。数据操纵语言(DML)：负责数据的操纵，包括查询及增, 删, 改等操作。数据限制语言(DCL)：负责数据完整性, 平安性的定义及检查以及并发限制, 故障复原等功能，包括系统初启程序, 文件读写及维护程序, 存取路径管理程序, 缓冲区管理程序, 平安性限制程序, 完整性检查程序, 并发限制程序, 事务管理程序, 运行日志管理程序, 数据库复原程序等。数据库管理员(DBA)：由于数据库的共享性，因此对数据库的规划, 设计, 维护, 监视等须要有专人管理，称他们为数据库管理员。数据库系统(DBS)：由数据库(数据), 数据库管理系统(软件), 数据库管理员(人员), 系统硬件平台(硬件), 系统软

40、件平台(软件)这五局部组成，称为数据库系统。数据库应用系统(DBAS)：是数据库系统再加上应用软件及应用界面这三者所组成。E-R模型该模型将现实世界的要求转化成实体, 联系, 属性等几个根本概念，以及它们间的两种根本联接关系，并且可以用一种图特别直观地表示出来。下面是E-R模型的根本概念。目前较为出名的概念模型有E-R模型, 扩大的E-R模型, 面对对象模型及谓词模型等。实体：现实世界中的事物可以抽象成为实体。实体是概念世界中的根本单位，它们是客观存在的且又相互区分的事物。但凡有共性的实体可组成一个集合称实体集。如学生A和学生B，他们都是实体，他们又都是学生，从而组成一个学生实体集。 属性：现

41、实世界中的事物均有一些特性，这些特性可以用属性来表示。属性刻画了实体的特征。一个实体往往可以有假设干个属性。 联系：现实世界中事物间的关联称为联系。在概念世界中联系反映了实体集间的肯定关系。如工人及设备间的操作关系，上, 下级间的领导关系等。 实体集间的联系有多种，就实体集的个数而言有： 1) 两个实体集间的联系。2) 多个实体集间的联系。3) 一个实体集内部的联系：是一个实体集内的不同实体间的联系。实体集间联系的个数可以是单个也可以是多个，包括：一对一的联系，简记为1:1一对多或多对一的联系，简记为1:M或M:1 (其中M也可以小写)多对多的联系，简记为M:N 或 m:n E-R模型由上面三

42、个根本概念组成。由实体, 联系, 属性三者结合起来才能表示现实世界。 E-R图：E-R模型可以用一种特别直观的图的形式表示，这种图称为E-R图。在E-R图中我们分别用下面不同的几何图形表示E-R模型中的三个概念及两个联接关系。 1) 实体集表示法 用矩形表示实体集，在矩形内写上该实体集的名字。照实体集学生(student), 课程(course)可表示为： 2) 属性表示法 用椭圆形表示属性，在椭圆形内写上该属性的名称。如学生有属性：学号(S#), 姓名(Sn)及年龄(Sa)，可表示为： 3) 联系表示法 用菱形表示联系，在菱形内写上联系名。如学生及课程间的联系SC，可表示为： 上面是三个根本

43、概念分别用三种几何图形表示。下面是它们之间的联接关系的图形表示。 4) 实体集或联系及属性间的联接关系属性依附于实体集，属性也依附于联系，因此它们之间分别有联接关系。参见以下图： 其中：C#(课程号), Cn(课程名), P#(预修课号) 5) 实体集及联系间的联接关系 如以下图表示实体集及联系间的联接关系： 还可以在线段边上注明其对应的函数关系，如1:1, 1:n, n:m等。以下图表示student及course间有多对多联系： 两个实体集间联系叫二元联系，多个实体集间联系叫多元联系。以下图联系FPU是一种三元联系(工厂, 产品及用户间的联系)： 下面是实体间多种联系图： (a)图：公司职

44、工(enployee)间上, 下级管理(manage)的联系。即一个实体集内部可以有多种联系。(b)图：老师(T)及学生(S)之间可以有教学(E)联系也可以有管理(M)联系。即实体集间可以有多种联系。 下面是E-R图的一个实例图 关系模型关系模型采纳二维表来表示，简称表。二维表由表框架(Frame)及表的元组(Tuple)组成。表框架由n个命名的属性(Attribute)组成，n称为属性元数(Arity)。每个属性有一个取值范围，称为值域(Domain)。表框架对应了关系的模式，即类型的概念。在表框架中按行可以存放数据，每行数据称为元组，事实上，一个元组是由n个元组重量所组成，每个元组重量是表框架中每个属性的投影值。一个表框架可以存放m个元组，m称为表的基数(Cardinality)。一个n元表框架及框架内m个元组构成了一个完整的二维表。