一、数组
a+(5*2+3)*2 = a+26
稀疏矩阵：矩阵中大部分元素都是0
解题技巧：代入法（记公式太难！！！）
答案：A
二、数据结构
计算机存储和组织数据的方式。
非线性结构：树，图（有环路）
（1）线性表
单向链表删除元素a2：p->next = (a3) = q->next
单向链表插入x，a1与a2之间：s->next = (a2) = p->next，p->next = s
双向链表原理相同，只是操作两套指针。
顺序存储与链式存储对比：
存储密度：包括存储头节点指针与数据，比如一个元素数据大小为2，可能整个链元素大小为3~4。
队列和栈
队列：先进先出
栈：先进后出
循环队列：队列头尾相接，存入一个元素尾指针向后移一位，删除一个元素头指针向后移动一位。缺点：队空和队满都是头尾指针指在一起，解决：少存一个元素，可以清晰判断尾指针+1就是头指针，表示队满。
练习答案：
（2）广义表
长度：最外层元素个数
深度：层数
表头：最外层第一个元素
表尾：除了表头之外的所有元素组成的广义表
例2答案：
tail(LS1) --> ((b,c),(d,e))
head(tail(LS1)) --> (b,c)
head( head ( tail(LS1) ) ) --> b
(3) 树与二叉树
节点的度：一个节点拥有的孩子节点数，如节点1的度为 2，节点7为0；
树的度：所有节点度数最高值；
叶子节点：4，5，7，8没有孩子节点
分支节点：有分支
内部节点：夹在中间，2，3，6
兄弟节点：同父亲，平级，如4，5
层次：
层次遍历：1，2，3，4，5，6，7，8
前序：根-左-右：1-2-4-5-7-8--3-6
中序：左-根-右：4-2-7-8-5-1-3-6
后序：左-右-根：4-8-7-5-2-6-3-1
普通数转二叉树
连线法：兄弟节点连接起来，有多个孩子的只保留左边第一个那条线
查找（排序）二叉树：左孩子节点均小于根，右孩子节点均大于根
哈夫曼树：无损压缩方式，构造树的带权路径长度最小。
权：元素内值
带权路径长度：
空闲的资源利用起来，方便遍历。
平衡二叉树：提高查找效率，每个节点的平衡度只能为1，0，-1。
平衡度：左右两孩子节点的深度差。
（4）图
矩阵大小取决于节点数量n，矩阵为n*n
邻接表：数组记录可达节点及距离，链表存储
没有被箭头指，表示不受约束。
掌握拓扑排序的流程
图的最小生成树：把图节点间的连线去掉，用最少量线把所有节点连接起来，使得代价总和最小。
普里姆算法：从任意一个节点出发，并设这个节点为红点集，其余为蓝点集，选择该节点距离最近的点连接起来，并将该节点纳入红点集
注意：选的边不能形成环
克鲁斯卡尔算法：从最短边选起，依次选取短边，除去形成环的边。
（5）算法基础
重点：时间复杂度，分析算法的时间复杂度
所有常数级的复杂度都用 O(1) 表示；
循环n次，时间复杂度O(n);
log2(n) 是二叉树查找，有n个节点，最多查找的时间复杂度
限制：键值有序排列
散列表：按内容查询
线性探测法：
伪随机数法：
（6）排序
希尔排序先大致调整排序，再梳理，效率高于直接插入排序
堆排序：先建堆，取走根节点，再重建堆，再取走根节点....
冒泡排序：后面（底部）的往前冒，注意下标的范围变化
快速排序：选定基准，小于基准的放基准前面，大于基准的放基准后面，将原数列分成了两个小数列。再对小数列用递归的方法，就可继续拆分。
归并排序：分组不断合并
基数排序：先按个位收集排序，再按十位收集排序，再按百位收集排序...
