全国计算机二级公共基础知识--复习(20210308212517)

1、全国计算机二级公共基础知识 一、数据结构与算法 数据结构 指的是数据之间的相互关系，即数据的组织形式。 数据结构用来反映一个数据的内部构成， 即一个数据由哪些成分构成、 以什 么方式构成、呈现什么样的结构 。数据结构有逻辑上的数据结构 和物理上的数据结构之分 。逻辑上的数据结构反映数据之间的逻辑 关系，而物理上的数据结构反映数据在计算机内部的存储安排。 数据结构是数据 存在的形式。 算法是解题的步骤，是指令的有限序列。 它们规定了解决某一特定类型 问题的一系列运算， 是对解题方案的准确与完整的描述。 一个问题的解决方案要 以算法为基础。 1.1 概念介绍 算法的时间复杂度: 算法的时间复杂度

2、是指执行算法所需要的计算工作量。 算法的工作量用算法所执行的基本运算次数来度量， 而算法所执行的基本运 算次数是问题规模的函数，即 算法的工作量 =f(n) 其中 n 是问题的规模。 例如， 两个 n 阶矩阵相乘所需要的基本运算 （即两个实数的乘法 ）次数为 n3，即计算工作量为n3，也就是时间复杂度为n3。 算法的空间复杂度： 算法的空间复杂度一般是指执行这个算法所需要的内存空间。 数据的逻辑结构 数据元素相互之间的关系，称为结构。 数据的逻辑结构：是指反映数据元素之间逻辑关系的数据结构。 数据的存储结构 数据的存储结构： 是数据的逻辑结构在计算机存储空间中的存放形式。 也称 数据的物理结构

3、。 各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相 同的。同一种数据的逻辑结构可以根据需要表示成任意一种或几种不同的存储结 构。 数据的顺序存储方式 ：是将逻辑上相邻的结点存储在物理位置上亦 相邻的存储单元里。也就是将所有存储结点相继存入在一个连续相邻的存储区 里。 数据的链式存储方式 ：是在存储每个结点信息的同时，增加一个指 针来表示结点间的逻辑关系。该方式不要求逻辑上相邻结点在物理位置上亦相 邻，结点间的逻辑关系是由附加的指针字段表示的。因此， 链式存储结构中的每 个结点都由两部分组成： 一部分用于存储结点本身的信息，称为 数据域 ；另一 部分用于存储该结点的后继结点 （

4、或前驱结点 ）的存储单元地址，称为 指针域 。 指针域可以包含一个或多个指针，这由结点之间的关系所决定。 线性结构和非线性结构 如果在一个线性结构中， 一个数据元素都没有， 则称该数据结构为空数据结 构。 线性结构的逻辑特征 ：在一个非空的数据结构中，除第一个数据元 素只有一个后继没有前驱、 最后一个数据元素只有一个前驱没有后继外， 其他的 每一个数据元素仅有一个前驱和一个后继。线性结构也称为 线性表 。 注：某个元素直接相邻的前一个元素称为此元素的 前驱 、直接相邻的后一 个元素称为此元素的 后继 。 非线性结构的逻辑特征 ：在一个非空的数据结构中， 某数据元素可 能有多于一个前驱或后继。如

5、树型结构等。 习题： （一）选择题 （单选 ） 1. 算法的时间复杂度是指（ D ） A）算法的执行时间 B）算法所处理的数据量 C）算法程序中的语句或指令条数 D）算法在执行过程中所需要的基本运算次数 1.2 线性表 线性表是由同一类型的数据元素构成的一种线性的数据结构。是一种最基 本、最常用的数据结构。线性表常用的存储方式有两种： 顺序存储方式和链接存 储方式。 线性表的数学定义： L=（a i,a2,a3,na 说明： 线性表是具有相同类型的n（n X）个数据元素组成的有限序列。 L:为表的名称。 ai（i=1,2,为表的元素，也称为线性表中的一个结点。它可以是一个数、 一个字符、一个字

