第1章 公共基础知识

本章内容主要是计算机等级考试二级的公共基础知识部分。本章主要介绍一些关于程序设计的基础知识和面向对象的程序设计基础。本章分为4节内容，包括数据结构与算法、程序设计基础、软件工程基础和数据库设计基础。

1.1 数据结构与算法

考点1 算法

1．算法的基本概念

算法是指对解题方案准确而完整的描述。

（1）算法的基本特征。

●可行性：针对实际问题而设计的算法，执行后能够得到满意的结果，即必须有一个或多个输出。注意，即使某一算法在数学理论上是正确的，但如果在实际的计算工具上不能执行，则该算法也是不具有可行性的。

●确定性：指算法中每一步骤都必须是有明确定义的。

●有穷性：指算法必须能在有限的时间内做完。

●拥有足够的情报：一个算法是否有效，还取决于为算法所提供的情报是否足够。

（2）算法的基本要素。

算法一般由两种基本要素构成：

●对数据对象的运算和操作；

●算法的控制结构，即运算和操作时间的顺序。

算法中对数据的运算和操作：算法就是按解题要求从指令系统中选择合适的指令组成的指令序列。因此计算机算法就是计算机能执行的操作所组成的指令序列。不同的计算机系统，其指令系统是有差异的，但一般的计算机系统中都包括的运算和操作有4类，即算术运算、逻辑运算、关系运算和数据传输。

算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。算法的功能不仅取决于所选用的操作，还与各操作之间的执行顺序有关。基本的控制结构包括顺序结构、选择结构和循环结构。

（3）算法设计的基本方法。

算法设计的基本方法有列举法、归纳法、递推法、递归法、减半递推技术和回溯法。

2．算法复杂度

算法的复杂度主要包括时间复杂度和空间复杂度。

（1）算法的时间复杂度。

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

一般情况下，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f（n）

其中n是问题的规模。这个表达式表示随着问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同。

在同一个问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入，可以用两种方法来分析算法的工作量：平均性态分析和最坏情况分析。

（2）算法的空间复杂度。

一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。算法执行期间所需要的存储空间包括3个部分：

●算法程序所占的空间；

●输入的初始数据所占的存储空间；

●算法执行过程中所需要的额外空间。

在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术。

考点2 数据结构的基本概念

1．数据结构的定义

数据结构是指相互有关联的数据元素的集合，即数据的组织形式。

（1）数据的逻辑结构。

所谓数据的逻辑结构，是指反映数据元素之间逻辑关系（即前、后件关系）的数据结构。它包括数据元素的集合和数据元素之间的关系。

（2）数据的存储结构。

数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称为数据的物理结构）。数据结构的存储方式有顺序存储方法、链式存储方法、索引存储方法和散列存储方法。而采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构是很重要的。

数据结构研究的内容主要包括3个方面：

●数据集合中各数据元素之间的逻辑关系，即数据的逻辑结构；

●在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；

●对各种数据结构进行的运算。

2．数据结构的图形表示

数据元素之间最基本的关系是前、后件关系。前、后件关系，即每一个二元组，都可以用图形来表示。用中间标有元素值的方框表示数据元素，一般称之为数据结点，简称为结点。对于每一个二元组，用一条有向线段从前件指向后件。

用图形表示数据结构具有直观易懂的特点，在不引起歧义的情况下，前件结点到后件结点连线上的箭头可以省去。例如，树形结构中，通常是用无向线段来表示前、后件关系的。

3．线性结构与非线性结构

根据数据结构中各数据元素之间前、后关系的复杂程度，一般将数据结构分为两大类型，即线性结构和非线性结构。

如果一个非空的数据结构有且只有一个根结点，并且每个结点最多有一个直接前驱或直接后继，则称该数据结构为线性结构，又称线性表。不满足上述条件的数据结构称为非线性结构。

真题精选

下列叙述中正确的是（ ）。

A．程序执行的效率与数据的存储结构密切相关

B．程序执行的效率只取决于程序的控制结构

C．程序执行的效率只取决于所处理的数据量

D．以上3种说法都不对

【答案】 A

【解析】在计算机中，数据的存储结构对数据的执行效率有较大影响，如在有序存储的表中查找某个数值比在无序存储的表中查找的效率高很多。

考点3 线性表及其顺序存储结构

1．线性表的基本概念

在数据结构中，线性结构也称为线性表，线性表是最简单也是最常用的一种数据结构。

线性表是由n（n≥0）个数据元素a1, a2, …, an组成的一个有限序列，除表中的第一个元素外，其他元素有且只有一个前件，除了最后一个元素外，其他元素有且只有一个后件。

线性表要么是个空表，要么可以表示为

（a1, a2, …, an）

其中ai（i=1,2, …, n）是线性表的数据元素，也称为线性表的一个结点。

每个数据元素的具体含义，在不同情况下各不相同，它可以是一个数或一个字符，也可以是一个具体的事物，甚至其他更复杂的信息。但是需要注意的是，同一线性表中的数据元素必定具有相同的特性，即属于同一数据对象。

2．线性表的顺序存储结构

将线性表中的元素一个接一个地存储在一片相邻的存储区域中。这种顺序表示的线性表也称为顺序表。

线性表的顺序存储结构具有以下两个基本特点：

●元素所占的存储空间必须是连续的；

●元素在存储空间的位置是按逻辑顺序存放的。

从这两个特点也可以看出，线性表是用元素在计算机内物理位置上的相邻关系来表示元素之间逻辑上的相邻关系。只要确定了首地址，线性表内任意元素的地址都可以方便地计算出来。

3．线性表的插入运算

在线性表的插入运算中，在第i个元素之前插入一个新元素，完成插入操作主要有以下3个步骤：

（1）把原来第n个结点至第i个结点依次往后移动一个元素位置；

（2）把新结点放在第i个位置上；

（3）修正线性表的结点个数。

如果需要在线性表末尾进行插入运算，则只需要在表的末尾增加一个元素即可，不需要移动线性表中的元素。

如果在第一个位置插入新的元素，则需要移动表中的所有数据。

4．线性表的删除运算

在线性表的删除运算中，删除第i个位置的元素，则要从第i+1个元素开始直到第n个元素之间，共n-i个元素依次向前移一个位置。完成删除运算主要有以下几个步骤：

（1）把第i个元素之后（不包括第i个元素）的n-i个元素依次前移一个位置；

（2）修正线性表的结点个数。

显然，如果删除运算在线性表的末尾进行，即删除第n个元素，则不需要移动线性表中的元素。

如果要删除第1个元素，则需要移动表中的所有数据。

真题精选

【例1】下列有关顺序存储结构的叙述，不正确的是（ ）。

A．存储密度大

B．逻辑上相邻的结点物理上不必邻接

C．可以通过计算机直接确定第i个结点的存储地址

D．插入、删除操作不方便

【答案】B

【解析】顺序存储结构要求逻辑上相邻的元素物理上也相邻，所以只有选项B叙述错误。

【例2】在一个长度为n的顺序表中，向第i个元素（1≤i≤n+1）位置插入一个新元素时，需要从后向前依次移动（ ）个元素。

A.n-i

B.i

C.n-i-1

D.n-i+1

【答案】D

【解析】根据顺序表的插入运算的定义知道，在第i个位置上插入x，从ai到an都要向后移动一个位置，共需要移动n-i+1个元素。

考点4 栈和队列

1．栈及其基本运算

（1）栈的基本概念。

栈实际上也是线性表，只不过是一种特殊的线性表。在这种特殊的线性表中，其插入与删除运算都只在线性表的一端进行。

