计算机二级 公共基础知识_栈的元素个数计算方法

公共基础知识考试要求：

1.掌握算法的基本概念；
2.掌握基本数据结构及其操作；
3.掌握基本排序和查找算法；
4.掌握逐步求精的结构化程序设计方法；
5.掌握软件工程的基本方法，具有初步运用相关技术进行软件开发的能力；
6.掌握数据库的基础知识，了解关系数据库的设计。

数据结构与算法

算法的概念：解题方案的准确而完整的描述。算法不等于程序，也不等于计算方法，是两者结合。

算法的特征：可行性（所有操作都必须足够基本，都可以利用已经实现的基本操作运算有限次实现）、确定性（任何操作都有确定定义）、有穷性（一定能结束，在有限时间内完成）、拥有足够的情报（有足够实践实例证明它是正确的）

算法的基本要素：
对数据对象的运算和操作（算术、逻辑）
算法的控制结构，即运算和操作时间的顺序（执行顺序）
描述算法的工具通常有传统流程图、N-S结构化流程图（是无线的流程图，又称盒图）、算法描述语言等

一个算法基本都可以用顺序、选择、循环三种基本控制结构组合而成。

流程图的描述、N-S图的描述、伪代码描述

算法设计方法：
列举法：列举所有可能，把所有有可能的情况都一一列举出来。不能解决无限复杂的问题。
归纳法：从特殊到一般。类似于高中的数学归纳法。
递推：从条件到结论，逐次推出结果。正向。
递归：函数的自调用。降低问题的复杂程度，将问题逐层分解。逆向。
减半递推：分治。二分查找。
回溯：反证。

算法的复杂度：时间复杂度和空间复杂度

时间复杂度（和时间没有关系）：
执行算法所需要的计算工作量。
计算工作量：用算法所执行的基本运算次数来度量。
基本运算次数：是问题规模的函数。
则：算法的计算工作量=f(n)，其中n是问题的规模。
方法：
（1）平均性态（Average Behavior）
平均性态分析是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。
（2）最坏情况复杂性（Worst-Case Complexity）
最坏情况分析是指在规模为n时，算法所执行的基本运算的最大次数。
比如多次运行某个算法，次数分别为10万次、9万次、8万次，则（1）为9万次，（2）为10万次。

空间复杂度：
执行这个算法所需要的内存空间或者存储空间。
类似于算法的时间复杂度，空间复杂度作为算法所需存储空间的度量。

数据结构的主要研究的三个问题
1.数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；
2.在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构，又称物理结构；
3.对各种数据结构进行的运算。

数据元素：现实世界中存在的一切个体。比如，春夏秋冬可以作为季节的数据元素。

在数据处理领域中，每一个需要处理的对象都可以抽象成数据元素。

数据结构：带有结构的数据元素的集合。
一个数据结构应包含如下两种信息：
1.表示数据元素的信息；
2.表示各数据元素之间的前后件关系（即逻辑关系，与其在计算机中的存储位置无关）

数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构（即前、后件关系）
数据的逻辑结构在计算机存储空间中的存放形式称为数据存储结构（也称数据的物理结构）

在数据的存储结构中，不仅要存放各数据元素的信息，还要存放各数据元素之间的前后件关系的信息。

一种数据的逻辑结构可以表示成各种存储结构。

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

对于一种数据的逻辑结构，如果采用不同的存储结构，则数据处理的效率是不同的。

数据结构的表示：二元关系、图形

数据结构的分类（根据数据结构中的各数据元素之间前后件关系的复杂程度）：线性结构与非线性结构

线性结构 又称线性表的定义：
如果一个非空的数据结构满足以下条件：
1.有且只有一个根结点；
2.有且只有一个终端结点；
3.除根结点外，其它结点均只有一个前件；
4.除终端结点外，其它结点均只有一个后件。

线性表的基本概念：是指n个数据元素的有限序列。是最简单、最常用的一种数据结构。

线性表可以表示为（a1,a2,…,ai,…,an），其中ai是属于数据对象的元素，通常也称其为在线性表中的一个结点。

当n=0时，称为空表。

在一个线性结构中插入或删除任何一个结点后还应该是线性结构。

