计算机二级公共基础知识

随着社会的发展，计算机和互联网的应用在生活中愈发深入，计算机二级证书也变成了大学生必备证书，本导图主要导入了计算机二级Ms Office选择题的部分内容。

公共基础知识

• 数据结构与算法
  • 算法
    • 概念及其基本特征
      • 概念
        • 对解题方法完整而准确的描述，即解决问题的操作步骤（≠程序）
      • 基本特征
        • 可行性
          • 步骤可以实现，执行效果达到预期目的
        • 确定性
          • 步骤明确，不模棱两可，不准有多义性
        • 有穷性
          • 有限的时间完成
        • 拥有足够的情报
          • 算法要有一定的输入数据和必须要有输出结果
    • 算法的基本要素
      • 对数据对象的运算和操作
        • 算术运算
        • 逻辑运算
        • 关系运算
      • 算法的控制结构
        • 算法中各操作之间的执行顺序
        • 描述算法的工具
          • 传统流程图
          • N-S结构化流程图
          • 算法描述语言
    • 算法复杂度
      • 一个算法一般可以用顺序、选择和循环三种基本结构组合而成
      • 算法的时间复杂度和空间复杂度相互独立
      • 时间复杂度
        • 指执行算法所需要的的计算工作量
          • 算法的时间复杂度≠算法程序执行的具体时间
          • 算法的计算工作量是用算法所执行的基本运算次数来度量的
      • 空间复杂度
        • 指执行这个算法所需要的内存空间
          • 通常采用压缩技术降低算法的空间复杂度
  • 数据结构
    • 概念
      • 是指相互有关联的数据元素的集合
        • 数据
          • 数据元素是数据的基本单位，数据项是数据的最小单位
          • 需要处理的具有某个共同特征的数据元素的集合
        • 结构
          • 即关系，是集合中各个数据元素之间存在的某种联系
        • 数据结构
          • 一种逻辑结构可以有多种存储结构，不同的存储结构其数据处理效率不同
          • 逻辑结构
            • 反映元素之间的逻辑关系（前后件关系）
              • 线性结构：线性表、栈、队列
                • 有且只有一个根节点
                • 每个节点做多有一个前件，做多有一个后件
              • 非线性结构：树、图
                • 不满足线性结构条件的
          • 存储结构
            • 及物理结构，是逻辑结构在计算机存储空间中的存放方式
              • 顺序存储
              • 链式存储
          • 运算
            • 插入、删除、查找、排序
    • 表示方法
      • 二元组：B=(D,R)
        • 一日三餐为例：B=(D,R) D={早餐,午餐,晚餐} R={(早餐,午餐),(午餐,晚餐)}
      • 图形
        • 如图1所示
          • 标有元素值的方框为数据元素，称为数据节点，即节点
            • 根节点
            • 终端节点（叶子节点）
            • 内部节点
          • 有向线段由前件指向后件
    • 线性结构与非线性结构
      • 线性结构
        • 有且只有一个根节点
        • 每个节点最多有一个前件和一个后件
      • 非线性结构
        • 树形结构
        • 网状结构
  • 线性表及其顺序存储结构
    • 基本概念
      • 概念
        • 数据元素组成的有限序列
      • 特征
        • 只有一个根节点
        • 只有一个终端节点
        • 其他所有节点只有一个前件，也只有一个后件
    • 顺序存储
      • 所有元素所占的存储空间是连续
      • 按数据元素的逻辑顺序依次存放
      • 可以随机访问数据元素
      • 做插入、删除时需移动大量元素
  • 栈和队列
    • 栈
      • 概念
        • 栈的所有插入与删除都限定在表的同一端（栈顶）进行
        • 栈的修改原则是“先进后出”或“后进先出”
        • 栈底指针不变，栈顶指针top反映了栈的状态不断变化
        • 栈支持子程序的调用
      • 运算规则
        • 入栈
        • 退栈
        • 读栈顶元素
    • 队列
      • 定义
        • 指允许在一端（队尾）进行插入，另一端（队头）进行删除的线性表
        • 队列的修改原则是“先进先出”或“后进后出”
      • 运算
        • 顺序存储结构的线性表，队头指针front指向队头的前一个元素，队尾指针rear指向队尾的后一个元素
        • front与rear共同反映了队列中元素的动态变化
      • 循环队列
        • 将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间
        • 当front=rear时，不能确认队列是满还是空。所以，当s=0时，队列为空；当s=1且front=rear时，队列为满
  • 线性链表
    • 基本概念
      • 线性链表
        • 线性表的链式存储结构
          • 单链表
            • 每个节点只有一个指针域
          • 双向链表
            • 每个节点设置左指针（放前件）和右指针（放后件）
          • 二叉链表
            • 二叉树的链式存储结构
        • 特点
          • 各数据结点的存储空间可以不连续
          • 各数据元素的存储顺序与逻辑顺序可以不一致
          • 线性表的链式存储所占存储空间大于顺序存储结构
          • 查找结点时链式存储要比顺序存储慢
          • 链式存储在插入、删除元素时要比顺序存储灵活
        • 存储单元是任意的
        • 指向第一个元素的头指针HEAD等于NULL或者0时，称为空表
      • 带链的栈
      • 带链的队列
      • 顺序表和链表对比
        • 顺序表
          • 优点
            • 可以随机存取表中任意节点
            • 无需为节点逻辑关系增加空间
          • 缺点
            • 插入和删除运算效率很低
            • 不便于扩充
            • 不便于对存储空间的动态分配
        • 链表
          • 优点
            • 插入和删除时只需改变指针
            • 存储空间易于扩充，便于动态分配
          • 缺点
            • 需要额外的空间存储节点之间的逻辑关系
            • 存储密度比顺序表第
    • 循环链表
      • 将表头节点与表尾节点相连接所构成的环状链
      • 在表中没有数据元素的情况下依然存在一个数据节点，使得空表和非空表的运算统一
  • 树与二叉树
    • 树的基本概念
      • 非线性结构
        • 父节点
          • 每一个节点的前件称为该节点的父节点
          • 根
            • 没有前件的节点称为该树的根
        • 子节点
          • 每一个节点的后件称为该节点的子节点
          • 没有后件的节点称为叶子节点
        • 度
          • 一个节点所拥有的的后件的个数
          • 最大的度称为该树的度
        • 深度
          • 树的最大层次
    • 二叉树及其基本性质
      • 定义
        • 空二叉树没有节点
        • 每个节点最多有两棵子树
        • 子树有左右之分，次序不能随意颠倒
      • 性质
        • 在二叉树的第k层上，最多有2k-1(k≥1)个节点
        • 深度为m的二叉树中，最多有2m-1个节点
        • 任意一棵二叉树，度为0的节点总是比度为2的节点多一个
        • 具有n个节点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示取得整数部分
        • 具有n个节点的完全二叉树的深度为[log2n]+1
      • 满二叉树与完全二叉树
        • 满二叉树
          • 除最后一层外，每一层上都有两个子节点
        • 完全二叉树
          • 只在最后一层上缺少右边的若干节点的二叉树
          • 特点
            • 叶子节点只出现在最后两层
            • 对于任一节点，若其右子树深度为m，则其左子树深度为m或m+1
        • 满二叉树一定是完全二叉树，完全二叉树一般不是满二叉树
    • 二叉树的存储结构
      • 链式存储结构
        • 指向该节点左子节点的为左指针域，指向该节点右子节点的为右指针域
    • 二叉树的遍历
      • 不重复的访问二叉树的所有节点（先左后右）（如图2所示）
        • 前序遍历
          • A、B、D、H、E、I、C、F、G
        • 中序遍历
          • H、D、B、E、I、A、C、G、F
        • 后序遍历
          • H、D、I、E、B、G、F、C、A
      • 已知一棵树的前序遍历和后序遍历不能唯一确定这课二叉树
  • 查找技术
    • 顺序查找
      • 唯一方法
        • 线性表为无序表
        • 链式存储结构
      • 最好的情况下比较1次
      • 最坏的情况下比较n次
    • 二分法查找
      • 满足条件
        • 顺序存储结构
        • 有序表，元素按“从小到大”排列
      • 最坏情况下比较log2n次