在栈中，允许插入与删除的一端称为栈顶（top），另一端称为栈底（bot-tom）。当栈中没有元素时称为空栈，栈也被称为“先进后出”表，或“后进先出”表。

（2）栈的特点。

根据栈的上述定义，可知栈具有以下特点：

●栈顶元素总是最后被插入的元素，也是最早被删除的元素；

●栈底元素总是最早被插入的元素，也是最晚才能被删除的元素；

●栈具有记忆功能；

●在顺序存储结构下，栈的插入和删除运算都不需要移动表中其他数据元素；

●栈顶指针top动态反映了栈中元素的变化情况。

（3）栈的顺序存储及其运算。

栈的状态如图1.1所示。

根据栈的状态，可以得知栈的基本运算有3种。

●入栈运算：在栈顶位置插入一个新元素。

●退栈运算：取出栈顶元素并赋给一个指定的变量。

●读栈顶元素：将栈顶元素赋给一个指定的变量。

2．队列及其基本运算

（1）队列的基本概念。

队列是指允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为尾指针（rear）的指针指向队尾元素；允许删除的一端称为队头，通常用一个头指针（front）指向头元素的前一个位置。

因此，队列又称为“先进先出”（FIFO, FirstIn FirstOut）的线性表。插入元素称为入队运算，删除元素称为退队运算。

队列的基本结构如图1.2所示。

（2）循环队列及其运算。

所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。

在循环队列中，用尾指针指向队列的尾元素，用头指针指向头元素的前一个位置，因此，从头指针指向的后一个位置直到尾指针指向的位置之间所有的元素均为队列中的元素。循环队列的初始状态为空，即rear=front。

循环队列的基本运算主要有两种：入队运算与退队运算。

●入队运算是指在循环队列的队尾加入一个新的元素。

●退队运算是指在循环队列的队头位置退出一个元素，并赋给指定的变量。

真题精选

【例1】下列对队列的叙述，正确的是（ ）。

A．队列属于非线性表

B．队列按“先进后出”原则组织数据

C．队列在队尾删除数据

D．队列按“先进先出”原则组织数据

【答案】D

【解析】队列是一种特殊的线性表，它只能在一端进行插入，在另一端进行删除。允许插入的一端称为队尾，允许删除的一端称为队头。队列又称为“先进先出”或“后进后出”的线性表，体现了“先到先服务”的原则。

【例2】下列关于栈的描述，正确的是（ ）。

A．在栈中只能插入元素而不能删除元素

B．在栈中只能删除元素而不能插入元素

C．栈是特殊的线性表，只能在一端插入或删除元素

D．栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素

【答案】C

【解析】栈是一种特殊的线性表。在这种特殊的线性表中，其插入和删除操作只在线性表的一端进行。

考点5 线性链表

1．线性链表的基本概念

线性表的链式存储结构称为线性链表。

为了存储线链性表中的每一个元素，一方面要存储数据元素的值；另一方面要存储各数据元素之间的前、后件关系。为此，在链式存储结构中，每个结点由两部分组成：一部分称为数据域，用于存放数据元素值；另一部分称为指针域，用于存放下一个数据元素的存储序号，即指向后件结点。链式存储结构既可以表示线性结构，也可以表示非线性结构。

线性表链式存储结构的特点是：用一组不连续的存储单元存储线性表中的各个元素。因为存储单元不连续，数据元素之间的逻辑关系，就不能依靠数据元素的存储单元之间的物理关系来表示。

2．线性链表的基本运算

线性链表主要包括以下几种运算：

●在线性链表中包含指定元素的结点之前插入一个新元素；

●在线性链表中删除包含指定元素的结点；

●将两个线性链表按要求合并成一个线性链表；

●将一个线性链表按要求进行分解；

●逆转线性链表；

●复制线性链表；

●线性链表的排序；

●线性链表的查找。

3．循环链表及其基本运算

（1）循环链表的定义。

在单链表的第一个结点前增加一个表头结点，队头指针指向表头结点，在最后一个结点的指针域的值由NULL改为指向表头结点，这样的链表称为循环链表。在循环链表中，所有结点的指针构成了一个环状链。

（2）循环链表与单链表的比较。

对单链表的访问是一种顺序访问，从其中某一个结点出发，只能找到它的直接后继，但无法找到它的直接前驱，而且对于空表和第一个结点的处理必须单独考虑，空表与非空表的操作不统一。

在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点。并且，由于表头结点是循环链表所固有的结点，因此，即使在表中没有数据元素的情况下，表中也至少有一个结点存在，从而使空表和非空表的运算统一。

真题精选

下列叙述中，正确的是（ ）。

A．线性链表是线性表的链式存储结构

B．栈与队列是非线性结构

C．双向链表是非线性结构

D．只有根结点的二叉树是线性结构

【答案】A

【解析】根据数据结构中各数据元素之间前后关系的复杂程度，可将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件：①有且只有一个根结点；②每个结点最多有一个前驱，也最多有一个后继。则称该数据结构为线性结构，也叫做线性表。若不满足上述条件，则称之为非线性结构。线性表、栈、队列和线性链表都是线性结构，而二叉树是非线性结构。

考点6 树和二叉树

1．树的基本概念

树是一种简单的非线性结构，直观地来看，树是以分支关系定义的层次结构。树是由n（n≥0）个结点构成的有限集合，n=0的树称为空树；当n≠0时，树中的结点应该满足以下两个条件：

●有且仅有一个没有前驱的结点称之为根；

●其余结点分成m（m＞0）个互不相交的有限集合T1, T2, …, Tm，其中每一个集合又都是一棵树，称T1, T2, …, Tm为根结点的子树。

在树的结构中主要涉及下面几个概念：

●每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根；

●每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点；

●一个结点所拥有的后继个数称为该结点的度；

●所有结点最大的度称为树的度；

●树的最大层次称为树的深度。

2．二叉树及其基本性质

（1）二叉树的定义。

二叉树是一种非线性结构，是一个有限的结点集合，该集合或者为空，或者由一个根结点及其两棵互不相交的左、右二叉子树所组成。当集合为空时，称该二叉树为空二叉树。

二叉树具有以下特点：

●二叉树可以为空，空的二叉树没有结点，非空二叉树有且只有一个根结点；

●每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

（2）满二叉树和完全二叉树。

满二叉树：除最后一层外，每一层上的所有结点都有两个子结点，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树中有2m-1个结点。

完全二叉树：除最后一层外，每一层上的结点数都达到最大值；在最后一层上只缺少右边的若干结点。

满二叉树与完全二叉树的关系：满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

（3）二叉树的主要性质。

●一棵非空二叉树的第k层上最多有2k-1个结点（k≥1）。

●深度为m的满二叉树中有2m-1个结点。

●对任何一棵二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个。

●具有n个结点的完全二叉树的深度k为[log2n] +1。

3．二叉树的存储结构

在计算机中，二叉树通常采用链式存储结构。用于存储二叉树中各元素的存储结点由数据域和指针域组成。由于每一个元素可以有两个后件（即两个子结点），所以用于存储二叉树的存储结点的指针域有两个：一个指向该结点的左子结点的存储地址，称为左指针域；另一个指向该结点的右子结点的存储地址，称为右指针域。因此，二叉树的链式存储结构也称为二叉链表。

对于满二叉树与完全二叉树可以按层次进行顺序存储。

二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历主要是针对非空二叉树的，对于空二叉树，则结束遍历并返回。

4．二叉树的遍历