线性表的顺序存储结构，其特点如下：
1.线性表中所有元素所占的存储空间是连续的；
2.线性表中各数据结构在存储空间中是按逻辑顺序依次存放的。

线性表在顺序存储结构下的插入与删除运算：
插入步骤：
1）把原来第 i个结点至第 n个结点依次往后移动一个元素位置；
2）把新结点放在第 i个位置上；
3）修正线性表的结点个数。
删除步骤：
1）把第 i个元素之后的 n-i个元素依次前移一个位置；
2）修正线性表的结点个数。

线性表的顺序存储结构适合用于小线性表或者建立之后其它元素不常变动的线性表，而不适合用于需要经常进行插入和删除运算的线性表和长度较大的线性表。

栈的基本概念：栈（stack）是限定仅在一端进行插入和删除运算的线性表。
在栈中，允许插入和删除的一端称为栈顶，而不允许插入和删除的另一端称为栈底。

栈的入口和出口是同一个口。
栈：“先进后出”，“后进先出”

栈内元素个数计算公式： |top-bottom|+1
如果栈当中 top=bottom=0 说明栈是空的。

栈的基本计算有三种：入栈、退栈与读栈顶元素。

入栈运算：在栈顶位置插入一个新元素。
基本操作：首先将栈顶指针进一， top=top+1；然后将新元素插入到栈顶指针指向的位置。

退栈运算：取出栈顶元素并赋给某个变量。
基本操作：首先将栈顶元素赋给一个指定的变量；然后将栈顶指针退一， top=top-1。

读栈顶元素：将栈顶元素赋给一个指定的变量。在这个运算中，栈顶指针不会改变。

在栈的入栈和退栈的运算中，栈底指针 bottom维持不变。

栈能保存数据，因此栈具有记忆作用。

栈是线性结构，在计算机中担任着临时存储的功能。

队列的基本概念：限定仅在表的一端进行插入，而在表的另一端进行删除的线性表。（尾进头出）
在队列中，允许插入的一端称为队尾，允许删除的一端称为队头。
队列又称为“先进先出”或“后进后出”的线性表。

在队列中，通常用指针 front指向队头元素的前一个位置，用 rear指向队尾最后一个元素。

循环队列：将队列存储空间的最后一个位置绕到第一个位置上，形成逻辑上的环状空间，供队列循环使用。依然属于线性结构。
从头指针 front指向的后一个位置直到队尾指针 rear指向的位置之间，所有的元素均为队列中的元素。

循环队列元素个数的计算：
循环队列中的元素的个数= rear（尾）- front（头）
（1） rear- front为正数时，便是循环队列的元素个数；
（2） rear- front为负数时，需要再加上循环队列的容量；
（3） rear- front为零时，可以取以上两种情况。

线性链表的基本概念：线性表的链式存储结构。用一组不连续的存储单元存储线性表中的各个元素。

线性表中的每一个元素由以下两部分组成。数据域用于存放数据元素值；指针域用于存放下一个数据结点的存储序号，即指向后件结点。

双向链表：对线性链表中的每一个结点设置两个指针域，一个指向其前件结点，称为前件指针或左指针；另一指向其后件结点，称为后件指针或右指针。

由于栈和队列均是线性表，所以两者也可采用链式存储结构。二者均为线性结构。

循环链表的结构具有下面两个特点：
（1）在循环链表中增加了一个表头结点。表头结点的数据域为任意或者根据需求来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。
（2）循环链表中最后一个结点的指针域不是空的，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。

普通线性链表与循环链表的区别在于：循环链表能访问链表中的任意一个元素。

不管是顺序栈还是带链的栈，在操作过程中其栈顶指针均是动态变化的。
顺序栈的栈底指针在操作中固定不变，带链栈的栈底指针在操作中是有可能改变的。

树的基本概念：树（ tree ）是一种非线性结构。在这种数据结构中，所有数据元素之间的关系具有明显的层次特点。

在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为根结点（简称根）。

在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点，没有后件的结点称为叶子结点。

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

在树结构中，所有结点中的最大的度称为树的度。

在树结构中，层数称为树的深度。

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

二叉树的基本概念：二叉树（ binary tree ）是一种非常用的非线性数据结构。二叉树与前面介绍的树结构不同，但它与树结构很相似，并且，有关树结构的所有术语都可以用到二叉树这种数据结构上。

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

