计算机二级公共基础知识

1算法的基本概念

1、算法一般应具有以下几个基本特征：可行性、确定性、有穷性、拥有足够的情报。

算法是对解题方案的准确而完整的描述，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效和明确的，此顺序将在有限的次数下终止。

2、算法的基本要素

（1）算法中对数据的运算和操作。通常有4类：算术运算，逻辑运算，关系运算和数据传输。

（2）算法的控制结构。算法的功能不仅仅取决于所选择的操作，还与操作之间的执行顺序及算法的控制结构有关。

3、算法设计基本方法

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

4、算法的复杂度（在算法正确的前提下，评价算法的标准）

（1）算法的时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数。

（2）算法的空间复杂度

算法的空间复杂度，一般是指执行这个算法所需要的内存空间。一个算法所占的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。

数据结构，直接影响算法的选择和效率。而数据结构包括两方面，即数据的逻辑结构和数据的存储结构。

数据之间的相互关系称为逻辑结构。通常分为4类基本逻辑结构，即集合、线性结构、树形结构和图状结构或网状结构。存储结构图是逻辑结构在存储器中的映象，它包含数据元素的映象和关系的映象。存储结构在计算机有两种，即顺序存储结构和链式存储结构。

时间复杂度与空间复杂度之间没有必然的联系。

2数据结构基本概念

1、 数据结构是指反映数据元素之间的数年据元素集合的表示。

2、 所谓数据的逻辑结构，是指所映数据元素之间逻辑关系的数据结构。数据的逻辑结构有两个要素：一是数据元素的集合；二是数据元素之间的关系。

3、 各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的。数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。

3线性表和线性链表

1、 线性结构与非线性结构

根据数据结构中各数据元素之间前后件关系复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件：

（1） 有且只有一个根结点。（2）每一个结点最多有一个前件，也最多有一个后件。

则称该数据结构不是线性结构，则称之为非线性结构。

如果一个关系中的属性或属性组并非该关系的关键字，但它是另一个关系的关键字，则称其为本关系的外关键字

2、 线性表的基本概念

线性表是由n（n>=0）个数据元素

组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。

3、线性表的顺序存储结构

线性表的顺序存储结构具有以下两个基本特点：线性表中所有元素所占的存储空间是连续的。线性表中各数据元素在存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。

在顺序存储结构中，线性表中每一个数据元素在计算机存储空间中的存储地址由该元素在线性表中的位置序号唯一确定。

3、 线性链表

大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而应采用链式存储结构。

在链式存储结构中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针于指向该结点的前一个或后一个结点。

在链式存储结构称为线性链表。一般来说，在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。栈和队列也是线性表，也可以采用链式存储结构。

4、 线性链表的基本运算

线性链表的基本运算有：在非空线性链表中寻找包含指定元素值X的前一个结点P，线性链表的插入，线性链表的删除。

5、 循环链表及其基本运算

循环链表的结构与一般的单链表相比，具有以下两个特点：

(1) 在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。

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

(3) 在单链表中，增加头结点的目的是方便运算的实现。

(4) 循环链表的主要优点是从表中任一结点出发都能访问到整个链表。

⑸ 线性表的顺序存储结构和线性表的链式存储结构分别是随机存取的存储结构、顺序存取的存储结构

4栈和队列

栈是限定在一端进行插入与删除的线性表。栈是按照“先进后出”或“后进先出”的原则组织数据的。栈的运算、退栈运算、读栈顶元素。

队列是是允许在一端进行插入、而在另一端进行删除的线性表。队列又称为“先进先出”或“后进后出”的线性表，它体现了“先来先服务”的原则。

所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上环状空间，供队列循环使用。循环队列的初始状态为空，即rear=front=m。

循环队列主要有两个基本运算：入队运算和退队运算。

5树与二叉树

1、 树的基本概念

树是一种简单的非线性结构。树结构中，每一个结点只有一个前件，称为父结点。在树中，没前件的结点只有一个，称为树的根结点，简称为树的根。在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。

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

树结构具有明显的层次关系，树是是一种层次结构。根结点在第1层。同一层上所有结点的所有子结点在下一层。树的最大层次称为树的深度。