• 程序设计基础
  • 程序设计风格
    • 清晰第一，效率第二
    • 源程序内部文档化
    • 数据说明
    • 语句的结构
    • 输入和输出
  • 结构化程序设计
    • 原则
      • 自顶向下
        • 先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标
      • 逐步求精
        • 对复杂的问题，先设计一个目标作为过渡，然后逐步细化
      • 模块化
        • 把程序要解决的总目标分解为一个一个的模块
      • 限制使用goto语句
        • 程序的质量与goto语句数量成反比
    • 基本结构
      • 顺序结构
      • 选择结构
      • 循环结构
      • 特征：只有一个入口和一个出口
      • 优点
        • 程序易于理解、使用和维护
        • 提高了编程工作效率，降低了软件开发成本
  • 面向对象的程序设计
    • 优点
      • 与人类习惯的思维方式一致
      • 稳定性好
      • 可重用性好
      • 容易开发大型软件产品
      • 可维护性好
    • 概念
      • 对象
        • 标识唯一性
          • 对象可由内在本质来区分，而不是通过描述来区分
        • 分类性
          • 可以将具有相同属性和操作的对象抽象成类
        • 多态性
          • 同一操作可以是不同对象的行为
        • 封装性
          • 从外面看不到对象的内部，只能看到对象的外部特征
        • 模块独立性好
          • 对象是面向对象的软件的基本模块，内聚性强
      • 类和实例
        • 类是具有共同属性、共同方法的对象的集合
        • 一个具体对象则是其对应类的一个实例
      • 消息
        • 消息传递是对象间通信的手段
      • 继承
        • 类与类之间也可以继承，一个子类可继承其父类的全部描述
        • 使用已有的类建立新类的定义技术，能直接获得已有的性质，而不必重复定义他们
      • 多态性
        • 子类对象可以像父类对象那样使用，同样的消息既可以发送给父类对象也可以发送给子类对象
        • 是指同样的消息被不同的对象接收时可导致完全不同的行动的现象