在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。

满二叉树与完全二叉树是两种特殊的二叉树。

满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上。

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

显然，满二叉树也是完全二叉树，而完全二叉树不一定是满二叉树。

二叉树的基本性质：
（1）在二叉树中，第 i层的结点数最多为 2^（ i-1）个。 （ i>=1 ）
（2）在深度为 k的二叉树中，结点总数最多为 2^ k -1个。 （ k>=1 ）
（3）对任意一棵二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个。
（4）1.具有 n个结点的二叉树，其深度至少为[ log2 n ]+1，其中 [ log2 n ]表示取其整数部分。2.具有 n个结点的完全二叉树的深度为 [ log2 n ]+1。

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

二叉树的遍历：遍历是二叉树的重要运算，指按一定的次序访问二叉树中的每一个结点，使每个结点被访问一次且只被访问一次。

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

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

前序遍历：访问根结点的操作发生在遍历其左右子树之前。
中序遍历：访问根结点的操作发生在遍历其左右子树之中（间）。
后序遍历：访问根结点的操作发生在遍历其左右子树之后。

顺序查找：又称为顺序搜索，一般是指在线性表中查找指定的元素。
基本方法如下：从线性表的第一个元素开始，依次将相信表中的元素与被查找元素进行比较，若相等则表示找到（即查找成功）；若线性表中所有的元素都与被查找元素进行了比较，但都不相等，则表示线性表中没有要查找的元素（即查找失败）。

二分查找：只适用于顺序存储的有序表，即要求线性表中的元素按元素值的大小排列（递增排列或者递减排列）。假设有序线性表是按元素值递增排列的，并设表的长度为 n，被查元素为 x，则二分法查找过程如下：将 x与线性表的中间元素进行比较：
若等于，则说明查找成功，查找结束；
若小于，则在线性表的前半部分以相同的方法查找；
若大于，则在线性表的后半部分以相同的方法查找。
这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。

对于长度为 n的有序线性表，在最坏的情况下，二分查找只需要比较 log2n次，顺序查找需要比较 n次。

交换类排序法：
1.冒泡排序法：最简单的交换类排序法，它是通过相邻数据元素的交换逐步将线性表变成有序的。
基本操作如下：首先，从表头开始往后扫描线性表，在扫描过程中依次比较相邻两元素的大小，若前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后。然后，按相反的方向扫描剩下的线性表，在扫描过程中依次比较相邻两个元素的大小，若后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。显然，在扫描过程中，不断地将两个相邻元素中的小者往前移动，最后就将剩下的线性表中的最小者换到了表的最前面。此时，线性表的第一个元素就是最小者，最后一个元素就是最大者。对剩下的元素构成的线性表重复上述过程，直到剩下的元素为空或者在扫描过程中没有交换任何元素，此时，线性表变为有序。在最坏情况下，需要比较 n(n-1)/2 次*
2.快速排序法：是对冒泡排序法的改进，又叫分区交换排序法。
基本思想如下：从线性表中任意选取一个元素（通常选第一个元素），设为 T，将线性表的小于 T的元素移到 T的前面，而大于 T的元素移到 T的后面，结果就将线性表分成了两部分（称为两个子素）， T处于分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以 T为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于 T，而后面子表中的所有元素均不小于 T.在最坏情况下，需要比较 n(n-1)/2 次*

插入类排序法：
1.简单插入排序法：也叫直接插入排序法。插入排序是指无序序列中的各元素依次插入到已经有序的线性表中。在最坏情况下，需要比较 n(n-1)/2 次*
2.希尔排序法：又称缩小增量排序法，它对简单插入排序做了较大的改进。
其方法如下：将整个无序序列分割成若干小的子序列分别进行简单插入排序。子序列的分割方法如下：使相隔某个增量 h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当 h减到1时，进行一次简单插入排序，排序就完成。在最坏情况下，需要比较 o( n^1.5) 次

选择类排序法：
1.简单选择排序：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面。在最坏情况下，需要比较 n(n-1)/2 次*
2.堆排序法：在简单排序法的基础上借助于完全二叉树结构而构成的一种排序方法。在最坏情况下，需要比较 o(nlog2n) 次