在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。要树中，叶子结点没有子树。

2、 二叉树的特点

（1） 非空二叉树只有一个根结点；每一个结点最多有两个棵子树，且分别称为该结点的左子树与与右子树。

（2） 在二叉树中，每一个结点的度最大为2，即所有子树（左子树或右子树）也均为二叉树。而树结构中的每一个结点的度可以是任意的。另外，二叉树中的每一个结点的子树被明显地分为左子树与右子树。在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时，该结点即是叶子结点。

3、 二叉树的性质

（1） 在二叉树的第K层上，最多有2 k-1(k≥1)个结点。

（2） 深度为m的二叉树最多有2 m-1个结点。

（3） 在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。

（4） 具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分。

4、 满二叉树与完全二叉树

（1） 满二叉树，除最后一层外，每一层上的所有结点都有两个子结点。这就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2 k-1个结点，且深度为m的满二叉树有2 m-1个结点。

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

对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现；对于任何一个结点，若其右分支下的子孙结点的最大层次为p，则其左分支下的子孙结点的最大层次或为p，或为p+1.

满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。

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

5、 二叉树的存储结构

二叉树通常采用链式存储结构。与线性链表类似，用于存储二叉树中各元素的存储结点也由两部分组成：数据域与指针域。

6、 二叉树的遍历 微信公众号：高校学习墙

二叉树的遍历是指不重复地访问二叉树中的所有结点。在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为3种：前序遍历、中序遍历、后序遍历。

（1） 前序遍历（DLR）。所谓前序遍历是首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。因此，前序遍历二叉树的过程是一个递归的过程。

（2） 中序遍历（LDR）。所谓中序遍历是首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。因此，中序遍历二叉树的过程也是一个递归的过程。

（3） 后序遍历（LRD）。所谓后序遍历是首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后右子树，最后访问根结点。因此，后序遍历二叉树的过程也是一个递归的过程。

6查找技术

1、顺序查找

顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素。

如果线性表中的第一个元素就是被查找的元素，则只需做一次比较就查找成功，最坏的情况是被查元素是线性表中的最后一个元素，或者被查元素在线性表中根本不存在，则为了查找这个元素需要与线性表中所有的元素进行比较。平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较。

2、二分法查找

二分法查找只适用于顺序存储的有序表。

设有序线性表的长度为n，被查元素为x，则对分查找的方法为：将x与线性表的中间项进行比较，如果中间项的值等于x，则说明查到，查找结束；如果x小于中间项的值，则在线性表的前半部分以相同的方法进行查找；如果大于中间项的值，则在线性表的后半部分以相同的方法进行查找，这个过程一直进行到查找成功或子表长度为0（说明线性表中没有该元素）为止。

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

最简单的交换排序方法是冒泡排序法。

7排序技术

排序是指将一个无序序列整理成按值非递减顺序排序的有序序列。

1、 交换类排序法

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

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

（2） 快速排序。快速排序法的基本思想为：从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成了两部分，T插入到分界线的位置处，这个过程称为线性表的分隔。如果对分割后的各子表再按上述原则进行分割，并且，这种分割过程可以一直做下去，直到所有子表为空为止，则此时的线性表就变成了有序表。

2、 插入排序法

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

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

（2） 希尔排序法。希尔排序的效率与所选取的增量序列有关。如果选取上述增量序列，则在最坏情况下，希尔排序所需要的比较次数为O（n1.5）.

3选择类排序

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

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

4常见的排序方法有插入排序（包括简单插入排序法和希尔排序法等）、交换排序（包括冒泡排序和快速排序法等）和选择排序（包括简单选择排序和堆排序等）。

8程序设计方法与风格

1、 源程序文档化

（1） 符号的命名：符号名应具有一定的实际含义，以便于对程序功能的理解。

（2） 程序注释：正确的注释能够帮助读者理解程序。注释一般分为序言性注释和功能性注释。

（3） 视觉组织：为使程序的结构一目了然，可以在程序中利用空格、空行、缩进等技巧使程序层次清晰。

2、 数据说明的方法

数据说明的风格一般应注意：数据说明的次序规范化；说明语句中变量安排有序化；使用释来说明复杂数据的结构。

