一、公共基础知识算法：对解决方案准确而完整的描述复杂度包括时间复杂度和空间复杂度时间复杂度执行算法所需要的计算工作量空间复杂度................................内存空间数据结构：相互有关联的数据元素的集合=数据的组合形式分类：逻辑结构存储结构影响程序执行的效率数据结构中各数据元素之间前后关系的复杂程度分线性结构非线性结构一个非空的数据结构满足有且只有一个根结点，且每个结点最多有一个直接前驱或直接后继。插入/删除任一结点还是线性线性表：有限数列。同一表中数据元素相同特性。逻辑上相邻物理上也相邻。顺序存储结构适合元素不常变动的线性表。栈：插入和删除运算都只在线性表的一端进行的线性表。栈顶top栈底bottom特点：顶最后插入元素，最早删除；记忆功能；不需移动其他元素;指针反映元素变化情况基本运算：入栈运算退栈读栈顶元素队列;先进先出线性链表线性表的链式存储结构二叉树：非线性结构有限的结点集合。或空或一个根结点及其两棵互不相交的左右二叉子。满二叉树k层2^k-1深度m有2^m-1结点完全二叉树每层最大值最后层缺少右边的满二叉树<完全二叉树0°结点-2°结点=1链式存储结构=二叉链表左指针右指针遍历：不重复的访问二叉树中所有结点前序DLR中序LDR后序LRD前中后中顺序查找：线性表中查找指定元素比较n/2次时间复杂度o(n)仅此的程序：排列无序链式存储结构二分查找：顺序存储结构线性表是有序表（小→大，允许相邻元素相等）eg有序线性表n次；log2的n次排序方法概念基本思想复杂度交换类排序法：冒泡前→后n/2后→前n/2；n（n-1)/2次数量级n²；快速逐个分割表插入类............：简单插入分为有序表+无序表和冒泡一样每次比较最多移掉一个无序表；希尔把序列分割成若干子序列并分别插入排序效率与增量序列有关选择类............：简单选择一样；堆O（n倍log2的n）程序设计基础模块设计低耦合高内聚原则上→下逐步求精模块化限制goto。基本结构：顺序选择循环面向对象的基本概念对象;表示客观世界中任何实体特点;标识唯一性分类性多态性封装性类：共同属性、共同方法的对象的集合实例：一个具体对象则是其对应类的一个实例消息：一个实例与另一实例传递的信息继承：使用已有的类定义作为基础建立新类的定义方法面向对象方法的重要特性封装性继承性多态性软件工程基础软件：与计算机有关的计算机程序、规程、规则以及可能有的文件、文档及数据特点：抽象性无明显制作过程无磨损老化对计算机有依赖性复杂性高成本昂贵软件工程的目标：在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性开发工具：初期的单项工具→集成工具开发环境：全面支持软件开发过程的软件工具集合CASE计算机辅助软件工程需求分析：用户对目标软件系统在功能、行为、性能、设计约束等的期望。需求获取、需求分析、编写需求规格说明书、需求评审。结构化分析方法+面向对象分析方法数据流图：交换流数据流；变换型事务型数据字典：数据流数据项数据存储数据加工注：数据存储静止数据流运动；概要设计任务：设计软件系统结构数据结构及数据库设计编写概要设计文档概要设计文档评审准则：模块独立性规模适中作用域<控制域降低模块之间接口复杂程度设计单入口、单出口的模块模块功能应该可以预测工程管理角度，软件设计=概要设计+详细设计软件测试目的：发现错误而执行程序准则：所有测试追溯到用户需求；严格执行测试计划，排除测试的随意性；注意测试中的群集现象；穷举测试不可能实施白盒测试=结构测试=逻辑驱动，根据程序内部逻辑设计测试用例逻辑覆盖基本路径黑盒测试=功能测试=数据驱动，........规格说明书的功能等价类似边界值分析因果图实施过程：单元测试集成测试确认测试系统测试程序调试任务：诊断、改正程序中的错误程序调试方法：静态：人的思维分析源程序代码和排错。动态辅助软件调试方法：强行排错、回溯法、原因排除法数据库设计基础数据（Data）：描述事物的符号记录数据库（DB）：长期存储在计算机内的、有组织的、可共享的数据集合数据库系统：数据库、数据库管理系统（软件管理员）、计算机硬件、操作系统及数据库数据库管理系统主要类型：文件管理系统层次数据库系统网状..关系..功能：数据组织、数据操纵、数据维护、控制及保护、数据服务数据库技术发展3阶段：人工管理阶段、文件系统、数据库系统基本特点：数据集成性、数据的高共享性与低冗余性、数据独