二叉树的遍历有前序遍历、中序遍历和后序遍历。

（1）前序遍序（DLR）。

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

（2）中序遍历（LDR）。

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

（3）后序遍历（LRD）。

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

真题精选

对如图1.3所示二叉树进行后序遍历的结果为（ ）。

A.ABCDEF

B.DBEAFC

C.ABDECF

D.DEBFCA

【答案】D

【解析】执行后序遍历，依次执行以下操作：

①首先按照后序遍历的顺序遍历根结点的左子树；

②然后按照后序遍历的顺序遍历根结点的右子树；

③最后访问根结点。

考点7 查找技术

1．顺序查找

顺序查找一般是指在线性表中查找指定的元素。其基本思路是：从表中的第一个元素开始，依次将线性表中的元素与被查找元素进行比较，直到两者相符，查到所要找的元素为止；否则，表中没有要找的元素，查找不成功。

在最好的情况下，第一个元素就是要查找的元素，则比较次数为1次。

在最坏的情况下，顺序查找需要比较n次。

在平均情况下，需要比较n/2次。因此，查找算法的时间复杂度为O（n）。

在下列两种情况下只能够采取顺序查找：

●如果线性表中元素的排列是无序的，则无论是顺序存储结构还是链式存储结构，都只能采用顺序查找；

●即便是有序线性表，若采用链式存储结构，则只能进行顺序查找。

2．二分查找

使用二分查找的线性表必须满足两个条件：

●顺序存储结构；

●线性表是有序表。

所谓有序表，是指线性表中的元素按值非递减排列（即从小到大，但允许相邻元素值相等）。

对于长度为n的有序线性表，利用二分查找元素x的过程如下：

（1）将x与线性表的中间项进行比较；

（2）若中间项的值等于x，则查找成功，结束查找；

（3）若x小于中间项的值，则在线性表的前半部分以二分法继续查找；

（4）若x大于中间项的值，则在线性表的后半部分以二分法继续查找。

这样反复进行查找，直到查找成功或子表长度为0（说明线性表中没有这个元素）为止。

当有序线性表为顺序存储时采用二分查找的效率要比顺序查找高得多。对于长度为n的有序线性表，在最坏的情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。

真题精选

下列数据结构中，能用二分法进行查找的是（ ）。

A．顺序存储的有序线性表

B．线性链表

C．二叉链表

D．有序线性链表

【答案】A

【解析】二分查找只适用于顺序存储的有序表。所谓有序表是指线性表中的元素按值非递减排列（即从小到大，但允许相邻元素值相等）。

考点8 排序技术

1．交换类排序法

交换类排序法是指借助数据元素的“交换”来进行排序的一种方法。这里介绍的冒泡排序法和快速排序法就属于交换类排序法。

（1）冒泡排序法。

冒泡排序的思想如下：

在线性表中依次查找相邻的数据元素，将表中最大的元素不断往后移动，反复操作直到消除所有逆序，此时，该表已经排序结束。

冒泡排序法的基本过程如下：

①从表头开始往后查找线性表，在查找过程中逐次比较相邻两个元素的大小。若在相邻两个元素中，前面的元素大于后面的元素，则将它们交换；

②从后向前查找剩下的线性表（除去最后一个元素），同样，在查找过程中逐次比较相邻两个元素的大小。若在相邻两个元素中，后面的元素小于前面的元素，则将它们交换；

③对剩下的线性表重复上述过程，直到剩下的线性表变空为止，线性表排序完成。

假设线性表的长度为n，则在最坏的情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前扫描，需要比较n（n-1）/2次，其数量级为n2。

（2）快速排序法。

快速排序法的基本思想如下：

在线性表中逐个选取元素，将线性表进行分割，直到所有元素全部选取完毕，此时线性表已经排序结束。

快速排序法的基本过程如下：

①从线性表中选取一个元素，设为T，将线性表后面小于T的元素移动到前面，而将大于T的元素移到后面，这样就将线性表分成了两部分（称为两个子表）, T就是处于分界线的位置，将线性表分成了前、后两个子表，且前面子表中的所有元素均不大于T，而后面的子表中的所有元素均不小于T，此过程称为线性表的分割；

②对分割后的子表再按上述原则进行反复分割，直到所有子表为空为止，则此时的线性表就变成有序表。

2．插入类排序法

插入排序是指将无序序列中的各元素依次插入到已经有序的线性表中。这里主要介绍简单插入排序法和希尔排序法。

（1）简单插入排序法。

简单插入排序是把n个待排序的元素看成一个有序表和一个无序表，开始时，有序表只包含一个元素，而无序表包含n-1个元素，每次取无序表中的第一个元素插入到有序表中的正确位置，使之成为增加一个元素的新的有序表。插入元素时，插入位置及其后的记录依次向后移动。最后有序表的长度为n，而无序表为空，此时排序完成。

在简单插入排序中，每一次比较后最多移掉一个逆序，因此，该排序方法的效率与冒泡排序法相同。在最坏的情况下，简单插入排序需要n（n-1）/2次比较。

（2）希尔排序法。

希尔排序法的基本思路为：将整个无序序列分割成若干个小的子序列并分别进行插入排序。

分割方法如下：

①将相隔某个增量h的元素构成一个子序列；

②在排序过程中，逐次减少这个增量，直到h减少到1时，进行一次插入排序，排序即可完成。

希尔排序的效率与所选取的增量序列有关。

3．选择类排序法

选择排序的基本思想是通过每一趟从待排序序列中选出值最小的元素，按顺序放在已排好序的有序子表的后面，直到全部序列满足排序要求为止。下面就介绍选择类排序法中的简单选择排序法和堆排序法。

（1）简单选择排序法。

简单选择排序的基本思想是：首先从所有n个待排序的数据元素中选择最小的元素，将该元素与第一个元素交换，再从剩下的n-1个元素中选出最小的元素与第二个元素交换。重复这样的操作直到所有的元素有序为止。

简单选择排序在最坏情况下需要比较n（n-1）/2次。

（2）堆排序法。

堆排序的方法如下：

①将一个无序序列建成堆；

②将堆顶元素与堆中最后一个元素交换。忽略已经交换到最后的那个元素，考虑前n-1个元素构成的子序列，只有左、右子树是堆，可以将该子树调整为堆。这样重复去做第二步，直到剩下的子序列为空时止。

在最坏的情况下，堆排序需要比较的次数为O（nlog2n）。

真题精选

对于长度为n的线性表，在最坏的情况下，下列各排序法所对应的比较次数中正确的是（ ）。

A．冒泡排序为n/2

B．冒泡排序为n

C．快速排序为n

D．快速排序为n（n-1）/2

【答案】D

【解析】假设线性表的长度为n，则在最坏的情况下，冒泡排序需要经过n/2遍的从前往后扫描和n/2遍的从后往前扫描，需要比较次数为n（n-1）/2。快速排序法在最坏的情况下，比较次数也是n（n-1）/2。

1.2 程序设计基础

考点9 程序设计方法与风格

1．程序设计方法

程序设计是指设计、编制、调试程序的方法和过程。

程序设计方法是研究问题求解如何进行系统构造的软件方法学。常用的程序设计方法有结构化程序设计方法、软件工程方法和面向对象方法。

2．程序设计风格

程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。良好的程序设计风格可以使程序结构清晰合理，程序代码便于维护，因此，程序设计风格深深地影响着软件的质量和维护。要形成良好的程序设计风格，主要应注重和考虑的因素有以下几点：

●源程序文档化；

●数据说明方法；

●语句的结构；

●输入和输出。