• 软件设计基础
  • 软件工程基本概念
    • 软件定义与软件特点
      • 定义
        • 由程序、数据及相关文档构成的完整集合
          • 程序和数据是机器可执行的，文档不是
      • 特点
        • 逻辑实体，具有抽象性
        • 没有明显的制作过程
        • 不存在磨损、老化问题
        • 对硬件和换件具有依赖性
        • 复杂性高，成本昂贵
    • 软件的分类
      • 系统软件
        • 最靠近计算机硬件的软件
          • 操作系统、编译程序、汇编程序、网络软件、数据库管理系统
      • 应用软件
        • 应用于特定的领域
          • 事务处理软件、工程与科学计算软件、实时处理软件、人工智能软件
      • 支撑软件
        • 协助用户开发软件的工具型软件
          • 需求分析工具软件、编译工具软件、测试工具软件、维护工具软件
    • 软件工程
      • 要素
        • 方法
          • 完成软件工程项目的技术手段
        • 工具
          • 支持软件的开发、管理和文档生成
        • 过程
          • 支持软件开发的各环节的控制和管理
      • 原则
        • 抽象
        • 信息隐蔽
        • 模块化
        • 局部化
        • 确定性
        • 一致性
        • 完备性
        • 可检验性
    • 软件过程
      • 概念
        • 把输入转为输出的一组彼此相关的资源和活动
      • 基本活动
        • 软件规格说明
        • 软件开发（软件设计与实施）
        • 软件确认
        • 软件演进
    • 软件生命周期
      • 软件定义期
        • 问题定义
        • 可行性研究
          • 可行性分析报告
        • 需求分析
          • 需求规格说明书
      • 软件开发期
        • 概要设计
          • 概要设计说明书
        • 详细设计
          • 详细设计说明书
        • 软件实现
          • 用户操作手册
        • 软件测试
          • 测试分析报告
      • 运行维护期
        • 运行维护
  • 需求分析及其方法
    • 需求分析
      • 概念
        • 需求分析将创建所需的数据模型、功能模型和控制模型
        • 工作的四个方面
          • 需求获取
          • 需求分析
          • 编写需求规格说明书
          • 需求评审
      • 需求规格说明书
        • 需求分析阶段的最后成果
        • 重点描述
          • 软件的目标
          • 软件的功能需求
          • 性能需求
          • 外部接口
          • 属性
          • 约束条件
        • 特点
          • 正确性
          • 无歧义性
          • 完整性
          • 可验证性
          • 一致性
          • 可理解性
          • 可修改性
          • 可追踪性
      • 需求分析方法
        • 结构化分析法
        • 面向对象分析法
    • 结构化分析方法的常用工具
      • 数据流图
        • 每个元素都必须命名
        • 编号，既有输入也有输出
        • 数据存储之间不应有数据流
        • 父图、子图关系与平衡规则
      • 数据字典
        • 是结构化分析的核心
      • 结构化英语
      • 判定表
      • 判定树
  • 软件设计及其方法
    • 基本概念
      • 软件设计是确定系统的物理模型
      • 高内聚，低耦合
    • 分类
      • 从工程管理角度划分
        • 概要设计
        • 详细设计
      • 按技术观点划分
        • 结构设计
        • 数据设计
        • 接口设计
        • 过程设计
    • 基本原理
      • 抽象
      • 模块化
      • 信息隐蔽
      • 模块独立性
        • 内聚性
        • 耦合性
    • 概要设计
      • 任务
        • 设计软件系统结构
        • 数据结构及数据库设计
        • 编写概要设计文档
        • 概要设计文档评审
      • 结构图
        • 反映了整个系统的功能实现以及模块与模块之间的关系
        • 顶层高扇出，中间扇出较少，底层高扇入
    • 详细设计
      • 常用工具
        • 程序流程图（PFD）
        • N-S图
        • PAD图
        • HIPO图
        • 判定表
        • PDL
  • 软件测试
    • 目的和准则
      • 目的
        • 发现软件中的错误
      • 准则
        • 追溯到用户需求
        • 制定测试计划，并严格执行
        • 注意测试中的群集现象
        • 避免由程序编写者测试自己的程序
        • 不可能进行穷举测试
        • 妥善保存测试计划、测试用例、出错统计和最终分析报告
    • 测试方法
      • 是否需要被执行
        • 静态测试
          • 不实际运行，主要通过人工进行分析
        • 动态测试
          • 上机测试
      • 功能
        • 黑盒测试
          • 测试者完全不了解，或不考虑程序的结构和处理过程
            • 等价类划分法
            • 边界值分析法
            • 错误推测法
            • 因果图
        • 白盒测试
          • 测试者完全了解程序的结构和处理过程
            • 逻辑覆盖测试
            • 基本路径测试
    • 测试的实施
      • 单元测试（模块测试）
        • 方法
          • 动态测试通常以白盒测试法为主，测试其结构
          • 静态测试通常以黑盒测试法为主，测试其功能
        • 目的
          • 发现模块内部的错误
      • 集成测试（组装测试）
        • 目的
          • 发现与接口有关的错误
        • 方法
          • 通常采用黑盒测试法
      • 确认测试（验收测试）
        • 白盒测试
          • 测试程序的内部逻辑结构
            • 逻辑覆盖测试
            • 基本路径测试
        • 黑盒测试
          • 测试程序的外部功能
            • 等价划分法
            • 边界值分析法
            • 错误推测法
      • 系统测试
        • 在实际运行环境下对计算机系统进行一系列集成测试和确认测试
  • 程序调试
    • 基本概念
      • 任务是诊断和修正程序中的错误
    • 调试方法
      • 强行排错法
      • 回溯法
      • 原因排除法
