二级公共基础知识考点分析

二级公共基础知识考点分析

第1章数据结构与算法

1.1算法和数据结构的基本概念

1.算法

(1)算法的基本概念

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

A.算法的基本特征：①可行性；②确定性；③有穷性；④拥有足够的情报。

B.算法的基本要素：①算法中对数据的运算和操作：基本的运算和操作包括算术运算、

逻辑运算、关系运算和数据传输；②算法的控制结构：基本的控制结构包括顺序结构、选

择结构、循环结构。

C.算法设计的基本方法：①列举法；②归纳法；③递推；④递归；⑤减半递推技术；⑥

回溯法。

(2)算法的复杂度

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

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

的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数。即：算法的工

作量=f(n)其中n是问题的规模。

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

储空间包括算法程序所占的空间、输入的初始数据所占用的存储空间以及算法执行过程中

所需要的额外空间。

2.数据结构的基本概念

数据结构作为计算机的一门学科，主要研究和讨论以下三个方面的问题：

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

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

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

(1)数据结构的定义

①数据结构是指相互有关联的数据元素的集合。

②数据处理是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、

更改等运算，也包括对数据元素进行分析。

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

④数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物

理结构)。常用的存储结构有顺序、链接、索引等存储结构。

(2)数据结构的图形表示

在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的

方框表示，一般称之为数据结点，简称结点；为了进一步表示各数据元素之间的前后件关

系，对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。

(3)线性结构与非线性结构

如果一个非空的数据结构满足下列两个条件：

①有且只有T根结点；

②每一个结点最多有一个前件,也最多有一个后件。

则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称为非线性结构。

1.2线性表和线性链表

L线性表

(1)线性表的基本概念

线性表(LinearList)是最简单、最常用的一种数据结构。

线性表是由n(nNO)个数据元素为为，…，a“组成的一个有限序列，表中的每一个数据

元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。

(2)线性表的顺序存储结构

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

①线性表中所有元素所占的存储空间是连续的；

②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

(3)顺序表的插入运算

在线性表采用顺序存储结构时，如果插入运算在线性表的末尾进行，即在第n个元素

之后(可以认为是在第n+1个元素之前)插入新元素，则只要在表的末尾增加一个元素

即可，不需要移动表中的元素；如果要在线性表的第1个元素之前插入一个新元素，则需

要移动表中所有的元素。

(4)顺序表的删除运算

在线性表采用顺序存储结构时，如果删除运算在线性表的末尾进行，即删除第n个元

素，则不需要移动表中的元素；如果要删除线性表中的第1个元素，则需要移动表中所有

的元素。

2.线性链表

(1)线性链表的基本概念

在线性链表中，各健元素之间的前后件关系是由各结点的指针域来指示的，指向线

性表中第一个结点的指针HEAD称为头指针，当HEAD=NULL(或0)时称为空表。

(2)线性链表的基本运算

线性链表的运算主要有：线性链表的插入、删除、直找、合并、分解、逆转、复制、排

序等。

①在线性链表中查找指定元素

在非空线性链表中寻找包含指定元素值x的前一个结点p的基本方法如下：从头指针指

向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为x为

止。当线性链表中不存在包含元素x的结点时，则找到的p为线性链表中的最后一个结点

号。

②线性链表的插入

为了在线性链表中插入一个新元素，首先要给该元素分配一个新结点，它可以从可利用

栈中取得。然后1各存放新元素值的结点链接到线性链表中指定的位置。

③线性链表的删除

为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，然后

将要删除结点放回到可利用栈。

(3)循环链表及其基本运算

①在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指

向线性表的第一个元素的结点。循环链表的头指针指向表头结点。

②循环链表中最后一个结点的指针域不是空，而是指向表头结点。

1.3栈和队列

1.栈及其基本运算

栈是一种特殊的线性表，在这种线性表的结构中，一端是封闭的，不允许进行插入与删

除元素；另一端是开口的，允许插入与删除元素。在顺序存储结构下，对这种类型线性表

的插入与删除运算是不需要移动表中其他数据元素的。

在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。栈

是按照''先进后出"(FILO—FirstInLastOut)或''后进先出"(LIFO-LastInFirstOut)的

原则组织数据的。栈的基本运算有三种：入栈、退栈与读栈顶元素。

2.队列及其基本运算

(1)队列(queue)是指允许在一端进行插入、而在另一端进行删除的线性表。队列又

称为''先进先出”(FIFO-FirstInFirstOut)或''后进后出”(LILO-LastInLastOut)的线

性表。

(2)循环队列及其运算

在实际应用中，队列的II页序存储结构一般采用循环队列的形式。所谓循环队列，就是将

队列存储空间的最后一H立置绕到第一个位置，形成逻辑上的环状空间，供队列循环使

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

1.4树与二叉树

1.树的基本概念

树（tree）是一种简单的非线性结构。在树这种数据结构中，所有数据元素之间的关系

具有明显的层次特性。

2.二叉树的定义及其存储结构

（1）二叉树的定义

二叉树具有以下两个特点：

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

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

（2）二叉树的存储结构

在计算机中，二叉树通常采用链式存储结构。在二叉树中，由于每一个元素可以有两个

后件（即两个子结点），因此，用于存储二叉树的存储结点的指针域有两个：一个用于指

向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存

储地址，称为右指针域。

3.二叉树的遍历

二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为：

①前序遍历（DLR）

首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍

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

②中序遍历（LDR）

首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍

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

③后序遍历（LRD）

首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍

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

1.5查找技术和排序技术

