全国计算机二级公共基础知识复习复习资料重点

全国计算机二级公共基础知识

一、数据结构与算法

或攵据结构指的是数据之间的相互关系，即数据的组织形式。

数据结构用来反映一个数据的内部构成，即一个数据由哪些成分构成、以

什么方式构成、呈现什么样的结构。数据结构有逻辑上的数据结

构中口物理上的数据结构之分。逻辑上的数据结构反映数据之间的

逻辑关系，而物理上的数据结构反映数据在计算机内部的存储安排。数据结

构是数据存在的形式。

算法是解题的步骤，是指令的有限序列。它们规定了解决某一特定

类型问题的一系列运算，是对解题方案的准确与完整的描述。一个问题的

解决方案要以算法为基础。

1.1概念介绍

♦算法的时间复杂度：

算法的时间复杂度是指执行算法所需要的计算工作量。

算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本

运算次数是问题规模的函数，即

算法的工作量二f(n)

其中n是问题的规模。

彳列出口，两个n阶矩阵相乘所需要的基本运算(即两个实数的乘法)次数

为即计算工作量为1?,也就是时间复杂度为

♦算法的空间复杂度：

算法的空间复杂度一般是指执行这个算法所需要的内存空间。

♦数据的逻辑结构

数据元素相互之间的关系，称为结构。

数据的逻辑结构：是指反映数据元素之间逻辑关系的数据结构。

♦数据的存储结构

数据的存储结构：是数据的逻辑结构在计算机存储空间中的存放形式。也

称数据的物理结构。

各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是

相同的。同一种数据的逻辑结构可以根据需要表示成任意一种或几种不同的

存储结构。

数据的顺序存储方式：是将逻辑上相邻的结点存储在物理位置上亦

相邻的存储单元里。也就是将所有存储结点相继存入在一个连续相邻的存储区

里。

数据的链式存储方式：是在存储每个结点信息的同时，增加一个

指针来表示结点间的逻辑关系。该方式不要求逻辑上相邻结点在物理位置上亦

相邻，结点间的逻辑关系是由附加的指针字段表示的。因此，链式存储结构

中的每个结点都由两部分组成：一部分用于存储结点本身的信息，称为数据

域；另一部分用于存储该结点的后继结点（或前驱结点）的存储单元地址，称为

指针域。指针域可以包含一个或多个指针，这由结点之间的关系所决定。

♦线性结构和非线性结构

如果在一个线性结构中，一个数据元素都没有，则称该数据结构为空数据

结构。

线性结构的逻辑特征：在一个非空的数据结构中，除第一个数据

元素只有一个后继没有前驱、最后一个数据元素只有一个前驱没有后继外，其

他的每一个数据元素仅有一个前驱和一个后继。线性结构也称为线，性表。

注：某个元素直接相邻的前一个元素称为此元素的前3区、直接相邻的后

一个元素称为此元素的后欠L

非线性结构的逻辑外寺征：在一个非空的数据结构中，某数据元素

可能有多于一个前驱或后继。如树型结构等。

习题：

（-）选择题（单选）

1.算法的时间复杂度是指（D）

A）算法的执行时间

B）算法所处理的数据量

0算法程序中的语句或指令条数

D）算法在执行过程中所需要的基本运算次数

1.2线性表

线性表是由同一类型的数据元素构成的一种线性的数据结构。是一种最

基本、最常用的数据结构。线性表常用的存储方式有两种：顺序存储方式和链

接存储方式。

线性表的数学定义：

L=（ai,a2,a3,…,aQ

说明：

线性表是具有相同类型的n（n2O）个数据元素组成的有限序列。

L：为表的名称。

ai（i=l,2,...,n）：为表的元素，也称为线性表中的一个结点。它可以是一个

数、一个字符、一个字符串，也可以是一条记录，还可以是复杂的数据对象。

ai是a2的前驱、a?是a1的后继，a2是a3的前驱、a3是a2的后继，…，依次

类推。

n：为线性表的长度(元素个数)，当n=0时称线性表为空表。

线性表的特点：

在非空的线性表中：存在唯一的一个“第一个元素”(根结点)。存在唯一

的一个“最后一个元素”(终端结点)。除第一个元素外，其他的元素均有唯一

的前驱。除最后一个元素外，其他的元素均有唯一的后继。

1.3栈和队列

栈和队列本质上也是线性表，只是它们的操作受到了限制。

1.3.1栈