真题精选

【例1】下列叙述中，不属于良好程序设计风格要求的是（ ）。

A．程序的效率第一，清晰第二

B．程序的可读性好

C．程序中要有必要的注释

D．输入数据前要有提示信息

【答案】A

【解析】著名的“清晰第一，效率第二”的论点已经成为主导的程序设计风格，所以选项A是错误的，其余选项都是良好程序设计风格的要求。

【例2】下列选项中不符合良好程序设计风格的是（ ）。

A．源程序要文档化

B．数据说明的次序要规范化

C．避免滥用goto语句

D．模块设计要保证高耦合、高内聚

【答案】D

【解析】良好的程序设计风格使程序结构清晰合理，使程序代码便于维护。主要应注意和考虑的因素有：①源程序要文档化；②数据说明的次序要规范化；③语句的结构应简单直接，不应该为提高效率而把语句复杂化，避免滥用goto语句；④模块设计要保证低耦合、高内聚。

考点10 结构化程序设计

1．结构化程序设计的原则

结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、模块化及限制使用goto语句。

（1）自顶向下：程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑具体问题。

（2）逐步求精：将复杂问题细化，细分为逐个小问题再依次求解。

（3）模块化：是把程序要解决的总目标分解为若干目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。

（4）限制使用goto语句。

2．结构化程序设计的基本结构

结构化程序设计有3种基本结构，即顺序结构、选择结构和循环结构，其基本形式如图1.4所示。

3．结构化程序设计的原则和方法的应用

结构化程序设计是一种面向过程的程序设计方法。在结构化程序设计的具体实施中，需要注意以下问题：

●使用程序设计语言的顺序、选择、循环等有限的控制结构表示程序的控制逻辑；

●选用的控制结构只准许有一个入口和一个出口；

●程序语句组成容易识别的块，每块只有一个入口和一个出口；

●复杂结构应该应用嵌套的基本控制结构进行组合嵌套来实现；

●语言中所没有的控制结构，应该采用前后一致的方法来模拟；

●严格控制goto语句的使用。

真题精选

下列选项中不属于结构化程序设计方法的是（ ）。

A．自顶向下

B．逐步求精

C．模块化

D．可复用

【答案】D

【解析】20世纪70年代以来，提出了许多软件设计方法，主要包括：①逐步求精，对复杂的问题，应设计一些子目标作过渡，逐步细化。②自顶向下，程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。一开始不要过多追求细节，先从最上层总目标开始设计，逐步使问题具体化。③模块化，一个复杂问题，肯定是由若干相对简单的问题构成。模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。而可复用是面向对象程序设计的一个优点，不是结构化程序设计方法。

考点11 面向对象的程序设计

1．面向对象方法的本质

面向对象方法的本质就是主张从客观世界固有的事物出发来构造系统，提倡用人类在现实生活中常用的思维方法来认识、理解和描述客观事物，强调最终建立的系统能够映射问题域。

2．面向对象方法的优点

●与人类习惯的思维方法一致；

●稳定性好；

●可重用性好；

●易于开发大型软件产品；

●可维护性好。

3．面向对象方法的基本概念

（1）对象。

对象是面向对象方法中最基本的概念。对象可以用来表示客观世界中任何实体，它既可以是具体的物理实体的抽象，也可以是人为概念，或者是任何有明确边界和意义的东西。

（2）类。

类是具有共同属性、共同方法的对象的集合，是关于对象的抽象描述，反映属于该对象类型的所有对象的性质。

（3）实例。

实例是指一个具体对象则是其对应类的一个实例。

（4）消息。

消息是一个实例与另一个实例之间传递的信息，它请求对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。

（5）继承。

继承是使用已有的类定义作为基础建立新类的定义方法。在面向对象方法中，类组成为具有层次结构的系统：一个类的上层可有父类，下层可有子类；一个类直接继承其父类的描述（数据和操作）或特性，子类自动地共享基类中定义的数据和方法。

（6）多态性。

对象根据所接收的信息而做出动作，同样的消息被不同的对象接收时可以有完全不同的行动，该现象称为多态性。

真题精选

在面向对象方法中，实现信息隐蔽是依靠（ ）。

A．对象的继承

B．对象的多态

C．对象的封装

D．对象的分类

【答案】C

【解析】对象是由数据和操作组成的封装体，与客观实体有直接的对应关系。对象之间通过传递消息互相联系，以模拟现实世界中不同事物彼此之间的关系。面向对象方法的3个重要特性为：封装性、继承性和多态性。

1.3 软件工程基础

考点12 软件工程的基本概念

1．软件定义与软件特点

（1）软件的定义。

软件（software）是与计算机系统的操作有关的计算机程序、规程、规则，以及可能有的文件、文档及数据。

计算机软件由两部分组成：一是机器可执行的程序和数据；二是机器不可执行的，与软件开发、运行、维护、使用等有关的文档。

（2）软件的特点。

软件主要包括以下几个特点：

●软件是一种逻辑实体，具有抽象性；

●软件的生产与硬件不同，它没有明显的制作过程；

●软件在运行、使用期间，不存在磨损、老化问题；

●软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题；

●软件复杂性高、成本昂贵；

●软件开发涉及诸多的社会因素。

2．软件危机与软件工程

（1）软件危机。

软件危机泛指在计算机软件的开发和维护中所遇到的一系列严重问题。具体地说，在软件开发和维护过程中，软件危机主要表现在以下几个方面：

●软件需求的增长得不到满足；

●软件的开发成本和进度无法控制；

●软件质量难以保证；

●软件不可维护或维护程度非常低；

●软件的成本不断提高；

●软件开发生产率的提高赶不上硬件的发展和应用需求的增长。

总之，可以将软件危机归结为成本、质量、生产率等问题。

（2）软件工程。

软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。

软件工程包括两方面内容：软件开发技术和软件工程管理。软件工程包括3个要素，即方法、工具和过程。软件的核心思想是把软件产品看做是一个工程产品来处理。

3．软件工程过程与软件生命周期

（1）软件工程过程。

软件工程过程是把输入转化成为输出的一组彼此相关的资源和活动。

（2）软件生命周期。

通常，将软件产品从提出、实现、使用维护到停止使用的过程称为软件生命周期。

软件生命周期主要包括软件定义、软件开发及软件运行维护3个阶段。其中软件生命周期的主要活动阶段包括可行性研究与计划制订、需求分析、软件设计、软件实现、软件测试和运行维护。

4．软件工程的目标与原则

（1）软件工程的目标。

软件工程需达到的目标是：在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。

（2）软件工程的原则。

为了实现上述的软件工程目标，在软件开发过程中，必须遵循软件工程的基本原则。这些原则适用于所有的软件项目，包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。

5．软件开发工具与软件开发环境

软件开发工具与软件开发环境的使用，提高了软件的开发效率、维护效率和软件质量。

（1）软件开发工具。

软件开发工具的产生、发展和完善促进了软件的开发速度和质量的提高。软件开发工具从初期的单项工具逐步向集成工具发展。与此同时，软件开发的各种方法也必须得到相应的软件工具的支持，否则方法就很难有效地实施。

（2）软件开发环境。

软件开发环境是全面支持软件开发过程的软件工具集合。这些软件工具按照一定的方法或模式组合起来，支持软件生命周期的各个阶段和各项任务的完成。

计算机辅助软件工程（CASE）是当前软件开发环境中富有特色的研究工作和发展方向。CASE将各种软件工具、开发机器和一个存放过程信息的中心数据库组合起来，形成软件工程环境。一个良好的软件工程环境将最大限度地降低软件开发的技术难度并使软件开发的质量得到保证。

