【408精华知识】速看!408选择题考点全面复盘!!

时间复杂度与空间复杂度:时间复杂度——层层(循环、递归)复杂度相加,空间复杂度——计算额外空间开销。

线性表的顺序表示:基于数组。

线性表的链式表示:基于指针。

栈和队列的基本性质:常考出入栈/队列顺序,牢记栈后进先出、队列先进先出,在头脑中进行模拟。

栈和队列的存储结构:常考循环队列,详见 【408精华知识】循环队列考点总结

双端队列:常考双端队列操作,和基本队列一样,只不过两端均可进或出,在头脑中进行模拟。

栈与队列的应用:常考缓冲区、字符匹配、中缀表达式转后缀表达式等栈与队列的应用,牢记栈后进先出、队列先进先出。

多维数组的存储:常考数组元素存储地址,注意举例子具象化计算数组元素的地址,先算是第多少个元素,再算地址,不要死记硬背。

特殊矩阵的压缩存储:常考对称矩阵、三角矩阵、稀疏矩阵的存储,视情况而定。

串的模式匹配算法:常考KMP算法和优化KMP算法,详见 【408精华知识】KMP算法考点大总结!

树的基本性质:常考树的性质。 (1)树的性质:详见 【408真题】2010-05

二叉树的定义与性质:常考二叉树的性质。 (1)二叉树的性质:详见 【408真题】2010-05

二叉树的遍历:常考三种遍历方式的基本操作。

树、森林与二叉树的转换:常考转换过程,牢记左孩子、右兄弟。

线索二叉树的基本概念和构造:常考线索二叉树的基本概念和构造,左边连左孩子或者前驱,右边连右孩子或者后继,详见 【408精华知识】史上最全的数据结构代码题总结!三万字长文!!!

哈夫曼树与哈夫曼编码:常考哈夫曼树特点与哈夫曼编码过程,详见 【408精华知识】哈夫曼树与哈夫曼编码

并查集:详见 【408精华知识】并查集考点大总结!

图的基本概念:常考图的性质。 (1)图的性质:详见 【408真题】2009-07

图的存储及基本操作:常考图的邻接矩阵、邻接表存储,详见 【408精华知识】史上最全的数据结构代码题总结!三万字长文!!!

图的遍历:常考深度优先遍历、广度优先遍历,详见 【408精华知识】史上最全的数据结构代码题总结!三万字长文!!!

最小生成树:常考Prim算法和Kruskal算法,详见 【408精华知识】图的应用

最短路径:常考Dijkstra算法和BFS算法,详见 【408精华知识】图的应用

拓扑排序:常考AOE网,详见 【408精华知识】图的应用

关键路径:常考AOV网,详见 【408精华知识】图的应用

有向无环图存储算数表达式:常考有向无环图表示表达式,详见 【408真题】2019-06

顺序查找法&折半查找法:常考查找长度,详见 【408精华知识】速看!各种查找的大总结!

二叉排序树:常考二叉排序树概念,左子树所有结点值<根结点值<右子树所有结点值。

平衡二叉树:常考平衡二叉树概念、插入、删除操作。 (1)概念:任何一个结点的左右高度差不超过1。 (2)插入:分为LL、LR、RR、RL四种情况,详见 【408精华知识】平衡二叉树与红黑树的考察

红黑树:常考红黑树概念、插入操作,详见 【408精华知识】平衡二叉树与红黑树的考察

B树及其基本操作、B+树的基本概念:常考B树及其基本操作(插入、删除)、B+树的基本概念,详见 【408精华知识】B树与B+树

散列(Hash)表:常考散列函数、冲突处理方法、装填因子,详见 【408精华知识】散列(Hash)表

插入排序 (1)直接插入排序:详见 【408精华知识】速看!各种排序的大总结! (2)折半插入排序:详见 【408精华知识】速看!各种排序的大总结! (3)希尔排序:详见 【408精华知识】速看!各种排序的大总结!

交换排序 (1)冒泡排序:详见 【408精华知识】速看!各种排序的大总结! (2)快速排序:详见 【408精华知识】速看!各种排序的大总结!

选择排序 (1)简单选择排序:详见 【408精华知识】速看!各种排序的大总结! (2)堆排序:常考堆排序过程,详见 【408精华知识】速看!各种排序的大总结!

二路归并排序:详见 【408精华知识】速看!各种排序的大总结!

基数排序:详见 【408精华知识】速看!各种排序的大总结!

各种内部排序方法的比较:常考各种排序算法之间的对比,详见 【408精华知识】速看!各种排序的大总结!

外部排序的思想:常考外部排序过程,详见 【408精华知识】外部排序考点大总结!