栈是限定仅在表尾进行插入和删除操作的线性表。表尾称为栈顶(top),表

头称为栈底(bottom)。

栈这种数据结构，类似于子弹夹，底端是封闭的，最后压入的子弹总是最

先被弹出，最先压入的子弹只能最后被弹出。

栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元

素总是最先被插入的元素，从而也是最后能被删除的元素。即栈是按照“先进

后出”或“后进先出”的原则组织数据的。因此，栈也被称为“先进后

出”表或“后进先出”表。由此可以看出，栈具有记忆作用。

1.3.2队列

队列是指只允许在表的一端插入元素、在另一端删除元素的线性表。允许插入

的一端称为队尾(rear)，允许删除的一端称为队头(front)。

在队列这种数据结构中，最先插入的元素将最先能够被删除，反之最后插入

的元素将最后才能被删除。因此，队列又称为“先进先出”或“后

进后出”的线性表。

1.4树和二叉树

1.4.1树

树形结构是数据结构中一种很重要的非线性结构。在树形结构中，所有

数据元素之间的关系具有明显的层次特性。树形结构很像自然界中的树，像

一棵倒长的树。在现实生活中，能用树形结构表示的例子很多。参见下面的

树形结构的基本特征及基本术语:

以下图为例:

树的根：

在树形结构中，没有前驱的结点只有一个，称为树的根结点，简称为树

的根。如：上图中的“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均为叶子结点。

结点的度：

在树形结构中，一个结点所拥有的后继个数称为该结点的度。

如：上图中根结点R的度是4；结点T的度是3；结点P、Q、D、0、Y、

W的度都为1。叶子结点的度为0。

树的度：

在树形结构中，所有结点中的最大的度称为树的度。如：上图中树的度

为4,因为结点R的度最大，是4。

树的深度：

在树形结构中，树的最大层数称为树的深度(或高度)o如：上图中树的

深度是5。说明：树形结构具有明显的层次关系，即树是一种层次结构。

在树形结构中一般按如下原则分层：

1)根结点在第1层。

2)其余结点的层数等于其父结点的层数加lo

子树：

在树形结中，以某结点的一个子结点为根构成的树称为该结点的一棵子

树。

如：上图中，结点R有4棵子树，它们分别以K、P、Q、D为根结点；结点

P有1棵子树，其根结点为N；结点T有3棵子树，它们分别以W、Z、A为

根结点。

在树形结构中，子树间互不相交，叶子结点没有子树。

森林：

森林是M(MNO)棵互不相交的树的集合。删去一棵树的根，就得到一个

森林；反之，加上一个结点作树根，森林就变为一棵树。

1.4.2二叉树

(1)二叉树的特点

①非空二叉树只有一个根结点。

②二叉树中的每个结点，最多有两棵子树，分另称为该结点的左子树与

右子树。当一个结点即没有左子树也没有右子树时，该结点就是叶子结点。在

下面的图中，左面是只有根结点的二叉树，右面是深度为4的二叉树：

(2)满二叉树与完全二叉树

1)满二叉树:

满二叉树是指除最后一层外，每一层上的所有结点都有两个子结点。

就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉

树的第k层上有2M(k2i)个结点，且深度为k的满二叉树有2k-1(k^1)

个结点。

在下图中分别是深度为2、3,4的满二叉树:

E

(a)深度为2的满二叉树(b)深度为3的满二叉树(C)深度为4的满二叉树

图1.32满二叉树

满二叉树中不存在度数为1的结点，每个分支结点均有两棵深度相同的子树,

且叶子结点都在最下一层。

2)完全二叉树:

若一棵二叉树最多只有最下面的两层上结点的度数可以小于2,并且最下

一层上的所有结点都集中在该层最左边的若干位置上，则此二叉树称为完全二

叉树。

在下图的4棵二叉树中，分别是深度为3和4的完全二叉树:

(»)深度为3的完全二叉树(b)深度为4的完全二叉树

田1.33完全二叉树

满二叉树是完全二叉树，完全二叉树不一定是满二叉树。

在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍

然是一棵完全二叉树。

在完全二叉树中，若某个结点没有左子结点，则它一定没有右子结点，即

该结点必是叶子结点。

(3)二叉树的性质

假设定义根结点的层数为1(注意：有些资料中规定根结点的层数为0)。

性质1：在二叉树的第i层上，最多有2i-1(i21)个结点。