程序设计基础

程序：将计算机语言代码依据一定的语法规则描述为完成特定任务的算法的指令序列。

程序设计：完成一项程序工作的过程。

计算机语言：人与计算机交流的工具。

算法+数据结构=程序 Wirth公式

计算机程序语言：机器语言、汇编语言、高级语言

编码风格：“清晰第一，效率第二”

源程序文档化：
（1）符号名的命名：反映它所代表的实际东西，应有一定的实际含义。
（2）程序的注释。分为序言性注释（模块的首部）和描述性注释/功能性注释（嵌在源程序体之中）。
（3）视觉组织。

数据说明：次序规范、变量安排有序化、使用注释来说明复杂数据的结构。

语句的结构：在一行内只写一条语句、优先考虑清晰性、在保证程序正确的基础上再要求提高效率、避免使用临时变量、避免不必要的转移、尽量使用库函数、避免采用复杂的条件语句、尽量减少使用否定条件语句、数据结构要有利于程序的简化、模块化、利用信息隐蔽，确保模块独立性、从数据出发去构造程序、不要修补不好的程序，要重新编写。

结构化程序设计：功能分解并逐步求精。
主要原则：自顶向下，逐步求精，模块化，限制使用 goto 语句。

结构化程序的基本结构：
分为顺序结构、选择结构、循环（重复）结构。

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

面向对象的程序设计主要考虑的是提高软件的可重用性。

对象是属性和方法的封装体。

对象的基本特点：
（1）标识唯一性：对象可区分，并且由对象的内在本质来区分；
（2）分类型：可以将具有相同属性的操作的对象抽象成类；
（3）多态性：同一个操作可以是不同的对象的行为；
（4）封装性：只能看到对象的外部特性，对象的内部（处理能力的实行和内部状态）对外不可见；信息隐蔽是通过对象的封装性来实现的。
（5）模块独立性好：高内聚、低耦合。

类是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象，对象是对应类的一个实例。

消息是一个实例与另一个实例之间传递的消息。

继承是指能够直接获得已有的性质和特征，而不必重复定义它们。分为单继承和多重继承。

方法：对象中的属性只能通过该对象所提供的操作来存取或修改。

类的继承性是类之间共享属性和操作的机制，它提高了软件的可重用性。

多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。

软件工程基础

软件的组成：机器可执行的程序和数据有关文档。

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

软件的特点：
（1）逻辑实体：不是物理实体，具有抽象性；
（2）其生产与硬件不同，没有明显的制作过程；
（3）在运行、使用过程中不存在磨损、老化问题；
（4）其开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题；
（5）复杂性高、成本昂贵；
（6）开发涉及诸多的社会因素。

软件工程概念的提出源自软件危机。软件危机可以归纳为成本、质量、生产率等问题。软件工程是试图用工程、科学和数学的原理与方法研制、维护计算机软件的有关技术及管理方法。

软件工程的主要内容：
（1）软件开发技术
（2）软件工程管理：3要素：方法、工具和过程。

软件工程过程：为获得软件产品，在软件工具的支持下由软件人员完成的一系列软件工程活动，是把输入转化为输出的一组彼此相关的资源和活动。

软件的生命周期：将软件产品提出、实现、使用、维护到停止使用退役的过程。

软件的生命周期分为定义、开发及维护三个阶段。
定义阶段：制定计划、需求分析（数据）
开发阶段：软件设计、软件实现、软件测试
运行维护阶段：软件投入运行，并在使用中不断地维护，进行必要的扩充和删改。

软件生命周期中所花费最多的阶段是 软件运行维护阶段。

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

软件工程研究的内容主要包括：软件开发技术和软件工程管理。
软件工程的原则：
（1）抽象：抽取事物最基本的特性和行为，忽略非本质细节。
（2）信息隐蔽：用封装技术，将程序模块的实现细节隐藏起来，使模块接口尽量简单。
（3）模块化：模块是程序中相对独立的成分。
（4）局部化：高内聚、低耦合。
（5）确定性：所有概念的表达应是确定的、无歧义且规范的。
（6）一致性：程序内外部接口应保持一致，系统规格说明与系统行为应保持一致。
（7）完备性：软件系统不丢失任何重要成分，完全实现系统所需的功能。
（8）可验证性：应遵循容易检查、测评、评审的原则，以确保系统的正确性。