6、符串，也可以是一条记录，还可以是复杂的数据对象。a1 是 a2的前驱、a2是ai的后继，a2是a3的前驱、a3是a2的后继，依次类推。 n ：为线性表的长度（元素个数），当n=0时称线性表为空表。 线性表的特点 : 在非空的线性表中：存在唯一的一个“第一个元素” （根结点 ）。存在唯一的 一个“最后一个元素” （终端结点 ）。除第一个元素外，其他的元素均有唯一的前 驱。除最后一个元素外，其他的元素均有唯一的后继。 1.3 栈和队列 栈和队列本质上也是线性表， 只是它们的操作受到了限制。 1.3.1 栈 栈是限定仅在表尾进行插入和删除操作的线性表。表尾称为栈顶 (top) ，表 头称为栈底 (b

7、ottom) 。 栈这种数据结构，类似于子弹夹， 底端是封闭的， 最后压入的子弹总是最先被弹 出，最先压入的子弹只能最后被弹出。 栈顶元素总是最后被插入的元素， 从而也是最先能被删除的元素； 栈底元素 总是最先被插入的元素， 从而也是最后能被删除的元素。 即栈是按照“先进后出” 或“后进先出”的原则组织数据的。因此， 栈也被称为 “先进后出” 表 或“后进先出”表。 由此可以看出，栈具有记忆作用。 1.3.2 队列 队列是指只允许在表的一端插入元素、 在另一端删除元素的线性表。 允许插入的 一端称为队尾 (rear) ，允许删除的一端称为队头 (front) 。 在队列这种数据结构中， 最先插

8、入的元素将最先能够被删除， 反之最后插入的元 素将最后才能被删除。因此， 队列又称为“先进先出”或“后进后 出”的线性表。 1.4树和二叉树 1.4.1 树 树形结构是数据结构中一种很重要的非线性结构。在树形结构中，所有数据 元素之间的关系具有明显的层次特性。 树形结构很像自然界中的树，像一棵倒长 的树。在现实生活中，能用树形结构表示的例子很多。参见下面的图形： 辔桶*塞学蔭 树形结构的基本特征及基本术语: 以下图为例： 树的根： 在树形结构中，没有前驱的结点只有一个，称为树的根结点，简称为树的根 如：上图中的“ R”。 父结点： 在树形结构中，每一个结点（除了树的根结点）只有一个前驱，称为父

9、结点。 女如:上图中的“ 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均为叶子结点。 结点的度: 在树形结构中，一个结点所拥有的后继个数称为该结点的度。 如如:上图中根结点R的度是4;结点T的度是3;结点P、Q、D、0、丫、 W 的度都为 1。叶子结点的度为 0。 树的度： 在树形结构中， 所有结点中的最大的度称为树的

10、度。 如：上图中树的度为 4， 因为结点 R 的度最大，是 4。 树的深度： 在树形结构中，树的最大层数称为树的深度 (或高度)。如：上图中树的深度 是 5。说明：树形结构具有明显的层次关系，即树是一种层次结构。在树形 结构中一般按如下原则分层： 1) 根结点在第 1 层。 2) 其余结点的层数等于其父结点的层数加 1。 子树： 在树形结中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。 如：上图中，结点R有4棵子树，它们分别以K、P、Q、D为根结点；结点P 有1棵子树，其根结点为N ;结点T有3棵子树，它们分别以 W、Z、A为根 结点。 在树形结构中，子树间互不相交，叶子结点没有子树

11、。 森林： 森林是M(M 0)棵互不相交的树的集合。删去一棵树的根，就得到一个森 林;反之，加上一个结点作树根，森林就变为一棵树。 1.4.2二叉树 (1)二叉树的特点 非空二叉树只有一个根结点。 二叉树中的每个结点，最多有两棵子树，分另称为该结点的左子树与右 子树。当一个结点即没有左子树也没有右子树时，该结点就是叶子结点。在下面 的图中，左面是只有根结点的二叉树，右面是深度为4的二叉树： (2)满二叉树与完全二叉树 1)满二叉树： 满二叉树是指除最后一层外，每一层上的所有结点都有两个子结点 就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的 第k层上有2i-1 (k 1)个结