性质2：深度为k的二叉树最多有2k-1(k21)个结点。

性质3：在任意二叉树中，若度为o的结点(即叶子结点)的个数为no，度

为2的结点的个数为及，则：nO=n2+1

(对于完全二叉树还有如下属性)

性质4：具有n个结点的完全二叉树，其深度为[Iog2n]+1o/i：[log2n]

表示取log2n的整数部分。性质5：如果将一棵有n个结点的完全二叉树自

顶向下、同一层自左向右连续给结点编号1、2、3、…、n,则对于任意结

点i(lWiWn)有如下结论：

1）如果i=l,此结点为根结点，无前驱（即无父结点）；

如果i>l,则该结点的父结点编号为Int（i/2）o也可表示成[i/2],

都表示取整数。

2）如果2i>n,则结点i无左子结点，显然也没有右子结点，是叶子结点。

如果2iWn,则结点i的左子结点是编号为2i的名吉点。

3）如果2i+l>n,则结点i无右子结点。

如果2i+lWn,则结点i的右子结点的编号为2i+1o

（4）二叉树的遍历

二叉树的遍历就是遵从某种次序，访问二叉树中的所有结点，使得每

个结点仅被访问一次。

一棵非空二叉树是由根结点、左子树和右子树三部分组成。因此遍历一棵

非空二叉树的问题就可以分解为三项“子任条”：

①访问根结点（假设用D表示）。

②遍历左子树（假设用L表示）。

③遍历右子树（假设用R表示）。

在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。在先

左后右的原则下，根据访问根结点的次序，二叉树的遍历可分为三种：前序

遍历（DLR）、中序遍历（LDR）、后序遍历（LRD）。

以下图中的二叉树为例:

前序遍历（DLR）:

首先访问根结点，然后遍历左子树，最后遍历右子树;在遍历左、右子

树时，仍然先访问子树的根结点，然后遍历其左子树，最后遍历其右子树。即,

前序遍历是指访问所有的根结点（包括子树的根结点）都在遍历其左、右子树之

刖。

前序遍历的操作：

若二叉树为空，则结束反返回。否则：

①访问根结点

②前序遍历左子树

③前序遍历右子树

如，对上图中的二叉树进行前序遍历的结果是：FCADBEGHP

中序遍历（LDR）:

首先遍历左子树，然后访问根结点，最后遍历右子树。在

遍历左、右子树时，仍然先遍历其左子树，然后访问子树的根结点，最后遍

历其右子树。即，中序遍历是指访问所有的根结点（包括子树的根结点渚R在遍

历其左子树之后、在遍历其右子树之前。

中序遍历的操作：

若二叉树为空，则结束反返回。否则：

①中序遍历左子树

②访问根结点

③中序遍历右子树

如，对上图中的二叉树进行中序遍历的结果是：ACBDFEHGP

后序遍历（LRD）：

首先遍历左子树，然后遍历右子树，最后访问根结点。

在遍历左、右子树时，仍然先遍历其左子树，然后遍历其右子树，最后访问

子树的根结点。即，后序遍历是指访问所有的根结点（包括子树的根结点）都在

遍历其左、右子树之后。

后序遍历的操作：

若二叉树为空，则结束反返回。否则：

①后序遍历左子树

②后序遍历右子树

③访问根结点

如，对上图中的二叉树进行后序遍历的结果是：ABDCHPGEF

1.5查找

查找又称检索。查找是指在一个给定的数据结构中查找某个指定的元素。

通常，根据不同的数据结构，应采用不同的查找方法。

1.5.1顺序查找

顺序查找又称顺序搜索或线性查找。顺序查找一般是指在线性表中查找指

定的元素。

顺序查找的基本思想：

在n个结点组成的线性表中，从线性表的一端开始，依次将线性表中的元

素与被查元素进行比较，若相等则表示找到，即查找成功；若线性表中所有的

元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素，

即查找失败。

在顺序查找中，查找成功时最多需要比较n次、最少

比较1次、平均比较次数约为表长的一半。查找失败时比

较n+1次。

顺序查找的时间复杂度为0（n）。

对于无序表（即表中的元素的排列是无序的）和链式存储结构的线性表（有序

的和无序的），只能用顺序查找。

顺序查找的优点：

算法简单而适用范围广。对表中元素的排列次序无要求，既可以是按

关键字排列的有序表，也可以是无序表；对表的存储结构也无任何要求，既