3、 语言结构

程序应简单易懂，语句构造应简单直接。

4、 输入和输出

输入输出的方式和格式应尽可能方便用户的使用。

9结构化程序设计

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

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

（1） 自顶向下：程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标；先从最上层总目标开始设计，逐步使问题具体化。

（2） 逐步求精：对复杂问题，应设计一些子目标作为过渡，逐步细化。

（3） 模块化：一个复杂问题，是由若干个简单问题构成的。模块化是把程序要解决的总目标分解分目标，再进一步分解为具体的小目标，把每一个小目标称为一个模块。

（4） 限制使用goto语句：滥用goto语句有害，应尽量避免。

2、 结构化程序的基本结构和特点

采用结构化程序设计方法编写程序，可使程序结构良好、易读、易理解、易维护。程序设计语言仅用顺序、选择、重复3种基本控制结构就可以表达出各种其他形式结构的程序设计方法。

（1） 顺序结构：顺序结构是顺序执行结构，所谓顺序执行，就是按照程序语句行的自然顺序，一条语句一条语句地执行程序。

（2） 选择结构：又称为分支结构，它包括简单选择和多分支选项择结构。这种结构根据设定的条件，判断应该选择哪一条分支来执行相应的语句。

（3） 重复结构：又称循环结构，它根据给定的条件，判断是否需要重复执行某一相同的或类似的程序段，利用重复结构可简化大量的程序行。重复结构有两类循环语句，先判断后执行循环体的称为当型循环结构，先执行循环后判断的称为直到型循环结构。

遵循结构化程序的设计原则，按结构化程序设计方法设计出的程序具有的优点为：其一，程序易于理解、使用和维护；其二，提高了编程工作的效率，降低了软件开发成本。

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

在结构图化程序设计的具体实施中，要注意把握如下因素：

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

（2） 选用的控制结构只准许有一个入口和一个出口。

（3） 程序语句组成容易识别的块，每块只有一个入口和一个出口。

（4） 复杂结构应该应用嵌套的基本控制结构进行组合嵌套来实现。

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

（6） 严格控制goto语句的使用。

10面向对象的程序设计

1、 面向对象方法的主要优点

面向对象方法的主要优点为：与人类习惯的思维方式一致；稳定性好；可重用性好；易于开发大型软件产品；可维护性好。

2、 面向对象技术的基本概念

（1） 对象。面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。

（2） 类和实例。类是具有共同属性、共同方法的对象的集合。类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象是其对应类的一个实例。类同对象一样，也包括一组数据属性和在数据上的一组合法操作。

（3） 消息。消息是一个实例与另一个实例之间传递的信息，它请求对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。消息的使用类似于函数调用，消息中指定了某一个实例，一个操作和一个参数表。

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

（5） 多态性。对象根据所接受的信息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。更多资料关注微信公众号：高校学习墙

（6） 面向对象技术中包括以下几个基本概念，即对象、类、方法、消息、继承和封装，其中封装是一种信息隐蔽技术，目的在于将对象的使用者对象的和设计者分开。

11软件工程基本概念

1、 软件及软件工程的定义

软件是计算机系统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整集合。

程序是软件开发人员根据用户需求开发的，用程序设计语言描述的、适合计算机执行的指令序列。数据是使程序能正常操纵信息的数据结构。文档是与程序开发、维护和使用有关的图文资料。

软件工程学是用工程、科学和数学的原理与方法研制、维护计算机软件的有关技术及管理方法的一门工程学科。软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。

软件工程包括3个要素，即方法、工具和过程。方法是完成软件工程项目的技术手段；工具支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理。

2、 软件生命周期

软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。一般包括可行性研究与需求分析、设计、实现、测试、交付使用以及维护等活动。还可将软件生命周期分为软件定义、软件开发及软件运行维护3个阶段。软件生命周期的主要活动阶段是：可行性研究与计划指定、需求分析、软件设计、软件测试、运行和维护。

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

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

软件工程的出现是由于软件危机的出现。

软件开发离不开系统环境资源的支持，其中必要的测试数据属于辅助资源。

软件结构是以模块化为基础而组成的一种控制层次结构。

12结构化分析方法

1、 需求分析与需求分析方法