12、点，且深度为k的满二叉树有2k-1(k 1)个结点。 在下图中分别是深度为2、3、4的满二叉树： A 2）裸度为2的甫二叉树（h）深度为3的灌二貝撕 （c）深度为4的摘二叉树 S 1.32 #|-XW 满二叉树中不存在度数为1的结点，每个分支结点均有两棵深度相同的子树， 且 叶子结点都在最下一层 2）完全二叉树： 若一棵二叉树最多只有最下面的两层上结点的度数可以小于 2，并且最下一 层上的所有结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉 树。 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然 是一棵完全二叉树。 在完全二叉树中， 若某个结点没有左子结点，则它

13、一定没有右子结点， 即该 结点必是叶子结点。 (3) 二叉树的性质 假设定义根结点的层数为 1(注意：有些资料中规定根结点的层数为 0) 。 性质1：在二叉树的第i层上，最多有2i- 1(i 1)个结点。 性质2:深度为k的二叉树最多有2k-1(k 1)个结点。 性质3:在任意二叉树中，若度为0的结点(即叶子结点)的个数为no，度为 2的结点的个数为n2,贝U： n0= n2+1 (对于完全二叉树还有如下属性 ) 性质 4：具有 n 个结点的完全二叉树， 其深度为 log2n+1 。注： log 2n 表示取 log 2n 的整数部分。性质 5：如果将一棵有 n 个结点的完全二叉树自 顶向下、

14、同一层自左向右连续给结点编号 1、2、3、n,则对于任意结 点i(1 i 1 ，贝该结点的父结点编号为 Int(i/2) 。也可表示成 i/2 ，都 表示取整数。 2) 如果 2in ，贝结点 i 无左子结点，显然也没有右子结点，是叶子结点。 如果2i n ，贝结点 i 无右子结点。 如果2i+1 n，则结点i的右子结点的编号为2i+1。 (4) 二叉树的遍历 二叉树的遍历就是遵从某种次序，访问二叉树中的所有结点，使得每个结点 仅被访问一次 一棵非空二叉树是由根结点、 左子树和右子树三部分组成。因此遍历一棵非 空二叉树的问题就可以分解为三项“子任条”： 访问根结点（假设用D表示）。 遍历左子树

15、（假设用L表示）。 遍历右子树（假设用R表示）。 在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。在先左后 右的原则下，根据访问根结点的次序，二叉树的遍历可分为三种：前序遍历（DLR）、 中序遍历（LDR）、后序遍历（LRD）。 以下图中的二叉树为例: 前序遍历（DLR）: 首先访问根结点，然后遍历左子树，最后遍历右子树。在遍历左、右子树时, 仍然先访问子树的根结点，然后遍历其左子树，最后遍历其右子树。即，前序遍 历是指访问所有的根结点（包括子树的根结点）都在遍历其左、右子树之前。 前序遍历的操作: 若二叉树为空，则结束反返回。否则： 访问根结点 前序遍历左子树 前序遍历右子树 如，

16、对上图中的二叉树进行前序遍历的结果是： F C A D B E G H P 中序遍历 (LDR) ： 首先遍历左子树，然后访问根结点 ，最后遍历右子树。在遍历 左、右子树时，仍然先遍历其左子树，然后访问子树的根结点，最后遍历其右子 树。即，中序遍历是指访问所有的根结点 (包括子树的根结点 )都在遍历其左子树 之后、在遍历其右子树之前。 中序遍历的操作： 若二叉树为空，则结束反返回。否则： 中序遍历左子树 访问根结点 中序遍历右子树 如，对上图中的二叉树进行中序遍历的结果是： A C B D F E H G P 后序遍历 (LRD) ： 首先遍历左子树，然后遍历右子树，最后访问根结点。 在遍历左

17、、右子树时，仍然先遍历其左子树，然后遍历其右子树，最后访问子树 的根结点。即，后序遍历是指访问所有的根结点 (包括子树的根结点 )都在遍历其 左、右子树之后。 后序遍历的操作： 若二叉树为空，则结束反返回。否则： 后序遍历左子树 后序遍历右子树 访问根结点 如，对上图中的二叉树进行后序遍历的结果是： A B D C H P G E F 1.5 查找 查找又称检索。 查找是指在一个给定的数据结构中查找某个指定的元素。 通 常，根据不同的数据结构，应采用不同的查找方法。 1.5.1 顺序查找 顺序查找又称顺序搜索或线性查找。 顺序查找一般是指在线性表中查找指定 的元素。 顺序查找的基本思想： 在