适用于顺序存储的顺序表，也适用于链接存储的链表。

顺序查找的缺点：

查找效率低，平均查找长度较大。当n很大时不宜采用顺序查找。

1.5.2二分查找

二分查找又称折半查找。它是一种查找效率较高的查找方法。该方法只

适用于顺序存储结构的有序表。通常是指有序表中的元素按值升序排列(非递

减有序排列)0二分查找不能用于链式存储结构的线性表。

二分查找的基本思想：参见“C语言程序设计”或“VB程序设计”课件的

相应内容动画。

对于长度为n的有序线性表，查找成功时最多需

要比较Iog2(n+1)次、最少比较1次、平均查找长度近

似Iog2no当查找失败时，比较log2n或Iog2(n+1)

次。

不管二分查找成功与否，其时间复杂度均为

0(log2n)o

二分查找的最坏性能和平均性能相当接近。

1.6排序

排序就是将文件中的记录进行整理，使之按照关键字进行递增或递减的

顺序排列起来，成为一个有序序列的过程。在本节所介绍的排序方法中，其

排序的对象一般认为是顺序存储的线性表，在程序设计语言中就是一维数组。

这里的排序算法，都是针对升序排序。

1.6.1交换排序

交换排序是两两比较待排序记录的关键字，若发现两个记录关键字的次序

相反时即进行交换，直到没有反序的记录为止。下面介绍两种常用的交换排

序。

(1)冒泡排序

冒泡排序的基本思想：参见“C语言程序设计”或“VB程序设计”课件的

相应内容动画。

对于长度为n的线性表，在最坏情况下，冒泡

排序需要经过n/2遍的扫描，比较次数为n(n-1)/2o

冒泡排序算法的平均时间复杂度为0(n2),空

间复杂度为0(1)。

(2)快速排序

快速排序的基本思想：

参见下图：

分割

分割

快速排序示意图

从线性表中选取一个元素，设为T,将线性表后面小于T的元素移到前

面，将线性表前面大于T的元素移到后面，结果就把线性表分成了两部分(称

为两个子表)，T插入到其分界线的位置处，这个过程称为线性表的分割。通

过对线性表的一次分割，就以T为分界线，将线性表分成了前后两个子表，且

前面子表中的所有元素均不大于T,后面子表中的所有元素均不小于T。

如果对分割后的各子表再按上述原则进行分割，并且这种分割过程可以一

直做下去，随着对各子表不断地进行分割，划分出的子表会越来越多(一次只

能对一个子表进行再分割处理)，直到所有子表中的元素都排好序为止，则此

时的线性表就变成了有序表。

对于长度为n的线性表：

在最坏情况下，快速排序比较次数为n(n-1)/2。算

法的时间复杂度为0(n2),空间复杂度为0(n)。

在最好情况下，快速排序算法的时间复杂度为

0(nlog2n),空间复杂度为0(log2n)。

快速排序算法的平均时间复杂度是0(nlog2n),平

均比较次数不大于(n+1)Iog2n

1.6.2插入排序

插入排序是每次将一个待排序的记录按其关键字大小，插入到前面已排好

的序列中的适当位置，直到全部记录插入为止。

(1)直接插入排序

快速排序的基本思想：请查看相关资料。

对于长度为n的线性表：

在最坏情况下，直接插入排序比较次数为n(n-1)/2。

算法的时间复杂度为0(n2)。

(2)希尔排序

希尔排序的基本思想：请查看相关资料。

对于长度为n的线性表：

在最坏情况下希尔排序比较次数为0(n1.5)。

1.6.3选择排序

选择排序的基本思想是：每一遍在n-i+l(i=l,2,…,n-l)个待排序记录中选取关

键字最小的记录作为有序序列中第i个记录，直到全部记录排完为止。

（1）直接选择排序

选择排序的基本思想：参见“C语言程序设计”或“VB程序设计”课件的

相应内容动画。

在最坏情况下，直接选择排序比较次数为

n（n-1）/2o

（2）堆排序

希尔排序的基本思想：请查看相关资料。

在最坏情况下，堆排序比较次数为0（nlog2n）。

习题：

（-）选择题（单选）

1.下列叙述中正确的是（D）

A）栈是“先进先出”的线性表

B）队列是“先进后出”的线性表

C）循环队列是非线性结构

D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构

2.下列关于栈的叙述中正确的是（A）

A）栈顶元素最先被删除B）栈顶元素最后才能被删除