软件需求是指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。需求分析的任务是发现需求、求精、建模和定义需求的过程。

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

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

2、 结构化分析方法

结构化分析方法是结构化程序设计理论在软件需求分析阶段的运用。结构化分析方法是着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。

结构化分析的常用工具有数据流图、数字字典、判断树、判断表。

（1） 数据流图（DFD）。数据流图是描述数据处理过程的工具，是需求理解的逻辑模型的图形表示，它直接支持系统的功能建模。数据流图从数据传递和加工的角度，来刻画数据流从输入到输出的移动变换过程。数据流图中的主要图形元素如下图。

第一个是加工（转换）；第二个是数据流；第三个是存储文件（数据源）；第四个是源（潭）。

建立数据流图的步骤：由外向里，自顶向下，逐层分解。

（2） 数据字典（DD）。数据字典是结构化分析方法的核心。数据字典是对所有与系统相关的数据元素的一个有组织的列表。数据字典的作用是对数据流图中出现的被命名的图形元素的确切解释。数据字典包含的信息有名称、别名、何处使用如何使用、内容描述、补充信息等。

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

3、 软件需求规格说明书

软件需求规格说明书把在软件计划中确定的软件范围加以展开，制定出完整的信息描述、详细的功能说明、恰当的检验标准以及其他与要求有关的数据。

13结构化设计方法

1、 软件设计的基本概念

从技术观点来看，软件设计包括结构设计、数据设计、接口设计、过程设计。从工程管理角度来看，软件设计分两步完全，即概要设计和详细设计。

2、 软件设计的基本原理

衡量软件的模块独立性使用耦合性和内聚性两个定性的度量标准。耦合性是模块间互相联结的紧密程度的度量。内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量。一般较优秀的软件设计，应尽量做到高内聚、低耦合。

3、 概要设计

概要设计也称总体设计。软件概要设计的任务是：设计软件系统结构、数据结构及数据库设计、编写概要设计文档、概要设计文档评审。

常用的软件设计工具为程序结构图。

典型的数据流类型有两种：变换型和事务型。

设计准则：提高模块独立性；模块规模适中；深度、宽度、扇入和扇出适当；使模块的作用域在该模块的控制域内；应减少模块的接口和界面的复杂性；设计成单入口、单出口的模块；设计功能可预测的模块。

4、 详细设计

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

设计工具：图形工具（程序流程图、N-S、PAD、HIPO）、表格工具（判定表）、语言工具（伪码）。

结构化程序设计主要强调的是程序易读性。

软件的过程设计是指系统结构部件转换成软件的过程描述。

软件设计模块化的目的是降低复杂性。

结构化分析方法主要包括：面向数据流的结构化分析方法（SA-Structured analysis），面向数据结构的Jackson方法（JSD-Jackson system development method）和面向数据结构的结构化数据系统开发方法（DSSD-Data structured system development method）。

14软件测试

1、 软件测试方法和技术

软件测试是为了发现错误而执行程序的过程，其主要过程涵盖了整个软件生命期的过程。

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

（1） 白盒测试

白盒测试方法也称结构测试或逻辑驱动测试。白盒测试把测试对象看做一个打开的盒子，允许测试人员利用程序内部进行，主要用于完成软件内部操作的验证。

白盒测试的基本原则：保证所测模块中每一独立路径至少执行一次；保证所测模块所有判断的每一分支至少执行一次；保证所测模块中每一循环都在边界条件和一般条件下至少各执行一次；验证所有内部数据结构的有效性。

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

（2） 黑盒测试方法

黑盒测试方法也称功能测试或数据驱动测试。黑盒测试完全不考虑程序内部的逻辑结构和内部特性，只依据程序的需求和功能规格说明，检查程序的功能是否符合它的功能说明。黑盒测试在软件接口处进行。

黑盒测试主要诊断功能不对或遗漏、界面错误、数据结构或外部数据库访问错误、性能错误、初始化和终止条件错误。

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

2、 软件测试的实施

软件测试一般按4个步骤进行，即单元测试、集成测试、确认测试和系统测试。通过这些步骤的实施来验证软件是否合格，能否交付用户使用。

