计算机公共基础知识

马上就要考计算机二级了，但你却对知识概念不清楚？一张图帮你轻松搞定公共基础部分知识，让你高分飘过考试。本土涵盖了二级考试中的算法、数据结构、程序设计基础、软件工程基础以及数据库设计基础等基础知识点。快点收藏学习拿证挣钱啦。

公共基础知识

• 算法
  • 含义：解决问题的操作步骤。不等于程序，程序可以描述
  • 特征
    • 可行性
    • 确定性
    • 有穷性
    • 拥有足够情报
  • 复杂度
    • 时间复杂度
      • 含义：执行算法所需要的计算工作量
      • ≠算法程序执行所需具体时间
      • 衡量：利用算法所执行的基本运算次数赖衡量，与问题规模有关
      • 在具体分析算法工作量时，同一问题规模下，算法所执行的次数还可能与特定的输入有关。
    • 空间复杂度
      • 含义：执行这个算法所需要的内存空间
      • 组成
        • 输入数据所占的存储空间（即问题规模）
        • 程序本身所占的存储空间
        • 算法输入过程所需要的额外空间
          • 算法执行程序过程中的工作单元
          • 某种数据结构所需要的附加存储空间
        • 算法原地工作：额外空间不随问题规模的变化而变化
      • 减低方法：压缩存储技术（减少输入数据所占存储空间以及额外空间）
