公共基础知识

计算机二级 基础知识 计算机 考试 数据结构 算法

数据结构与算法

• 算法（步骤）
  • 定义：是指解决方案的准确而完整的描述。 算法≠程序
  • 特征
    • 可行性
    • 确定性
    • 有穷性：有限步骤，有限时间内完成。
    • 拥有足够情报
  • 算法复杂度（衡量算法的优劣）
    • 时间复杂度：即所需要计算的工作量，≠具体时间，即不受很多细节的影响
    • 空间复杂度：即内存空间
      • 采用压缩技术来降低空间复杂度
      • 输入
      • 程序本身
      • 额外空间
• 数据结构
  • 定义：指相互有关联的数据元素的集合。
    • 包含两要素
      • 数据：集合
      • 结构：关系
  • 表示
    • 数学形式定义：二元组
    • 图形
  • 分类
    • 逻辑结构：反映数据元素之间的逻辑关系（即前后件关系）
      • 线性结构 1.有且只有一个根节点 2.每个节点最多只有一个前件， 最多只有一个后件
        • 线性表 最常用也是最简单的一种数据结构
          • 顺序存储（顺序表）
            • 特征
              • 存储空间连续
              • 按逻辑顺序依次存放
              • 可以随机访问
              • 不便于插入和删除元素
            • 特殊情况
              • 栈：在限定的一端插入和删除
                • 原则：先进后出
                • 特点
                • 运算
              • 队列：是指允许在一端进行插入在另一端进行删除
                • 原则：先进先出
                • 特点
                • 循环队列
          • 链接存储（线性链表，链表，单链表）
            • 特点
            • 双向链表
            • 循环链表
        • 非空线性表
      • 非线性结构
        • 树：是n个元素的有限集合
          • 父节点
          • 子节点
          • 根节点
          • 叶子结点
          • 节点的度
          • 树的度
          • 树的深度
          • 子树
        • 二叉树：是一个有限节点的集合，该集合或者为空，或者有一个根节点及其两课不相交的左右二叉树所组成。
          • 特点
          • 状态
          • 特殊二叉树
          • 性质
          • 遍历
    • 存储结构（物理结构）：逻辑结构在计算机中的存放方式。
  • 查找技术
    • 顺序查找
    • 二分查找
  • 排序
    • 交换类
    • 插入类
    • 选择类
• 与问题规模有关也与输入有关
• 用基本运算次数来度量
• 根节点：无前件 终端节点（叶子节点）：无后件 内部节点：除以上两种外的节点