18、n 个结点组成的线性表中， 从线性表的一端开始， 依次将线性表中的元素 与被查元素进行比较，若相等则表示找到， 即查找成功； 若线性表中所有的元素 都与被查元素进行了比较但都不相等， 则表示线性表中没有要找的元素， 即查找 失败。 在顺序查找中，查找成功时最多需要比较 n 次、最少比 较 1 次、平均比较次数约为表长的一半。 查找失败时比较 n+1 次。 顺序查找的时间复杂度为 O(n) 。 对于无序表 (即表中的元素的排列是无序的 ) 和链式存储结构的线性表 (有序 的和无序的 )，只能用顺序查找。 顺序查找的优点： 算法简单而适用范围广。 对表中元素的排列次序无要求， 既可以是按关键字 排

19、列的有序表，也可以是无序表； 对表的存储结构也无任何要求， 既适用于顺序 存储的顺序表，也适用于链接存储的链表。 顺序查找的缺点： 查找效率低，平均查找长度较大。当 n 很大时不宜采用顺序查找。 1.5.2 二分查找 二分查找又称折半查找。 它是一种查找效率较高的查找方法。 该方法只适用 于顺序存储结构的有序表。通常是指有序表中的元素按值升序排列(非递减有序 排列)。二分查找不能用于链式存储结构的线性表。 二分查找的基本思想：参见“ C 语言程序设计”或“ VB 程序设计”课件的 相应内容动画。 对于长度为 n 的有序线性表，查找成功时最多需 要比较 log2(n+1) 次、最少比较 1 次、

20、平均查找长度 近似 log2n 。当查找失败时，比较 log2n 或 log2(n+1) 次。 不管二分查找成功与否，其时间复杂度均为 O(log2n) 。 二分查找的最坏性能和平均性能相当接近。 1.6 排序 排序就是将文件中的记录进行整理， 使之按照关键字进行递增或递减的顺序 排列起来，成为一个有序序列的过程。在本节所介绍的排序方法中， 其排序的对 象一般认为是顺序存储的线性表，在程序设计语言中就是一维数组。 这里的排序算法，都是针对升序排序。 1.6.1 交换排序 交换排序是两两比较待排序记录的关键字， 若发现两个记录关键字的次序相 反时即进行交换，直到没有反序的记录为止。下面介绍两种常

21、用的交换排序。 (1) 冒泡排序 冒泡排序的基本思想：参见“ C 语言程序设计”或“ VB 程序设计”课件的 相应内容动画。 对于长度为 n 的线性表，在最坏情况下，冒泡排 序需要经过 n/2 遍的扫描，比较次数为 n(n-1)/2 。 冒泡排序算法的平均时间复杂度为 O(n2) ，空间 复杂度为 O(1) 。 (2) 快速排序 快速排序的基本思想： 参见下图： 可编辑 无序线件表 分割 WT 分割 分割 快速排序示竟 从线性表中选取一个元素，设为 T,将线性表后面小于T的元素移到前面， 将线性表前面大于T的元素移到后面，结果就把线性表分成了两部分(称为两个 子表)，T插入到其分界线的位置处，

22、这个过程称为线性表的分割。通过对线性 表的一次分割，就以T为分界线，将线性表分成了前后两个子表，且前面子表中 的所有元素均不大于T,后面子表中的所有元素均不小于 To 如果对分割后的各子表再按上述原则进行分割， 并且这种分割过程可以一直 做下去，随着对各子表不断地进行分割，划分出的子表会越来越多(一次只能对 一个子表进行再分割处理)，直到所有子表中的元素都排好序为止，则此时的线 性表就变成了有序表。 对于长度为n的线性表： 在最坏情况下，快速排序比较次数为n(n-1)/2。算法 的时间复杂度为0(n2)，空间复杂度为0(n)。 在最好情况下，快速排序算法的时间复杂度为 0(nlog2n)，空间