真题精选

下列描述中，正确的是（ ）。

A．程序就是软件

B．软件开发不受计算机系统的限制

C．软件既要是逻辑实体，又是物理实体

D．软件是程序、数据与相关文档的集合

【答案】D

【解析】计算机软件是计算机系统中与硬件相互依存的另一部分，包括程序、数据及相关文档的完整集合。软件具有以下特点：①软件是一种逻辑实体，而不是物理实体，具有抽象性；②软件的生产过程与硬件不同，没有明显的制作过程；③软件在运行、使用期间，不存在磨损、老化问题；④软件的开发、运行对计算机系统具有不同程度的依赖性，这导致软件移植的问题；⑤软件复杂性高，成本昂贵；⑥软件开发涉及诸多的社会因素。

考点13 结构化分析方法

1．需求分析和需求分析方法

（1）需求分析。

软件需求是指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。

需求分析的任务是发现需求、求精、建模和定义需求的过程。需求分析将创建所需的数据模型、功能模型和控制模型。

需求分析阶段的工作，可以概括为4个方面：需求获取、需求分析、编写需求规格说明书、需求评审。

（2）需求分析方法。

常用的需求分析方法有结构化分析方法和面向对象分析方法。

2．结构化分析方法

（1）结构化分析方法。

结构化分析方法是结构化程序设计理论在软件需求分析阶段的应用。

结构化分析方法的实质是着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。

（2）结构化分析方法的常用工具。

常用工具包括数据流图（DFD）、数据字典（DD）、判断树、判断表。下面主要介绍数据流图和数据字典。

数据流图（DataFlowDiagram, DFD）是描述数据处理的工具，是需求理解的逻辑模型的图形表示，它直接支持系统的功能建模。

数据流图从数据传递和加工的角度，来刻画数据流从输入到输出的移动变换过程，其主要图形元素及说明见表1.1。

数据字典是结构化分析方法的核心，是对所有与系统相关的数据元素的一个有组织的列表，以及明确的、严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。通常数据字典包含的信息有名称、别名、何处使用/如何使用、内容描述、补充信息等。数据字典中有4种类型的条目：数据流、数据项、数据存储和数据加工。

3．软件需求规格说明书

软件需求规格说明书是需求分析阶段的最后结果，是软件开发中的重要文档之一。

软件需求规格说明书的标准主要有正确性、无歧义性、完整性、可验证性、一致性、可理解性、可修改性和可追踪性。

考点14 结构化设计方法

1．软件设计的基本概念及方法

（1）软件设计的基础。

软件设计是软件工程的重要阶段，是一个把软件需求转换为软件表示的过程。软件设计的基本目标是用比较抽象概括的方式确定目标系统如何完成预定的任务，即软件设计是确定系统的物理模型。

（2）软件设计的基本原理。

软件设计遵循软件工程的基本目标和原则，建立了适用于在软件设计中应该遵循的基本原理和与软件设计有关的概念。主要包括抽象、模块化、信息隐藏及模块的独立性。下面主要介绍模块独立性的一些度量标准。

模块的独立程度是评价设计好坏的重要度量标准。衡量软件的模块独立性的定性度量标准是使用耦合性和内聚性。

耦合性是模块间互相连接的紧密程度的度量。内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量。通常较优秀的软件设计，应尽量做到高内聚、低耦合。

（3）结构化设计方法。

结构化设计就是采用最佳可能方法，设计系统的各个组成部分及各成分之间的内部联系的技术。也就是说，结构化设计是这样一个过程，它决定用哪些方法把哪些部分联系起来，才能解决好某个具体有清楚定义的问题。

结构化设计方法的基本思想是将软件设计成由相对独立、单一功能的模块组成的结构。

2．概要设计

（1）概要设计的任务。

●设计软件系统结构；

●数据结构及数据库设计；

●编写概要设计文档；

●概要设计文档评审。

（2）面向数据流的设计方法。

在需求分析设计阶段，产生了数据流图。面向数据流的设计方法定义了一些不同的映射方法，利用这些映射方法可以把数据流图变换成结构图表示的软件结构。数据流图从系统的输入数据流到系统的输出数据流的一连串连续加工形成了一条信息流。下面首先介绍数据流图的不同类型。

数据流图的信息流可分为两种类型：变换流和事务流。相应地，数据流图有两种典型的结构形式：变换型和事务型。

面向数据流的结构化设计过程：

●确认数据流图的类型（是事务型还是变换型）；

●说明数据流的边界；

●把数据流图映射为程序结构；

●根据设计准则对产生的结构进行优化。

（3）结构化设计的准则。

大量的实践表明，以下的设计准则可以借鉴为设计的指导和对软件结构图进行优化的条件：

●提高模块独立性；

●模块规模应该适中；

●深度、宽度、扇入和扇出都应适当；

●模块的作用域应该在控制域之内；

●降低模块之间接口的复杂程度；

●设计单入口、单出口的模块；

●模块功能应该可以预测。

3．详细设计

（1）详细设计的任务。

详细设计的任务是为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。

（2）详细设计的工具。

●图形工具：程序流程图、N-S、PAD及HIPO。

●表格工具：判定表。

●语言工具：PDL（伪码）。

真题精选

从工程管理角度，软件设计一般分为两步完成，它们是（ ）。

A．概要设计与详细设计

B．数据设计与接口设计

C．软件结构设计与数据设计

D．过程设计与数据设计

【答案】 A

【解析】从工程管理角度看，软件设计分两步完成：概要设计与详细设计。概要设计将软件需求转化为软件体系结构、确定系统级接口、全局数据结构或数据库模式；详细设计确立每个模块的实现算法和局部数据结构，用适当方法表示算法和数据结构的细节。

考点15 软件测试

软件测试是保证软件质量的重要手段，其主要过程涵盖了整个软件生命周期的过程，包括需求定义阶段的需求测试、编码阶段的单元测试、集成测试以及其后的确认测试、系统测试，验证软件是否合格、能否交付用户使用等。

1．软件测试的目的及准则

（1）软件测试的目的。

软件测试是为了发现错误而执行程序的过程。

一个好的测试用例是指很可能找到迄今为止尚未发现的错误的用例；

一个成功的测试是发现了至今尚未发现的错误的测试。

（2）软件测试的准则。

鉴于软件测试的重要性，要做好软件测试，除了设计出有效的测试方案和好的测试用例，软件测试人员还需要充分理解和运用软件测试的一些基本准侧：

●所有测试都应追溯到用户需求；

●严格执行测试计划，排除测试的随意性；

●充分注意测试中的群集现象；

●程序员应避免检查自己的程序；

●穷举测试不可能实施；

●妥善保存测试计划、测试用例、出错统计和最终分析报告，为软件维护提供方便。

2．软件测试技术和方法综述

软件测试的方法是多种多样的，对于软件测试方法和技术，可以从不同角度加以分类。

若从是否需要执行被测软件的角度，可以分为静态测试和动态测试。若按照功能划分，可以分为白盒测试和黑盒测试。

（1）静态测试与动态测试。

静态测试不实际运行软件，主要通过人工进行分析，包括代码检查、静态结构分析、代码质量度量等。其中代码检查分为代码审查、代码走查、桌面检查、静态分析等具体形式。

动态测试是基于计算机的测试，是为了发现错误而执行程序的过程。设计高效、合理的测试用例是做好动态测试的关键。