软件测试的目标是在精心控制的环境下执行程序，以发现程序中的错误，给出程序可靠性的鉴定；调试也称排错，它是一个与测试有联系又有区别的概念。具体来说，测试的目的是暴露错误，评价程序的可靠性，而调试的目的是发现错误的位置，并改正错误。

15程序的调试

程序进行了成功的测试之后进入调试阶段，程序调试是诊断和改正程序中潜在的错误。调试主要在开发阶段。

程序的调试活动由两部分组成，一是根据错误的迹象确定程序中错误的确切性质、原因和位置。二是对程序进行修改，排除错误。

程序调试的基本步骤为：错误定位，修改设计和代码，进行回归测试。

软件调试的方法从是否跟踪和执行程序的角度，可分为静态调试和动态调试。静态调试主要指通过人的思维来分析源程序代码和排错，是主要的调试手段，而动态调试是辅助静态调试的。

主要的调试方法为：强行排错法，回溯法，原因排除法。

16数据库系统的基本概念

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

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

（2） 数据库。数据库是数据的集合，它具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序所共享。

（3） 数据库管理系统。数据库管理系统（Database Management System,DBMS）是位于用户与操作系统之间的一个数据管理软件。负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等。

（4） 数据库管理系统提供给用户的接口是宿主语言。

（5） 数据库管理员。由于数据库的共享性，因此对数据库的规划、设计、维护、监视等需要有专人管理，称他们为数据管理员。主要工作有数据库设计、数据库维护、改善系统性能和提高系统效率等。

（6） 数据库系统。数据库系统(Database Sytem,DBS)由数据库（数据）、数据库管理系统（软件）、数据管理员（人员）、硬件平台（系统平台之一）和软件平台（系统平台之一）5部分组成。在数据库系统中，硬件平台包括：计算机和网络，软件平台包括：操作系统数据库开发工具和接口软件。

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

2、 数据库系统的发展

数据管理的发展经历了3个阶段：

（1） 人工管理阶段主要用于科学计算，硬件没有磁盘，数据被直接存取，软件没有操作系统。

（2） 文件系统阶段具有简单的数据共享和数据管理能力，无法提供统一的、完整的管理和数据共享能力。

（3） 数据库系统阶段

数据库系统阶段具有以下特点：

1、 数据的集成性：采用统一的数据结构方式：按照多个应用的需要组织全局的统一的数据结构；每个应用的数据是全局结构中的一部分。

2、 数据的高共享性与低冗余性：数据共享可减少数制冗余及存储空间，避免数据的不一致。

3、 数据独立性：这是数据与程序间的互不依赖性，即数据库中数据独立于应用程序而不依赖于应用程序。也就是说，数据的逻辑结构、存储结构与存取方式的改变不会影响应用程序。数据独立性分为物理独立性和逻辑独立性。

4、 数据统一管理与控制：主要包含3个主面，即数据的完整性检查、数据的安全性保护和并发控制。数据的恢复。

5、 安全性控制：防止未经授权的用户有意或无意存取数据库中的数据，以免数据被泄露、更改或破坏；完整性控制：保证数据库中数据及语义的正确性和有效性，防止任何对数据造成错误的操作；并发控制：正确处理好多用户、多任务环境下的并发操作，防止错误发生；恢复：当数据库被破坏或数据不正确时，使数据库能恢复到正确的状态。

3、 数据库系统的内部结构体系

数据库的三级模式：概念模式、外模式、内模式。

数据库的二级映射：概念模式到内模式的映射，外模式到概念模式的映射。

内模式是能够给出数据库物理存储结构与物理存取方式。

外模式是用户的数据视图。也就是用户所见到的数据模式。

概念模式是数据库系统中全局逻辑结构的描述，是全体用户的公共数据视图。

数据库技术的主要特点有以下几个方面：数据的集成性，数据的高共享性与低冗余性，数据独立性，数据统一管理与控制。

数据元素之间逻辑关系的整体称为逻辑结构。数据的逻辑结构就是数据的组织形式。

分布式数据库系统不具有的特点是数据冗余。而具有数据分布性、逻辑整体性、位置透明性和复制透明性、分布性。

为用户与数据库系统提供接口的语言是汇编语言。