1.查找技术

查找是数据处理领域中的一个重要内容，查找的效率将直接影响到数据处理的效率。

(1)顺序查找

在进行顺序查找过程中，如果线性表中的第一个元素就是被查找元素，则只需做一次比

较就查找成功，查找效率最高；但如果被查的元素是线性表中的最后一个元素，或者被查

元素根本不在线性表中，则为了查找这个元素需要与线性表中所有的元素进行比较，这是

顺序查找的最坏情况。在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要

与线性表中一半的元素进行比较。

(2)二分法查找

二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非

递减排列。对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较1。管n次，

而顺序查找需要比较n次。

2.排序技术

(1)交换类排序法

交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快

速排序法都属于交换类的排序方法。假设线性表的长度为n,则在最坏情况下，冒泡排序

需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-

1)/2.在快速排序过程中，随着对各子表不断地进行分割，划分出的子表会越来越多，但

一次又只能对一个子表进行再分割处理，需要将暂时不分割的子表记忆起来，这就要用一

个栈来实现。

(2)插入类排序法

插入排序是指将无序序列中的各元素依次插入到已经有序的线性表中。在简单插入排序

法中，每一次匕瞰后最多移掉一个逆序，因此,这种排序方法的效率与冒泡排序法相同。

在最坏情况下，简单插入排序需要n(n-l)/2次比较。

(3)选择类排序法

选择排序法的基本思想是扫描整个线性表，从中选出最小的元素，将它交换到表的最前

面(这是它应有的位置)；然后对剩下的子表采用同样的方法，直到子表空为止。简单选

择排序法在最坏情况下需要比较n(n-l)/2次。

第2章程序设计基础

2.1程序设计方法与风格

程序设计是一门技术，需要相应的理论、技术、方法和工具来支持。就程序设计方法和

技术的发展而言,主要经过了结构化程序设计和面向对象的程序设计阶段。程序设计风格

是指编写程序时所表现出的特点、习惯和逻辑思路。著名的'清晰第一，效率第二”的论点

已成为当今主导的程序设计风格。要形成良好的程序设计风格，应注重和考虑这些因素：

①源程序文档化；②数据说明的方法；③语句的结构；④输入和输出。

2.2结构化般削

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

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

goto语句。

2.结构化程序设计的基本结构与方法的应用

结构化程序设计的三种基本结构分别是：顺序结构、选择结构和循环结构。

在结构化程序设计的具体实施中，要注意把握如下要素：①使用程序设计语言中的顺

序、选择、循环等有限的控制结构表示程序的控制逻辑；②选用的控制结构只准许有一

个入口和一个出口；③程序语句组成容易识别的块,每块只有一个入口和一个出口；④复

杂结构应该用嵌套的基本控制结构进行组合嵌套来实现；⑤语言中所没有的控制结构，应

该采用前后一致的方法来模拟；⑥严格控制got。语句的使用。

2.3面向对象的程序设计

1.关于面向对象方法

面向对象方法的优点：①与人类习惯的思维方法一致；②稳定性好；③可重用性好；④

易于开发大型软件产品；⑤可维护性好。

2.面向对象方法的基本概念

①面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构

成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。通

常把对象的操作称为方法或服务。②属性即对象所包含的信息，它在设计对象时确定，一

般只能通过执行对象的操作来改变。③对象的基本特征有：a.标识惟一性;b.分类性；c.

多态性；d.封装性;e.模块独立性好。④继承是使用已有的类定义作为基础建立新类的定

义技术。广义地说，继承是指能够直接获得已有的性质和特征，而不必重复定义它们。

继承分为单继承与多重继承。⑤多态性是指子类对象可以像父类对象那样使用，同样的消

息既可以发送给父类对象也可以发送给子类对象。

第3章软件工程基础

3.1软件工程基本概念

1.软件定义与软件危机

(1)软件的定义：软件是与计算机操作相关的计算机程序、规程、规则，以及可能有

的文件、文档及数据。软件的三个要素：程序、数据和文档。

(2)软件分类：软件按功能可分为应用软件、系统软件和支撑软件(或工具软件)三

大类。

(3)软件危机的定义：软件危机是泛指在计算机软件的开发和维护过程中所遇到的一

系列严重问题。

2.软件工程定义与软件生命周期

(1)软件工程

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

实践标准和工序。软件工程的三个要素：方法、工具和过程。

(2)软件生命周期

定义：软件生命周期就是软件产品从提出、实现、使用维护到停止使用退役的全过程。

软件生命周期包括软件定义、软件开发及软件维护三个阶段。软件定义阶段的任务包括

可行性研究与计划制定、需求分析；软件开发阶段的任务包括概要设计、详细设计、软件

实现、软件测试；软件维护的任务包括软件的运行、维护和退役。

3.软件开发工具与软件开发环境

(1)软件开发工具：软件开发工具的发展是从单项工具的开发逐步向集成工具发展

的，软件开发工具为软件工程方法提供了自动的或半自动的软件支撑环境。

(2)软件开发环境：软件开发环境或称软件工程环境是全面支持软件开发全过程的软

件工具集合。这些软件工具按照一定的方法或模式组合起来，支持软件生命周期内的各个

阶段和各项任务的完成。

3.2结构化分析和设计方法

1.结构化分析方法

(1)关于结构化分析方法

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

工具有数据流图(DFD)、数据字典(DD)、判定树和判定表。其中最重要的工具是数据

流图。

(2)结构化分析的常用工具

①数据流图是描述数据处理过程的工具，是通过对需求的理解构造出逻辑模型的图形表