0栈底元素永远不能被删除D）以上三种说法都不对

3.下列叙述中正确的是（B）

A）有一个以上根结点的数据结构不一定是非线性结构

B）只有一个根结点的数据结构不一定是线性结构

0循环链表是非线性结构

D）双向链表是非线性结构

4.支持子程序调用的数据结构是（A）

A）栈B）树C）队列D）二叉树

5.某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是（C）

A）10B）8C）6D）4

提示：在任意二叉树中，若度为0的结点（即叶子结点）的个数为no,度为2的结点的个

数为n2,则：n0=n2+l即nO（叶子结点数）=5+1=6

6.某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点

在第一层）（D）

A）3B）4C）6D）7

7.下列排序方法中，最坏情况下比较次数最少的是（D）

A）冒泡排序B）简单选择排序C）直接插入排序D）堆排序

8.下列叙述中正确的是（A）

A）对长度为n的有序链表进行查找，最坏的情况下需要的比较次数为n

B）对长度为n的有序链表进行对分查找，最坏的情况下需要的比较次数为（n/2）

0对长度为n的有序链表进行对分查找，最坏的情况下需要的比较次数为（logzn）

D）对长度为n的有序链表进行对分查找，最坏的情况下需要的比较次数为（nlogzn）

（-）填空题

1.假设用一个长度为50的数组（数组元素的下标从0到49）作为栈的存储空间，栈底指

针bottom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom=49,top=30（数组下标）,

则栈中具有个元素。

答案：20

2.一个队列的初始状态为空。现将元素A、B、C、D、E、F、5、4、3、2、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,则后

序遍历结果为o

答案：DEBFCA

6.有序线性表能进行二分查找的前提是该线性表必须是存储。

答案：顺序

二、软件工程基础

计算机软件是计算机系统中与硬件相互依存的另一部分，是包括程序、数

据及相关文档的完整集合。

软件由两部分组成：一是机器可执行的程序和数据；二是机器不可执行的，

与软件开发、运行、维护、使用等有关的文档。

软件的分类

软件按功能可以分为：应用软件、系统软件、支撑软件（或工具软件）。

应用软件：是为解决特定领域的应用而开发的软件。

系统软件：是计算机管理自身资源，提高计算机使用效率并为计算机用

户提供各种服务的软件。

支撑软件：是介于系统软件和应用软件之间，协助用户开发软件的工具性

软件。

软件生命周期

通常将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件

生命周期。参见下图：

结构化分析方法

结构化分析的常用工具：

数据流图（DFD）：是描述数据处理过程的工具，是需求理解的逻辑模型的

图形表示，它直接支持系统的功能建模。

数据字典（DD）：是结构化分析方法的核心。

判定树

判定表

结构化设计方法

常见的过程设计工具：

图形工具：程序流程图，N-S图，PAD图（问题分析图），HIPO

表格工具：判定表。

语言工具：PDL（伪码）

软件设计的基本原理

1）抽象：是一种思维工具，就是把事物本质的共同特性提取出来而不考

虑其他细节。

2）模块化：是指把一个待开发的软件分解成若干小的简单的部分。如高级

语言中的过程、函数、子程序等。每个模块可以完成一个特定的子功能，各个

模块可以按一定的方法组装起来成为一个整体，从而实现整个系统的功能。

3）信息隐蔽：是指在一个模块内包含的信息（过程或数据），对于不需要这

些信息的其他模块来说是不能访问的。

4）模块独立性：是指每个模块只完成系统要求的独立的子功能，并且与其他

模块的联系最少且接口简单。模块的独立程度是评价设计好坏的重要度量标

准。衡量软件的模块独立性使用耦合性和内聚性两

个定性的度量标准。

内聚性：是一个模块内部各个元素间彼此结合的紧密程度的度量。内

聚是从功能角度来度量模块内的联系。

内聚性是信息隐蔽和局部化概念的自然扩展。一个模块的内聚性越强则

该模块的模块独立性越强。作为软件结构设计的设计原则，要求每一个模块的

内部都具有很强的内聚性，它的各个组成部分彼此都密切相关。

耦合性：耦合性是模块间相互连接的紧密程度的度量。

一个模块与其他模块的耦合性越强则该模块的模块独立性越弱。原则上讲,

模块化设计总是希望模块间的耦合表现为非直接耦合方式。但是，由于问题所

固有的复杂性和结构化设计的原则，非直接耦合往往是不存在的。