• 数据库设计基础
  • 数据库系统的基本概念
    • 数据库、数据库管理系统和数据库系统
      • 数据
        • 描述事物的符号
      • 数据库
        • 长期存储在计算机内的、有组织的、可共享的数据集合
        • 特点：“集成”与“共享”
      • 数据库管理系统（DBMS）（数据库系统的核心）
        • • 数据语言
            • 数据定义语言（DDL）
              • 数据模式定义
              • 数据存取的物理构建
            • 数据操纵语言（DML）
              • 数据操纵
            • 数据控制语言（DCL）
              • 数据的安全性的定义与检查
              • 并发控制与故障修复
              • 数据的完整性
      • 数据库系统（DBS）
        • 数据库管理员（DBA）
          • 数据库设计
          • 数据库维护
          • 改善系统性能，提高系统效率
        • 硬件平台
          • 计算机
          • 网络
        • 软件平台
          • 操作软件
          • 开发工具
          • 接口软件
        • 数据库
        • 数据库管理系统
      • 数据库应用系统
        • 数据库系统
        • 应用软件
        • 应用界面
    • 数据库技术的发展
    • 数据库系统的基本特点
      • 集成性
      • 高共享、低冗余
      • 独立性
      • 统一管理控制
    • 数据库系统的内部结构体系
  • 数据模型
    • 基本概念
      • 概念
      • 三要素
        • 数据结构
        • 数据操作
        • 数据约束
      • 类型
        • 概念数据模型
          • E-R模型
            • 概念
            • 连接关系
            • E-R图
        • 逻辑数据模型
          • 层次模型
          • 网状模型
          • 关系模型
          • 面向对象模型
        • 物理数据模型
    • 关系模型
      • 数据结构
      • 完整性约束
        • 实体完整性约束
        • 参照完整性约束
        • 束和用户定义的完整性约束
  • 关系代数
    • 差运算
    • 交运算
    • 并运算
    • 笛卡尔积运算
    • 投影运算
    • 选择运算
    • 除运算
    • 连接运算
  • 数据库设计
    • 概述
      • 设计一个能满足用户要求、性能良好的数据库
      • 基本任务
        • 根据用户对象的信息需求、处理需求和数据库的支持环境设计出数据模式
      • 两种方法
        • 面向数据：以信息需求为主，兼顾处理需求（主流）
        • 面向过程：以处理需求为主，兼顾信息需求
    • 设计步骤
      • 需求分析（建立数据字典）
      • 概念设计（设计E-R图）
      • 逻辑设计（把E-R图转换为关系模式）
      • 物理设计
    • 范式
• A
  • B
    • D
      • H
    • E
      • I
  • 图2
  • C
    • 空
    • F
      • G
      • 空
• 图1
  • 连长
    • 排长
      • 班长
        • 战士
        • 战士
        • 战士
      • 班长
        • 战士
        • 战士
        • 战士
    • 排长
      • 班长
        • 战士
        • 战士
        • 战士
      • 班长
        • 战士
        • 战士
        • 战士