23、复杂度为 O(log2n)。 快速排序算法的平均时间复杂度是 0(nlog2n)，平均 比较次数不大于(n+1)log2n 1.6.2 插入排序 插入排序是每次将一个待排序的记录按其关键字大小， 插入到前面已排好的 序列中的适当位置，直到全部记录插入为止。 (1) 直接插入排序 快速排序的基本思想：请查看相关资料。 对于长度为 n 的线性表： 在最坏情况下，直接插入排序比较次数为 n(n-1)/2 。 算法的时间复杂度为 O(n2) 。 (2) 希尔排序 希尔排序的基本思想：请查看相关资料。 对于长度为 n 的线性表： 在最坏情况下希尔排序比较次数为 O(n1.5) 。 1.6.3 选择排序

24、选择排序的基本思想是：每一遍在n-i+1(i=1,2,n-1)个待排序记录中选取 关键字最小的记录作为有序序列中第 i 个记录，直到全部记录排完为止。 (1) 直接选择排序 选择排序的基本思想：参见“ C 语言程序设计”或“ VB 程序设计”课件的 相应内容动画。 在最坏情况下，直接选择排序比较次数为 n(n-1)/2 。 (2) 堆排序 希尔排序的基本思想：请查看相关资料。 O(nlog2n) 。 在最坏情况下，堆排序比较次数为 习题： (一)选择题 (单选 ) 1. 下列叙述中正确的是 ( D ) A )栈是“先进先出”的线性表 B )队列是“先进后出”的线性表 C) 循环队列是非线性结构

25、 D) 有序线性表既可以采用顺序存储结构，也可以采用链式存储结构 2. 下列关于栈的叙述中正确的是 ( A ) A) 栈顶元素最先被删除 B) 栈顶元素最后才能被删除 C) 栈底元素永远不能被删除 D) 以上三种说法都不对 3. 下列叙述中正确的是 ( B ) A) 有一个以上根结点的数据结构不一定是非线性结构 B) 只有一个根结点的数据结构不一定是线性结构 C) 循环链表是非线性结构 D) 双向链表是非线性结构 4. 支持子程序调用的数据结构是 ( A ) A) 栈 B) 树 C) 队列 D) 二叉树 5. 某二叉树有 5 个度为 2 的结点，则该二叉树中的叶子结点数是( C ) A )10

26、 B)8C)6D )4 提示：在任意二叉树中，若度为 0 的结点 (即叶子结点 )的个数为 n0 ，度为 2 的结点的个数 为 n2 ，则： n0= n2+1即 n0( 叶子结点数 )=5+1=6 6. 某二叉树共有 7 个结点， 其中叶子结点只有 1 个，则该二叉树的深度为 (假设根结点在第 一层 )( D ) A) 3 B) 4C) 6D)7 7. 下列排序方法中，最坏情况下比较次数最少的是( D ) A )冒泡排序B)简单选择排序C)直接插入排序D)堆排序 8. 下列叙述中正确的是 ( A ) A) 对长度为 n 的有序链表进行查找，最坏的情况下需要的比较次数为 n B) 对长度为 n

27、的有序链表进行对分查找，最坏的情况下需要的比较次数为( n/2 ) C) 对长度为 n 的有序链表进行对分查找，最坏的情况下需要的比较次数为(log 2n) D) 对长度为 n 的有序链表进行对分查找，最坏的情况下需要的比较次数为 (nlog 2n) ( 二) 填空题 1. 假设用一个长度为 50 的数组(数组元素的下标从 0 到 49 )作为栈的存储空间，栈底指 针 bottom 指向栈底元素，栈顶指针 top 指向栈顶元素，如果 bottom=49,top=30( 数组 下标 )，则栈中具有 个元素。 答案：20 2. 一个队列的初始状态为空。现将元素A、B、C、D、E、F、5、4、3、2

28、、1 一次入队， 然后再一次退队，则元素退队的顺序为 答案：A、B、C、D、E、F、5、4、3、2、1 3设某循环队列的容量为50,如果头指针front=45（指向队头元素的前一个位置 ），尾指针 rear=10 （指向队尾元素），则该循环队列中共有 元素。 答案：15 4.设二叉树如下： 对该二叉树进行后序遍历的结果为 答案：E、D、B、G、H、F、C、A 5. 一棵二叉树的中序遍历结果为 DBEAFC，前序遍历结果为 ABDECF，则后序 遍历结果为 答案：DEBFCA 存储。 6. 有序线性表能进行二分查找的前提是该线性表必须是 答案：顺序 二、软件工程基础 计算机软件是计算机系统中与硬