耦合性与内聚性是模块独立性的两个定性标准，耦合性与内聚性是相互

联系的。在程序结构中，各模块的内聚性越强，则耦合性越弱。一般优秀

的软件设计，应尽量做到高内聚，低耦合，即减弱模块之间的耦合性和提高

模块内的的内聚性，有利于提高模块的独立性。

软件测试

软件测试是在软件投入运行前对软件需求、设计、编码的最后审核。软件

测试是为了发现错误而执行程序的过程。软件测试应当制定明确的测试计划并

按计划执行。

软件测试的目的：是发现错误。

软件测试方法和技术：若从是否需要执行被测软件的角度，可以分为静态

测试和动态测试方法。若按照功能划分可以分为白盒测试和黑盒测试方法。

静态测试：包括代码检查、静态结构分析、代码质量度量等。静态测试不

实际运行软件，主要通过人工进行。

动态测试：是基于计算机的测试，是为了发现错误而执行程序的过程。需

要精心设计一批测试用例，并利用这些测试用例去运行程序，以发现程序错误

的过程。测试用例的格式为：

［（输入值集）,（输出值集）］

白盒测试：也称结构测试或逻辑驱动测试。它是根据软件产品的内部工作

过程，检查内部成分，以确认每种内部操作符合设计规格要求。白盒测试

把测试对象看作一个打开的盒子，允许测试人员利用程序内部的逻辑结构及有

关信息来设计或选择测试用例，对程序所有的逻辑路径进行测试。通过在不同

点检查程序的状态来了解实际的运行状态是否与预期的一致。所以，白盒测

试是在程序内部进行，主要用于完成软件内部操作的验证。

白盒测试的主要方法有逻辑覆盖、基本路径测试等。

黑盒测试：也称功能测试或数据驱动测试。黑盒测试是对软件已经实现的

功能是否满足需求进行测试和验证。黑盒测试完全不考虑程序内部的逻辑结构

和内部特征，只依据程序的需求和功能规格说明，检查程序的功能是否符合

它的功能说明。所以，黑盒测试是在软件接口处进行，完成功能验证。黑盒

测试只检查程序功能是否按照需求规格说明书的规定正常使用，程序是否能适

当地接收输入数据而产生正确的输出信息，并且保持外部信息（如数据库或文件）

的完整性。

黑盒测试主要诊断功能不对或遗漏、界面错误、数据结构或外部数据库访

问错误、性能错误、初始化和终止条件错误。黑盒测试方法主要有等价类划分

法、边界值分析法、错误推测法、因果图等，主要用于软件确认测试。

程序调试

在对程序进行了成功的测试之后，将进入程序调试（通常称Debug,即排

错）。程序调试的任务是诊断和改正程序中的错误。

它与软件测试不同，软件测试是尽可能多地发现软件中的错

误，并找出软件错误的具体位置。软件测试贯穿整

个软件生命期，调试主要在开发阶段。

习题：

（-）选择题（单选）

1.软件按功能可以分为：应用软件、系统软件和支撑软件（或工具软件）。下面属于应用

软件的是（C）

A）编译程序B）操作系统C）教务管理系统D）汇编程序

2.软件按功能可分为：应用软件、系统软件、和支撑软件（或工具软件）。下面属于系统

软件的是（B）

A）编辑软件B）操作系统C）教务管理系统D）浏览器、

3.软件（程序）调试的任务是（A）

A）诊断和改正程序中的错误B）尽可能多的发现程序中的错误

0发现并改正程序中的所有错误D）确定程序中错误的性质

4.下面叙述中错误的是（A）

A）软件测试的目的是发现错误并改正错误

B）对被调试的程序进行“错误定位”是程序调试的必要步骤

C）程序调试通常也称为Debug

D）软件测试应严格执行测试计划，排除测试的随意性

5.耦合性和内聚性是对模块独立性度量的两个标准。下列叙述中正确的是（B）

A）提高耦合性、降低内聚性有利于提高模块的独立性

B）降低耦合性、提高内聚性有利于提高模块的独立性

C）耦合性是指一个模块内部各个元素间彼此结合的紧密程度

D）内聚性是指模块间互相连接的紧密程度

6.数据流图（DFD图）是（C）

A）软件概要设计的工具B）软件详细设计的工具

0结构化方法的需求分析工具D）面向对象方法的需求分析工具