软件工具主要包括需求分析工具、设计工具、编码工具、确认工具、维护工具等。

软件工程环境是全面支持软件开发全过程的软件工具集合。

结构化分析的常用工具：数据流图（ DFD ）、数据字典（核心）（ DD ）、判定表、判定树

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

作用：
（1）便于用户、开发用户进行理解和交流；
（2）反映出用户问题的结构，可以作为软件开发工作的基础和依据；
（3）作为确认测试和验收的依据。
内容：概述；数据描述；功能描述；性能描述；参考文献；附录。
特点：正确性；无歧义性（最重要）；完整性；可验证性；一致性；可理解性；可修改性；可追踪性。

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

从工程角度来看，软件设计分为概要设计（又称结构设计）和详细设计。

数据流的类型：变换型和事务型

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

软件测试的准则：
（1）所有测试都应追溯到需求；
（2）严格执行测试计划，排除测试的随意性；
（3）充分注意测试中的群集现象；
（4）程序员应避免检查自己的程序；
（5）穷举测试不可能；
（6）妥善保存测试计划、测试用例、出错统计和最终分析报告，为维护提供方便。

软件测试技术与方法：
从是否需要执行被测软件的角度，分为：静态测试和动态测试；
静态测试：人工评审软件文档或程序；
动态测试：在样板测试数据上执行程序并分析输出以发现错误。
按照功能划分，分为：白盒测试和黑盒测试。
白盒测试：看得见程序内部，测试内部结构和流程。也称结构测试/逻辑驱动测试。基本原则是验证所有内部数据结构的有效性。主要用于软件的单元测试。主要方法有逻辑覆盖、基本路径测试等。
黑盒测试：看得见程序外部，测试外部功能与特性。不考虑程序内部的逻辑结构和内部特性。主要用于软件的确认测试。主要方法有等价类划分法、边界值分析法、错误推测法和因果图等。

软件测试的实施：
（1）单元测试：对软件设计的最小单位-模块进行正确性检验的测试。目的是发现各模块内部可能存在的各种错误。依据是详细设计书和源程序。用白盒测试方法。
（2）集成测试：测试和组装软件的过程。目的是发现与接口有关的错误。依据是概要设计说明书。
（3）确认测试：验证软件的有效性，即验证软件的功能和性能及其他特性是否与用户的要求一致。依据是软件需求规格说明书。用黑盒测试方法。
（4）系统测试：通过测试确认的软件，作为整个基于计算机系统的一个元素，与计算机硬件、外设、支持软件、数据和人员等其他系统元素组合在一起，在实际运行（使用）环境下对计算机系统进行一系列的集成测试和确认测试。目的是通过与系统的需求定义进行比较，发现软件与系统定义不符合或与之矛盾的地方。依据是根据需求分析规格说明来设计。

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

软件的调试方法：
（1）强行排错法：传统的调试方法，其过程可以概括为：设置断点、程序暂停、观察程序状态、继续运行程序。使用较多、效率较低。涉及的调试技术主要是设置断点和监视表达式。
（2）回溯法：适用于小规模程序的排错。即一旦发现了错误，先分析错误征兆，确认最先发现症状的位置。然后，从发现症状的地方开始，沿程序的控制流程，逆向跟踪源程序代码，直到找到错误根源或确定错误产生的范围。
（3）原因排除法：通过演绎和归纳，以及二分法来实现。

数据库设计基础

数据（ data ）：描述事物的符号记录。

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

数据库管理系统（ database management system，简称 DBMS）：是数据库的机构，它是一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等。

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

数据库定义语言：负责数据的模式定义与数据的物理存取构建。
数据库操纵语言：负责数据的操纵，包括查询、增、删、改等操作。
数据库控制语言：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等功能。

数据库管理员（ database administrator，简称 DBA ）：管理数据库的规划、设计、维护、监视等。

数据库系统（ database system，简称 DBS）：数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、系统平台（硬件、软件）构成了一个以数据库为核心的完整的运行实体。

数据库应用系统（ database application system，简称 DBAS）：数据库系统加上应用软件及应用界面所组成。

