一 公共基础
第一章数据结构
1.1算法
1.算法是指解题方案的准确而完整的描述
2.算法的特征：可行性、确定性、有穷性、拥有足够的情报
算法的确定性，是指算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性。 算法的有穷性，是指算法必须能在有限的时间内做完，即能在执行有限个步骤后终止
3. 算法控制结构主要有顺序、选择和循环三种控制结构 4. 算法的复杂度主要包括时间复杂度和空间复杂度
5. 算法时间复杂度并不是指执行算法程序所需要的时间，而是指执行算法所需要的计算工作量，可以用算法
在执行过程中所需基本运算的执行次数来度量算法的工作量， 6. 算法的空间复杂度是指执行这个算法所需要的内存空间 7.时间复杂度和空间复杂度没有直接联系
1.2数据结构的基本概念
1.数据结构分为逻辑结构和物理结构，物理结构也被称为存储结构
2. 逻辑结构是指反映数据元素之间逻辑关系的数据结构，数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称为数据的物理结构）。
3.在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息 4. 一种数据的逻辑结构根据需要可以表示成多种存储结构
5.在实际进行数据处理时，各数据元素在计算机存储空间中的位置关系与它们的逻辑关系可能相同也可能不同。
6.存储结构影响数据处理的效率，采用不同的存储结构，其数据处理的效率是不同的；影响数据处理效率的因素不是只有存储结构
7.数据的逻辑结构分为线性结构和非线性结构，线性结构有线性表、栈和队列；非线性结构有树、二叉树、完全二叉树和满二叉树。 1.3线性表
1.线性表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件 2.线性表的顺存储称为顺序表，链式存储称为线性链表，链式存储主要有线性链表、双向链表和循环链表，链式存储需要存放指针，因此顺序存储比链式存储节省存储空间。
1.4栈和队列
1.栈实际上也是线性表，在栈中其插入与删除运算都只在线性表的一端进行。 2.栈是限定在一端进行插入与删除的线性表。允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。
3.栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后被删除的元素。 4.栈按照“先进后出”（FILO）或“后进先出”（LIFO）原则组织数据，栈具有记忆作用。 5.栈可以顺序存储也可以链式存储
6. 栈的插入（入栈）和删除（退栈）运算不需要改变栈底指针，只需要改变栈顶指针。 7.栈是线性结构，带链的栈是线性结构
8.队列是指允许在一端进行插入，而在另一端进行删除的线性表。 9.队列中允许插入的一端称为队尾，通常用一个称为尾指针(rear)的指针指向队尾，即尾指针总是指向最后被插入的元素；允许删除的一端称为排头，通常用一个排头指针(front)指向排头元素的前一个位置。 10.在队列中，最先插入的元素将最先被删除，最后插入的元素将最后才能被删除。队列是“先进行出”（FIFO）
或“后进后出”（LILO）的线性表。
11.队列是线性结构，带链的队列是线性结构 12.队列可以顺存储也可以链式存储。
13循环队列是存储结构，循环队列是顺序存储 14循环队列是线性结构；
15.循环队列中队头指针与队尾指针都会变化； 1
16．循环队列中队头指针可以大于队尾指针，也可以小于队尾指针。
1.6树与二叉树
1.树是非线性结构、二叉树是非线性结构、只有根接点的的二叉树是非线性结构 2在二叉树的第k层上，最多有2k-1(k≥1)个结点； 3深度为m的二叉树最多有2m -1个结点；
4二叉树中度为0的结点（即叶子结点）总是比度为2的结点多一个
1.7查找技术
1. 二分法查找只适用于顺序存储的有序表
2. 对于长度为n的有序线性表，顺序查找在最坏情况下需要比较n次，二分法查找最坏情况只需比较log2 n次。
1.8排序技术 排序分类 排序方法 最坏情况下比较次数 冒泡排序法 交换类排序法 快速排序法 n(n-1)/2 简单插入排序法 插入类排序法 希尔排序法 O(n1.5) 简单选择排序法 n(n-1)/2 选择类排序法 堆排序法 O(nlog2n) 第二章程序设计基础 2.1程序设计方法和风格
1.“清晰第一，效率第二”的论点已成为当今主导的程序设计风格。 2.要形成良好的程序设计风格，主要应注重和考虑下述一些因素
（1）符号名的命名应具有一定含义，以便于对程序功能的理解。
（2）程序注释可帮助读者理解程序。程序注释分为序言性注释和功能性注释。 （3）视觉的组织：可以利用空格、空行、缩进等技术使程序能够一目了然。 （4）在编写程序时，程序中的数据说明更易于理解和维护；
（5）程序应该简单易懂，语句构造应该简单直接，不应该为提高效率而把语句复杂化； （6）在一行只写一条语句；
（7）编写程序时应优先考虑清晰性；
（8）除非对效率有特殊要求，程序编写要做到清晰第一，效率第二； （9）要模块化，模块功能尽可能单一化；
（10）利用信息隐蔽，确保每一个模块的独立性。
（11）输入和输出的方式和格式应尽可能方便用户的使用。 （12）数据输入前最好有提示信息
2.2结构化程序设计
1.结构化程序设计方法的主要原则是自顶向下，逐步求精，模块化，限制使用goto语句 2. 结构化程序设计的三种基本控制结构顺序、选择和重复
2.3面向对象程序设计
1.对象由一组表示其静态特征的属性和他可执行的一组操作组成（动态属性也被称为方法），对象是属性和方法的封装体
2. 类是具有共同属性、共同方法的对象的集合，对象则是其对应类的一个实例 3.对象的特点是唯一性、分类性、多态性、封装性、模块独立性好 4. 对象封装实现了信息隐蔽、信息隐蔽确保了模块独立性 5. 消息是一个实例与另一个实例之间传递的信息
6. 在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送消息 7.继承是类之间共享属性和操作的机制
第三章软件工程 3.1软件工程基本概念
1. 算机软件(SoftWare)是包括程序、数据及相关文档的完整集合 2. 程序就是软件的观点是不正确的
2
3.软件是一种逻辑实体，而不是物理实体，具有抽象性 4. 软件在运行、使用期间不存在磨损、老化问题
5.软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制。 6. 软件按功能可以分为：应用软件、系统软件、支撑软件（或工具软件）
7. 应用软件：主要有事物处理软件，工程与科学计算软件，实时处理软件，嵌入式软件，人工智能软件 8. 系统软件：主要有操作系统，编译程序，汇编程序，网络软件，数据库管理系统等
9.支撑软件：主要有需求分析工具软件，设计工具软件，编码工具软件，测试工具软件，维护工具软件等 10. 软件危机主要表现在：
（1）.软件需求的增长得不到满足。用户对系统不满意的情况经常发生。
（2）.软件开发成本和进度无法控制。开发成本超出预算，开发周期大大超过规定日期的情况经常发生。 （3）.软件质量难以保证。
（4）.软件不可维护或维护程度非常低。 （5）.软件的成本不断提高。
（6）.软件开发生产率的提高赶不上硬件的发展和应用需求的增长。
11软件工程的主要思想都是强调在软件开发工程中需要应用工程化的原则。 12. 软件工程包括3个要素，即方法、工具和过程。 13. 方法是完成软件工程项目的技术手段。 14.工具支持软件的开发、管理、文档生成。
15.过程支持软件开发的各个环节的控制、管理。 16. 总体设计阶段要承担软件功能分解的任务。
17. 软件交付使用后，生命周期并没有结束，还要进行不断维护。软件维护并不是简单地指修复程序中被破坏
的指令
18. 软件开发环境或称软件工程环境是全面支持软件开发全过程的软件工具集合
19. 软件工程的基本原则包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性
3.2结构化分析方法
1 需求分析确定“系统必须做什么”以及目标系统必须具备哪些功能和性能。 2 需求分析阶段的工作可以概括为四个方面：（1）需求获取（2）需求分析（3）编写需求规格说明书（4）需求评审。
3. 结构化分析工具是数据流图（DFD）、数据字典（DD）、结构化英语、判定表和判定树等 4. 数据流图（DFD）中箭头表示数据的流向
5. 数据字典的作用是对DFD（数据流图）中出现的被命名的图形元素的确切解释 6. 数据字典是结构化分析方法的核心
7. 软件需求规格说明书是需求分析阶段的最后成果，是软件开发中的重要文档之一。
3.3结构化设计方法
1. 从技术观点来看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。 2. 从工程管理角度来看，软件设计分两步完成，概要设计和详细设计。
3. 每个模块的功能不是越多越好，每个模块完成一个特定的子功能，做到模块功能单一化 4. 模块规模不是越大越好，也不是越小越好；要求做到规模适中 4. 信息隐蔽是指，在一个模块内包含的信息（过程或数据），对于不需要这些信息的其他模块来说是不能访问
的。
5. 衡量软件的模块独立性使用耦合性和内聚性两个定性的度量标准。 6. 内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量 7. 耦合性是模块间互相连接的紧密程度的度量
8. 耦合性与内聚性是模块独立性的两个定性标准，耦合与内聚是相互关联的。在程序结构中，各模块的内聚
性越强，则耦合性越弱
9. 一般较优秀的设计，应尽量做到高内聚、低耦合
10. 常用的软件结构设计工具是结构图（SC—Structure Chart），也称程序结构图 11. 典型的数据流类型有两种：变换型和事务型。
12常见的过程设计工具有图形工具：程序流程图，结构化程序的流程图N-S, 问题分析图PAD,HIPO；表格工
具：判定表；语言工具：过程设计语言PDL（伪码）
3
13.程序流程图（PFD）箭头代表的是控制流
3.4软件测试
1. 以尽可能多的发现软件中潜在的错误为软件测试的目的。 2. 测试不是使程序运行结果正确，也绝不能证明程序是正确的
3. 测试不能证明软件中没有错误，也不是来确定程序中错误的位置 4. 所有测试都应追溯到需求
5. 严格执行测试计划，排除测试随意性 6. 充分注意测试中的群集现象 7. 程序员应避免检查自己的程序 8. 穷举测试不可能
9. 测试只能证明程序中有错误，不能证明程序中没有错误 10. 从是否需要执行被测试软件的角度，可以分为静态测试方法和动态测试方法。其中动态测试按照功能又可
以分为白盒测试方法和黑盒测试方法。 11. 测试用例包括输入值集和输出值集
12. 黑盒测试方法主要有等价类划分法、边界值分析法、错误推测法、因果图等，主要用于软件确认测试。 13. 软件测试过程一般按4个步骤进行，即单元测试、集成测试、验收测试（确认测试）和系统测试。
3.5程序的调试
1. 在对程序进行了成功的测试之后将进入程序调试（通常称Debug,即排错）。 2. 程序调试的任务是诊断和改正程序中的错误。
3. 程序调试的基本步骤：错误定位?修改设计和代码，以排除错误?进行回归测试，防止引进新的错误 4. 程序调试完毕后要进行回归测试
第4章 数据库设计基础 4.1数据库基础知识
1. 数据库技术的根本目标是解决数据的共享问题。
2. 数据库管理系统（Database Management System,简称DBMS）是一种在操作系统支持下的系统软件 3. 数据库管理系统是数据库系统的核心软件
4. 数据定义语言（Data Definition Language 简称DDL）负责数据的模式定义与数据的物理存取构建
5. 数据操纵语言（Data Manipulation Language 简称DML）负责数据的操纵，包括查询及增、删、改等操作 6. 数据控制语言（Data Control Language 简称DCL）言负责数据完整性、安全性的定义与检查以及并发控
制、故障恢复等功能。
7. 数据库系统的运行离不开操作系统，需要操作系统支持
8. 数据管理发展至今已经经历了三个阶段：人工管理阶段、文件系统阶段和数据库系统阶段，其中数据库系统
阶段数据独立性最高，数据共享性最好。
9. 数据一致性是指在系统中同一数据的不同出现应保持相同的值
10. 数据独立性是数据与程序的互不依赖性，并不是数据与程序的独立存放 11. 数据独立性一般分为物理独立性与逻辑独立性两级。
12. 物理独立性：物理独立性即是数据的物理结构（包括存储结构、存储方式等）的改变，如存储设备的更换、
物理存储的更换、存取方式改变等都不影响数据库的逻辑结构，从而不致引起应用程序的变化。
13. 逻辑独立性：数据库总体逻辑结构的改变，如修改数据模式、增加新的数据类型、改变数据间联系等，不
需要相应修改应用程序，这就是数据的逻辑独立性 。
14. 数据库系统在其内部具有三级模式及二级映射，三级模式分别是概念级模式、内部级模式与外部级模式，
二级映射则分别是概念级到内部级的映射以及外部级到概念级的映射 15. 外模式也称子模式或用户模式, 是用户所见到的数据模式 16. 数据库设计中反映用户对数据要求的模式是外模式
4.2数据模式
1. 在E-R图中用矩形表示实体（集）、椭圆形表示属性、菱形表示联系 2. 按数据的组织形式，数据模型分为层次模型、网状模型、关系模型 3. 层次模型用树形结构表示实体和实体之间的联系
4. 关系模型采用二维表(关系)来表示实体和实体之间的联系 5. 在关系模型中每一个二维表就是一个关系
4
6. 在二维表中行称为元组，列被称为属性
7. 二维表中元组的分量是不可分割的基本数据项 8. 关系模式允许定义三类数据约束，它们是实体完整性约束、参照完整性约束以及用户自定义的完整性约束，其中前两种完整性约束由系统自动支持。
4.4 数据库设计与管理
1. 数据库设计是数据库应用的核心
2. 数据库设计步骤：需求分析?概念设计?逻辑设计?物理设计。
3. 从E-R图向关系模式转换中实体与联系都表示成关系，E-R图中属性转换成关系的属性，实体集也转换成关系。
二 ACCESS数据库程序设计
第一章 数据库基础知识
1. 数据处理的三个阶段：人工处理、文件系统、数据库系统，其中数据独立性最高，共享性最强的阶段是数据库系统阶段
2. 数据库系统的核心：数据库管理系统
3. 数据模型：按数据的组织形式数据模型分为：层次模型、网状模型、关系模型 层次模型：用树形结构表示实体和实体之间的联系 网状模型：用无向图结构表示实体和实体之间的联
关系模型：用二维表/关系结构表示实体和实体之间的联 4. ACCESS支撑关系模型 5. 关系就是二维表
6. 关系中垂直方向的列称为属性：水平方向的行称为元组
7. 关系中其值能够唯一标识一个实体的属性或属性的组合称为关键字 8. 属性不是本表的关键字但是其他表的关键字，称为外部关键字 9. 表中每个属性分量必须是不可分割的 10. 专门关系运算是选择、投影、连接
选择: 从关系中筛选出满足条件的元祖组成新的关系 投影: 从关系中指定若干属性组成新的关系 联接：两个表按照某个条件组成新的关系
等值联接：两个表按照某些字段相等为条件进行的连接 自然联接：去掉重复属性的等值连接
11. ACESS的七个对象：表、查询、窗体、报表、页、宏、模块 表：数据库的基础和核心
查询：数据库设计目的的体现 窗体：用于设计输入界面
报表：用于打印输出数据库中的数据
页：将数据库中数据发布到internet网上的数据库对象 12 . ACCESS特点
1. 可以保存多种数据，包括多媒体数据
2. ACCESS具备了程序设计的能力，可以通过编写应用程序来操作数据库中数据 3. 支持Internet/Intranet应用
4. 做为关系数据模型支持客户机/服务器应用系统 13、实体之间的联系
一对一：两个实体集A和B，A中一个实体可以和B中一个实体相对应，反之亦然，则A与B之间的联系
为一对一的联系。
一对多（多对一）：两个实体集A和B，A中一个实体可以和B中多个实体相对应，但是B中一个实体可以
和A中一个对应。
多对多：两个实体集A和B，A中一个实体可以和B中多个实体相对应，反之B中一个实体可以和A中多
个实体对应。
5