7.软件生命周期可分为定义阶段，开发阶段和维护阶段。详细设计属于（B）

A）定义阶段B）开发阶段0维护阶段D）上述三个阶段

8.在软件开发中，需求分析阶段产生的主要文档是（D）

A）软件集成测试计划B）软件详细设计说明书0用户手册D）软件需求规格说

明书

9.结构化程序所要求的基本结构不包括（B）

A）顺序结构B）60T0跳转C）选择（分支）结构D）重复（循环）结构

10.下面描述中错误的是（A）

A)系统总体结构图支持软件系统的详细设计

B)软件设计是将软件需求转换为软件表示的过程

0数据结构与数据库设计是软件设计的任务之一

D)PAD图是软件详细设计的表示工具

(二)填空题

1.软件测试可分为白盒测试和黑盒测试。基本路径测试属于测试。

答案：白盒

2.符合结构化原则的三种基本控制结构是：选择结构、循环结构和

答案：顺序结构

3.软件是、数据和文档的集合。

答案：程序

4.对软件设计的最小单位(模块或程序单元)进行的测试通常为测试。

答案：单元或模块

三、数据库设计基础

计算机应用的三大领域：科学计算、数据处理、过程控制。

数据库系统的基本概念

数据(Data)：就是描述事物的符号记录。

数据库(DB)：是数据的集合，它具有统一的结构形式并存放于统一的存储

介质内，是多种应用数据的集成，并可被各个应用程序所共享。数据库中

的数据具有“集成”、“共享”的特点。

数据库管理系统(DBMS)：是数据库的机构，是一种系统软件，负责数

据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等。数据库

管理系统是数据库系统的核心。

数据库管理系统一般提供相应的数据语言(DataLanguage)来完成相应的功

能:

数据定义语言(DDL)：负责数据的模式定义与数据的物理存取构建。

数据操纵语言(DML)：负责数据的操纵，包括查询及增、删、改等操作。

数据控制语言(DCL)：负责数据完整性、安全性的定义与检查以及并发控

制、故障恢复等功能，包括系统初启程序、文件读写与维护程序、存取路径管

理程序、缓冲区管理程序、安全性控制程序、完整性检查程序、并发控制程序、

事务管理程序、运行日志管理程序、数据库恢复程序等。

数据库管理员(DBA)：由于数据库的共享性，因此对数据库的规划、设计、

维护、监视等需要有专人管理，称他们为数据库管理员。

数据库系统(DBS)：由数据库(数据)、数据库管理系统(软件)、数据库管理

员(人员)、系统硬件平台(硬件)、系统软件平台(软件)这五部分组成，称为数

据库系统。

数据库应用系统(DBAS):是数据库系统再加上应用软件及应用界面这三

者所组成。

E-R模型

该模型将现实世界的要求转化成实体、联系、属性等几个基本概念，以及

它们间的两种基本联接关系，并且可以用一种图非常直观地表示出来。下

面是E-R模型的基本概念。

目前较为有名的概念模型有E-R模型、扩充的E-R模型、面向对象模型及

谓词模型等。

实体：现实世界中的事物可以抽象成为实体。实体是概念世界中的基本单

位，它们是客观存在的且又相互区别的事物。凡是有共性的实体可组成一个

集合称实体集。如学生A和学生B,他们都是实体，他们又都是学生，从

而组成一个学生实体集。

属性：现实世界中的事物均有一些特性，这些特性可以用属性来表示。属

性刻画了实体的特征。一个实体往往可以有若干个属性。

联系：现实世界中事物间的关联称为联系。在概念世界中联系反映了实

体集间的一定关系。如工人与设备间的操作关系，上、下级间的领导关系等。

实体集间的联系有多种，就实体集的个数而言有：

1)两个实体集间的联系。

2)多个实体集间的联系。

3)一个实体集内部的联系：是一个实体集内的不同实体间的联系。

实体集间联系的个数可以是单个也可以是多个，包括：

一对一的联系，简记为1:1

一对多或多对一的联系，简记为1:M或M:1(其中M也可以小写)

多对多的联系，简记为M:N或m:n

E-R模型由上面三个基本概念组成。由实体、联系、属性三者结合起来才

能表示现实世界。

E-R图：E-R模型可以用一种非常直观的图的形式表示，这种图称为E-R

图。在E-R图中我们分别用下面不同的几何图形表示E-R模型中的三个概念

与两个联接关系。

1)实体集表示法