数据库的发展：人工管理阶段、文件系统阶段、数据库系统阶段。

数据库系统的基本特点：
数据的集成性
数据的高共享性与低冗杂性

数据的独立性
物理独立性：数据的物理结构（存储结构、存取方式等）的改变都不影响数据库的逻辑结构，从而不致引起应用程序的变化。
逻辑独立性：数据库总体逻辑结构的改变，如修改数据模式增加新的数据类型改变数据间的联系等，不需要相应修改应用程序。

数据统一管理与控制：完整性检查、安全性保护、并发控制。

数据库系统的内部结构体系：

三级模式：
（1）概念模式：数据库系统中全局数据逻辑结构的描述，是全体用户（应用）公共数据视图。
（2）外模式：也称子模式或用户模式，是用户的数据视图，也就是用户所见到的数据模式，由概念模式推导而出。
（3）内模式：也称物理模式，给出了数据库物理存储结构与物理存取方法。对用户一般是透明的，但设计直接影响数据库的性能。

二级映射：
（1）概念模式/内模式的映射：实现了概念模式到内模式之间的相互转换。保证了数据具有很高的物理独立性。
（2）外模式/概念模式的映射：实现了外模式到概念模式之间的相互转换。保证了数据具有较高的逻辑独立性。

一个数据库只有一个概念模式、一个内模式，有多个外模式。

数据模型的基本概念：数据模型是数据特征的抽象，它从抽象层次上描述了系统的静态特征、动态行为和约束条件，为数据库系统的信息表示与操作提供一个抽象的框架，是数据库设计的核心。实体是指存在的并可相互区别的任何事物。属性是指实体代表的某特定事物所具有的某方面的特征。用计算机表示每一个实体时，由其所有信息项组成一条记录，相应于属性的数据称为数据项。实体内部的联系反映在数据上是数据项之间的联系，实体间的联系反映在数据上是记录间的联系。实体与属性有“型”与“值”之分，型是指结构，值是指结构约束下的具体取值。

数据模型所描述的内容有三个部分：数据结构、数据操作与数据约束。

数据模型按不同的引用层次分成三种类型：
概念数据模型（概念模型）：主要有 E-R模型（实体联系模型）、扩充的 E-R模型、面向对象模型及谓词模型等。

E-R模型（ entity-relationship model ）：实体是概念世界中的基本单位，是客观存在的且又能相互区别的事物。

联系是实体集间关系。有下面几种：一对一的联系（1：1）；一对多或多对一的联系（1：M或 M：1）；多对多联系（ M：N）

该模型可用图表示：实体集表示法、属性表示法、联系表示法。
逻辑数据模型（数据模型）：主要有层次模型、网状模型、关系模型、面向对象模型等。

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

物理数据模型（物理模型）：面向计算机物理表示。

关系中的数据约束：
（1）实体完整性约束：关系的主键中属性值不能为空值。
（2）参照完整性约束：关系之间相互关联的基本约束，不允许关系引用不存在的元组。
（3）用户定义的完整性约束：反映某一具体应用涉及的数据必须满足的语义要求。

关系的数据结构：关系可视为元组的集合。

集合运算及选择、投影、连接运算：
（1）并：将两个以上表的行并到一起，去除相同的行。
（2）差：在关系 R中减去 S有的行，保留的是 S中没有的行。运算的时候依次将两个表的一行一行相减。
（3）交：求两个以上表的公共行，前提是表的结构必须相同。
（4）笛卡尔积：行与行的重新组合。
（5）除法：行与行的重新拆分。

关系运算的三种操作：
（1）选择：从二维关系表的全部记录中，把那些符合指定条件的记录挑出来（选行）。
（2）投影：从所有字段中选取一部分字段及其值进行操作，是一种纵向操作（选列）。
（3）联接：将两个关系模式拼接成一个更宽的关系模式，生成的新关系中包含满足联接条件的元组。

数据库设计方法：以信息需求为主；以处理需求为主。

数据库设计阶段：需求分析阶段；概念设计阶段；逻辑设计阶段；物理设计阶段；编码阶段；测试阶段；运行阶段；进一步修改阶段。

在数据库设计中采用前四个阶段，并且重点以数据结构与模型的设计为主线。