栈与队列的共同点：
皆为线性结构，只允许在端点处插入与删除，而且不须移动其他元素。
考点6：
线性链表
线性表的链式存储结构称为线性链表
在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。
链式存储结构即可用于表示线性结构，也可用于表示非线性结构，栈与队列也可以采用链式存储结构。
★考点7：
二叉树的基本性质
树是典型的非线性结构，在树中，每个结点的前件称为父结点，没有父结点的只有一个，称为根结点（有且仅有一个）。
每个结点拥有的后件称为子结点，没有子结点的称为叶子结点。
一个结点所拥有的子结点的个数称为该结点的度，叶子结点的度为0。
树的最大层次称为树的深度。
二叉树：
每个结点最大的度为2，如下图所示
性质1：
在二叉树的第k层上，最多有2k-1个结点
性质2：
深度为m的二叉树最多有2m-1个结点
性质3：
在任意一棵二叉树中，度为0的结点（叶子结点）总是比度为2的结点多一个。
满二叉树：
每一层上的结点数都达到最大值，即第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点
完全二叉树：
除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。
当完全二叉树有n个结点，若n为偶数，则有n/2个叶子结点；若n为奇数，则有[n/2]+1个叶子结点（[]表示只取整数部分）。
★考点8：
二叉树的遍历
（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；
（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；
（3）后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。
考点9：
查找技术
对于长度为n的线性表：
顺序查找在最坏情况下，需要比较n次。
二分法查找只适用于顺序存储的有序表，在最坏情况下只需要比较log2n次。
考点10：
排序技术
在最坏情况下，对于长度为n的线性表，冒泡排序法、快速排序法、简单插入排序法、简单选择排序法都需要比较n（n-1）/2次；希尔排序法需要比较O（n1.5）次；堆排序法需要比较O（nlog2n）次。
在各种排序法中，冒泡排序法最简单，比较次数最少（通常少于n（n-1）/2次）。
第二章程序设计基础
考点1：
程序设计风格
主要风格：
清晰第一，效率第二
形成良好的程序设计风格应注重的因素：
1.源程序的文档化：
要包含必要的程序注释
2.数据说明的方法：
数据说明的次序规范化
3.语句的结构
4.输入与输出
考点2：
结构化程序设计的原则
1.自顶向下
2.逐步求精
3.模块化
4.限制使用goto语句
结构化程序设计的基本结构包括顺序结构、选择结构和循环结构。
考点3：
面向对象的基本概念
1、对象的特点：
标识唯一性、分类性、多态性、封装性（实现信息隐蔽）、模块独立性
2、类是具有共同属性、共同方法的对象的集合，类具有继承性
3、类与对象的关系：
类是对象的抽象，对象则是其对应类的一个实例
第三章软件工程基础
考点1：
软件的定义及特点
计算机软件是包括程序、数据及相关文档的完整集合。
软件的特点包括：
（1）软件是一种逻辑实体，而不是物理实体。
（2）软件的生产与硬件不同，它没有明显的制作过程；
（3）软件在运行、使用期间不存在磨损、老化问题；
（4）软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题；
（5）软件复杂性高，成本昂贵；
（6）软件开发涉及诸多的社会因素。
软件按功能可以分为：
应用软件、系统软件和支撑软件〔或工具软件〕。
考点2：
软件工程的定义
软件工程强调在软件开发过程中应用工程化原则
软件工程包括3个要素：
方法、工具和过程。
方法是完成软件工程项目的技术手段；工具支持软件开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理
考点3：
软件生命周期
1.定义阶段：
可行性研究、需求分析
2.开发阶段：
概要设计、详细设计、实现、测试
3.维护阶段：
使用、维护、退役
考点4：
结构化分析方法
1、结构化分析的常用工具
（1）数据流图（DFD）
源、潭
存储文件（数据源）
数据流
加工
（2）数据字典：
作用是对DFD中出现的被命名的图形元素的确切解释
（3）判定树
（4）判定表
2、软件需求规格说明书：
是需求分析阶段的最后成果。
其最重要的特点是无歧义性。
考点5：
结构化设计方法
1、软件设计的分类
从技术观点来看，软件设计包括软件结构设计、数据设计、接口设计、过程设计
从工程管理角度来看，软件设计分两步完成：
概要设计和详细设计
2、衡量软件模块独立性的两个标准
内聚性：
是一个模块内部各个元素间彼此结合的紧密程度的度量
耦合性：
是模块间互相连接的紧密程度的度量
在程序结构中，各模块的内聚性越强，则耦合性越弱。
优秀的软件设计应尽量做到高内聚、低耦合。
3、概要设计（软件结构设计）
概要设计的常用工具是结构图（SC）
结构图的有关术语：
1）深度：
结构图的最大层次数
2）宽度：
结构图横向上最大模块数
3）扇出：
一个模块拥有的下级从属模块的个数
4）扇入：
一个模块拥有的上级模块的个数
注意：
软件模块的规模要适中
4、详细设计（软件过程设计）
常用的过程设计工具有：
●图形工具：
程序流程图、N-S图、PAD图、HIPO图
●表格工具：
判定表
●语言工具：
PDL（伪代码）
程序流程图的基本图符
逻辑条件
加工步骤
控制流
考点6：
软件测试
1、软件测试的目的：
尽可能多的发现错误，而不是证明程序是否正确。
2、软件测试的准则
1）所有测试都应回溯到需求
2）严格执行计划，排除随意性
3）充分注意测试中的群集现象
4）程序员应避免检查自己的程序
5）穷举测试不可能
6）妥善保存测试计划
3、软件测试的方法
（1）静态测试：
包括代码走查、静态结构分析、代码质量度量等，可以由人工进行。
（2）动态测试：
是基于计算机的测试，设计合理的测试用例去运行程序，以便发现错误。
测试用例的格式为[（输入值集），{输出值集}]
常用的动态测试方法又分为：
●白盒测试：
针对软件程序内部逻辑结构进行测试，其基本原则是保证所测模块中每一独立路径至少执行一次。
白盒测试的主要方法有逻辑覆盖、基本路径测试。
●黑盒测试：
完全不考虑程序内部的逻辑结构和内部特性，只是对软件已经实现的功能是否满足需求进行测试，检查程序的功能是否符合它的功能说明。
黑盒测试方法主要有等价类划分法、边界值分析法、错误推测法、因果图等。
4、软件测试的实施
软件测试分4个步骤：
单元测试、集成测试、验收测试（确认测试）和系统测试
特别注意4个步骤的次序
考点7：
程序的调试（debug）
程序调试的任务是诊断和改正程序中的错误
程序调试的基本步骤：
1.错误定位
2.修改设计和代码，以排除错误
3.进行回归测试，防止引进新的错误
第四章数据库设计基础
考点1：
数据库系统的基本概念
（1）数据库设计的根本目标：
实现数据共享
（2）数据库管理系统（DBMS）：
是数据库系统的核心，是实现各种数据管理功能的核心软件。
是在操作系统支持下的系统软件。
数据库管理系统通过提供数据语言完成各项功能，主要包括：
●数据定义语言（DDL）：
负责数据的模式定义与数据的物理存取构建
●数据操纵语言（DML）：
负责数据的操纵，包括查询及增、删、改等操作
●数据控制语言（DCL）：
负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等功能
（3）数据库系统（DBS）
由五部分组成：
数据库、数据库管理系统、数据库管理员、硬件平台、软件平台
数据库系统需要操作系统（OS）的支持
考点2：
数据库系统的发展
分三个阶段：
人工管理、文件系统、数据库系统。
其中数据库系统阶段实现的数据共享程度最大，数据独立性最高。
考点3：
数据库系统的基本特点
（1）数据的集成性
如在关系数据库中采用二维表作为统一的结构方式。
（2）数据的高共享性与低冗余性
数据一致性是指在系统中同一数据的不同出现应保持相同的值。
（3）数据独立性
数据独立性是数据与程序间的互不依赖性，即数据库中数据独立于应用程序而不依赖于应用程序。
分为物理独立性和逻辑独立性。
◆物理独立性：
数据的物理结构（包括存储结构、存取方式等）的改变，不影响数据库的逻辑结构，从而不致引起应用程序的变化。
◆逻辑独立性：
数据库总体逻辑结构的改变，不需要相应修改应用程序。
（4）数据统一管理与控制
v数据的完整性检查
v数据的安全性保护
v并发控制
考点4：
数据库系统的内部结构体系
数据库系统具有三级模式：
（1）概念模式：
数据库系统中全局数据逻辑结构的描述，全体用户公共数据视图；
（2）外模式：
也称子模式与用户模式。
是用户的数据视图，也就是用户所见到的数据模式；一个概念模式可以推导出多个外模式。
（3）内模式：
又称物理模式，它给出了数据库物理存储结构与物理存取方法。
（如索引等）
考点5：
E-R模型
E-R模型的三个要素：
1.实体：
现实世界中的事物。
在E-R图中用矩形框表示。
2.属性：
事物的特性；在E-R图中用椭圆表示。
3.联系：
现实世界中事物间的关系。
在E-R图中用菱形框表示。
联系类型有3种：
1对1，1对多，多对多。
特别注意实体间联系的举例，如学校与校长、学生与宿舍、学生与课程等。
考点6：
关系模型的特点
关系模型采用二维表（也称为关系）表示，二维表中列称为属性，行称为元组，凡能惟一标识元组的最小属性集称为该表的键或码。
二维表应满足7个性质：
●二维表中元组个数是有限的—元组个数有限性
●二维表中元组均不相同—元组的惟一性
●二维表中元组的次序可以任意交换—元组的次序无关性
●二维表中元组的分量是不可分割的基本数据项—元组分量的原子性
●二维表中属性名各不相同—属性名惟一性
●二维表中属性与次序无关，可任意交换—属性的次序无关性
●二维表属性的分量具有与该属性相同的值域—分量值域的同一性
考点7：
关系运算（看图题）
●选择运算、投影运算、笛卡尔积运算×
●并运算∪、交运算∩、差运算—
●自然连接运算|×|
设有关系R与S
RS
A
B
C
1
2
3
4
5
6
7
8
9
A
B
C
4
5
6
7
8
9
10
11
12
R∪S（并运算）R∩S（交运算）
A
B
C
1
2
3
4
5
6
7
8
9
10
11
12
A
B
C
4
5
6
7
8
9
R–S（差运算）
A
B
C
1
2
3
设有关系R与S:
RS
R1
R2
R3
a
b
c
d
e
f
g
h
i
S1
S2
S3
j
k
l
m
n
o
p
q
r
R×S（笛卡尔积）
R1
R2
R3
S1
S2
S3
a
b
c
j
k
l
a
b
c
m
n
o
a
b
c
P
q
r
d
e
f
j
k
l
d
e
f
m
n
o
d
e
f
p
q
r
g
h
i
j
k
l
g
h
i
m
n
o
g
h
i
p
q
r
设有关系R与S:
RS
A
B
C
D
1
2
3
4
1
5
8
3
2
4
2
6
1
1
4
7
D
E
5
1
6
4
7
3
6
8
R|×|S（自然联接）
A
B
C
D
E
2
4
2
6
4
2
4
2
6
8
1
1
4
7
3
设有关系R，经过投影运算得到S
R
A
B
C
1
2
3
4
5
6
7
8
9
A
B
1
2
4
5
7
8
设有关系R，经过选择运算得到S
R
A
B
C
1
2
3
4
5
6
7
8
9
A
B
C
1
2
3
4
5
6
考点8：
数据库设计
数据库设计分四个阶段：
需求分析、概念设计、逻辑设计、物理设计
数据库逻辑设计的主要工作是将E-R图转换成指定RDBMS中的关系模式
E-R模型
关系
E-R模型
关系
属性
属性
实体集
关系
实体
元组
联系
关系
升级会员 