• 数据结构
  • 含义：相互有关联的数据元素的集合
  • 要素
    • 数据
      • 含义：需要处理的数据元素的集合（元素具备共同特征）
    • 结构
      • 含义：集合中各种元素间存在的某种关系
      • 通常把两两元素之间的关系用前后件关系（直接前驱与直接后关系）来描述
  • 包含
    • 数据的逻辑结构
      • 数据元素之间逻辑关系（即前后件关系）
    • 数据的存储结构
      • 数据逻辑结构在计算机存储空间中的存放方式（数据的物理结构）
  • 表示
    • B=(D,R)
      • B表示数据结构，D表示数据元素集合，R是D上的数据元素的关系
  • 划分
    • 线性结构
      • 含义：非空的数据结构；有且只有一个根节点；每个节点最多只有一个前件和后件
      • 名称：线性表（是有限序列）
      • 表示：（a1,a2,...ai,...,an)
      • 存储结构
        • 顺序存储结构
          • 元素一个接一个地存储在相邻区域（也称作顺序表）
            • 特征
              • 元素存储所占空间是连续的
              • 按照逻辑循序排列
        • 链接存储
          • 线性链表（链表/单链表）
            • 第一个元素没有前件，指向链表第一个元素的指针称为头指针（head）最后一个元素没有后件，最后一个指针域为空用null或者0表示
            • 各元素之间可以连续/不连续，位置关系与逻辑关系不一致
          • 带链的栈
          • 带链的队列
          • 循环链表
            • 子主题
        • 顺序表：优，随机存储任意节点，逻辑关系不需要额外空间；缺，插入与删除效率低，不便于扩充，不便于动态分配；链表与之相反
      • 特殊线性表
        • 栈
          • 栈顶：允许插入与删除
          • 栈底
          • 原则：后进先出或先进后出
          • 基本运算
            • 入栈
            • 退栈
            • 读栈顶元素
          • 实现方法
            • 顺序方式
            • 链接方式
        • 队列
          • 队头：允许删除运输
          • 队尾：允许插入运输
          • 原则：先进先出或后进后出
          • 循环队列
            • 含义：将队列存储空间的最后一个位置绕到第一个位置，形成环状空间
            • 队头指针front的后一个位置到队尾指针real之间的所有元素都为队列中的元素
    • 非线性结构
      • 除了线性结构的条件，主要指树形结构和网状结构
      • 树
        • 父节点；子节点和叶节点；度；深度；子树
        • 节点数=节点度+1
      • 二叉树
        • 特点
          • 可以为空
          • 每个节点最多两棵子树
          • 子树有左右之分，次序不能颠倒
        • 性质
          • 第K层上最多有2∧(K-1)个节点
          • 深度为M的二叉树，最多有2∧M-1个节点
          • 任何一颗二叉树，度为0的节点总是比度为2的节点多一个
          • 具有N个节点的二叉树，其深度至少为[㏒₂n]+1，其中[㏒₂n]表示㏒₂n取整数的部分
          • 具有n个节点的完全二叉树的深度为[㏒₂n]+1
        • 满二叉树
          • 除最后一层外，每层上所有节点都有两个子节点的二叉树
        • 完全二叉树
          • 除最后一层外，每层上所有节点均达到最大值，在最后一层上只缺少右边的若干节点的二叉树
          • 特点
            • 叶子节点只可能出现在最后两层
            • 对于任意节点，若右子树的深度为m则左子树的深度为m+1
        • 采用链式存储结构
          • 数据域
          • 指针域
        • 顺序存储
          • 满二叉树
          • 完全二叉树
        • 二叉树的遍历
          • 不重复的访问二叉树中的所有节点
          • 先左后右
            • 前序遍历
              • 根 左 右
            • 后序遍历
              • 左 右 根
            • 中序遍历
              • 左 根 右
            • 已知前序遍历和中序遍历可以唯一确定二叉树，一直后序遍历和中序遍历可以唯一确定二叉树
    • 查找技术
      • 顺序查找：从线性表的第一个元素开始，逐个将线性表中的元素与被查找的元素进行比较，若成功停止查找，不成功继续查找。直至整个线性表查找完毕，查找失败
        • 最好：第一个就是要找的元素1次
        • 最坏：最后一个元素才是要找的元素，或者是没有找到元素n次
        • 平均情况：n/2
        • 只能用顺序查找
          • 线性表是无序的
          • 线性表是有序的，但存储结构为链式存储
      • 二分法查找
        • 条件
          • 顺序存储结构
          • 线性表是有序的（从小到大排序）
        • 过程
          • X值与中间值进行比较如果相同，结束查找
          • X值＜中间值，则在线性表的前半部分以二分法继续查找
          • X值＞中间值，则在线性表的后半部分以二分法继续查找
    • 排序技术
      • 含义：将无序序列整理成按从小到大排序的有效序列
      • 交换类排序法
        • 含义：借助数据元素的交换来进行排序的一种方法
        • 冒泡排序法
          • 两两相邻数据元素之间的比较和交换，不断地消去逆序（某个元素后存在比其小的元素），直到所有数据元素有序为止
          • 最坏：对长度n的线性表进行排序，冒泡排序需要比较的次数为n(n-1)/2
        • 快速排序
          • 在待排序的n个元素中抽取一个，以这个元素K作为分割标准，把所有小于K的元素，移到K的左边，把所有大于K的元素，移到K的右边。以K为分界线，把线性表分成两个子表（成为一趟排序），两个子表重复上述过程。直至子表长度为1
      • 插入类排序
        • 含义：将每次将一个待排序的元素，按其值大小插入到前面已经排好序的子表中
        • 简单插入排序
          • 把n个待排序的元素看成由有序表和无序表，开始时有序表只有一个，每次取一个无序表中的元素插入到有序表的正确位置。最后有序表长度为n，无序表长度为0
          • 最坏的情况：排序进行n(n-1)/2次
        • 希尔排序
          • 先取一个整数d₁小于n，把所有元素分成d₁个组，所有距离为d₁倍数的元素放在一起，组成子序列对每个子序列进行简单插入排序。然后去d₂小于d₁重复上述过程，直到di=1
          • 最坏的情况：n∧r
      • 选择类排序法
        • 含义：每次从待排序序列中选出值最小的一个，放在已排好序的有序子表的后面，直至排好序
        • 简单选择排序法
          • 从n个带排序的元素中选择最小的一个与第一个交换，再从剩下的元素中找到最小的元素与第二个交换，重复以上过程直至排序完成。
          • 最坏的情况：排序进行n(n-1)/2次
        • 堆排序法
          • 若有n个元素的序列，将元素按照顺序组成一个完全二叉树，满足Hi≥H2i且Hi≥H2i+1或者Hi≤H2i且Hi≤H2i+1
          • Hi≥H2i且Hi≥H2i+1为大根堆，所有节点值大于或者等于左右子节点的值
          • Hi≤H2i且Hi≤H2i+1为小根堆，所有节点值小于或者等于左右子节点的值
          • 最坏的结果：n㏒₂n
    • 没有数据元素☞
• 程序设计基础
  • 程序的质量
    • 方法
    • 技术
    • 风格
      • 源程序文档化
      • 数据说明风格
      • 语句结构
      • 输入与输出
  • 程序设计
    • 结构化程序设计
      • 原则
        • 自顶向下
        • 逐步求精
        • 模块化
        • 限制使用goto语句
      • 基本结构
        • 循序结构
        • 选择结构
        • 循环结构
        • 一个入口一个出口
      • 优点：易于理解、使用和维护，提高效率，降低开发成本
    • 面向对象程序设计
      • 优点：人类思维一致，稳定性豪，可重用性好，容易开发大型软件产品，可维护性好
      • 对象
        • 数据
        • 方法
        • 特点：标识唯一性，分类性。多态性，封装性，模块独立性好
      • 类和实例
        • 类：具有共同属性和共同方法的对象的集合
        • 实例：即类中的一个具体对象
      • 消息
        • 对象间通信的手段
      • 继承
        • 类与类之间可以继承，一个子类可以重新定义其父类的全部描述，也可以定义自己的属性和操作。
        • 继承具有传递性
      • 多态性
        • 子类对象可以和父类对象那样使用，消息可以发给父类对象也可以发给子类对象。
