数据结构和算法.ppt

全国计算机二级考试公共基础部分考点分析数据结构与算法程序设计基础软件工程基础数据库设计基础 第一部分数据结构与算法一 算法重点考点1 算法的概念 记忆 算法是指解决问题方案的准确而完整的描述 2 算法的基本特征 记忆 可行性 确定性 有穷性 拥有足够的情报3 算法的控制结构 记忆 顺序 选择 分支 循环 4 算法设计的两种重要方法的比较 理解 记忆 递推 从已知条件出发 逐次推出中键结果和最后结果 递归 将问题逐层分解 解决简单问题 再朝逆方向综合 递归算法要比递推算法清晰易读 且易设计 但执行效率低5 算法复杂度时间复杂度 是指执行算法所需要的计算工作量 空间复杂度 是指执行算法所需要的内存空间 存储空间包括 算法程序所占空间 输入原始数据所占空间执行算法时需要的额外空间 如果额外空间是常量 则称该算法是 原地工作 二 数据结构的考点1 数据结构的概念数据的逻辑结构 指反应数据元素之间逻辑关系的数据结构 数据的存储结构 物理结构 指数据的逻辑结构在计算机中的存储形式 数据的逻辑结构可以表示成多种存储结构 有顺序 链接索引等 不同的存储结构 数据处理的效率不同 2 数据结构的两大类型A 线形结构和非线形结构的基本概念非空的数据结构 满足下列条件则为线形结构 又称线性表 1 有且只有一个根结点 2 每个节点最多有一个前件 也最多有一个后件 B 线形表的顺序存储结构是计算机中存储线形表的最简单的方法 两个基本特点 1 线形表中所有元素所占的空间都是连续的 2 线形表中各数据元素在存储空间中是按逻辑顺序依次存放的 3 栈及基本运算 1 栈的概念 栈是限定在一端插入与删除的线形表 允许插入和删除端为栈顶 另一端为栈底 即满足 先进后出 的原则 FILO或LIFO 后进先出 2 栈的基本运算入栈 插入元素出栈 删除元素读栈 把栈顶元素赋给一个变量 4 队列队列是允许在一端 队尾 进行插入 而在另一端 队头 进行删除的线形表 特点 先进先出 FIFO或 后进后出 LILO队列运算 入队 从队尾插入退队 从队头删除 5 线性链表 1 概念 线性表的链式存储结构称为线形链表 2 存储原理 把存储结点分成两部分 第一部分存储数据元素 第二部分存储下一元素的序号 即存储结点的地址 3 特点 各数据结点的存储序号是不连续的 各结点在存储空间中的位置与逻辑关系也不一致 4 特别说明栈和队列也可以采用链式存储结 三 树与二叉树1 概念 树 是一种简单的非线形结构 所有元素都有明显的层次结构 树根 子结点 树叶二叉树 非空二叉树只有一个根结点 每个结点最多有两棵子树 且分别称为左子树 右子树 2 二叉树的特点 1 在第K层上 最多有2k 1 K 1 个结点 2 深度为M的二叉树 最多有2M 1个结点 深度指层数 3 任何二叉树中 度为0的结点 叶子 总比度为2的结点多一个 4 具有n个结点的二叉树 深度至少为 lon2n 1 3 完全二叉树和满二叉树完全二叉树是指最后一层外 每一层上的结点数均达到最大值 在最后一层上只缺少右边的若干结点 满二叉树满二叉树是指除最后一层外 每一层上的所有结点有两个子结点 则在第K层上有2k 1个结点 深度为m的满二叉树有2m 1个结点 4 二叉树的遍历遍历 是指不重复访问二叉树中的所有结点 三种遍历方式 前续遍历 DLR 先访问根结点 然后遍历左子树 最后遍历右子树 中序遍历 LDR 首先遍历左子树 然后访问根结点 最后遍历右子树 后序遍历 LRD 首先遍历左子树 然后遍历右子树 最后访问根结点 四 查找技术 1 顺序查找 从线形表的第一个元素开始 依次将线性表中元素与被找元素进行比较 最坏情况下 需比较N次 下列情况必须用顺序查找 1 线性表中的元素是无须排放的 即无序表 2 采用链式存储结构也只能用顺序查找 2 二分法查找 只适用于顺序存储的有序表 查找原则 A 先与线形表中间项比较 若等于中间项 找到B 若中间项 则再用相同方法在中间项的后部分查找最坏情况 需比较log2N次 五 排序技术1 交换类排序A 冒泡排序 通过相邻数据元素的交换逐步将线性表边成有序 最坏情况 n n 1 2B 快速排序法 任取一个记录 以它为基准 用交换的方法把其他元素分成两部分 再对这两部分实施上述过程 2 插入类排序法 1 简单插入排序法 第一个元素不动 把后面的元素依次插入到相关的位置中去 最坏情况需要比较n n 1 2次 2 希尔排序法 了解 把序列表分成若干个小序列 再进行插入排序 第二部分程序设计基础1 程序设计方法和风格 清晰第一 效率第二 一 源程序文档化 1 符号名的命名应具有一定的实际含义 便于理解 2 程序应加上一定的注释 序言性注释和功能性注释 3 为使程序结构一目了然 可以利用空格 空行 缩进等技巧 是程序层次清晰 二 数据说明的方法 1 数据说明的次序规范化 2 说明语句中变量安排有序化 3 使用注释来说明复杂数据的结构 三 语句的结构 1 在一行内只写一条语句 尽量使用库函数 2 首先保证程序正确 然后再考虑提高效率 3 避免使用临时变量而使程序的可读性下降 4 避免不必要的转移 避免采用复杂的条件语句 5 要模块化 是模块功能尽可能单一化 6 利用信息隐蔽 确保每个模块的独立性 7 不要修补不好的程序 要重新编写 四 输入和输出 1 对所有的输入数据都要检验数据的合法性 2 检查输入项的各种重要组合的合理性 3 输入格式要简单 以使输入的步骤和操作简单 4 输入数据时 应允许使用自由格式 5 应允缺省值 6 输入一批数据时 最好使用输入结束标志 7 以交互输入 输出方式进行输入时 要采用人 机会话给出明确的提示信息和运行的状态信息 8 设计输出报表格式 2 结构化程序设计 1 设计原则 自顶向下 逐步求精 模块化 限制使用GOTO语句 2 结构化程序的结构顺序结构选择结构 分支结构 重复结构 循环结构 3 结构化程序设计的具体实施中 注意要素 1 使用顺序 选择和循环三种基本控制结构表示程序的控制结构 2 选用的控制结构只许有一个入口和一个出口 3 程序模块化 每个模块也只能有一个入口和一个出口 4 使用基本控制结构进行嵌套与组合来实现复杂结构 5 用前后一致的方法来模拟3种基本结构以外的控制结构 6 严格控制GOTO语句的使用 4 面向对象程序设计优点 1 与人类习惯的思维方法一致 面向对象的核心是对象 2 稳定性好 3 可重用性好 可继承父类的所有属性和方法 4 易于开发大型软件产品 5 可维护性好 原因 稳定性好 容易修改 容易理解 易于测试和调试 5 面向对象方法的基本概念 1 对象对象是指一组属性以及这组属性上的专用操作的封装对象由对象名 属性和操作3部分组成 对象的基本特点 标识惟一性 分类性 多态性封装性 模块独立性好 2 封装封装是一种信息隐蔽技术 用户只能看见对象封装界面上的信息 对象的内部实现是隐蔽的 3 属性属性就是对象的特征 是对象外观及行为的特征 4 类和实例类 指具有共同属性 方法的对象的集合实例 类的一个具体应用就是一个实例 5 消息实例之间相互传递的信息叫消息 6 继承继承是在已有的类定义的基础上建立新类的定义技术 7 多态性和动态绑定多态性 指同一操作作用于不同对象可以有不同解释产生不同的执行结果 动态绑定 在运行过程中 当一个对象发送消息请求服务时 根据接收对象的具体情况将请求的操作和具体实现的方法进行连接 第三部分软件工程一 基本概念1 软件定义和软件特点定义 软件是包括程序 数据及相关文档的完整指令 与硬件相互依存 构成计算机系统 特点 1 软件是一种逻辑实体 2 软件的生产和硬件不同 没有明显的制作过程 3 软件在运行 使用期间不存在磨损 老化问题 4 软件的开发和运行具有依赖计算机系统的特性受计算机系统的限制 软件移植可能会有问题 5 软件的复杂性高 成本昂贵 6 软件开发涉及诸多社会因素 2 软件危机与软件工程软件危机 指在软件在开发和维护过程中所遇到的一系列严重问题 包括成本 质量 生产率等软件工程 是应用于计算机软件的定义 开发和维护的一整套方法 工具 文档实践标准和工序核心思想是 把软件产品作为一个工程产品处理 软件工程三要素 方法 工具和过程 3 软件工程过程和软件生命周期软件工程过程 是指为了获得软件产品 由软件工程师完成的一系列软件工程活动 软件工程四种活动 软件规格说明 软件开发 软件确认 软件演进软件生命周期 1 可行性研究与计划确定 2 需求分析 3 软件设计 结构模块的划分 4 软件实现 5 软件测试 6 运行和维护 4 软件工程的目标和原则目标 付出较低的成本 达到要求的软件功能 取得较好的软件性能 开发的软件易于移植 需要较低的维护费用 能按时完成开发 及时交付原则 抽象 信息隐蔽 模块化 局部化 确定性一致性 完备性和可验证性 二 结构化分析1 需求分析定义 通过文档描述用户解决问题或达到目标所需的条件或权能 及系统要满足合同 标准规范所具有的条件 需求分析阶段的工作 需求获取 需求分析 编写需求规格说明书 需求评审 2 需求分析的方法 1 结构化分析方法SA 面向数据流的结构化分析方法JSD 面向数据结构Jackson方法DSSD 面向数据结构的结构化数据系统开发方法 2 面向对象的分析方法OOA 3 结构化分析方法的常用工具数据流图 DFD 椭圆 加工转换 箭头 数据流向 双横线 存储文件 矩形 实体 数据字典 DD 判定表和判定树等工具4 软件需求规则说明书是需求分析阶段的最后成果 是软件开发中的重要文档之一 5 软件设计总体步骤从技术观点来看 软件设计包括如下几个过程 1 软件结构设计 定义软件系统各部件之间的关系 2 数据设计 将分析时创建的模型转为数据结构的定义 3 接口设计 描述软件内部 软件和操作系统之间及软件与人之间如何通信 4 过程设计 把系统结构部件转换成软件的过程描述从工程管理来看 软件设计分为 1 概要设计 确定总体结构 模块的划分 2 详细设计 确定每一模块的实现 6 软件模块的独立性独立性 每个模块完成系统要求的独立的功能 与其他模块的联系最少且接口简单 独立性的两个标准 耦合和内聚 应满足 低耦合 高内聚 耦合 模块之间联系的紧密程度 内聚 模块内部各元素之间联系的紧密程度 7 概要设计的准则 1 提高模块独立性 2 模块规模适度 3 深度 宽度 扇出和扇入适当好的软件结构设计应该满足 顶层扇出教高 中间扇出教少 低层模块高扇入 4 使模块的作用域在该模块的控制域内 5 应减少模块的接口和界面的复杂性 6 设计成单入口和单出口的模块 8 数据流类型两种 交换流和事物流 9 软件测试的目的目的 尽可能多地发现软件产品中的错误和缺陷 准则 1 所有测试应追溯到需求 2 严格执行测试计划 排除测试的随意性 3 充分注意测试中的群集显现 4 程序应避免检查自己的程序 5 穷举测试不可能 6 妥善保存测试计划 测试用例 出错统计和最终分析报告 为维护提供方便 软件测试的方法从是否要执行软件的角度 静态测试 代码检查 静态的结构分析 代码质量度量等 动态测试 基于计算机的测试 为了发现错误而执行程序 动态测试分为 白盒测试 黑盒测试白盒测试 根据程序的内部逻辑来设计测试黑盒测试 根据程序的功能说明来设计测试 10 软件测试的实施过程单元测试 对各模块进行正确性检验集成测试 测试与组装软件的测试 发现与接口有关的问题验收测试 验证软件的功能 性能系统测试 将测试确认的软件加入到计算机系统中进行测试 11 程序调试是指诊断和改正程序中的错误 其关键是推断程序内部的错误位置及原因 调试的步骤 错误定位 修改设计和代码 以排除错误 进行回归测试 防止引进新的错误 调试方法 1 强行排错法 2 回溯法 3 原因排除法 第四部分数据库基础知识1 数据 数据库 数据库管理系统 数据库系统基本概念 关系 DBS包含数据库管理系统 数据库 数据 数据库管理系统是数据库系统的核心2 数据库系统的特点1 实现数据共享 减少数据冗余2 采用特定的数据模型3 较高的数据独立性4 统一的数据控制功能 3 数据库系统的发展人工管理阶段 无磁盘 直接存取 没有操作系统文件系统阶段 无法提供完整的 统一的 管理和数据共享能力 数据库系统阶段 网状模型 层次模型和关系模型实现数据统计管理 数据共享等 4 数据库系统内部的体系结构数据库系统内部具有三级模式和两级映射三级模式 1 概念模式 是数据库中对全局数据的逻辑结构和特征的描述 是所有用户的公共数据视图 中间层 反映设计者的全局数据逻辑要求 2 外模式 是指拥护能够看见 是使用的 局部的逻辑结构和特征的描述 最高层 反映用户要求 3 内模式 存储模式或物理模式 能给出数据库物理存储结构和存储方法 最低层 反映存储形式两个映射 外模式 概念模式映射 概念模式 内模式映射 5 数据模型 概念模型 E R模型 基本概念 实体 属性 联系实体集的三种关系 一对一 一对多 多对多E R模型的表示法 矩形 表示实体椭圆 表示实体的属性菱形 表示实体联系无向线段 连接实体和属性