计算机二级知识点数据结构与算法思维导图

是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止

特征包括：

一是对数据对象的运算和操作

二是算法的控制结构

一个计算机系统能执行的所有指令的集合

算术运算、逻辑运算、关系运算、数据传输

列举法、归纳法、递推、递归、减斗递推技术、回溯法

顺序结构、选择结构、循环结构

算法时间复杂度和算法空间复杂度

（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；

（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；

（3）对各种数据结构进行的运算

（1）表示数据元素的信息；

（2）表示各数据元素之间的前后件关系

（1）有且只有一个根结点；

（2）每一个结点多有一个前件，也多有一个后件

（1）且只有一个根结点a1，它无前件；

（2）有且只有一个终端结点an，它无后件；

（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表

插入元素称为入栈运算

删除元素称为退栈运算

读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化

入队运算：从队尾插入一个元素

退队运算：从队头删除一个元素

用于存储数据元素值，称为数据域

用于存放指针，称为指针域，用于指向前一个或后一个结点

非空二叉树只有一个根结点

每一个结点多有两棵子树，且分别称为该结点的左子树与右子树

（1）在二叉树的第k层上，多有2k-1(k≥1)个结点；

（2）深度为m的二叉树多有2m-1个结点；

（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；

（4）具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分；

（5）具有n个结点的完全二叉树的深度为[log2n]+1；

（6）设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，….n给结点进行编号（k=1,2….n），有以下结论：

（1）前序遍历（dlr），首先访问根结点，然后遍历左子树，后遍历右子树；

（2）中序遍历（ldr），首先遍历左子树，然后访问根结点，后遍历右子树；

（3）后序遍历（lrd）首先遍历左子树，然后访问遍历右子树，后访问根结点

（1）线性表为无序表；

（2）表采用链式存储结构

冒泡排序法，需要比较的次数为n(n-1)/2

快速排序法

简单插入排序法，坏情况需要n(n-1)/2次比较

希尔排序法，坏情况需要o(n1.5)次比较

简单选择排序法，坏情况需要n(n-1)/2次比较

堆排序法，坏情况需要o(nlog2n)次比较