（DDL）是数据描述语言，（DML）数据操纵语言。

关系的完整性约束指关系的某种约束条件，包括实体完整性、参照完整性和用户定义的完整性。其中，前两种完整性约束由关系数据库系统自动支持。

17数据模型（数据库设计的核心）

1、 数据模型的基本概念

数据是现实世界符号的抽象，而数据模型是数据特征的抽象。数据模型所描述的内容有3个部分：数据结构、数据操作和数据约束。数据模型按不同的应用层次分成3种类型，分别是概念数据模型、逻辑数据模型和物理数据模型。

概念模型与具体的数据库管理系统无关，与具体的计算机平台无关。较为有名的概念模型有E-R模型、扩充的E-R模型、面向对象模型及谓词模型等。

逻辑数据模型又称数据模型，是一种面向数据库系统的模型。概念模型只有在转换成数据模型后才能在数据库中得以表示。大量使用过的逻辑数据模型有层次模型、网状模型、关系模型（坚实理论基础）和面向对象模型。

物理数据模型又称物理模型，它是一种面向计算机物理表示的模型，此模型给出了数据模型在计算机上物理结构的表示。

2、E-R模型

（1）E-R模型的基本概念

现实世界中的事物可以抽象成为实体，实体是概念世界中的基本单位，它们是客观存在的且又能相互区别的事物。凡是有共性的实体可组成一个集合，称为实体集。

属性刻画了实体的特征。一个实体可以有若干个属性。每个属性可以有值，一个属性的取值范围称为该属性的值域或值集。

（2）实体间的联系

实体集间的联系可以归结为3类：

a) 一对一的联系，简记为1:1。

b) 一对多的联系，简记为M:1(m：1)或1:M（1:m）。

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

（3）E-R模型的图示法

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

（4）一个关系中属性个数为1时，称此关系为一元关系。

3、层次模型

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

4、 网状模型

网状模型是不加任何条件限制的无向图。网状模型在数据表示和数据操纵方面比层次模型更高效、更成熟。但网状模型在使用时涉及系统内部的物理因素较多，用户使用操作并不方便，其数据模式与系统实现也不甚理想。

5、 关系模型

（1） 关系的数据结构

关系模型采用二维来表示，简称表。二维表由表框架和表的元组组成。表框架由n个命名的属性组成，每个属性有一个取值范围称为值域。在框架中按行可以存放数据，每行数据称为元组。

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

表中一定要有键，如果表中所有属性的子集均不是键，则表中属性的全集必为键。在关系元组的分量中允许出现空值表示信息空缺。主键中不允许出现空值。

关系框架与关系元组构成一个关系。一个语义相关的关系集合构成一个关系数据库。关系的框架称为关系模式，而语义相关的关系模式集合构成了关系数据库模式。

关系模式支持子模式，关系子模式是关系数据库模式中用户所见到的那部分数据模式的描述。关系子模式也是二维表结构，关系子模式对应用户数据库称为视图。

（2） 关系的操纵

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

（3） 关系中的数据约束

关系模型允许定义3类数据约束，它们是实体完整性约束、参照完整性约束和用户完整性约束。

18关系代数

关系数据库系统建立在数学理论的基础之上，使用关系代数可以表示关系模型的数据操作。由于操作是对关系的运算，而关系是有序组的集合，因此，可以将操作看成是集合的运算。

1、 关系模型的基本运算

（1） 插入

设有关系R需插入若干元组，要插入的元组组成关系R`，则插入可用集合并运算表示为R并R`。

（2） 删除

设有关系R需删除若干元组，要删除的元组组成关系R`，则删除可用集合差运算表示为R-R`。

（3） 修改