示,它高妾支持系统的功能建模。

②数据字典是结构化分析方法的核心。数据字典是对所有与系统相关的数据元素的一个

有组织的列表，以及精确的、严格的定义，使得用户和系统分析员对于输入、输出、存储

成分和中间计算结果有共同的理解。

（3）软件需求规格说明书

软件需求规格说明书（SRS）是需求分析阶段的最后结果,是软件开发中的重要文档之

O

①软件需求规格说明书有以下几个作用：1）便于用户、开发人员进行理解和交流；

2）反映出用户问题的结构，可以作为软件开发工作的基础和依据；3）作为确认测试和验

收的依据。

②软件需求规格说明书的内容：包括概述、数据描述、功能描述、性能描述、参考文献

目录和附录。

③软件需求规格说明书的特点：软件需求规格说明书具有正确性、无歧义性、完整性、

可验证性、一致性、可理解性、可修改性和可追踪性等特点。

2.结构化设计方法

（1）软件设计的基本概念

①软件设计的基础

软件设计是软件工程的重要阶段，是一个把软件需求转换为软件表示的过程。软件设计

的基础目标是用比较抽象概括的方式确定目标系统如何完成预定的任务，即软件设计是确

定系统的物理模型。

软件设计的内容：从技术观点看，软件设计包括结构设计、数据设计、接口设出口过程

设计。其中结构设计是定义软件系统各主要部件之间的关系。数据设计是将分析时创建的

模型转化为数据结构的定义。接口设计是描述软件内部、软件和协作系统之间以及软件与

人之间如何通信。过程设计是把系统结构部件转换成软件的过程性描述。

软件设计的一般过程是：软件设计是一个迭代的过程；先进行高层次的结构设计；后进

行低层次的过程设计；穿插进行数据设计和接口设计。

②软件设计的基本原理

软件设计遵循软件工程的基本目标和原则。

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

构。为了提高模块的独立性，应该尽量提高模块的内聚性，降低模块间的耦合性。

（2）概要设计

①概要削的瞄

概要设计的基本任务：设计软件系统结构、确定数据结构及数据库设计、编写概要设计

文档、进行概要设计文档评审。软件结构设计工具——结构图（SC）,也称为程序结构

图。结构图是描述软件结构的图形工具。

软件设计的准则：a才是高模块独立性；b.模块规模适中；c.深度、宽度、扇出和扇入适

当；d.使模块的作用域在该模块的控制域内；e.应减少模块的接口和界面的复杂性；f.设

计成单入口、单出口的模块；g.设计功能可预测的模块。

②详细设计

详细设计的任务：为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种

选定的表达工具表示算法和数据结构的细节。

过程设计的任务：对每个模块规定的功能以及算法的设计，给出适当的算法描述。

常见的过程设计工具有：

图形工具：程序流程图，N-S,PAD,HIP0o

表格工具：判定表。

语言工具：PDL（伪码）。

3.3软件测试及程序的调试

1.软件测试

软件测试是保证软件质量的重要手段，其主要过程涵盖了整个软件生命期的过程，包括

需求定义阶段的需求测试、编码阶段的单元测试、集成测试以及后期的确认测试、系统测

试、验证软件是否合格、能否交付用户使用等。

(1)软件测试的目的

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

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

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

(2)软件测试的准则

软件测试过程中应遵循以下准则：①所有测试都应追溯到需求；②严格执行测试计划，

排除测试的随意性；③充分注意测试中的群集现象；④程序员应避免检查自己的程序；⑤

穷举测试不可能；⑥妥善保存测试计划、测试用例、出错统计和最终分析报告。

(3)软件测试技术与方法综述

①软件测试从是否要执行被测试软件的角度可以分为静态测试和动态测试。

②软件测试按照功能划分可分为白盒测试和黑盒测试方法。

白盒测试：白盒测试又称结构测试或逻辑驱动测试，是根据软件产品的内部工作过程，

检查内部成分，以确认每种内部操作符合设计规范要求。

白盒测试的基本原则：1)保证所测模块中每一独立路径至少执行一次；2)保证所测

模块所有判断的每一分支至少执行一次；3)保证所测模块每一循环都在边界条件和一般

条件下至少各执行一次；4)验证所有内部数据结构的有效性。

白盒测试的主要方法：1)逻辑覆盖测试方法：逻辑覆盖是泛指一系列以程序内部的逻

辑结构为基础的测试用例设计技术。逻辑覆盖测试方法有语句覆盖、路径覆盖、判定覆

盖、条件覆盖以及判断-条件覆盖。2)基本路径测试：基本路径测试的思想和步骤是，根

据软件过程性描述中的控制流程确定程序的环路复杂性度量，用此度量定义基本路径集

合，并由此导出一组测试用例对每一条独立执行路径进行测试。

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

需求进行测试和验证。

黑盒测试的方法：1）等价类划分法：将程序的所有可能的输入数据划分成若干部分

（即若干等价类），然后从每个等价类中选取数据作为测试用例。2）边界值分析法：边

界分析法是对各种输入、输出范围的边界情况设计测试用例的方法。3）错误推测法：靠

经验和直觉推测程序中可能存在的各种错误，从而有针对性地编写检查这些错误的例子的

方法。

（4）软件测试的实施

软件测试过程一般按4个步骤进行，即单元测试、集成测试、验收测试（确认测试）和

系统测试。

①单元测试：单元测试是对软件设计的最〃弹位——模块进行正确性检验的测试。主要