测试用例就是为测试设计的数据，由测试输入数据和预期的输出结果两部分组成。测试用例的设计方法一般分为两类：黑盒测试和白盒测试。

（2）白盒测试方法与测试用例设计。

白盒测试也称结构测试或逻辑驱动测试，它根据程序的内部逻辑来设计测试用例，检查程序中的逻辑通路是否都按预定的要求正确地工作。

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

（3）黑盒测试方法与测试用例设计。

黑盒测试也称为功能测试或数据驱动测试，它根据规格说明书的功能来设计测试用例，检查程序的功能是否符合规格说明书的要求。

黑盒测试的主要诊断方法有等价类划分法、边界值分析法、错误推测法、因果图法等，主要用于软件确认测试。

3．软件测试的实施

软件测试的实施过程主要有4个步骤：单元测试、集成测试、确认测试（验收测试）和系统测试。

（1）单元测试。

单元测试也称模块测试，模块是软件设计的最小单位，单元测试是对模块进行正确性的检验，以期尽早发现各模块内部可能存在的各种错误。

（2）集成测试。

集成测试也称组装测试，它是对各模块按照设计要求组装成的程序进行测试，其主要目的是发现与接口有关的错误。

（3）确认测试。

确认测试的任务是用户根据合同进行，确定系统功能和性能是否可接受。确认测试需要用户积极参与，或者以用户为主进行。

（4）系统测试。

系统测试是将软件系统与硬件、外设或其他元素结合在一起，对整个软件系统进行测试。

系统测试的内容包括功能测试、操作测试、配置测试、性能测试、安全测试和外部接口测试等。

真题精选

下列叙述中，正确的是（ ）。

A．软件测试应该由程序开发者来完成

B．程序经调试后一般不需要再测试

C．软件维护只包括对程序代码的维护

D．以上3种说法都不对

【答案】D

【解析】程序调试的任务是诊断和改正程序中的错误。它与软件测试不同，软件测试是尽可能多地发现软件中的错误。先要发现软件的错误，然后借助于一定的调试工具去找出软件错误的具体位置。软件测试贯穿整个软件生命周期，调试主要在开发阶段。为了实现更好的测试效果，应该由独立的第三方来构造测试。软件的运行和维护是指将已交付的软件投入运行，并在运行使用中不断地维护，根据新提出的需求进行必要而且可能地扩充和删改。

考点16 程序的调试

在对程序进行了成功的测试之后将进行程序的调试。程序调试的任务是诊断和改正程序中的错误。

本节主要讲解程序调试的概念及调试的方法。

1．程序调试的基本概念

调试是成功测试之后出现的步骤，也就是说，调试是在测试发现错误之后排除错误的过程。软件测试贯穿整个软件生命期，而调试主要在开发阶段。

程序调试活动由两部分组成：

●根据错误的迹象确定程序中错误的确切性质、原因和位置；

●对程序进行修改，排除这个错误。

（1）调试的基本步骤。

①错误定位；

②修改设计和代码，以排除错误；

③进行回归测试，防止引入新的错误。

（2）调试的原则。

调试活动由对程序中错误的定性/定位和排错两部分组成，因此调试原则也从这两个方面考虑：

●确定错误的性质和位置的原则；

●修改错误的原则。

2．程序调试方法

调试的关键在于推断程序内部的错误位置及原因。从是否跟踪和执行程序的角度，类似于软件测试，分为静态调试和动态调试。静态调试主要是指通过人的思维来分析源程序代码和排错，是主要的调试手段，而动态调试是辅助静态调试的。

主要的软件调试方法有强行排错法、回溯法和原因排除法。其中，强行排错法是传统的调试方法；回溯法适合于小规模程序的排错；原因排除法是通过演绎和归纳及二分法来实现的。

真题精选

软件调试的目的是（ ）。

A．发现错误

B．更正错误

C．改善软件性能

D．验证软件的正确性

【答案】B

【解析】软件调试的目的是诊断和更正程序中的错误，更正以后还需要进行测试。

1.4 数据库设计基础

考点17 数据库系统的基本概念

1．数据、数据库、数据库管理系统、数据库系统

（1）数据。

数据（Data）是描述事物的符号记录。

（2）数据库。

数据库（DataBase, DB）是指长期存储在计算机内的、有组织的、可共享的数据集合。

（3）数据库管理系统。

数据库管理系统（DataBaseManagementSystem, DBMS）是数据库的机构，它是一个系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等。

数据库管理系统的主要类型有4种：文件管理系统、层次数据库系统、网状数据库系统和关系数据库系统，其中关系数据库系统的应用最广泛。

（4）数据库系统。

数据库系统（DataBaseSystem, DBS）是指引进数据库技术后的整个计算机系统，能实现有组织地、动态地存储大量相关数据，提供数据处理和信息资源共享的便利手段。

2．数据库系统的发展

数据管理发展至今已经经历了3个阶段：人工管理阶段、文件系统阶段和数据库系统阶段。

一般认为，未来的数据库系统应支持数据管理、对象管理和知识管理，应该具有面向对象的基本特征。在关于数据库的诸多新技术中，有3种是比较重要的，它们是面向对象数据库系统、知识库系统、关系数据库系统的扩充。

（1）面向对象数据库系统。

用面向对象方法构筑面向对象数据库模型使具有比关系数据库系统更为通用的能力。

（2）知识库系统。

用人工智能中的方法特别是用逻辑知识表示方法构筑数据模型，使模型具有特别通用的能力。

（3）关系数据库系统的扩充。

利用关系数据库作进一步扩展，使其在模型的表达能力与功能上有进一步的加强，如与网络技术相结合的Web数据库、数据仓库及嵌入式数据库等。

3．数据库系统的基本特点

数据库系统具有以下特点：数据的集成性、数据的高共享性与低冗余性、数据独立性、数据统一管理与控制。

4．数据库系统的内部机构体系

数据模式是数据库系统中数据结构的一种表示形式，具有不同的层次与结构方式。

数据库系统在其内部具有3级模式及2级映射，3级模式分别是概念模式、内模式与外模式；2级映射是外模式/概念模式的映射和概念模式/内模式的映射。3级模式与2级映射构成了数据库系统内部的抽象结构体系。

模式的3个级别层次反映了模式的3个不同环境及其不同要求，其中内模式处于最底层，它反映了数据在计算机物理结构中的实际存储形式；概念模式处于中层，它反映了设计者的数据全局逻辑要求，而外模式位于最外层，它反映了用户对数据的要求。

真题精选

【例1】下列叙述中，正确的是（ ）。

A．数据库系统是一个独立的系统，不需要操作系统的支持

B．数据库技术的根本目标是要解决数据的共享问题

C．数据库管理系统就是数据库系统

D．以上3种说法都不对

【答案】B

【解析】数据库系统是由数据库（数据）、数据库管理系统（软件）、计算机硬件、操作系统及数据库管理员组成。作为处理数据的系统，数据库技术的主要目的就是解决数据的共享问题。

【例2】在数据库系统中，用户所见的数据模式为（ ）。

A．概念模式

B．外模式

C．内模式

D．物理模式

【答案】B

【解析】概念模式是数据库系统中对全局数据逻辑结构的描述，是全体用户（应用）公共数据视图，它主要描述数据的记录类型及数据间关系，还包括数据间的语义关系等。数据库管理系统的3级模式结构由外模式、模式、内模式组成。数据库的外模式也叫做用户级数据库，是用户所看到和理解的数据库，是从概念模式导出的子模式，用户可以通过子模式描述语言来描述用户级数据库的记录，还可以利用数据语言对这些记录进行操作。内模式（或存储模式、物理模式）是指数据在数据库系统内的存储介质上的表示，是对数据的物理结构和存取方式的描述。