29、件相互依存的另一部分， 是包括 程序、数据 及相关 文档的完整集合。 软件由两部分组成：一是机器可执行的程序和数据；二是机器不可执行的， 与软件开发、运行、维护、使用等有关的文档。 软件的分类 软件按功能可以分为：应用软件、系统软件、支撑软件 （或工具软件 ）。 应用软件：是为解决特定领域的应用而开发的软件。 系统软件： 是计算机管理自身资源， 提高计算机使用效率并为计算机用户提 供各种服务的软件。 支撑软件： 是介于系统软件和应用软件之间， 协助用户开发软件的工具性软 件。 软件生命周期 通常将软件产品从提出、 实现、使用维护到停止使用退役的过程称为软件生 命周期。参见下图： 结构化分析方法

30、 结构化分析的常用工具： 数据流图(DFD):是描述数据处理过程的工具，是需求理解的逻辑模型的图 形表示，它直接支持系统的功能建模。 数据字典(DD):是结构化分析方法的核心。 判定树 判定表 结构化设计方法 常见的过程设计工具： 图形工具：程序流程图，N-S图，PAD图（问题分析图）,HIPO 表格工具：判定表。 语言工具：PDL（伪码） 软件设计的基本原理 1）抽象：是一种思维工具，就是把事物本质的共同特性提取出来而不考虑 其他细节。 2）模块化：是指把一个待开发的软件分解成若干小的简单的部分。如高级 语言中的过程、函数、子程序等。每个模块可以完成一个特定的子功能，各个模 块可以按一定的方

31、法组装起来成为一个整体，从而实现整个系统的功能。 3）信息隐蔽：是指在一个模块内包含的信息 （过程或数据 ），对于不需要这些 信息的其他模块来说是不能访问的。 4）模块独立性：是指每个模块只完成系统要求的独立的子功能，并且与其他模 块的联系最少且接口简单。模块的独立程度是评价设计好坏的重要度量标准。 衡量软件的模块独立性使用耦合性和内聚性两个定性 的度量标准 。 内聚性： 是一个模块内部各个元素间彼此结合的紧密程度的度量。 内聚是从 功能角度来度量模块内的联系 内聚性是信息隐蔽和局部化概念的自然扩展。 一个模块的内聚性越强则该模 块的模块独立性越强。 作为软件结构设计的设计原则， 要求每一个模

32、块的内部都 具有很强的内聚性，它的各个组成部分彼此都密切相关。 耦合性：耦合性是模块间相互连接的紧密程度的度量。 一个模块与其他模块的耦合性越强则该模块的模块独立性越弱。原则上讲， 模块化设计总是希望模块间的耦合表现为非直接耦合方式。 但是，由于问题所固 有的复杂性和结构化设计的原则，非直接耦合往往是不存在的。 耦合性与内聚性是模块独立性的两个定性标准， 耦合性与内聚性是相互联系 的。在程序结构中，各模块的内聚性越强， 则耦合性越弱。 一般优秀的软件设计， 应尽量做到高内聚， 低耦合，即减弱模块之间的耦合性和提高模块内的的内聚性， 有利于提高模块的独立性。 软件测试 软件测试是在软件投入运行前

33、对软件需求、设计、编码的最后审核。软件测 试是为了发现错误而执行程序的过程。 软件测试应当制定明确的测试计划并按计 划执行。 软件测试的目的：是发现错误。 软件测试方法和技术： 若从是否需要执行被测软件的角度， 可以分为静态测 试和动态测试方法。若按照功能划分可以分为白盒测试和黑盒测试方法。 静态测试：包括代码检查、静态结构分析、代码质量度量等。静态测试不实 际运行软件，主要通过人工进行。 动态测试： 是基于计算机的测试，是为了发现错误而执行程序的过程。需要 精心设计一批测试用例， 并利用这些测试用例去运行程序， 以发现程序错误的过 程。测试用例的格式为： （输入值集 ）,（输出值集 ） 白盒