• 软件工程基础
  • 计算机系统
    • 计算机软件
      • 组成
        • 相关文档
        • 数据
        • 程序
      • 特点
        • 逻辑实体，抽象性
        • 复杂性高，成本昂贵
        • 诸多社会因素
      • 分类
        • 系统软件
          • 管理计算机的资源
            • 操作系统os
            • 数据库管理系统DBMS
            • 汇编程序
            • 网络软件
        • 应用系统
        • 支撑软件（工具型软件）
      • 软件工程
        • 要素
          • 工具
          • 过程
        • 原则
          • 抽象、隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性
      • 软件过程
        • 含义：把输入转化为输出的一组彼此相关的资源和活动，规定了工作步骤。
        • 基本活动
          • 软件规格说明
          • 软件开发或者软件设计与实现
          • 软件确认
          • 软件演进
      • 软件生命周期
        • 软件定义期
        • 软件开发期
          • 软件开发
            • 独立性原则
              • 内聚性：一模块内部各元素彼此结合的紧密程度
              • 耦合性：不同模块间相互依赖的程度
            • 概念设计（总体设计）
              • 将软件按照功能分解
              • 任务
                • 设计软件系统结构
                • 数据结构和数据库设计
                • 编写概要设计文档
                • 概要设计文档评审
              • 工具
                • 结构图
              • 子主题
            • 详细设计
              • 确定实现算法和局部数据结构
              • 工具
                • 程序流程图
                • PDL
          • 软件测试
            • 尽可能发现软件中的错误
            • 方法
              • 是否需要被执行
                • 静态测试
                  • 人工分析
                • 动态测试
                  • 上机操作
              • 功能划分
                • 白盒测试
                  • 将程序看成装在一只透明的白盒子里，完全了解程序结构
                • 黑盒测试
                  • 把程序看成装在黑盒子里，测试者完全不了解
                  • 等价类划分法
                  • 边界值分析法
                  • 错误推测法
                  • 因果图
            • 实施
              • 单元测试（模块测试）
                • 动态测试
                • 静态测试
                • 以白盒测试为主，黑盒测试为辅
              • 集成测试
                • 各模块按照设计要求组装成程序进行测试
                • 黑盒测试
                • 集成方式
                  • 非增量方式继承
                  • 增量式方法集成
              • 确认测试（验收测试）
                • 黑盒测试
              • 系统测试
          • 程序调试
            • 发现错误之后排除错误
            • 步骤
              • 确定错误位置
              • 对错误进行修改
            • 方法
              • 动态调试
              • 静态调试
              • 强行排错法
              • 回溯法
              • 原因排除法
        • 运行维护期
        • 任务
          • 问题定义
          • 可行性研究
          • 需求分析
          • 软件设计
          • 软件实现
          • 运行维护
      • 程序、数据计算机可执行，文档计算机不可执行
    • 计算机硬件
  • 需求分析
    • 工作
      • 需求获取
      • 需求分析
      • 编写需求规格说明书
        • 目标
        • 功能需求
        • 性能需求
        • 外部接口
        • 属性及约束条件
        • 正确性、无歧义性、完整性、可验证性、一致性、可理解性、可修改性、可追踪性
      • 需求评审
    • 方法
      • 结构化分析方法
        • 工具
          • 数据流图
          • 数据字典
          • 结构化英语
          • 判定表
          • 判定树
      • 面向对象分析方法
      • 静态分析方法
      • 动态分析方法
• 数据库设计基础
  • 基本概念
    • 数据
      • 持久性数据
      • 临时性数据
    • 数据库：数据合集
      • 集成
      • 共享
    • 数据库管理系统
      • 是数据库的机构
    • 数据库管理员
    • 数据库系统
      • 内部结构
        • 三级模式、两级映射
    • 数据库应用系统
    • 数据库技术的发展
      • 人工管理阶段
      • 文件系统阶段
      • 数据库系统阶段
        • 集成性
        • 高共享低冗余
        • 数据统一管理与控制
  • 数据模型
    • 组成
      • 数据结构
      • 数据约束
      • 数据操作
    • 类型
      • 概念模型
        • E-R模型
          • 实体
          • 属性
          • 联系
            • 一对一
            • 一对多
            • 多对多
          • E-R图
            • 实体集表示法
            • 属性表示法
            • 联系表示法
        • 关系模型
          • 性质
            • 元组有限个，元组唯一性，元组是基本数据不可再分
            • 属性名唯一性，次序无关，值域统一性
      • 数据模型
      • 物理模型
  • 关系代数
    • 差运算
    • 交运算
    • 并运算
    • 笛卡儿积运算
    • 投影运算
    • 选择运算
    • 除运算
    • 连接运算
• 好的软件：高内聚，低耦合；顶层高扇出，中间扇出较少，底层高扇入
• 例如把一日三餐看作一个数据结构，则表示成： B=（D,R) D=｛早餐，午餐，晚餐｝ R=｛（早餐，午餐），（午餐，晚餐）｝