考点18 数据模型

1．数据模型的基本概念

数据是现实世界符号的抽象，而数据模型是数据特征的抽象。它从抽象层次上描述了系统的静态特征、动态行为和约束条件，为数据库系统的信息表示与操作提供一个抽象的框架。数据模型所描述的内容有3个部分，它们是数据结构、数据操作及数据约束。

数据模型按不同的应用层次分为3种类型，它们是概念数据模型、逻辑数据模型和物理数据模型。

目前，逻辑数据模型也有很多种，较为成熟并先后被人们大量使用过的有层次模型、网状模型、关系模型、面向对象模型等。

2.E-R模型

E-R模型（实体-联系模型）将现实世界的要求转化成实体、联系、属性等几个基本概念，以及它们之间的两种基本连接关系，并且可以用E-R图非常直观地表示出来。

E-R图提供了表示实体、属性和联系的方法。

●实体：客观存在并且可以相互区别的事物，用矩形表示，矩形框内写明实体名。

●属性：描述实体的特性，用椭圆形表示，并用无向边将其与相应的实体连接起来。

●联系：实体之间的对应关系，它反映现实世界事物之间的相互联系，用菱形表示，菱形框内写明联系名。

在现实世界中，实体之间的联系可分为3种类型：“一对一”的联系（简记为1∶1）、“一对多”的联系（简记为1∶n）、“多对多”的联系（简记为M∶N或m∶n）。

3．层次模型

层次模型是用树形结构表示实体及其之间联系的模式。在层次模型中，结点是实体，树枝是联系，从上到下是一对多的关系。

层次模型的基本结构是树形结构，自顶向下，层次分明。其缺点是：受文件系统影响大，模型受限制多，物理成分复杂，操作与使用均不理想，且不适用于表示非层次性的联系。

4．网状模型

网状模型是用网状结构表示实体及其之间联系的模型。可以说，网状模型是层次模型的扩展，可以表示多个从属关系的层次结构，并呈现一种交叉关系。

网状模型是以记录型为结点的网络，它反映现实世界中较为复杂的事物间的联系。

网状模型结构如图1.5所示。

5．关系模型

（1）关系的数据结构。

关系模型采用二维表来表示，简称表。二维表由表框架及表的元组组成。表框架是由n个命名的属性组成，n称为属性元素。每个属性都有一个取值范围，称为值域。表框架对应了关系的模式，即类型的概念。在表框架中按行可以存放数据，每行数据称为元组。

在二维表中唯一能标识元组的最小属性集称为该表的键（或码）。二维表中可能有若干个键，它们称为该表的候选码（或候选键）。从二维表的候选键中选取一个作为用户使用的键称为主键（或主码）。如表A中的某属性集是某表B的键，则称该属性集为A的外键（或外码）。

关系是由若干个不同的元组所组成的，因此关系可视为元组的集合。

（2）关系的操纵。

关系模型的数据操纵即是建立在关系上的数据操纵，一般有数据查询、增加、删除及修改4种操作。

（3）关系中的数据约束。

关系模型允许定义3类数据约束，它们是实体完整性约束、参照完整性约束和用户定义的完整性约束，其中前两种完整性约束由关系数据库系统自动支持。对于用户定义的完整性约束，则由关系数据库系统提供完整性约束语言，用户利用该语言写出约束条件，运行时由系统自动检查。

真题精选

【例1】下列说法中，正确的是（ ）。

A．为了建立一个关系，首先要构造数据的逻辑关系

B．表示关系的二维表中各元组的每个分量还可以分成若干个数据项

C．一个关系的属性名称为关系模式

D．一个关系可以包含多个二维表

【答案】A

【解析】元组已经是数据的最小单位，不可再分；关系的框架称为关系模式；关系框架与关系元组一起构成了关系，即一个关系对应一张二维表。选项A中，在建立关系前，需要先构造数据的逻辑关系是正确的。

【例2】用树形结构表示实体之间联系的模型是（ ）。

A．关系模型

B．网状模型

C．层次模型

D．以上3个都是

【答案】C

【解析】数据模型是指反映实体及其实体间联系的数据组织的结构和形式，有关系模型、网状模型和层次模型等。其中层次模型实际上是以记录型为结点构成的树，它把客观问题抽象为一个严格的、自上而下的层次关系，所以，它的基本结构是树形结构。

考点19 关系代数

1．传统的集合运算

（1）关系并运算。

若关系R和关系S具有相同的结构，则关系R和关系S的并运算记为R∪S，表示由属于R的元组或属于S的元组组成。

（2）关系交运算。

若关系R和关系S 具有相同结构，则关系R和关系S 的交运算记为R∩S，表示由既属于R的元组又属于S的元组组成。

（3）关系差运算。

若关系R和关系S具有相同的结构，则关系R和关系S的差运算记为R-S，表示由属于R的元组且不属于S的元组组成。

（4）广义笛卡儿积。

分别为n元和m元的两个关系R和S的广义笛卡儿积R×S是一个（n ×m）元组的集合。其中的两个运算对象R和S的关系可以是同类型也可以是不同类型。

2．专门的关系运算

专门的关系运算有选择、投影、连接等。

（1）选择。

从关系中找出满足给定条件元组的操作称为选择。选择的条件以逻辑表达式给出，使得逻辑表达式为真的元组将被选取。选择又称为限制。它是在关系R中选择满足给定选择条件F的诸元组，记作：

σF（R）={t|t∈R∧F（t）=′真′}

其中选择文件F是一个逻辑表达式，取逻辑值“真”或“假”。

（2）投影。

从关系模式中指定若干个属性组成新的关系称为投影。

关系R上的投影是从关系R中选择出若干属性列组成新的关系，记作：

πA（R）={t[A]|t∈R}

其中A为R中的属性列。

（3）连接。

连接也称为θ连接，它是从两个关系的笛卡儿积中选取满足条件的元组，记作：

其中，A和B分别为R和S上度数相等且可比的属性组；θ是比较运算符。

连接运算是从广义笛卡儿积R×S中选取R关系在A属性组上的值与S关系在B属性组上值满足关系θ的元组。

连接运算中有两种最为重要且常用的连接：一种是等值连接；另一种是自然连接。

θ为“=”的连接运算称为等值连接，是从关系R与关系S的广义笛卡儿积中选取A、B属性值相等的元组，则等值连接为

自然连接（Natural-join）是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且在结果中去掉重复的属性列，则自然连接可记作：

R|×|S={trts|tr∈R∧ts∈S∧tr[B] =ts[B]}

真题精选

【例1】设有以下3个关系表，如表1.2～表1.4所示。

下列操作中正确的是（ ）。

A.T=R∩S

B.T=R∪S

C.T=R×S

D.T=R/S

【答案】C

【解析】集合的并、交、差、广义笛卡儿积：设有两个关系为R和S，它们具有相同的结构，R和S的并是由属于R和S，或者同时属于R和S的所有元组组成，记作R∪S; R和S的交是由既属于R又属于S的所有元组组成，记作R∩S; R和S的差是由属于R但不属于S的所有元组组成，记作R-S；元组的前n个分量是R的一个元组，后m个分量是S的一个元组，若R有K1个元组，S有K2个元组，则R×S有K1×K2个元组，记为R×S。从表1.4中可见，关系T是关系R和关系S的简单扩充，而扩充的符号为“×”，故答案为T=R×S。

