一 数据库系统的三级模式结构由外模式、模式和内模式组成

外模式，单个用户使用的数据视图 或用户所见的数据模式

模式，或逻辑模式：是数据库中对全体数据的逻辑结构和特性的描述

内模式：物理存取方式的描述,索引属于内模式

二 设计使用的工具

详细设计使用的工具主要有：程序流程图，N-S图，PAD，HIPO

需求分析阶段常用工具有：数据流图（DFD）、数据字典（DD）、判定树和判定表等

数据流图表示： 加工（转换） 数据流 存储文件（数据源） 源，潭

在数据库设计中，将E-R图转换成关系数据模型的过程属于逻辑设计阶段

关系：是将E-R图转换为关系模式时,实体和联系,E-R图进行的是概念设计

在E-R图中用矩形表示实体集，用椭圆形表示属性，用菱形表示联系。

程序流程图也称为程序框图，箭头表示控制流，矩形表示加工步骤，菱形表示逻辑条件

用方框图来代替传统的程序流程图，通常也把这种图称为N-S图

三 线性结构与非线性结构

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

注意：线性结构包括：线性表，队列，栈

非线性结构包括：树、图、二叉树

线性结构元素之间存在一对一关系

非线性结构元素之间存在一对多关系

特点是：（1）线性表采用顺序存储，顺序存储结构的存储一定是连续的

（2）线性表采用链式存储（便于插入和删除）链式存储结构的存储空间不一定是连续的，线性链表是线性表的链式存储结构，进行插入和删除时，不需要移动表中的元素

单链表中增加头结点的目的是方便运算实现

四 树与二叉树

树是一种简单的非线性结构

二叉树的基本性质

性质1：在二叉树的第K层上，最多有2K-1（K>=1）个结点

性质2：在深度为m的二叉树最多有2m-1个结点

性质3:在二叉树中，叶子结点的个数等于度为2的结点数+1

性质4：满二叉树中，最后一层叶子结点的个数为2x-1

性质5：完全二叉树：求根结点：INT（总结点/2） 叶子结点：总结点-根结点

五 二叉树的遍历

概念：是指不重复的防问二叉树中的所有结点

根据防问要结点的次序：前序遍历，中序遍历，后序遍历

前序遍历：根→左→右

中序遍历：左→根→右

后序遍历：左→右→根

六 栈和队列

栈：是限定在一端进行插入与删除的线性表，插入与删除的一端叫做栈顶，不能插入与删除的一端叫做栈底，不含有元素的栈叫做空栈

特点：（1）栈是按照先进后出或后进先出组织数据

（2）栈具有记忆作用

（3）对栈的插入与删除操作不需要改变栈底指针

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

队列：一端进行插入另一端进行删除的线性表，允许队尾插入，队头删除，是一种顺序的存储结构

特点：（1）先进先出或后进后出线性表，体现先来先服务的原则

栈和队列的共同点是：只允许在端点处插入和删除元素

注意：计算栈或队列包含元素，如果从0开始，公式为底- 顶+1; 未说情况下默认从1开始，公式底-顶

例：有一件长度为50的数组，下标从0到49，现栈顶30，栈底49,有（ ）个元素

循环队列中元素的个数是由队头指针和队尾指针共同决定

七 软件是指程序、数据与相关文档的完整集合

软件生命周期：包括软件定义，软件开发，软件运行维护

其中软件开发阶段的任务中软件设计阶段可分解成概要设计阶段和详细设计阶段

软件生命周期中详细设计属于开发阶段

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

软件危机归结为成本高、质量难控制、生产率低

软件设计一般分为总体设计和详细设计两个阶段

总体设计的任务是确定软件的总体结构，定义需求并建立系统模型。详细设计的任务是确定每一模块实现的定义，包括数据结构、算法和接口。

软件功能设计属于总体设计阶段

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

在软件开发中，需求分析阶段产生的主要文档是软件需求规格说明书，任务是软件的功能

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

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

九 软件测试

白盒测试是路径的集合

黑盒测试也称为功能测试或数据驱动测试,是对软件已经实现的功能是否满足需求进行测试和验证

确认测试：检查软件功能是否满足需求规格说明书中的需求

单元测试:对软件设计的最小单位--模块（程序单元）进行正确性检验的测试。

十 在长度为n的顺序存储的线性表中删除一个元素，最坏情况下是删除第一个元素，需要移表中的元素个数为n-1