VF 全国二级公共基础知识(浓缩版NCRE)

第第 1 章章 数据结构与算法数据结构与算法 1 算法特征 可行性 确定性 有穷性 拥有足够的情报 足够的输入信息和初始化信息 2 算法的描述工具有 传统流程图 N S 结构化流程图 算法描述语言 2 算法的控制结构有 顺序 选择 也叫分支 循环 也叫重复 4 算法的设计方法 1 列举法 2 归纳法 3 递推法 4 递归法 5 减半递推 6 回溯法 5 递归分为直接递归 直接调用自己 和间接递归 A 调用 B B 再调用 A 6 算法的复杂度 时间复杂度和空间复杂度 O n 7 数据处理 包括插入 删除 查找 更新等运算 8 数据结构 数据元素及其关系 分为逻辑结构和物理结构 9 数据的逻辑结构 是指数据元素之间的逻辑关系的描述 包括集合 线性结构 树形结构和网状结构四种 10 数据的存储结构也称物理结构 是数据在存储空间中的存放形式 同一种逻辑结构的数据可以有多种存储结构 常用的存储结构有顺序 链接 索引等存储结构 采用不同的存储结构 其数据处理的效率是不同的 11 线性结构与非线性结构 12 线性结构 非空数据结构有且只有一个根结点 每个结点最多只有一个前驱 最多只有一个后继 该结构称为线 性结构或线性表 14 线性表的定义 n 0 各元素构成的有限序列 表中除第一个元素外的每一个元素 有且只有一个前驱 除最 后一个元素外 有且只有一个后继 线性表要么是一个空表 要么可以表示为 a1 a2 a3 an 15 线性表的顺序存储结构 利用连续的存储单元依次存储线性表的数据的方式 16 线性表的顺序存储结构的基本特征 线性表中所有元素所占的存储空间是连续的 线性表中各元素在存储空间 中是按逻辑顺序依次存放的 17 栈是逻辑结构上一种特殊的线性表 只能在栈顶删除或插入元素 操作特征 先进后出 出栈顺序 18 线性链表 也叫单链表 是线性表的链式存储结构 在该存储结构中 每个结点由数据域和指针域两部分组成 19 栈和队列都可以采用链式存储结构 20 顺序表与链表的区别 A 顺序表 线性表的顺序表表示 其特点是用物理存储位置上的邻接关系来表示结点间的逻辑关系 其优点 无须 为表示结点间的逻辑关系额外增加存储空间 可以方便随机存取表中的任意结点 其缺点 插入和删除运算不方便 除 队尾位置外 在表的其他位置上进行插入和删除操作都必须移动大量的结点 其效率较低 B 链表 线性表的链式存储表示 其特点是用指针来表示结点间的逻辑关系 其优点 插入和删除运算方便 链表 占用的存储空间可以随时改变 不会出现空间的闲置和溢出现象 其缺点 为表示结点间的逻辑关系 需要增加额外的 存储空间 指针域 存储密度比顺序表低 21 双向链表 在单链表中的结点中增加一个指针域指向它的直接前驱 这样的链表称为双向链表 即一个链表结点 含有两个指针 22 循环链表 把单链表最后一个结点的指针域的值由 NULL 该为指向链表的第一个元素的地址 则整个链表就构成 一个闭合的环链 这样的链表叫循环链表 相应的也有双向循环链表 23 树 是一种非线性结构 元素间具有明显的层次特征 树是由 n 个结点组成的有限集合 n 0 称为空树 n 0 时 有一个根结点 24 树的特点 A 每一个树只有一个根结点 每一个结点最多只有一个前驱 它称为该结点的父结点 B 每一个结点 可以有多个后继 它们都称为该结点的子结点 没有后继的结点称为叶子结点 C 一个结点所拥有的后继个数称为树中 该结点的度 D 树的最大层次叫树的深度 25 二叉树由一个根结点和两棵互不相干的子树 左子树和右子树 构成 且左右子树都是二叉树 26 特点 非空二叉树只有一个根结点 每一个结点最多有两棵子树 分别为左子树和右子树 每个结点最多有两个 子结点 即所有结点的度小于等于 2 二叉树是有序树 而树上无序的 且二叉树不能颠倒 因此二叉树只有 5 种基本 形态 二叉树 右子树 左子树 根树 空树 27 满二叉树 除了最后一层外 每一层上的所有结点都有两个子结点的二叉树 深度为 k 的满二叉树 第 k 层上有 2k 1个结点 整棵二叉树共有 2k 1 个结点 28 完全二叉树 除了最后一层外 每层的结点数都达到最大值的二叉树叫完全二叉树 即本层结点树达到最大值后 才能放入下一层 若左边有空时不能将结点放入右边 最后一层只缺少右边的若干结点 满二叉树是完全二叉树 但完 全二叉树不一定是满二叉树 29 二叉树的性质 A 在二叉树的第 k 层最多有 2k 1个结点 B 深度为 m 的二叉树 最多有 2m 1 个结点 C 对于任意二叉树 度为 0 的结点 即子结点 总比度为 2 的结点 叶子结点 多一个 D 二叉树都是按照从上到下 从左到右的顺序 30 二叉树通常采用链式结构 由于每一个元素可以有两个后继 所以用于存储二叉树的存储结点的指针域有两个 31 二叉树的三种遍历 1 前序遍历 根结点 左子树 右子树 且遍历左右子树时仍然是根结点 左子树 右子树 2 中序遍历 左子树 根结点 右子树 且遍历左右子树时仍然是左子树 根结点 右子树 3 后序遍历 左子树 右子树 根结点 且遍历左右子树时仍然是左子树 右子树 根结点 32 查找的类型 顺序查找和二分法查找是两种基本的查找方法 顺序查找算法简单 对表结构无任何要求但是效率低 当结点数较大时 不宜采用 但是无序线性表或链式存储 结构只能用顺序查找 二分法查找 也称折半查找 高效 要求顺序存储结构且有序 33 排序有 交换类排序 冒泡和快速两种排序方法 选择排序 堆排序 插入排序 希尔排序 第第 2 章章 程序设计基础程序设计基础 1 结构化程序设计和面向对象的程序设计 前者面向过程 以算法为核心 后者面向对象 以对象为核心 2 结构化程序设计主要原则是层次分析法 即自顶向下 逐步求精 模块化 3 基本结构 顺序结构 选择结构 单分支和多分支 循环结构 4 面向对象程序设计优点 与人类习惯的思维方法一致 稳定性和可重复使用性好 易于开发大型软件 可维护 性好 易于修改 理解 测试和调试 3 基本概念 A 对象 是最基本的概念 数据操作封装的统一体 有 5 个特点 标识唯一性 分类性 多态性 封装性 模块 独立性 B 属性 用来表征对象的静态特征 C 操作 用于表征对象的动态行为 通常称为方法或事件 D 类 具有共同属性 共同方法的对象的集合 是关于对象的抽象描述 反映了属于该对象类型的所有对象的性 质 而一个具体对象则是其对应类的一个实例 E 消息 对象之间相互请求或相互协作的途径 F 继承 是指直接获得已有的性质和特征 而不必重复定义它们 G 多态性 减少了信息冗余提高了软件的可重用性和可扩充性 第第 3 章章 软件工程基础软件工程基础 1 软件包括程序 数据及相关文档的完整集合 2 软件是一种逻辑实体 而不是物理实体 具有抽象性 软件的生产没有明显的制作过程 软件的对计算机系统 具有依赖性 软件复杂性高 成本昂贵 3 分类 系统软件 如操作系统 数据库管理系统 设备驱动程序 设备处理程序等 支撑软件 帮助程序人员开 发软件产品的工具 应用软件 4 软件危机泛指计算机软件的开发和维护过程中所遇到的一系列严重问题 软件危机可归结为成本 质量 生产 率问题 5 软件工程的包括三要素 方法 工具 过程 软件工程的核心思想是把软件产品看作一个工程产品来处理 工 程项目的三要素 进度 经费和质量 6 软件的生命周期从软件提出 实现 使用维护到停止使用退役的过程称为软件的生命周期 还可 分为软件定义 开发和运行维护三个阶段 7 软件工程 原则 A 抽象 抽取事物最基本的特征和行为 用分层次抽象 自顶向下和逐层细化的办法 B 信息隐蔽 采用封装技术 使模块接口尽量简单 C 模块化 模块的大小要适中 D 局部化 松耦合 紧内聚 内聚性最强的是功能性内聚 E 确定性 所有概念的表达应是确定 无歧义且规范的 F 一致性 如概念 符号和术语 内外接口等的一致性 G 完备性 软件系统不丢失任何重要成分 完全实现系统所需的功能 H 可验证性 系统分解应遵循易检验 测评 评审的原则 以确保系统的正确性 8 需求分析方法有两种 A 结构分析方法 B 面向对象的分析方法 9 结构化分析方法 简称 SA 着眼于数据流 自顶向下 逐层分解析阶段的运用 10 结构化分析工具 数据流图 DFD 数据字典 DD 判断树 判断表 11 软件设计一个把软件需求转化为软件表示的过程 12 软件开发阶段 设计 编码 测试 占软件项目总成本的绝大部分 计是开发阶段最重要的步 骤 13 模块具有接口 功能 逻辑和状态等四种基本属性 14 软件设计基本原理 1 抽象 2 模块化 3 信息隐蔽 15 模块的独立性是评价设计好坏的重要标准 主要用内聚性和耦合性作为评价标准 耦合性越弱 则独立性越强 16 模块的作用范围和控制范围 模块控制范围指模块本身以及其下属模块的集合 模块的作用范围应在其控制范围内 优化模块 的原则 高内聚 低耦合 保持相对独立性 17 详细设计的工具 图形工具 程序流程图 N S PAD HIPO 表格工具 判定表 语言工具 伪 码 PDL 18 软件测试涵盖了整个软件生命期的过程 19 目的 为了发现错误 测试用例 20 准则 所有的测试都应该追溯到用户的需求 程序员应避免检查自己的程序 21 根据是否需要执行被测软件 可将测试分为静态测试和动态测试 根据功能可分为白盒测试和 黒盒测试 22 白盒测试保证所测模块每一独立路径至少执行一次 判断的每一分支至少执行一次 每一循环 都在边界条件和一般条件下至少各执行一次 验证所有内部数据结构的有效性 白盒测试的方法 逻辑覆盖测试和基本路径测试 23 黒盒测试 也称功能测试或数据驱动测试 它是对软件已经实现的功能是否满足需求进行测试 和验证 黒盒测试时在软件接口处进行功能验证 24 程序调试常称 Debug 即排错 其任务是诊断和改正程序中的错误 25 软件调试方法 强行排错法 回溯法 原因排除法 第第 4 章章 数据库设计基础数据库设计基础 1 据库 简称 DB 是指长期存储在计算机内 有组织 可共享的大量数据集合 2 数据库管理系统 简称 DBMS 是一种系统软件 是数据库系统的核心软件 3 数据库管理员 简称 DBA 4 数据库系统 简称 DBS 由 DB DBMS DBA 硬件 软件五部分组成 DBS 的核心是 DBMS 5 数据库系统的发展 人工管理阶段 无共享 冗余大 不独立 文件管理阶段 共享差 冗 余大 独立差 数据没有实现结构化 数据库系统阶段 共享强 冗余小 独立性强 整体数据的 结构化 5 数据库系统的基本特点 数据的集成性 数据的高共享性与低冗余性 数据独立性 数据统一管 理与控制 6 数据库系统的内部结构体系 三级模式 外模式 用户模式 模式 内模式 7 数据模型的三要素是数据结构 数据操作和完整性约束 8 数据模型的类型主要有层次模型 网状模型 关系模型 面向对象模型等 9 实体 概念世界的基本单位 10 属性 实体