【例2】在下列关系运算中，不改变关系表中的属性个数但能减少元组个数的是（ ）。

A．并

B．交

C．投影

D．笛卡尔乘积

【答案】B

【解析】关系的基本运算有两类：传统的集合运算（并、交、差）和专门的关系运算（选择、投影、连接）。集合的并、交、差：设有两个关系为R和S，它们具有相同的结构，R和S的并是由属于R和S，或同时属于R和S的所有元组组成，记作R∪S; R和S的交是由既属于R又属于S的所有元组组成，记作R∩S; R和S的差是由属于R但不属于S的所有元组组成，记作R-S。因此，在关系运算中，不改变关系表中的属性个数但能减少元组（关系）个数的只能是集合的交。

考点20 数据库设计与管理

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

1．数据库设计概述

数据库设计的基本任务是根据用户对象的信息需求、处理需求和数据库的支持环境设计出数据模型。

数据库设计的基本思想是过程迭代和逐步求精。数据库设计的根本目标是要解决数据共享问题。

在数据库设计中有两种方法：

●面向数据的方法，是以处理信息需求为主，兼顾处理需求；

●面向过程的方法，是以处理需求为主，兼顾信息需求。其中，面向数据的方法是主流的设计方法。

目前数据库设计一般采用生命周期法，即将整个数据库应用系统的开发分解成目标独立的若干阶段。它们是需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段和进一步修改阶段。

2．数据库设计的需求分析

需求收集和分析是数据库设计的第一阶段，这一阶段收集到的基础数据和一组数据流图是下一步设计概念结构的基础。需求分析的主要工作有绘制数据流图、数据分析、功能分析，确定功能处理模块和数据之间的关系。

需求分析和表达经常采用的方法有结构化分析方法和面向对象的方法。结构化分析方法用自顶向下、逐层分解的方式分析系统。数据流图表达了数据和处理过程的关系，数据字典对系统中数据的详尽描述，是各类数据属性的清单。

数据字典是各类数据描述的集合，它通常包括5个部分，即数据项，是数据的最小单位；数据结构，是若干数据项有意义的集合；数据流，可以是数据项，也可以是数据结构，表示某一处理过程的输入和输出；数据存储，处理过程中存取的数据，常常是手工凭证、手工文档或计算机文件；处理过程。

数据字典是在需求分析阶段建立的，在数据库设计过程中不断修改、充实、完善的。

3．数据库的概念设计

（1）数据库概念设计。

数据库概念设计的目的是分析数据间内在的语义关联，在此基础上建立一个数据的抽象模型。

数据库概念设计的方法主要有两种：集中式模式设计法和视图集成设计法。

（2）数据库概念设计的过程。

使用E-R模型与视图集成法进行设计时，需要按以下步骤进行：

①选择局部应用；

②视图设计；

③视图集成。

4．数据库的逻辑设计

（1）从E-R图向关系模式转换。

从E-R图到关系模式的转换是比较直接的，实体与联系都可以表示成关系，在E-R图中属性也可转换成关系的属性。实体集也可转换成关系，见表1.5。

如联系类型为1∶1，则每个实体的码均是该关系的候选码。

如联系类型为1∶N，则关系的码为N端实体的码。

如联系类型为M∶N，则关系的码为诸实体的组合，具有相同码的关系模式可合并。

（2）逻辑模式规范化。

在关系数据库设计中存在的问题有数据冗余、插入异常、删除异常和更新异常。

数据库规范化的目的在于消除数据冗余和插入/删除/更新异常。规范化理论有4种范式，从第一范式到第四范式的规范化程度逐渐升高。

（3）关系视图设计。

关系视图是在关系模式的基础上所设计的直接面向操作用户的视图，它可以根据用户需求随时创建。

5．数据库的物理设计

（1）数据库物理设计的概念。

数据库在物理设备上的存储结构与存取方法称为数据库的物理结构，它依赖于给定的计算机系统。为一个给定的逻辑模型选取一个最适合应用要求的物理结构的过程，就是数据库的物理设计。

（2）数据库物理设计的主要目标。

数据库物理设计的主要目标是对数据库内部物理结构作调整并选择合理的存取路径，以提高数据库访问速度及有效利用存储空间。

6．数据库管理

数据库是一种共享资源，它需要维护与管理，这种工作称为数据库管理，而实施此项管理的人称为数据库管理员（DBA）。

数据库管理包括数据库的建立、数据库的调整、数据库的重组、数据库安全性与完整性控制、数据库故障恢复和数据库监控。

真题精选

在E-R图中，用来表示实体之间联系的图形是（ ）。

A．矩形

B．椭圆形

C．菱形

D．平行四边形

【答案】 C

【解析】E-R图中规定：用矩形表示实体，椭圆形表示实体属性，菱形表示实体关系。

1.5 综合自测

选择题

1．对下列二叉树进行中序遍历的结果是（ ）。

A.ACBDFEG

B.ACBDFGE

C.ABDCGEF

D.FCADBEG

2．按照“后进先出”原则组织数据的数据结构是（ ）。

A．队列

B．栈

C．双向链表

D．二叉树

3．下列叙述中，正确的是（ ）。

A．一个逻辑数据结构只能有一种存储结构

B．数据的逻辑结构属于线性结构，存储结构属于非线性结构

C．一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率

D．一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率

4．下面选项中，不属于面向对象程序设计特征的是（ ）。

A．继承性

B．多态性

C．类比性

D．封装性

5．下列叙述中，正确的是（ ）。

A．软件交付使用后还需要进行维护

B．软件一旦交付使用就不需要再进行维护

C．软件交付使用后其生命周期就结束

D．软件维护是指修复程序中被破坏的指令

6．下列描述中，正确的是（ ）。

A．软件工程只是解决软件项目的管理问题

B．软件工程主要解决软件产品的生产率问题

C．软件工程的主要思想是强调在软件开发过程中需要应用工程化原则

D．软件工程只是解决软件开发中的技术问题

7．在软件设计中，不属于过程设计工具的是（ ）。

A.PDL（过程设计语言）

B.PAD图

C.N-S图

D.DFD图

8．数据库设计的4个阶段是需求分析、概念设计、逻辑设计和（ ）。

A．编码设计

B．测试阶段

C．运行阶段

D．物理设计

9．数据库技术的根本目标是要解决数据的（ ）。

A．存储问题

B．共享问题

C．安全问题

D．保护问题

10．数据库独立性是数据库技术的重要特点之一。所谓数据独立性是指（ ）。

A．数据与程序独立存放

B．不同的数据被存放在不同的文件中

C．不同的数据只能被对应的应用程序所使用

D．以上3种说法都不对

11．下列关于栈的叙述，正确的是（ ）。

A．栈是非线性结构

B．栈是一种树状结构

C．栈具有“先进先出”的特征

D．栈具有“后进先出”的特征

12．结构化程序设计所规定的3种基本控制结构是（ ）。

A．输入、处理、输出

B．树型、网型、环型

C．顺序、选择、循环

D．主程序、子程序、函数

13．下列叙述，正确的是（ ）。

A．算法的效率只与问题的规模有关，而与数据的存储结构无关

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

C．数据的逻辑结构与存储结构是一一对应的

D．算法的时间复杂度与空间复杂度一定相关

14．在结构化程序设计中，模块划分的原则是（ ）。

A．各模块应包括尽量多的功能

B．各模块的规模尽量大

C．各模块之间的联系应尽量紧密

D．模块内具有高内聚度、模块间具有低耦合度

15．某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为（ ）。

A.n+1

B.n-1

C.2n

D.n/2