全国计算机等级考试--公共基础.ppt

课程内容 数据结构与算法程序设计基础软件工程基础数据库设计基础 算法基本概念 什么是算法算法是指用系统的方法描述解决问题的策略机制 算法的基本特征有穷性 确定性 可行性 拥有足够的情报算法的构成要素对数据对象的运算和操作 算法的控制结构 算法复杂度 时间复杂度执行算法所需要的计算工作量 算法的工作量是问题规模的函数 即算法的工作量 f n 1 最坏情况复杂性2 期望复杂性 算法复杂度 空间复杂度执行算法所需要的内存空间 包括算法程序所占空间 输入初始数据所占空间及算法执行中所需额外空间 时空复杂度 返回 数据结构基本概念 什么是数据结构 DataStructure 数据结构是研究数据元素 DataElement 之间抽象化的相互关系和这种关系在计算机中的存储表示 即所谓数据的逻辑结构和物理结构 并对这种结构定义相应的运算 设计出相应的算法 而且确保经过这些运算后所得到的新结构仍然是原来的结构类型 为了叙述上的方便和避免产生混淆 通常把数据的逻辑结构统称为数据结构 把数据的物理结构统称为存储结构 StorageStructure 栈和队列 1 栈的定义栈 stack 是一种只允许在一端进行插入和删除的操作受限的线性表 在表中只允许进行插入和删除的一端称为栈顶 top 另一端称为栈底 bottom 当栈中无数据元素时 称为空栈 根据栈的定义可知 栈也被称为 后进先出 的线性表 栈和队列 2 栈的基本运算 1 入栈 在栈s的顶部插入元素x 若栈满 则返回FALSE 否则 返回TRUE 2 出栈 若栈s不空 则返回栈顶元素 并从栈顶中删除该元素 否则 返回空元素NULL 3 读取栈顶元素 若栈s不空 则返回栈顶元素 否则返回空元素NULL 栈和队列 3 队列的定义队列 queue 是一种只允许在一端进行插入 而在另一端进行删除的线性表 它是一种操作受限的线性表 在表中只允许进行插入的一端称为队尾 rear 只允许进行删除的一端称为队头 front 当队列中无数据元素时 称为空队列 队列也被称为 先进先出 表 栈和队列 循环队列将顺序队列的存储区假想为一个环状的空间 如图所示 我们可假想q queue 0 接在q queue MAXNUM 1 的后面 当发生假溢出时 将新元素插入到第一个位置上 这样做 虽然物理上队尾在队首之前 但逻辑上队首仍然在前 入列和出列仍按 先进先出 的原则进行 这就是循环队列 MAXNUM 1 0 1 rear front 循环队列示意 栈和队列 仅凭q front q rear不能判定队列是空还是满 返回 线性链表 线性链表是线性表的链式存储结构 是一种物理存储单元上非连续 非顺序的存储结构 数据元素的逻辑顺序是通过链表中的指针链接次序实现的 因此 在存储线性表中的数据元素时 一方面要存储数据元素的值 另一方面要存储各数据元素之间的逻辑顺序 为此 将每一个存储结点分为两部分 一部分用于存储数据元素的值 称为数据域 另一部分用于存放下一个数据元素的存储结点的地址 即指向后继结点 称为指针域 线性链表 此种形式的链表因只含有一个指针域 又称为单向链表 简称单链表 图2 7 a 所示为一个空线性链表 图2 6 b 所示为一个非空线性链表 a0 a1 a2 an 1 树与二叉树 树结构的基本术语 1 结点的度 Degree 树中的一个结点拥有的子树数称为该结点的度 Degree 一棵树的度是指该树中结点的最大度数 度为零的结点称为叶子 Leaf 或终端结点 度不为零的结点称分支结点或非终端结点 除根结点之外的分支结点统称为内部结点 根结点又称为开始结点 树与二叉树 树结构的基本术语 2 结点的层数 Level 和树的高度 Height 结点的层数 Level 从根起算 根的层数为1其余结点的层数等于其双亲结点的层数加1 双亲在同一层的结点互为堂兄弟 树中结点的最大层数称为树的高度 Height 或深度 Depth 注意 很多文献中将树根的层数定义为0 树与二叉树 二叉树的重要性质 性质1二叉树第i层上的结点数目最多为2i 1 i 1 性质2深度为k的二叉树至多有2k 1个结点 k 1 性质3在任意 棵二叉树中 若终端结点的个数为n0 度为2的结点数为n2 则n0 n2 1性质4具有n个结点的二叉树的深度至少为 树与二叉树 1 满二叉树 FullBinaryTree 一棵深度为k且有2k 1个结点的二又树称为满二叉树 满二叉树的特点 1 每一层 k 上的结点数都达到最大值 2k 1 即对给定的高度 它是具有最多结点数的二叉树 2 满二叉树中不存在度数为1的结点 每个分支结点均有两棵高度相同的子树 且树叶都在最下一层上 树与二叉树 2 完全二叉树 CompleteBinaryTree 若一棵二叉树至多只有最下面的两层上结点的度数可以小于2 并且最下一层上的结点都集中在该层最左边的若干位置上 则此二叉树称为完全二叉树 树与二叉树 遍历算法 1 先序遍历 根结点 左子树 右子树 2 中序遍历 左子树 根结点 右子树 3 后序遍历 左子树 右子树 根结点 树与二叉树 先序序列ABDCEF中序序列DBAECF后序序列DBEFCA 返回 查找技术 顺序查找 基本思想折半查找 二分法 基本思想 排序技术 冒泡排序 基本思想直接插入排序 基本思想希尔排序选择排序 排序技术 按平均时间将排序分为四类 1 平方阶 O n2 排序例如直接插入 直接选择和冒泡排序 2 线性对数阶 O nlgn 排序如快速 堆和归并排序 3 O n1 阶排序 是介于0和1之间的常数 即0 1 如希尔排序 4 线性阶 O n 排序如桶 箱和基数排序 排序技术 各种排序最坏情况下的时间复杂度 顺序查找二分查找 程序设计基础 结构化程序设计面向对象程序设计 结构化程序设计 设计原则 1 自顶向下 先考虑总体 后考虑细节2 逐步求精 对复杂问题 可以设计子目标作过渡 逐步细化3 模块化 把要解决的总目标分解为分目标 进一步分解为具体的小目标 把每个小目标称为一个模块4 限制使用goto语句 结构化程序设计 结构化程序的基本结构 结构化程序设计 StructuredProgramming 简称SP 方法是由E Dijkstra等人于1972年提出来的 它建立在Bohm Jacopini证明的结构定理的基础上 结构定理指出 任何程序逻辑都可以用顺序 选择和循环等三种基本结构来表示 面向对象程序设计 对象基本特点 1 标识唯一性 指对象由内在本质是可以区分的2 分类性 指可以将相同属性和操作的对象抽象成类3 多态性 指同一个操作可以是不同对象的行为4 封装性 从外面只能看到对象的外部特征5 模块独立性好 对象内部元素彼此结合紧密 内聚性强 软件工程基础 软件工程基本概念结构化分析方法结构化设计方法软件测试程序调试 软件工程基本概念 软件 定义 软件 程序 数据 文档 软件工程基本概念 软件 功能分类 应用软件事务处理软件 人工智能软件 嵌入式软件系统软件操作系统 编译程序 数据库管理系统支撑软件编码软件工具 项目管理软件 过程控制软件 软件工程基本概念 软件工程 定义 软件工程基本概念 软件生命周期 包含软件定义 软件设计 软件使用与维护三阶段 而又可以具体分成几个子阶段 软件工程基本概念 软件工程原则 抽象信息屏蔽模块化局部化 返回 确定性一致性完备性可验证性 结构化分析方法 需求分析阶段的工作 需求获取 目的是确定对目标系统的各方面需求 需求分析 对获取的需求进行分析和综合 最终给出系统的解决方案和目标系统的逻辑模型 编写需求分析规格说明书 为各人员间交流提供方便和控制软件开发过程的进度 需求评审 需求分析最后一步 验证需求文档的一致性 可行性 完整性和有效性 结构化分析方法 常见需求分析方法 结构化分析方法 包括面向数据流的结构化分析方法 SA StructuredAnalysis 面向数据结构的Jackson方法 JSD JacksonSystemDevelopmentmethod 面向数据结构的结构化数据系统开发方法 DSSD DataStructuredSystemDevelopmentmethod 面向对象的分析方法 OOA Object Orientedmethod 结构化分析方法 常用工具 数据流图 DFD DataFlowDiagram 常用工具 数据字典 DD DataDictionary 判定表判定树 结构化设计方法 软件设计基本原理 模块化软件设计基本原理 信息屏蔽软件设计基本原理 模块独立性 高内聚 低耦合 结构化设计方法 概要设计 结构化设计方法 详细设计 程序流程图 PDF 详细设计 问题分析图 PAD 详细设计 N S图详细设计 过程设计语言 PDL 详细设计 判定表详细设计 判定树 软件测试 软件测试定义为了发现程序中的错误 软件测试 软件测试步骤 1 单元测试 又称模块测试 2 集成测试 将模块集成为系统的过程中可能出现的问题3 有效性测试 使用实际数据进行测试4 系统测试系统测试是把通过有效性测试的软件 与整个系统的其他元素结合起来测试 第一种方法是黑盒测试 第二种方法是白盒测试 白盒测路径 黑盒测功能 程序调试 调试步骤 调试过程由两个部分组成 首先 确定程序中错误的确切性质和位置 然后 对程序代码进行分析 确定问题的原因 并设法改正这个错误 程序调试 调试方法 强行排错调试方法 回溯法调试方法 归纳法调试方法 演绎法 数据库设计基础 数据库系统基本概念数据模型关系代数数据库设计与管理 数据库系统基本概念 数据 数据库 数据库管理系统 数据 data 数据库 DB 数据库管理系统 DBMS 数据库系统 DBS 数据库系统基本概念 数据库系统的发展 人工管理 文件系统 数据库系统 数据库系统基本概念 数据库系统三级模式结构 外模式 用户模式 数据库用户看到的数据视图 概念模式 逻辑模式 数据结构和特性的描述 内模式 物理模式 数据在数据库内部的表示 数据模型 E R Entity Relationship 模型的基本概念 实体 客观存在并可相互区分的事物 属性 实体所具有的特性 联系 实体之间及其内部的关联 数据模型 层次模型网状模型关系模型 数据模型 关系模型 完整性约束 实体完整性约束 任何实体具有的某种唯一性标识 参照完整性约束 某些属性的取值需要参照其他关系的属性 用户定义的完整性约束 某一具体应用所涉及的数据必须满足的语义要求 返回 集合运算 并 R S t