用矩形表示实体集，在矩形内写上该实体集的名字。如实体集学生

(student)>课程(course)可表示为：

studentcourse

实体集表示法

2)属性表示法

用椭圆形表示属性，在椭圆形内写上该属性的名称。如学生有属性：学

号(S#)、姓名(Sn)及年龄(Sa),可表示为:

(^Sn^)

属性表示法

3)联系表示法

用菱形表示联系，在菱形内写上联系名。如学生与课程间的联系SC,

可表示为:

上面是三个基本概念分别用三种几何图形表示。下面是它们之间的联接关系

的图形表示。

4）实体集或联系与属性间的联接关系

属性依附于实体集，属性也依附于联系，因此它们之间分别有联接关系。

其中：C#（课程号）、Cn（课程名）、P#（预修课号）

5）实体集与联系间的联接关系

如下图表示实体集与联系间的联接关系：

还可以在线段边上注明其对应的函数关系，如1:1、l:n、n:m等。下图表

示student与course间有多对多联系：

下图

联系FPU是一种三元联系(工厂、产品与用户间的联系)：

下面是实体间多种联系图:

(a)图：公司职工(enployee"可上、下级管理(manage)的联系。即一个实体

集内部可以有多种联系。

(b)图：教师(T)与学生(S)之间可以有教学(E)联系也可以有管理(M)联系。

即实体集间可以有多种联系。

关系模型

关系模型采用二维表来表示，简称表。

二维表由表框架(Frame)及表的元组(Tuple)组成。表框架由n个命名的属性

(Attribute)组成，n称为属性元数(Arity)。每个属性有一个取值范围，称为值

域(Domain)。表框架对应了关系的模式，即类型的概念。

在表框架中按行可以存放数据，每行数据称为元组，实际上，一个元组

是由n个元组分量所组成，每个元组分量是表框架中每个属性的投影值。一

个表框架可以存放m个元组，m称为表的基数(Cardinality)。

一个n元表框架及框架内m个元组构成了一个完整的二维表。

关系框架与关系元组构成了一个关系。一个语义相关的关系集合构

成一个关系数据库。关系的框架称为关系模式，而语义相关的关系模式集

合构成了关系数据库模式。

满足下面7个性质的二维表称为关系（Relation）：

1）元组个数有限性：二维表中元组个数是有限的。

2）元组的惟一性：二维表中元组均不相同。

3）元组的次序无关性：二维表中元组的次序可以任意交换。

4）元组分量的原子性：二维表中元组的分量是不可分割的基本数据项。

5）属性名惟一性：二维表中属性名各不相同。

6）属性的次序无关性：二维表中属性与次序无关，可任意交换。

7）分量值域的同一性：二维表属性的分量具有与该属性相同的值域。

以二维表（关系）为基本结构所建立的模型称为关系模型。

在关系模型中的一个重要概念是键（Key）或码。键具有标识元组、建立元

组间联系等重要作用。

键或码：在二维表中凡能惟一标识元组的最小属性集称为该表的键或码。

候选键或候选码：二维表中可能有若干个键，它们称为该表的候选键

（CandidataKey）或候选码。

主键或主码：从二维表的所有候选键中选取一个作为用户使用的键，称为

主键（PrimaryKey）或主码。一般主键也简称为键或码。

外键或外码：表A中的某属性集是某表B的键，则称该属性集为A的

外键（ForeignKey）或外码。

表中一定要有键，因为如果表中所有属性的子集均不是键，则表中属性的

全集必为键（称为全键），因此也一定有主键。

在关系元组的分量中允许出现空值（NullValue）以表示信息空缺。空值用

于表示未知的值或不可能出现的值，一般用NULL表示。一般关系数据库

系统都支持空值，但是有两个限制：关系的主键中不允许出现空值，因为如

主键为空值则失去了其元组标识的作用；需要定义有关空值的运算。

关系代数

关第代数是关于关系数据库的理论。

数据库设计与管理

数据库设计是数据库应用的核心。

数据库设计的四个阶段，参见下图:

DBMS模彗

DBMS条件

硬件、OS支膜

数据库内模式

数据库设计的四个阶段

从E-R图向关系模式转换

参见下表:

E-R模型与关系间的比较袅

E-R模型

关系E-R模型关系

属性

属性实体集关系

•

实体

元组联系关系

习题:

（-）选择题（单选）

1.数据库应用系统中的核心问题是（A）

A