目的是发现各模块内部可能诙的各种曲吴。

②集成测试：集成测试是把模块在按照设计要求组装起来的同时进行测试，主要目的是

发现与接口有关的错误。

③确认测试：确认测试的任务是验证软件的功能和性能及其他特性是否满足了需求规格

说明中确定的各种需求，以及软件配置是否完全、正确。

④系统测试：系统测试是将通过测试确认的软件，作为整个基于计算机系统的一个元

素，与计算机硬件、外设、支持软件、数据和人员等其他系统元素组合在一起，在实际运

行环境下对计算机系统进行一系列的集成测试和确认测试。

2.程序的调试

程序调试的任务是诊断和改正程序中的错误，它与软件测试不同，软件测试是尽可能多

地发现软件中的错误。软件测试贯穿整个软件生命期，调试主要在开发阶段。

（1）基本概念

①程序调试的基本步骤：第1步：错误定位；第2步：修改设计和代码，以排除错

误；第3步：进行回归测试，防止引进新的错误。

②程序调试的原则

确定错误的性质和位置时应该注意的事项有：分析思考与错误征兆相关的信息；避开死

胡同；只把调试工具当作辅助手段来用；避免用试探法，最多只能把它当作最后手段。

修改错误时应遵循如下原则：在出现错误的地方，还可能有别的错误；不应只修改了错

误的征兆或表现而没有修改错误本身；注意修正一个错误的同时有可能会引入新的错误；

修改错误的过程将迫使人们暂时回到程序设计阶段；修改源代码程序，不要改变目标代

码。

（2）软件调试方法

主要的软件调试方法有强行排错法、回溯法和原因排除法。其中强行排错法是传统的调

试方法，回溯法适合于小规模程序的排错，原因排除法是通过演绎和归纳，以及二分法来

实现的。

第4章数据库设计基础

4.1数据库系统的基本概念

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

（1）数据（Data）:数据实际上就是描述事物的符号记录。数据分为临时性数据和永

久性数据。

（2）数据库（DB）:数据库是数据的集合，它具有统一的结构形式并存放于统一的存

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

（3）数据库管理系统（DBMS）:数据库管理系统是数据库的机构，它是一种系统软

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

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

（4）数据库管理员（DBA）:对数据库进行规划、维护、监视等的专业人员。主要工

作：数据库设计、数据库维护和改善系统性能，提高系统效率。

（5）数据库系统（DBS）:由数据库（数据）、数据库管理系统（软件）、数据库管

理员（人员）、系统平台之一（硬件平台）和系统平台之二（软件平台）组成。

（6）数据库应用系统（DBAS）:数据库应用系统是数据库系统再加上应用软件及应用

界面这三者所组成。

2.数据库系统的发展

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

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

(1)数据的集成性。(2)数据的高共享性与低冗余性。(3)数据独立性。(4)数

据统一管理与控制。

4.数据库系统的内部结构体系

数据库系统在其内部具有三级模式及二级映射，三级模式分别是概念级模式、内部级模

式与外部级模式，二级映射则分别是概念级到内部级的映射以及外部级到概念级的映射。

这种三级模式与二级映射构成了数据库系统内部的抽象结构体系。

(1)数据库系统的三级模式：数据库系统提供概念模式、外模式和内模式三级数据模

式。

(2)数据库的两级映射：数据库的两级映射是指概念模式到内模式的映射和外模式到

概念模式的映射。

4.2数据模型、关系代数及数据库设计与管理

1.数据模型

(1)数据模型的基本概念

数据模型是数据特征的抽象，它从抽象层次上描述了系统的静态特征、动态行为和约束

条件，为数据库系统的信息表示与操作提供了一个抽象的框架。数据模型所描述的内容有

三个部分：数据结构、数据操作和数据约束。数据模型按不同的应用层次分为：概念数据

模型、逻辑数据模型和物理数据模型三种。

(2)E-R模型

①E-R模型的3个基本概念

实体：现实世界中的事物可以抽象为实体，实体是概念世界中的基本单位，它们是客观

存在的且又能够相互区分的事物。将具有共性的实体组织成一个集合，称之为实体集。

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

联系：现实世界中事物间的关联称为联系。

E-R模型由实体、联系、属性三者组成。

实体与实体之间的联系：一对一（1：1）、一对多（1：m）和多对多（m：n）三种。

②E-R模型三个基本概念之间的联接关系

实体集（联系）与属性间的联接关系：实体以及它的所有属性构成了实体的一个完整描

述。实体和隶属于它的属性之间可以建立这么一层联接关系。实体有型和值之别，一个实

体的所有属性构成了这个实体的型，实体中属性值的集合（即元组）则构成了这个实体的

值。相同型的实体构成实体集。

实体（集）与联系间的联接关系：实体集间可以通过联系建立联接关系。

③E-R模型的图示法

E-R模型中用矩形表示实体集，用椭圆表示属性，用菱形表示联系，用无向线段表示实

体集（联系）与属性、实体集与联系间的联接关系。

（3）基本的数据模型

数据发展过程中产生过三种基本的数据模型：层次模型、网状模型和关系模型。其中层

次模型的基本结构是树形结构。网状模型的基本结构是一个不加任何限制条件的无向图。

关系模型的基本结构是一张二维表。

（4）关系模型

①关系的数据结构

关系模型采用二维表来表示。二维表由表框架和表的元组组成。表框架由多个命名的表

属性组成。每个属性有一个取值范围称为值域。二维表中的每一行数据称为元组。

键（或码）：在二维表中能唯一标识元组的最小属性集。

