计算机二级公共基础知识（第一章）

计算机二级公共基础知识（第一章）

这是自己当年复习java时候留下的，所有的编程类的都要考。没有多少自己的东西，都是书上自己觉得重要的地方，最后考的基本上都在里面吧。如果想拿优（90分以上），这部分必须拿分（其他部分不能丢分）。最好看一下网上的一些模拟题或者真题，好像都是考那几个点。有些地方没写全，反正都在书上。

1. 算法基本特征：
   • 可行性：每个步骤能够实现；结果能达到预期；
   • 确定性
   • 有穷性
   • 拥有足够多的情报
2. 算法设计基本方法
   • 列举法
   • 归纳法
   • 递推
   • 递归
     • 自己调用自己的过程称为递归调用过程
   • 减半递推技术
     • 二分法求方程实根
   • 回溯法
3. 算法的复杂程度
   • 算法时间复杂度：算法的工作量与算法所执行的基本运算次数以及问题的规模有关，而有时算法所执行的基本运算次数与特定的输入有关
     • 平均性态：各种特定输入下基本运算次数的加权平均值。A(n)
     • 最坏情况复杂性：在规模为n时，算法所执行的基本运算的最大次数。W(n)。比A(n)更具有实用价值。
   • 算法的空间复杂度：执行这个算法所需要的内存空间。
4. 数据结构：
   • 数据结构是指反应数据元素之间关系的数据元素集合的表示。
   • 数据处理：是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等，也包括对数据元素进行分析。
   • 前后件关系是数据元素之间的一个基本关系，数据元素之间的任何关系都可以用前后件关系来描述。
5. 数据的逻辑结构：
   • 一个数据结构应该包括：
     • 表示数据元素的信息
     • 表示各元素之间的前后件关系
       其中，数据元素之间的前后件关系是指它们的逻辑关系，与它们在计算机中的存储位置无关
   • B=（D，R） data，relation
6. 数据的存储结构
   • 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构
   • 常用的存储结构：顺序、链接、索引
7. 线性结构与非线性结构
   • 如果在一个数据结构中一个元素都没有，则称该数据结构为空的数据结构
   • 线性结构（线性表）：
     • 有且只有一个根结点
     • 每一个结点最多有一个前件，也最多有一个后件
     • 在一个线性结构中插入或删除任何一个结点后还应是线性结构
   • 非线性结构：不是线性就是非线性
   • 一个空的数据结构是线性还是非线性根据具体情况确定，如果对该数据结构的运算是按线性结构规则处理的则属于线性结构，否则属于非线性结构。
8. 线性表及其顺序存储结构
   • 线性表是由n个数据元素组成的一个有限序列，表中的每一个元素，除了第一个以外，有且只有一个前件，除了最后一个外，有且只有一个后件。
   • 矩阵也是一个线性表
   • 复杂线性表中，由若干数据项组成的数据元素称为记录，由多个纪录构成的线性表又称为文件。
   • 线性表的顺序存储结构：
     • 线性表中所有元素所占的存储空间是连续的。
     • 线性表中个数据元素在存储空间中是按逻辑顺序依次存放的。
   • 顺序表的插入运算：效率低，可能发生“上溢”错误
   • 顺序表的删除运算：效率低，可能发生“下溢”错误
9. 栈和队列
   • 栈：限定在一端进行插入和删除的线性表
     • 在顺序存储结构下，对栈的插入与删除时不需要移动表中其他数据元素的
     • 允许插入与删除的一端称为栈顶，不允许插入和删除的一端称为栈底
     • 先进后出、后进先出（FILO、LIFO），栈具有记忆功能
     • 通常用指针top来指示栈顶的位置，用指针bottom指向栈底
     • 在栈中插入一个元素称为入栈运算，删除一个元素称为退栈运算
     • 栈的顺序存储及运算
       • 入栈运算
       • 退栈运算
       • 读栈顶元素
   • 队列：指允许在一端进行插入，而在另外一端进行删除的线性表
     • 允许插入的一端称为队尾，通常用一个尾指针（rear）指向队尾元素；允许删除的一端称为排头（队头），通常用排头指针（front）指向排头元素的前一个位置。
     • 先进先出、后进后出（FIFO、LILO）
     • 在队尾插入一个元素称为入队运算，从排头删除一个元素称为退队运算。
     • 循环队列：实际应用中，队列的顺序存储结构一般采用循环队列的形式。Front=rear时，队列要么为空，要么为满，所以要加一个标志s，s=0为空，1为非空。
10. 线性链表
    • 链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域，另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点。
    • 线性表的链式存储方式称为线性链表：指针域用于存放指向下一个元素的存储序号。
    • 双向链表：一个左指针（Llink）指向前件结点，一个右（Rlink）指针指向后件结点。
    • 带链的栈：
    • 带栈的队列：
    • 循环链表：增加一个表头结点，最后一个结点的指针域不为空，而是指向表头结点。
      • 只要指出表中任意结点位置，就可以从它出发访问到表中其他所有的结点，线性单链表做不到。
      • 由于设置表头结点，因此，在任何情况下循环链表中至少有一个结点，使空表与非空表运算统一。
11. 树与二叉树：
    • 树中，每一个结点只有一个前件，称为父结点，每一个节点可以有多个后件，称为子结点，没有后件的结点称为叶子结点。一个结点所拥有的后件个数称为该结点的度，在树中，所有结点中最大的度称为树的度；在树中，所有节点的度之和再加一为树的结点数。树的最大层数称为树的深度。
    • 二叉树基本性质：
      • 性质一
      • 性质二
      • 性质三：在任意一颗二叉树中，度为零的结点总是比度为2的结点多一个
      • 性质四：
    • 满二叉树：每一层上的结点数都达到最大值
    • 完全二叉树：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。
      • 性质五
      • 性质六
    • 二叉树存储结构：在计算机中，二叉树通常采用链式存储结构，对于满二叉树和完全二叉树来说，可以按层序进行顺序存储。
    • 二叉树的遍历：
      • 前序遍历（DLR）：根节点、左子树、右子树
      • 中序遍历（LDR）：左子树、根节点、右子树
      • 后序遍历（LRD）：左子树、右子树、根节点
      • 如果知道了前序序列和中序序列或者知道了中序序列和后序序列可以唯一地恢复该二叉树，但是知道了前序序列和后序序列，不能唯一地恢复该二叉树。
12. 查找技术：
    • 顺序查找：对于大的线性表效率低，但是对于无序表和链表只能用顺序查找。
    • 二分法查找：只适用于顺序存储的有序表
13. 排序技术：
    • 交换类排序方式：
      • 冒泡排序：最坏——n（n-1）/2
      • 快速排序：最坏——n（n-1）/2一般比冒泡要好
    • 插入类排序：
      • 简单插入排序：最坏——n（n-1）/2效率与冒泡相同
      • 希尔排序：最坏效率与所选取增量有关
    • 选择类排序：
      • 简单选择排序法：最坏——n（n-1）/2
      • 堆排序法：最坏——nlog2n，对于较小规模不适用，对于较大规模线性表很有效。

OK，第一章是一些数据结构什么的东西，基础的基础，计算机专业的应该都没问题，自学的话也应该了解，毕竟这东西太基础了，也很重要。其实这一本书一个星期就没问题了，最主要的是了解还有理解。在onenote上的笔记，转markdown有点，下面是onenote的链接，不知道能不能用。

ontenote链接