VF资料(公共基础).doc

第1章数据结构与算法1.1算法算法：是指解题方案的准确而完整的描述基 算法的基本特征：可行性、确定性、有穷性(有限的时间)、拥有足够的情报本 算法的 对数据对象的操作和运算：算术运算、逻辑运算、关系运算、数据传输概 基本要素 算法的控制结构 定义：算法中各操作之间的执行顺序念 类型：顺序、选择、循环 算法设计基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法算法 时间复杂度：算法所需要的计算工作量（算法所执行的基本运算次数）复杂度 空间复杂度：执行这个算法所需要的内存空间1.2数据结构的基本概念 逻辑结构：指反应数据元素之间逻辑关系的数据结构数据结构研究的三个问题 存储结构（物理结构）：数据的逻辑结构在计算机存储空间中的存放形式。（常用：顺序、链接、索引等结构） 对各种数据结构进行的运算数据处理 是指对数据集合中的各元素以各种方式进行运算 包括插入、删除、查找、更改等运算，也包括对数据元素进行分析在数据结构中没有前件的结点称为根结点，没有后件的结点为叶子结点。空的数据结构：一个元素都没有的数据结构。 定义：是指带有结构的数据元素的集合。 数据结构 类型 线性结构：有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件。 非线性结构1.3线性表及其顺序存储线性表是最简单、最常用的一种线性结构。 有且只有一个根结点，无前件非空线性表结构特征 有且只有一个终端（叶子）结点，无后件 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件线性表顺序存储结构的基本特点 所有元素所占的存储空间是连续的 各元素在存储空间中是按逻辑顺序依次存放的1.4栈和队列限定在一端进行插入与删除的线性表栈顶：允许插入与删除的一端栈 栈底：不允许插入与删除的一端 先进后出 或 后进先出 基本运算：入栈运算（上溢）、退栈运算（下溢）、读栈顶元素允许在一端进行插入、而在另一端进行删除的线性表 队尾：允许插入的一端 队中元素个数：队尾对头队 队头：允许删除的一端列 先进先出 或 后进后出 基本运算：入队运算、退队运算 循环队列：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间1.5线性链表线性表的链式存储结构称为线性链表栈和队列也可采用链式存储结构线性链表基本运算：插入、删除、合并、分解、逆转、复制、排序、查找1.6树与二叉树父结点：每一个结点只有一个前件，称为父结点。没有前件的结点只有一个，称为根。子结点：每一个结点可以有多个后件，这些后件称为子结点。没有后件的结点称为叶子结点。结点的度：一个结点所拥有的后件个数树的度：所有结点中的最大的度树的深度：树的最大层次根结点在第1层。叶子结点没有子树。特点：只有一个根结点，每一个结点最多有2颗子树（左子树、右子树） 在二叉树的第k层上，最多有2k-1（k=1）个结点 深度为m的二叉树最多有2m-1个结点二 性质 度为0的结点（叶子结点）是比度为2的结点多一个叉 具有n个结点的二叉树，其深度至少为log2n+1树 具有n个结点的完全二叉树，深度为log2n+1存储结构：链式存储结构 前序遍历：根左右遍历 中序遍历：左根右 后序遍历：左右根当完全二叉树总结点n为偶数时，叶子节点的个数为：n/2当完全二叉树总结点n为奇数时，叶子节点的个数为：(n+1)/21.7查找技术查 顺序查找： n（最坏）找 二分法查找：loag2n（最坏）1.8排序技术 交换类排序 冒泡排序法：n(n-1)/2（最坏） 快速排序法：n(n-1)/2（最坏） O(nlog2n)（平均）排 插入类排序 简单插入排序法：n(n-1)/2（最坏）序 希尔排序法：O(n1. 5)（最坏） 选择类排序 简单选择排序法：n(n-1)/2（最坏） 堆排序法：O(nlog2n) （最坏）第2章程序设计基础 程序设计风格：清晰第一，效率第二注释一般分为：序言性注释和功能性注释结构化程序设计的原则：自顶向下，逐步求精，模块化，限制使用 goto 语句结构化程序的基本结构：顺序结构、选择结构、重复结构（循环结构）面向对象方法的优点：与人类习惯的思维方法一致、稳定性好、可重用性好、易于开发大型软件产品、可维护性好对象：客观世界中的任何实体对象特点：标志唯一性、分类性、多态性、封装性、模块独立性好对象是类的一个实例。消息：是一个实例与另一个实例之间传递的信息，请求对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。在面向对象方法中，类之间共享属性和操作的机制称为：继承继承性的优点：相似的对象可以共享程序的代码和数据结构,从而大大减少了程序中的冗余信息,提高软件的可重用性,便于软件修改维护第3章软件工程基础软件：包括程序、数据及相关文档的完整集合软件按功能分为：应用软件、系统软件、软件软件工程概念的出现源自软件危机软件危机：是泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。软件危机归结为成本、质量、生产率等问题 方法：完成软件工程项目的技术手段。软件工程3要素 工具：支持软件的开发、管理、文档、生成。 过程：支持软件开发的各个环节的控制、管理。软件工程：是把输入转化为输出的一组彼此相关的资源和活动。 P(Plan)软件规格说明软件工程基本活动 D (Do)软件开发 C(Check)软件确认 A(Action)软件演进软件生命周期：将软件产品从提出、实现、使用维护到停止使用退役的过程。软件定义 可行性研究与计划制定：软件开发费用 需求分析：确定软件系统功能 软件设计 概要设计：软件开发方法（分析方法、设计方法、程序设计方法）软件生命周期 软件开发 详细设计 软件实现：软件开发工具 软件测试 软件运行和维护：花费时间最长付出较低的开发成本达到要求的软件功能软件工程基本目标 取得较好的软件性能开发的软件易于移植需要较低的维护费用能按时完成开发，及时交付使用软件工程研究 软件开发技术：软件开发方法学、开发过程、开发工具和软件工程环境。（主体内容：软件开发方法学） 软件工程管理：软件管理学、软件工程经济学、软件心理学。软件工程原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性、可验证性软件开发方法的保证 软件开发工具 软件开发环境：或称软件工程环境是全面支持软件开发全过程的软件工具集合。软件需求：是指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。需求分析的任务：发现需求、求精、建模和定义需求的过程需求分析的工作：需求获取、需求分析、编写规格需求说明书、需求评审 结构化分析方法：面向数据流的结构化分析方法、面向数据结构的Jackson方法、面向数据结构的结构化数据系统开发方法需求分析方法 面向对象的分析方法 （从需求分析建立的模型的特性来分，需求分析方法又分为：静态分析方法和动态分析方法）结构化分析方法：是使用数据流图(DFD)、数据字典(DD)、结构化英语、判定表、判定树等工具，来建立一种新的、称为结构化规格说明的目标文档。 加工（转换） 数据流图（DFD）：描述数据处理过程的工具。 数据流 结构化分析的常用工具 数据字典（DD）：结构化分析方法的核心。 存储文件 判定树 源，潭 判定表 以图形方式描述数据流图的加工逻辑，结构简单，易读易懂。定义：是需求分析阶段的最后成果，是软件开发中的重要文档之一。软件需 便于用户、开发人员进行理解和交流求规格 作用 反映出用户问题的结构，可以作为软件开发工作的基础和依据。说明书 作为确认测试和验收的依据。特点：正确性、无歧义性（最重要）、完整性、可验证性、一致性、可理解性、可修改性、可追踪性软件设计从技术观点看，软件设计包括软件结构设计、数据设计、接口设计、过程设计软件设计从工程管理角度看，软件设计分两步完成：概要设计和详细设计软件设计的基本原理抽象、模块化 、信息隐蔽、模块独立性 衡量软件独立性依据：耦合性（是模块间互相连接的紧密程度的度量）内聚性（是一个模块内部各个元素间彼此结合的紧密程度的度量）优秀的软件设计应做到“高内聚，低耦合”。与结构化需求分析方法对应的是结构化设计方法。典型的数据流类型有两种：变换型和事务型。 目的：是为了发现错误而执行程序的过程 所有测试都应追溯到需求严格执行测试计划，排除测试的随意性准则 充分注意测试中的群集现象程序员应避免检查自己的程序穷举测试不可能：测试只能证明程序中有错误，不能证明程序中没有错误妥善保存测试计划、测试用例、出错统计和最终分析报告，为维护提供方便 是否需要执行被侧软件 静态测试 软件测试 动态测试：关键是设计设计高效合理的测试用例（输入值集，输出值集）方法 也称结构测试或逻辑测试 白盒测试 基本原则：保证所侧模块中每一独立路径至少执行一次（穷举路径测试）功能划分 方法：逻辑覆盖测试（语句、路径、判定、条件、判断条件覆盖）、基本路径测试 也称功能测试或数据驱动测试黑盒测试 只检查程序功能是否按照需求规格说明书的规定正常使用 方法：等价类划分法、边界值分析法、错误推测法、因果图 单元测试：目的是发现各模块内部可能存在的各种错误过程 集成测试：是测试和组装软件的过程 确认测试：任务是验证软件的功能和性能及其他特性是否满足了需求规格说明中确定的各种需求 系统测试 任务：诊断和改正程序中的错误（主要在开发阶段）程序调试 基本步骤：错误定位、修改设计和代码，以排除错误、进行回归测试，防止引进新的错误 方法：强行排错发、回溯法、原因排除法第4章数据库设计基础数据：是描述事物的符号记录。有型和值之分。数据库(DB)：数据的集合数据库中的数据具有“集成”、“共享”的特点。数据库管理系统(DBMS)：是一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等。 是数据库系统的核心，位于用户和操作系统（OS）之间。DBMS功能：数据模式定义、数据存取的物理构建、数据操纵、数据的完整性、安全性定义与检查、数据库的并发控制与故障恢复、数据的服务。 数据定义语言（DDL）：负责数据的模式定义与数据的物理存取构建。数据语言 数据操纵语言（DML）：负责数据的操作，包括查询及增、删、改等操作。 数据控制语言（DCL）：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等功能。数据库管理员（DBA）：数据库设计、数据库维护、改善系统性能，提高系统效率。数据库系统（DBS）：数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、硬件平台（硬件）、软件平台（软件）数据库应用系统（DBAS）：是数据库系统再加上应用软件及应用界面这三者所组成。数据库管理经历阶段：人工管理阶段、文件系统阶段、数据库系统阶段数据的集成性 数据的高共享性与低冗余性数据库系统基本特点 数据独立性 物理独立性 逻辑独立性 数据统一管理与控制 概念模式：全体用户（应用）公共数据视图 三级模式 外模式：子模式（用户模式）。用户的数据视图数据库系统 内模式 ：物理模式 二级映射 概念模式到内模式的映射 外模式到概念模式的映射数据模型描述的内容：数据结构、数据操作、数据约束数据模型按不同的层次分为：概念数据模型、逻辑数据模型、物理数据模型实体：现实世界中的事物可以抽象成为实体基本概念 属性：事物的特性ER模型 联系：现实世界中事物之间的关联(实体联系) 实体集表示法：矩形图示法 属性表示法：椭圆形 联系表示法：菱形定义：用二维表来表示 投影关系模型 数据查询 选择 数据操纵 数据删除 笛卡尔积 (基本运算) 数据插入数据修改 交运算扩充运算 除运算 连接与自然连接运算 实体完整性约束关系中的数据约束 参照完整性约束 用户定义的完整性约束 定义：是数据库应用的核心，重点：需求分析、概念设计、逻辑设计数据库设计 需求分析阶段 方法：集中式模式设计法、视图集成设计法 概念设计阶段 选择局部应用 逻辑设计阶段 过程 视图设计：自顶向下、由底向上、由内向外 一般采用生命周期法 物理设计阶段 视图集成：