候选键（或候选码）：一个二维表中所有的键（或码）。

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

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

②关系操纵

关系模型的数据操纵是建立在关系上的数据操纵，一般有数据查询(基本单位是元组分

量)、数据删除(基本单位是元组)、数据插入(基本单位是元组)和数据修改(基本单

位是元组分量)四种操作。

③关系中的数据约束

关系模型中提供实体完整性约束、参照完整性约束和用户完整性约束三种数据约束。

2.关系代数

(1)关系模型的基本操作

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

有序组的集合。关系模型有插入、删除、修改和查询4种操作。

(2)关系模型的基本运算

由于操作是对关系的运算，而关系是有序组的集合，因此可以将操作看成是集合的运

算。

①插入：设需在关系R中插入若干个元组，待插入的元组组成关系R',则插入操作可

用集合''并”运算表示为：RUR'。

②删除：设需在关系R中删除若干个元组，待删除的元组组成关系R',则删除操作可

用集合''差"运算表示为：R-R；

③修改：修改关系R内的元组内容可用下面的方法实现：a.设待修改的元组构成关系

R',则先做删除操作，得R-R'；b.设修改后的元组构成关系R",此时将其插入即得到结果

(R-R()UR"

④查询：用于查询的3个操作无法用传统的集合运算表示，需引入一些新的运算。

A.投影(Projection)运算：对于关系内的域指定可引入新的运算叫投影运算。投影运

算是一个一元运算，一个关系通过投影运算后仍为一个关系R'o

B.选择(Selection)运算：选择运算也是一个一元运算,关系R通过选择运算(并由该

运算给出所选择的逻辑条件)后仍为一个关系。这个关系是由R中那些满足逻辑条件的元

组所组成。设关系的逻辑条件为F,则R满足F的选择运算可写为：oF(R)o

逻辑条件F是一个逻辑表达式，它由下面的规则组成：

它可以具有aep的形式，其中a,B是域(变量)或常量，但a,B又不能同为常量，0

是比较符，它可以是<,>,4,2,=及人A6B叫基本逻辑条件。由若干个基本逻辑条件

经逻辑运算得到，逻辑运算为人(并且)、v(或者)及~(否)构成，称为复合逻辑条

件。

C.笛卡尔积(CartesianProduct)运算：对于两个关系的合并操作可以用笛卡尔积表

示。设有n元关系R及m元关系S,它们分别有p、q个元组，则关系R与S经笛卡尔积

记为RxS,该关系是一个n+m元关系，元组个数是pxq,由R与S的有序组组合而成。

(3)关系代数中的扩充运算

①交运算：关系R和S经交运算后所得到的关系是由那些既在R内、又在S内的有序

组所组成，记为：RCIS。

②除运算：如果将笛卡尔积运算看作是乘运算，那么除运算就是它的逆运算。当关系

T=RxS时，则可将除运算写为：丁爪=$或丁保=$其中,S称为T除以R的商。

③连接运算：连接运算又可称为仇连接运算，这是一种二元运算，通过它可以将两个

关系合并成一个关系。

3.数据库设计与管理

(1)数据库设计概述

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

出数据模式。在数据库设计中有两种方法：一种是以信息需求为主，兼顾处理需求的面向

数据的方法；另一种是以处理需求为主，兼顾信息需求的面向过程的方法。

数据库设计目前一般采用生命周期法，将数据库应用系统的开发分解为需求分析阶段、概

念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段和进一步修

改阶段来完成。在数据库设计中主要采用需求分析、概念设计、逻辑设计、物理设计四个

阶段。

(2)数据库设计的需求分析

需求分析阶段的任务是通过详细调查现实世界要处理的对象，充分了解原系统的工作概

况，明确用户的各种需求，然后在此基础上确定新系统的功能。需求分析调查的是用户对

数据库的如下要求：①信息要求：指用户需要从数据库中获得信息的内容与性质；②处理

要求：指用户要完成什么处理功能，对处理的响应时间有何要求，处理的方式是批处理还

是联机处理；③安全性和完整性的要求。

在实际开展需求分析阶段工作时，有两点需要特别注意：

第一在需求分析阶段，一个重要而困难的任务就是收集将来应用所涉及的数据。

第二必须强调用户的参与，这是数据库应用系统设计的特点。

（3）数据库概念设计

①数据库概念设计概述

数据库概念设计的方法有以下两种：a.集中式模式设计法：集中式模式设计法是一种统

一的模式设计方法，它根据需求由一个统一机构或人员设计一个综合的全局模式；b.视图

集成设计法：这种方法是将一个单位分解成若干个部分，先对每个部分作局部模式设计，

建立各个部分的视图，然后以各个视图为基础进行集成。

②数据库概念设计的过程

数据库概念设计的过程分为以下三个步骤：

第1步：选择局部应用；

第2步：视图设计：一般有三种设计顺序：自顶向下（从一般到具体）、自底向上（从

具体到一般）、由内向外（从最基本和最明显的对象扩充到非一般、不明显的其他对

象）；

第3步：视图集成：将所有的局部视图统一与合并成一个完整的数据模式。

（4）数据库的逻辑设计

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

数据库逻辑设计的主要工作是将E-R图转换成指定RDBMS中的关系模式。实体集也可以

转换关系。

由E-R图转换成关系模型时会遇到以下一些问题：a.命名与属性域的处理；b.非原子属

性的处理；c.联系的转换。

②逻辑模式规范化及调整、实现

a.规范化：在逻辑设计中还需对关系做规范化验证；b.RDBMS:对逻辑模式进行调整

以满足RDBMS的性能、存储空间等要求，同时对模式做满足RDBMS限制条件的修改，

它们包括如下内容：调整性能以减少连接运算；调整关系大小，使每个关系数量保持在合

理水平，从而提高存取效率；尽量采用快照，若在应用中仅需某固定时刻的值，此时可用

快照将某时刻值固定，并定期更新，此种方法可以显著提高查询速度。

③关系视图削

关系视图能提供数据逻辑独立性，适应用户对数据的不同需求并且具有一定的数据保密

功能。

(5)数据库的物理设计

数据库物理设计的主要目标是对数据库内部物理结构作调整并选择合理的存取路径，以

提高数据库访问速度及有效利用存储空间。

(6)数据库管理

①数据库的建立。包括两部分的内容：数据模式的建立和数据加载。

②数据库的调整。在数据库建立并经一段时间运行后往往会产生一些不适应的情况，此

时需要对其作出调整。

③数据库的重组。数据库在经过一定的时间运行后，其性能会逐步下降，下降的原因主

要是由于不断的修改、删除和插入所造成的，这时需要对数据库进行重新整理，重新调整

存储空间，这种工作叫数据库的重组。

④数据库安全性控制与完整性控制。数据库安全性控制和完整性控制的目的是保证数据

库数据的正确性、一致性，不被没有授权的用户访问和修改。

⑤数据库的故障恢复。一旦数据库中的数据遭到破坏，需要及时进行恢复。

⑥数据库监控。DBA需随时观察数据库的动态变化，并在发生错误、故障或产生不适

应情况时随时采取措施；同时还需要监视数据库的性能变化，在必要时对数据库进行调

整。

第5章函数考点归纳

5.1函数定义

在标准C++中，函数的定义形式为：

<返回类型><函数名>（<形参列表>）

<函数体>

）

<函数名>一般是标识符，一个程序只有一个main函数，其他函数名可随意取（当然，

必须避免使用C++的关键字），好的程序设计风格要求函数名最好是取有助于记忆的名

字，如getchar函数，通过函数的名字可以知道函数的功能，这无疑会增加程序的可读

性。

（形参列表〉是由逗号分隔的，分别说明函数的各个参数。形参将在函数被调用时从调

用函数那里获得数据。在C++中，函数形参列表可以为空，即一个函数可以没有参数。

但即使函数形参列表为空，括起函数参数的一对圆括号也不允许省略。

〈返回类型〉又称函数类型,表示一个函数所计算（或运行）的结果值的类型。如果一个

函数没有结果值，如函数仅用来更新（或设置）变量值、显示信息等，则该函数返回类型为

void类型。一个没有返回值的函数类似于一些程序语言（如pascal语言）中的过程

（procedure）,

由一对花括号括起来的<函数体>是语句的序列，它定义了函数应执行的具体操作。

需要注意的是，C++不允许函数定义嵌套，即在一个函数体内不能包含有其他函数的

定义。

5.2函数调用

C++中函数调用的一般形式为：

〈函数名〉（〈实参表〉）

当调用一个函数时，其实参的个数、类型及排列次序必须与函数定义时的形参相一致，

也就是说实参与形参应该一对一地匹配。当函数定义时没有形参，则函数调用时，(实参

表》亦为空。

依据对函数返回值的使用方式，函数的调用方法可分为以下几种：

(1)语句调用，这通常用于不带返回值的函数。这种情况下，被调用函数作为一个独立

的语句出现在程序中。

(2)表达式调用。将被调用函数作为表达式的一部分来进行调用。它适用于被调用函数

带有返回值的情况。

(3)参数调用。被调用函数作为另一个函数的一个参数进行调用。

5.3函数原型

在C++中，函数在使用之前要预先声明。这种声明在标准C++中称为函数原型

(functionprototype),函数原型给出了函数名、返回类型以及在调用函数时必须提供的参

数的个数和类型。函数原型的语法为：

〈返回类型〉〈函数名〉((形参列表＞)；

(注意在函数原型后要有分号)

实际上函数原型说明有两种形式：

(1)直接使用函数定义的头部，并在后面加上一个分号。

(2)在函数原型说明中省略参数列表中的形参变量名，仅给出函数名、函数类型、参数

个数及次序。

注意：在C++中，在调用任何函数之前，必须确保它已有原型说明。函数原型说明通

常放在程序文件的头部，以使得该文件中所有函数都能调用它们。实际上，标准函数的原

型说明放在了相应的头文件中，这也是为什么在调用标准函数时必须要包含相应的头文件

的原因之一。

在了解了函数定义、函数调用和函数原型之后，就可以写出一个完整的C++程序,并

可将其编译和运行。

5.4函数返回类型

根据函数是否带有参数以及函数是否有返回值，可以将函数分为如下四类。

1.带参数的有返回值函数

定义形式为：

＜返回类型＞＜函数名＞（＜参数列表＞）

（

＜语句序列＞

）

2.不带参数的有返回值函数

定义形式为：

〈返回类型〉〈函数名〉（）

（

＜语句序列〉

）

3.带参数的无返回值函数

定义形式为：

void〈函数名〉（〈参数列表〉）

（

＜语句序列〉

）

4.不带参数的无返回值函数

定义形式为:

void＜函数名＞（）

（

＜语句序列〉

）

5.5函数参数

C++中，函数之间传递参数有传值和传地址两种传递方式。此外，C++还提供了默认

参数机制，可以简化复杂函数的调用。

1.参数的传递方式

⑴传值

传值是将实参值的副本传递（拷贝）给被调用函数的形参。它是C++的默认参数传递方

式，在此之前的多数函数参数传递都是传值。

由于传值方式是将实参的值复制到形参中，因此实参和形参是两个不同的变量，有各自

的存储空间，可以把函数形参看作是函数的局部变量。传值的最大好处是函数调用不会改

变调用函数实参变量的内容，可避免不必要的副作用。

（2）传地址

有时我们确实需要通过函数调用来改变实参变量的值，或通过函数调用返回多个值

（return语句只能返回一个值）,这时仅靠传值方式是不能达到目的。

2.默认参数

在C++中，可以为参数指定默认值，在函数调用时没有指定与形参相对应的实参时就

自动使用默认值。默认参数可以简化复杂函数的调用。

默认参数通常在函数名第一次出现在程序中的时候，如在函数原型中，指定默认参数

值。指定默认参数的方式从语法上看与变量初始化相似。

5.6函数重载

如果能用同一个函数名字在不同类型上做相类似的操作就会方便很多，这种情况即为函

数重载。其实这一技术早已用于C++的基本运算符。例如加法操作只有一个运算符+,但

它却可以用来做整型数、浮点数和指针的加法运算。将这一思想推广到函数，即为函数重

载。

5.7内联函数

C++引入内联(inline)函数的原因是用它来取代C中的预处理宏函数。内联函数和宏函

数的区别在于，宏函数是由预处理器对宏进行替换，而内联函数是通过编译器来实现的，

因此内联函数是真正的函数，只是在调用的时候，内联函数像宏函数一样的展开，所以它

没有一般函数的参数压栈和退栈操作，减少了调用开销，因此，内联函数比普通函数有更

高的执行效率。

在C++中使用inline关键字来定义内联函数。inline关键字放在函数定义中函数类型之

前。不过，编译器会将在类的说明部分定义的任何函数都认定为内联函数，即使它们没有

用inline说明。

5.8递归函数

如果一个函数在其函数体内直接或间接地调用了自己，该函数就称为递归函数。递归是

解决某些复杂问题的十分有效的方法。递归适用以下的一般场合。

(1)数据的定义形式按递归定义。

(2)数据之间的关系(即数据结构)按递归定义，如树的遍历，图的搜索等。

(3)问题解法按递归算法实现，例如回溯法等。

使用递归需要注意以下几点：

(1)用递归编写代码往往较为简洁，但要牺牲一定的效率。因为系统处理递归函数时都

是通过压栈/退栈的方式实现的。

(2)无论哪种递归调用，都必须有递归出口，即结束递归调用的条件。

(3)编写递归函数时需要进行递归分析，既要保证正确使用了递归语句，还要保证完成

了相应的操作。

5.9变量作用域与生存周期

1.C++中变量的存储类型分为如下几种类型：

auto一函数内部的局部变量(auto可省略不写)。

static——静态存储分配，又分为内部和外部静态。

extern——全局变量(用于外部变量说明)。

register——变量存储在硬件寄存器中。

(1)自动变量

①在函数内部定义的局部变量即为自动变量，用于说明自动变量的关键字aut。可以省

略。

②在函数头部定义的自动变量作用域为定义它的函数；而在块语句中定义的自动变量作

用域为所在块。与C不同，C++还允许在变量使用之前才定义变量。

③编译程序不给自动变量赋予隐含的初值，故其初值不确定。因此，每次使用自动变量

前，必须明确地赋初值。

④形参可以看成是函数的自动变量，作用域仅限于相应函数内。

⑤自动变量所使用的存储空间由程序自动地创建和释放。当函数调用时为自动变量创建

存储空间，函数调用结束时将自动释放为其创建的存储空间。因此，自动变量随函数的调

用而存在并随函数调用结束而消失，由一次调用到下一次调用之间不保存值。

(2)外部变量

①在函数外部定义的变量即为外部变量。

②外部变量的作用域是整个程序(全局变量)。

③在C++中，程序可以分别放在几个源文件上，每个文件可作为一个编译单位分别编

译。外部变量只需在某个文件上定义一次，其他文件若要引用此变量时，应用extern加以

说明。（外部变量定义时不必加extern关键字）。

④在同一文件中，若前面的函数要引用在其后面定义的外部（在函数之外）变量时，也应

用extern加以说明。

⑤外部变量是由编译程序在编译时给其分配空间，属于静态分配变量，对于数值型（整

型、浮点型和字符型）外部变量来说，其有隐含初值0。

引进外部变量的原因：其一是只要程序运行外部变量的值是始终存在的；其二是外部变

量可以在所有函数间共享。

在C++中，可以使用外部变量，但是，必须要清楚使用外部变量的副作用。使用外部

变量的函数独立性差，通常不能被移植到其他程序中，而且，如果多个函数都使用到某个

外部变量，一旦出现问题，就很难发现问题是由哪个函数引起的。在C++中，尽量不用

或少用外部变量，可使用参数在函数间进行数据的传递。

（3）静态变量

内部静态变量：

①在局部变量前加上''static"关键字就成为内部静态变量。

②内部静态变量仍是局部变量，其作用域仍在定义它的函数内。但该类型变量采用静态

存储分配，当函数执行完，返回调用点时，该变量并不撤消，其值将继续保留，若下次再

进入该函数时，其值仍然存在。内部静态变量有隐含初值0,并且只在编译时初始化一

次。

外部静态变量：

①在函数外部定义的变量前加上"static"关键字便成了外部静态变量。

②外部静态变量的作用域为定义它的文件，即成为该文件的''私有"（private）变量，只有

其所在文件上的函数可以访问该外部静态变量，而其他文件上的函数一律不得直接访问该

变量，除非通过外部静态变量所在文件上的各种函数来对它进行操作，这也是一种实现数

据隐藏的方式。

③与内部静态变量一样，外部静态变量也采用静态存储分配，有隐含初值0。

在C++中，除了支持C风格的内部和外部静态变量的使用之外，还可将类成员声明成

static,它有着不同的含义。

（4）寄存器变量

①只有自动（局部）变量和函数参数可指定为寄存器存储类，它的作用域与生存期与自动

变量完全相同。

②当指定的寄存器变量个数超过系统所能提供的寄存器数量时，多出的寄存器变量将视

同自动变量。

③只限于int,char,short,unsigned和指针类型可使用register存储类。

④不能对寄存器变量取地址（即&操作）。

⑤使用寄存器变量可以提高存取速度,可将使用频率最高的变量说明成为寄存器变量。

一般常用于说明循环变量。

由于硬件的快速发展，存储器（如内存）的性能有了很大的改进，因此，目前在实际应用

中，使用register来说明变量的情况并不多。

2.生存周期

（1）变量由编译程序在编译时给其分配存储空间（称为静态存储分配），并在程序执行过

程中始终存在，这类变量包括全局变量、外部静态变量和内部静态变量。这类变量的生存

周期与程序的运行周期相同，当程序运行时，该变量的生存周期随即存在,程序运行结

束，变量的生存周期随即终止。

（2）变量由程序在运行时自动给其分配存储空间（称为自动存储分配），这类变量为函数

（或块）中定义的自动变量。它们在程序执行到该函数（或块）时被创建，在函数（或块）执行

结束时释放所用的空间。

第6章类和对象考点归纳

6.1类的定义

1•类的定义

类的定义可以分为两部分：说明部分和实现部分。说明部分说明类中包含的数据成员和

成员函数，实现部分是对成员函数的定义。类定义的一般格式如下：

〃类的说明部分

class＜类名＞

public:

＜成员函数或数据成员的说明＞〃公有成员，外部接口

protected:

＜数据成员或成员函数的说明＞〃保护成员

private:

＜数据成员或成员函数的说明＞〃私有成员

)；

〃类的实现部分

(各个成员函数的实现〉

其中，class是声明类的关键字；＜类名〉是要声明的类的名字，必须符合标识符定义

规则；花括号表示类的声明范围，说明该类的成员，其后的分号表示类声明结束。类的成

员包括数据成员和成员函数，分别描述类所表达的问题的属性和行为。关键字public,

private和protected称为访问权限修饰符，它们限制了类成员的访问控制范围。

各个成员函数的实现即可以在类体内定义，也可以在类体外定义。如果一个成员函数在

类体内进行了定义，它将不出现在类的实现部分；如果所有的成员函数都在类体内进行了

定义，则可以省略类的实现部分。在类体内定义的成员函数都是内联函数。

2.类成员的访问控制

类中提供了3种访问控制权限：公有(public)、私有(private)和保护(protected)。其

中，公有类型定义了类的外部接口，任何一个外部的访问都必须通过外部接口进行；私有

类型的成员只允许本类的成员函数访问，来自类外部的任何访问都是非法的；保护类型介

于公有类型和私有类型之间，在继承和派生时可以体现出其特点。

3.类的数据成员

类中的数据成员描述类所表达的问题的属性。数据成员在类体中进行定义，其定义方式

与一般变量相同，但对数据成员的访问要受到访问权限修饰符的控制。

在定义类的数据成员时，要注意以下几个问题。

（1）类中的数据成员可以是任意类型，包括整型、浮点型、字符型、数组、指针和引用

等，也可以是对象。但是要注意，只有另外一个类的对象，才可以作为该类的成员，即作

为该类的成员对象而存在。自身类的对象是不可以作为自身类的成员存在的，但自身类的

指针可以。

（2）在类体中不允许对所定义的数据成员进行初始化。

4.类的成员函数

类的成员函数描述类所表达的问题的行为。类中所有的成员函数都必须在类体内进行说

明。但成员函数的定义既可以在类体内给出，也可以在类体外给出。

第一种方式是将成员函数直接定义在类的内部。

第二种方式是在类声明中给出对成员函数的说明，而在类外部对成员函数进行定义（但

成员函数仍然在类范围内）。这种在类外部定义的成员函数的一般格式是：

〈返回类型〉〈类名＞：：＜成员函数名〉（〈参数表〉）

（

＜函数体＞

）

在类体外定义成员函数时，要注意必须在成员函数名前加上类名和作用域运算符（：：）。

作用域运算符用来标识某个成员属于某个类。作用域运算符的使用格式如下：

（类名＞：：＜成员函数名＞（〈参数表〉）

或

（类名>::<数据成员名〉

成员函数的两种定义方式之间是有差别的。如果一个成员函数的声明和定义都在类体

内，那么这个成员函数就是内联函数。如果一个成员函数的声明在类体内，而定义在类体

外，这时对该成员函数的调用是按一般函数进行的。如果要将定义在类体外的成员函数也

作为内联函数处理，就必须在成员函数的定义前加上关键字'inline”,以此显式地说明该成

员函数也是一个内联函数。

成员函数除了可以定义为内联函数以外，也可以进行重载，可以对其参数设置默认值。

6.2对象的定义

1.对象的定义

对象是类的实例，一个