全国计算机等级二级公共基础.ppt

全国计算机等级二级公共基础 数据结构与算法 数据 Data 是对客观事物的符号 文字 数字 其他 表示 在计算机科学中是指所有能输入到计算机中并被计算机程序处理 存储 输出的符号的总称 它是计算机程序加工的 原料 例如 文档 记录 数组 句子 单词 算式 符号等都是数据 数据结构的基本知识 数据元素 DataElement 是数据的基本单位 在计算机程序中通常作为一个整体进行考虑和处理 数据记录 DataRecord 是数据处理中组织数据的基本单位 一个数据记录可由若干个数据项 Dataltem 组成 数据项可以是简单数据项 不可再分割 也可以是组合数据项 本身又是记录或数组 数据结构的基本知识 数据处理 DataProcessing 对数据进行检索 插入 删除 合并 拆分 排序 统计 计算 转换 输入 输出等的操作过程 具体应用领域 计算机情报检索 信息管理系统 图书管理系统 物资调配系统 银行核算系统 财务管理系统 MRPII ERP等 数据结构的基本知识 综上所述 数据处理的最小单位是数据项 由若干数据项组成数据元素 而数据是指能够被计算机识别 存储和加工处理的信息载体 数据结构是指数据之间的相互关系和数据运算 数据结构的基本知识 数据结构概念一般包括3个方面的内容 数据的逻辑结构物理结构或存储结构数据上的运算集合 数据结构的基本知识 数据的逻辑结构就是数据元素之间的逻辑关系 它是从逻辑上描述数据元素之间的关系 而不管它在计算机中的存储表示形式 数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式 在数据的存储结构中 不仅要存放各数据元素的信息 还需要存放各数据元素之间的前后件关系的信息 数据结构的基本知识 数据结构由数据的逻辑结构的中各数据元素之间前后间关系的复杂程度 一般可分为 线性结构非线性结构 数据结构的基本知识 常用的存储表示方法有4种 顺序存储链式存储索引存储散列存储 数据的存储形式 A B C D E F A B D E G C A B C D E 线性结构 非线性结构 对特定问题求解步骤的一种描述 流程图 伪码 程序 它是指令的有限序列 其中每一条指令表示一个或多个操作 算法 Algorithm 1 有穷性一个算法必须总是 对任何合法的输入值 在执行有穷步之后结束 且每一步都可在有穷时间内完成 2 确定性算法中每一条指令必须有确切的含义 读者理解时不会产生二义性 并且 在任何条件下 算法只有唯一的一条执行路径 即对于相同的输入只能得出相同的输出 算法 Algorithm 算法的五个特性 3 可行性一个算法是能行的 即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的 4 输入一个算法有零个或多个的输入 这些输入取自于某个特定的对象的集合 5 输出一个算法有一个或多个的输出 这些输出是同输入有着某些特定的关系 算法 Algorithm 算法的五个特性 结构化程序设计方法的主要原则可以概括为自顶向下 逐步求精 模块化及限制使用goto语句 总的来说可使程序结构良好 易读 易理解 易维护 算法 Algorithm 一个好的算法应考虑达到以下目标 1 正确性 Correctness 算法应当满足具体问题的需求2 可读性 Readability 算法主要是为了人的阅读与交流 其次才是机器执行 3 健壮性 Robustness 当输入数据非法时 算法也能适当地作出反应或进行处理 而不会产生莫明其妙的输出结果 4 简单性 Simplicity 算法的分析 算法的评价 算法分析是指对一个算法的运行时间和占用空间做定量的分析 一般计算出相应的数量级 常用时间复杂度和空间复杂度表示 分析算法的目的 降低算法的时间复杂度和空间复杂度 提高算法的执行效率 但算法的时间复杂度和空间复杂度并不相关 算法的分析 算法的评价 算法的时间复杂度是指执行算法所需要的计算工作量 即算法执行过程中所需要的基本运算的次数 算法的时间复杂度 算法的空间复杂度是对算法在运行过程中所需存储空间的量度 即指执行这个算法所需要的内存空间 1 存储空间的固定部分程序指令代码的空间 常数 简单变量 定长成分 如数组元素 结构成分 对象的数据成员等 变量所占的空间 2 可变部分尺寸与实例特性有关的成分变量所占空间 引用变量所占空间 递归栈所用的空间 通过new和delete命令动态使用的空间 S n O h n 其中n为问题的规模 或大小 算法的空间复杂度 时间复杂度 空间复杂度 栈 Stack 运算受限线性表 只允许在一端插入和删除的线性表允许插入和删除的一端称为栈顶 top 另一端称为栈底 bottom 特点 后进先出 LIFO 队列 Queue 运算受限的线性表 队列是只允许在一端删除 在另一端插入的线性表允许删除的一端叫做队头 front 允许插入的一端叫做队尾 rear 插入称进队 入队 删除称离队 出队 特点 先进先出 FIFO 树 非线性数据结构 递归的结构 树是由n n 0 个结点组成的有限集合 如果n 0 称为空树 如果n 0 则 有一个特定的根 root 的结点 它只有下层结点 但没有父结点或称前件 除根以外的其它结点划分为m m 0 个互不相交的有限集合T0 T1 Tm 1 每个集合又是一棵树 称之为根的子树 subTree 每棵子树的根结点有且仅有一个父结点 但可以有0个或多个下层结点 树的概念 树的概念 对于非空树 关系R满足下列条件 1 有且仅有一个结点没有前驱 该结点是树的根结点 A 2 除树的根结点外 其余结点有且仅有一个前驱结点 3 包括树根结点在内的所有结点可以有任意多个 含0个 后继结点 B 3 E 2 A 2 C 1 1 结点的度和树的度每个结点具有的子树数或后继结点数 称为该结点的度 B 3 E 2 A 2 C 1 树中所有结点度数的最大值称为该树的度 T 3 2 分支结点和叶子结点在一棵树中 度数为0的结点称为叶子结点或终端结点 DHIFG度数大于0的结点称为分支结点或非终端结点 ABCE 树的概念 3 孩子结点 双亲结点和兄弟结点在一棵树中 每个结点的子树的根 或每个结点的后继 称为该结点的孩子结点 或子女 儿子结点 该结点就是其孩子结点的双亲 父亲或父母结点 4 结点的层数和树的层数根结点在第一层 它的孩子在第二层 依次类推 A 1 B C 2 D E F G 3 H I 4 树中结点的最大层数为树的深度或高度 4 树的概念 1 树中的结点的数等于所有结点的度数加1 2 度为k的树中第i层上至多有ki 1个结点 i 1 3 深度为h的k叉树至多有个结点4 具有n个结点的k叉树的最小深度为 logk n k 1 1 树的特性 二叉树 BinaryTree 二叉树的五种不同形态 二叉树 结点的一个有限集合 该集合或者为空 或者是由一个根结点加上两棵分别称为左子树和右子树的 有序 互不相交的二叉树组成 1 若二叉树的层次从1开始 则在二叉树的第i层最多有2i 1个结点 i 1 2 高度为h的二叉树最多有2h 1个结点 h 1 3 对任何一棵二叉树 如果其叶结点个数为n0 度为2的非叶结点个数为n2 则有n0 n2 1 二叉树的特性 满二叉树 FullBinaryTree 一棵深度为h且有2h 1个结点的二叉树 完全二叉树 CompleteBinaryTree 若设二叉树的高度为h 除第h层外 其它各层 1 h 1 的结点数都达到最大个数 第h层从右向左连续缺若干结点 这就是完全二叉树 4 具有n n 0 个结点的完全二叉树的高度为 log2 n 1 或 log2n 15 若一棵二叉树为空 则它的深度为0 否则它的深度等于左子树和右子树中的最大深度加1 设depl为左子树的深度 depr为右子树的深度 则二叉树深度为 max depl depr 1 二叉树的特性 遍历二叉树 遍历是指按照一定次序访问树中所有结点 并且每个结点的值仅被访问一次的过程 问题可分解为三个子问题 访问根结点 D 遍历左子树 L 遍历右子树 R 遍历方案 前序遍历 DLR 中序遍历 LDR 后序遍历 LRD 前序遍历算法 DLR ABCDEFG 遍历二叉树 中序遍历算法 LDR CBDAEGF 后序遍历算法 LRD CDBGFEA 例 已知一棵二叉树的前序遍历的结果序列是ABECDFGHIJ中序遍历的结果序列是EBCDAFHIGJ试画出这棵二叉树 前序序列ABECDFGHIJ中序序列EBCDAFHIGJ A EBCD FHIGJ A B E CD HIGJ A 遍历二叉树 前序序列ABECDFGHIJ中序序列EBCDAFHIGJ A B F G C E D HI J A B E C D F G J H I 全国计算机等级二级公共基础 软件工程 软件工程的三要素 方法 是完成软件工程项目的技术手段工具 支持软件的开发 管理 文档生成过程 支持软件开发的各个环节的控制 管理 软件工程是用工程 科学和数学的原则与方法研制 维护计算机软件有有关技术及管理方法 软件工程 软件工程概念的出现源自软件危机 所谓软件危机是泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题 总之 可以将软件危机归结为成本 质量 生产率等问题 计算机软件有有关技术及管理方法 基本知识 基于软件工程的目标 软件工程的理论和技术性研究的内容主要包括 软件开发技术和软件工程管理 软件开发技术包括 软件开发方法学 开发过程 开发工具和软件工程环境 其主体内容是软件开发方法学 软件工程管理包括 软件管理学 软件工程经济学 以及软件心理学等内容 三部分组成 程序 在运行时 能提供所希望的功能和性能的指令集数据结构 使程序能够正确运行的数据结构文档 描述程序研制过程 方法及使用的文档 软件的基本概念 软件生存 生命 周期 一个软件从定义 开发 使用 和维护 直到最终被废弃要经历一个漫长的时期 这个时期称为生命周期 软件生存 生命 周期 瀑布模型 软件的需求分析 需求分析是软件定义的最后一个阶段 它的基本任务是准确地回答 系统必须做什么 这个问题 对目标系统提出完整 准确 清晰 具体的要求 需求分析对整个开发阶段都具有重大的影响 它是软件开发的基础 需求分析的任务是理解和表达用户的要求 用户的要求包括软件系统的范围 功能 性能 限制和约束 将进行分析 理解 最后用文档形式把用户要求的功能 性能表达出来 即编写软件需求说明书 软件的需求分析 软件需求规格说明书 SRS SoftwareRequirementSpecification 是需求分析阶段的最后成果 是软件开发中的重要文档之一 它有以下几个方面的作用 便于用户 开发人员进行理解和交流 反映出用户问题的结构 可以作为软件开发工作的基础和依据 作为确认测试和验收的依据 一 概述二 数据描述 数据流图 数据字典 系统接口说明 内部接口三 功能描述 功能 处理说明 设计的限制 需求说明书包括的内容和书写参考格式 四 性能描述 性能参数 测试种类 预期的软件响应 应考虑的特殊问题五 参考文献目录六 附录 软件结构 过程和模块 1 软件结构 是软件模块间关系的表示 2 软件过程 用以描述每个模块的操作细节 同时包括一个模块对下一层模块控制的操作细节 3 软件模块 模块是数据说明 可执行语句等程序元素的集合 模块具有独立性 模块独立性是通过制定具有单一功能并且和其它模块没有过多联系的模块来实现的 模块独立性是由两个定性指标来度量 内聚性 是度量一个模块功能强度的一个相对指标 耦合性 是用来度量模块之间的相互联系的程度 模块独立性越强 则信息隐蔽性越好 软件结构 过程和模块 内聚性 反映了模块内各成分之间的联系 耦合性 耦合反映了模块间互相连接的紧密程度 内聚性是信息隐蔽和局部化概念的自然扩展 一个模块的内聚性越强 则该模块的模块独立性越强 即信息隐蔽性越好 一个模块与其它模块的耦合性越强 则它的模块独立性越弱 耦合程度弱的模块 其内聚程度一定高 软件设计 软件设计是开发阶段最重要的步骤 从工程管理的角度来看可分为两步 概要设计和详细设计 从技术设计观点来看 软件设计包括软件结构设计 数据设计 接口设计 过程设计 软件设计 概要设计 将软件需求转化为软件体系结构 确定系统级接口 全局数据结构或数据模式 详细设计 确立每个模块的实现算法和局部数据结构 用适当方法表示算法和数据结构的细节 结构设计 是定义软件系统各主要部件之间的关系 数据设计 是将分析时创建的模型转化为数据结构的定义 接口设计 是描述软件内部 软件和操作系统之间及软件与人之间如何通信 过程设计 则是把系统结构部件转换成软件的过程性描述 软件开发之总体设计 总体设计过程通常由两个主要阶段组成 系统设计 确定系统的具体实现方案 结构设计 确定软件结构 为确定软件结构 首先需要从实现角度把复杂的功能进一步分解 分析员结合算法描述仔细分析数据流图中的每个处理 如果一个处理的功能过分复杂 必须把它的功能适当地分解成一系列比较简单的功能 结构化分析方法 常用的需求分析方法 1 结构化分析方法 主要包括 面向数据流的结构化分析方法 SA 面向数据结构的Jackson方法 JSD 和面向数据结构的结构化数据系统开发方法 DSSD 2 面向对象的分析方法 OOA 采用三大结构 即顺序结构 选择结构 循环结构来实现程序设计技术 它采用自顶向下 逐步求精的设计方法和单入口单出口的控制结构 结构化分析方法 结构化方法的核心和基础是结构化程序设计理论 结构化分析 需求阶段 的常用工具有 数据流图 DFD 数据字典 DD 判定树和判定表 结构设计 概要设计阶段 工具是 结构图 SC structurechart 过程设计 详细设计阶段 常见的工具有 程序流程图 N S图 PAD图 问题分析图 和PDL 过程设计语言 软件测试 软件测试的目标或定义1 测试是为了发现程序中的错误而执行程序的过程 2 好的测试方案是极可能发现迄今为止尚未发现的错误的测试方案 3 成功的测试是发现了至今为止尚未发现的错误的测试 软件测试方法 黑盒测试和白盒测试黑盒测试 要在软件的接口处进行测试 即把测试对象看做一个黑盒子 测试人员完全不考虑程序内部的逻辑结构和内部特性 只依据程序的需求规格说明书 检查程序的功能是否符合它的功能说明 又称功能测试或数据驱动测试 常用的有等价类划分 边界值分析法和错误推测法 软件测试方法 黑盒测试可以发现以下几类错误 1 是否有不正确或遗漏了的功能 2 在接口上 输入能否正确地接受 能否输出正确的结果3 是否有数据结构错误或外部信息 例如数据文件 访问错误 4 性能上是否能够满足要求 5 是否有初始化或终止性错误 软件测试方法 黑盒测试和白盒测试白盒测试 是对软件的过程性细节做细致的检查 该方法是把测试对象看作上个打开的盒子 它允许测试人员利用程序内部的逻辑结构及有关信息 设计或选择测试用例 对程序所有逻辑路径进行测试 通过在不同点检查程序的状态 确定实际的状态是否与预期的状态一致 又称为结构测试或逻辑驱动测试 软件测试方法 白盒测试方法 主要对程序模块进行如下的检查 1 对程序模块的所有独立的执行路径至少测试一次 2 对所有的逻辑判定 取 真 与取 假 的两种情况都能至少测试一次 3 在循环的边界和运行界限内执行循环体 4 测试内部数据结构的有效性 软件测试的实施过程 1 单元测试单元测试又称模块测试 是针对程序模块 进行正确性检验的测试工作 目的在于发现各模块内部可能存在的各种差错 主要采用白盒测试的测试用例 辅之以黑盒测试的测试用例 软件测试的实施过程 2 集成测试集成测试又称整体测试或结合测试 是软件测试中的一个重要环节 主要目的是发现与接口有关的错误 3 确认测试 验收测试 确认测试又称有效性测试 任务是验证软件的功能和性能 以及其他特性是否满足需求规格说明定的各种需求 4 系统测试系统测试是软件测试中的最后的 最完整的测试 它是在单元级测试和集成测试的基础上进行的 系统测试任务1 完成系统级的功能验证 2 完成系统的验收测试 软件调试 我们严格区分调试与测试 调试是已知有错误而来找错误 是被动的 测试有很多种 比如未发现错误但不能保证程序没错而来找BUG 还比如我们运行测试程序是否符合用户的要求 是主动的 软件调试 软件调试 Debug 即排错 的任务是诊断和改正程序中的错误 与软件测试不同 软件测试是尽可能多地发现软件中的错误 软件测试贯穿整个软件生命期 调试主要在开发阶段 调试的基本步骤 错误定位 修改和设计代码以排除错误 进行回归测试防治引进新的错误 软件调试的方法 强行排错法回溯法原因排除法试探法对分查找法归纳法演绎法 软件维护 软件维护活动包括以下几类 改正性维