计算机二级C语言考试

计算机二级C语言考试学习笔记，通过思维导图的形式，系统而全面地概述了算法设计、数据结构及其基本概念和方法。

计算机二级C语言

• 1.1算法
  • 1.1.1算法的基本概念
    • 解题方案的准确而完整的描述
    • 1.算法的基本特征
      • 可行性（effectiveness）
      • 确定性（definiteness）
      • 有穷性（finiteness）
      • 拥有足够的情报 [输入,输出]
    • 2.算法的基本要素
      • 算法中对数据的运算和操作
        • 算术运算：加、减、乘、除……
        • 逻辑运算：与、或、非……
        • 关系运算：大于、小于、等于、不等于……
        • 数据传输：赋值、输入、输出……
      • 算法的控制结构
        • 顺序
        • 分支 if
        • 循环 for
    • 3.算法设计的基本方法
      • 列举法（比较慢，计算机最擅长的方法）
      • 归纳法
      • 递推
      • 递归
      • 减半递推技术
      • 回溯法
  • 1.1.2算法复杂度：
    • 1.算法的时间复杂度
      • 执行算法所需要的计算工作量
        • 书写算法的程序设计语言
        • 编译产生的机器语言，代码质量
        • 机器执行指令的速度
        • 问题的规模
          • 问题的规模函数
            • 算法的工作量=f(n)
          • T(n)=O(f(n))
          • 常见算法复杂度
            • O(1):常数阶
            • O(n):作线性阶
            • O(n^2)：平方阶
            • O(n^3)：立方阶
            • O(logn)：对数阶
            • O(2^n)：指数阶
          • 分析算法的工作量的两种方法
            • 平均性态
            • 最坏情况复杂性
    • 2.算法的空间复杂度
      • 算法执行过程中所需的最大存储空间
      • 存储量
        • 算法程序所占的空间
        • 输入的初始数据所占的存储空间
        • 算法执行过程中所要的额外空间
      • 可定义为：S(n)=O(f(n))
      • 原地工作(in place)的算法：记作O(1)
      • 压缩存储技术
• 1.2数据结构的基本概率
  • 1.2.1什么是数据结构
    • 1.数据结构研究的主要内容（3个方面）
      • 数据的逻辑结构
        • a.线性结构
          • 线性表
          • 栈
          • 队
        • b.非线性机构
          • 树形结构
          • 图形结构
      • 数据的存储结构
        • a.顺序存储
        • b.链式存储
      • 对各种数据结构进行的运算
        • 检索
        • 排序
        • 插入
        • 删除
        • 修改
        • ……
    • 2.研究数据结构的目的
      • 提高数据处理的速度
      • 节省存储空间
    • 3.数据结构的定义
      • 相互有关联的数据元素的集合
      • 数据元素之间的关系可以用前后件关系来描述
      • 一个数据结构应包含以下两方面信息
        • 表示数据元素的信息
        • 表示各数据元素之间的前后件关系
    • 4.数据的逻辑结构
      • 逻辑关系：对数据元素之间的逻辑关系的描述
      • 只抽象地反应数据元素之间的逻辑关系，与计算机中的存储位置无关
      • 逻辑关系的两个要素：
        • D：数据元素的集合
        • R：前后件关系
      • 数据结构B=(D,R)
    • 5.数据的存储结构
      • 数据的逻辑结构在计算机存储空间的存放形式
      • 常用的存储结构
        • 顺序
        • 链式
        • 索引
      • 不同存储结构，效率不同
  • 1.2.2数据结构的图形表示