修改关系R内的元组内容可以用下面的方法实现：设需修改的元组构成关系R`，则先作删除得R-R`。设修改后的元组构成关系R``，此时将其插入即得到结果：（R-R`）U R’’。

（4） 查询

投影运算：投影运算是在给定关系的某些域上进行的运算。经过投影运算后，会取消某些列，而且有可能出现一些重复元组。

选择运算：关系R通过选择运算后，由R中满足逻辑条件的元组组成。

笛卡儿运算：对于两个关系的合并操作可以用笛卡儿积表示。设有n元关系R及m元关系S，它们分别有p、q个元组，则关系R与S经笛卡儿积记为RXS.该关系是一个n+m元关系，元组个数是pXq，由R与S的有序组组合而成。

2、 关系代数中的扩充运算

（1） 交运算。关系R与S经交运算后所得到的关系是由那些既在R内又在S内的有序组所组成，记为R∩S

（2） 除运算。当关系T=RXS时，则可将除运算写为T/R＝S。设有关系T、S，T能被R除的充分必要条件是：T中的域包含R中的所有属性；T中有一些域不出现在R中。在除运算中S的域由T中那些不出现在R中的域所组成。

（3） 连接与自然连接运算。连接运算又可称为

连接运算，通过它可以将两个关系合并成一个大关系。

注意：投影、选择、连接是从二维表的列的方向来进行运算。

19数据库设计与管理

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

1、 数据库设计的需求分析

需求分析阶段的任务是通过详细调查现实世界要处理的对象，充分了解原系统的工作概况，明确用户的各种需求，然后在此基础上确定新系统的功能。

分析和表达用户的需求，经常采用的方法有结构化分析方法和面向对象的方法。结构化分析方法用自顶向下、逐层分解的的方式分析系统。数据流图表达了数据和处理过程的关系，数据字典对系统中数据的详尽描述是各类数据属性的清单。数据字典是进行详细的数据收集和数据分析所获得的主要结果。数据字典是各类数据描述的集合，它包含5个部分，即数据项、数据结构、数据流、数据存储和处理过程。数据字典是在需求分析阶段建立，在数据设计过程中不断修改、充实、完善的。

2、 数据库的概念设计

（1） 数据库概念设计

数据库概念设计的目的是分析数据间内的语义关联，在此基础上建立一个数据的抽象模型。数据库概念设计的方法有两种：集中式模式设计法：视图集成设计法以下。

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

使用E-R模型与视图集成法进行设计时，需要按以下步骤进行：首先选择局部应用，再进行局部视图进行集成得到概念模式。

3、 数据库的逻辑设计

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

将E-R图转换为关系模型的转换方法如下：

一个实体型转换为一个关系模式。

一个1：1联系可以转换为一个独立的关系模式，也可以与任意一端（一般为全部参与方）对应的关系模式合并。

一个1：n联系可以转换为一个独立的关系模式，也可以与n端对应的关系模式合并。

一个m：n联系转换为一个关系模式。

3个或3个以上实体间的多元联系转换为一个关系模式。

具有相同码的关系模式可合并。

（2） 逻辑模式规范化

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

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

（3） 关系视图设计

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

4、 数据库的物理设计

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

5、 数据库管理

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

6、 数据库的建立包括数据模式的建立和数据加载。

定义指向整型元素的指针变量形式为：int*指针变量名。定义指向整型一维数组的行指针形式为：int(*指针变量名[长度]，定义指向返回值为整型的函数的指针变量的形式为：int(*函数名)()，定义返回值为指向整型的指针型函数的形式为:int *函数名()。本题定义的是一个返回值为指针型的函数f()。

程序设计语言的基本成分是数据成分、运算成分、控制成分和传输成分。

SQL语言又称为结构化查询语言。

C语言的函数可以嵌套调用

构成C程序的基本单位是函数

常用的存储表示方法有4种，顺序存储、链式存储、索引存储、散列存储。其中，顺序存储方法是把逻辑上相邻的结点存储在物理位置也相邻的存储单元中。

软件工程的理论和技术性研究的内容主要包括：软件开发技术和软件工程管理。软件开发技术包括：软件开发方法学、开发过程、开发工具和软件工程环境，其主体内容是软件开发方法学。软件工程管理包括：软件管理学、软件工程经济学，以及软件心理学等内容。

在关系操作中，所有操作对象与操作结果都是关系。而关系定义为元数相同的元组的集合。因此，关系操作的特点是集合操作。

在一般系统中，一个float型数据在内存中占4个字节（32位），一个double型数据占8个字节。

ASC表示升序排列，DESC表示降序排列，多用在索引定义和SELECT语句中的ORDER子句中。