34、测试： 也称结构测试或逻辑驱动测试。 它是根据软件产品的内部工作过 程，检查内部成分， 以确认每种内部操作符合设计规格要求。 白盒测试把测试对 象看作一个打开的盒子， 允许测试人员利用程序内部的逻辑结构及有关信息来设 计或选择测试用例， 对程序所有的逻辑路径进行测试。 通过在不同点检查程序的 状态来了解实际的运行状态是否与预期的一致。 所以，白盒测试是在程序内部进 行，主要用于完成软件内部操作的验证。 白盒测试的主要方法有逻辑覆盖、基本路径测试等。 黑盒测试： 也称功能测试或数据驱动测试。 黑盒测试是对软件已经实现的功 能是否满足需求进行测试和验证。 黑盒测试完全不考虑程序内部的逻辑结构和内

35、部特征，只依据程序的需求和功能规格说明， 检查程序的功能是否符合它的功能 说明。所以，黑盒测试是在软件接口处进行，完成功能验证。黑盒测试只检查程 序功能是否按照需求规格说明书的规定正常使用， 程序是否能适当地接收输入数 据而产生正确的输出信息，并且保持外部信息 （如数据库或文件 ）的完整性。 黑盒测试主要诊断功能不对或遗漏、 界面错误、 数据结构或外部数据库访问 错误、性能错误、初始化和终止条件错误。黑盒测试方法主要有等价类划分法、 边界值分析法、错误推测法、因果图等，主要用于软件确认测试。 程序调试 在对程序进行了成功的测试之后， 将进入程序调试 (通常称 Debug ，即排错 ) 程序调试

36、的任务是诊断和改正程序中的错误。 它与软件测试不同， 软件测试是尽可能多地发现软件中的错 误，并找出软件错误的具体位置。软件测试贯穿整个 软件生命期，调试主要在开发阶段。 习题： (一)选择题 ( 单选) 1. 软件按功能可以分为：应用软件、系统软件和支撑软件(或工具软件) 。下面属于应用软 件的是 ( C ) A) 编译程序 B) 操作系统 C) 教务管理系统 D) 汇编程序 2. 软件按功能可分为：应用软件、系统软件、和支撑软件(或工具软件) 。下面属于系统软 件的是 ( B ) A) 编辑软件B)操作系统C)教务管理系统D)浏览器、 3. 软件 (程序)调试的任务是 ( A ) A) 诊

37、断和改正程序中的错误 C) 发现并改正程序中的所有错误 4. 下面叙述中错误的是 ( A ) B) 尽可能多的发现程序中的错误 D) 确定程序中错误的性质 A) 软件测试的目的是发现错误并改正错误 B) 对被调试的程序进行“错误定位”是程序调试的必要步骤 C) 程序调试通常也称为 Debug D) 软件测试应严格执行测试计划，排除测试的随意性 5. 耦合性和内聚性是对模块独立性度量的两个标准。下列叙述中正确的是( B ) A) 提高耦合性、降低内聚性有利于提高模块的独立性 B) 降低耦合性、提高内聚性有利于提高模块的独立性 C) 耦合性是指一个模块内部各个元素间彼此结合的紧密程度 D) 内聚性

38、是指模块间互相连接的紧密程度 6. 数据流图 (DFD 图)是( C ) A) 软件概要设计的工具 C) 结构化方法的需求分析工具 B) 软件详细设计的工具 D) 面向对象方法的需求分析工具 7. 软件生命周期可分为定义阶段，开发阶段和维护阶段。详细设计属于 ( B ) A) 定义阶段 B) 开发阶段 C) 维护阶段 D) 上述三个阶段 8. 在软件开发中，需求分析阶段产生的主要文档是( D ) A) 软件集成测试计划 B) 软件详细设计说明书 C) 用户手册 D) 软件需求规格 说明书 9. 结构化程序所要求的基本结构不包括 ( B ) A) 顺序结构 B) GOTO 跳转 C) 选择(分支

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

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

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

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

43、学生B,他们都是实体，他们又都是学生，从而组成一个学生 实体集。 属性：现实世界中的事物均有一些特性，这些特性可以用属性来表示。属性 刻画了实体的特征。一个实体往往可以有若干个属性。 联系：现实世界中事物间的关联称为联系。 在概念世界中联系反映了实体集 间的一定关系。如工人与设备间的操作关系，上、下级间的领导关系等。 实体集间的联系有多种，就实体集的个数而言有： 1) 两个实体集间的联系。 2) 多个实体集间的联系。 3) 一个实体集内部的联系：是一个实体集内的不同实体间的联系。 实体集间联系的个数可以是单个也可以是多个，包括： 一对一的联系，简记为1:1 一对多或多对一的联系，简记为 1：M

44、或M:1(其中M也可以小写) 多对多的联系，简记为 M:N或m:n E-R模型由上面三个基本概念组成。由实体、联系、属性三者结合起来才能 表示现实世界。 E-R图：E-R模型可以用一种非常直观的图的形式表示，这种图称为E-R图 在E-R图中我们分别用下面不同的几何图形表示E-R模型中的三个概念与两个 联接关系 1) 实体集表示法 用矩形表示实体集，在矩形内写上该实体集的名字。如实体集学生 (student)、课程(course)可表示为： stvdeai course 实体集表示法 2) 属性表示法 用椭圆形表示属性，在椭圆形内写上该属性的名称。如学生有属性：学号 (S#)、姓名(Sn)及年龄

45、(Sa)，可表示为: 属性表示陡 SC，可表 3) 联系表示法 用菱形表示联系，在菱形内写上联系名。如学生与课程间的联系 示为: 上面是三个基本概念分别用三种几何图形表示。 下面是它们之间的联接关系的图 形表示。 4）实体集或联系与属性间的联接关系 属性依附于实体集，属性也依附于联系，因此它们之间分别有联接关系。参 见下图: 其中：C#（课程号）、Cn（课程名）、P#（预修课号） 5）实体集与联系间的联接关系 如下图表示实体集与联系间的联接关系： 还可以在线段边上注明其对应的函数关系，如1:1、1:n、n:m等。下图表 示student与course间有多对多联系： 两个实体集间联系叫二元联系

46、，多个实体集间联系叫多元联系。下图联系 FPU是一种三元联系(工厂、产品与用户间的联系)： 下面是实体间多种联系图： (a)图：公司职工(enployee)间上、下级管理(manage)的联系。即一个实体 集内部可以有多种联系。 (b)图：教师(T)与学生(S)之间可以有教学(E)联系也可以有管理(M)联系。即 实体集间可以有多种联系 F面是E-R图的一个实例图 关系模型 关系模型采用二维表来表示，简称表。 二维表由表框架(Frame)及表的元组(Tuple)组成。表框架由n个命名的属性 (Attribute)组成，n称为属性元数(Arity)。每个属性有一个取值范围，称为值域 (Domain

47、) 。表框架对应了关系的模式，即类型的概念。 在表框架中按行可以存放数据， 每行数据称为元组，实际上，一个元组是由 n 个元组分量所组成，每个元组分量是表框架中每个属性的投影值。一个表框架 可以存放 m 个元组， m 称为表的基数 (Cardinality) 。 一个 n 元表框架及框架内 m 个元组构成了一个完整的二维表。 关系框架与关系元组构成了一个 关系 。一个语义相关的关系集合构成一个 关系数据库。 关系的框架称为关系模式， 而语义相关的关系模式集合构成了关系 数据库模式。 满足下面 7 个性质的二维表称为关系 (Relation) ： 1) 元组个数有限性：二维表中元组个数是有限的。

48、 2) 元组的惟一性：二维表中元组均不相同。 3) 元组的次序无关性：二维表中元组的次序可以任意交换。 4) 元组分量的原子性：二维表中元组的分量是不可分割的基本数据项。 5) 属性名惟一性：二维表中属性名各不相同。 6) 属性的次序无关性：二维表中属性与次序无关，可任意交换。 7) 分量值域的同一性：二维表属性的分量具有与该属性相同的值域。 以二维表 (关系)为基本结构所建立的模型称为关系模型。 在关系模型中的一个重要概念是键 (Key) 或码。键具有标识元组、建立元组 间联系等重要作用。 键或码： 在二维表中凡能惟一标识元组的最小属性集称为该表的键或码。 候选键或候选码： 二维表中可能有若干个键，它们称为该表的候选键 (Candidata Key) 或候选码。 主键或主码： 从二维表的所有候选键中选取一个作为用户使用的键， 称为主 键 (Primary Key) 或主码。一般主键也简称为键或码。 外键或外码： 表