866数据结构重点内容

线性表是逻辑结构还是物理结构？
顺序表的随机访问是什么意思？
顺序表的插入与删除操作是如何实现的？
顺序表的插入和删除移动次数？
顺序表和单链表的结构体怎么定义？
带头结点和不带头结点判空怎么判断？
单链表插入和删除怎么实现？
单链表、双链表的插入删除顺序问题
如何高效的将顺序表逆置？
如何删除有序表的重复值？
如何将两个有序表合成一个有序表？
如何将单链表就地逆置？
如何删除单链表中介于两值之间的元素？
如何将两个有序单链表归并成一个有序单链表？
如何得到单链表的倒数第k个元素？

三、栈和队列

22年866真题：3个选择+1个简答，共计16分

栈和队列能在哪进行插入和删除？
栈和队列的特点？
顺序栈的两种定义以及操作（入栈、出栈、获取栈顶、判断栈空、栈满）
共享栈的栈满条件？
循环队列队满和元素个数公式？
N个元素进栈，出栈个数？
栈和队列顺序题目？（必考）
如何将队列逆置？
括号匹配思想和代码？
数组和特殊矩阵（对称、三角、三对角）存储注意事项？（优先带值法）

四、串

next数组和nextval数组计算

五、树和二叉树

22年866真题：1个选择+1个简答+1个计算+1个代码，共计37分

度为m的树和m叉树的区别？
满二叉树和完全二叉树有什么特点？
树和二叉树的常考性质（第i层最多结点、高度为h最多结点、最小高度h）
N个结点二叉链表空链域有多少？
二叉树和遍历序列之间如何转换（必考）
层次遍历的思想和代码
线索二叉树怎么构造？
孩子兄弟表示法怎么做？
树的先根和后根遍历与二叉树遍历有什么关系？
二叉排序树怎么逐步构造？相同值怎么处理？
二叉排序树插入和删除代码
二叉排序树的删除情况和ASL计算
平衡二叉树的逐步构造
高度为h的平衡二叉树最少结点个数？
哈夫曼树构造及哈夫曼编码
如何判断是否为完全二叉树？
如何判断是否是二叉排序树？
如何判断是否是平衡二叉树？

六、图

22年866真题：2个选择+2个计算+2个代码，共计44分

无向图和有向图边和结点关系？
连通图和强连通图是什么意思？
无向完全图和有向完全图边数
邻接矩阵、邻接表与图之间转换
BFS、DFS序列和生成树
BFS和DFS代码（王道+866）
最小生成树构造两种方法（Prim、Kruskal）
Dijkstra计算最短路径
Flyod代码（866）
拓扑排序序列（必考）
关键路径计算

七、查找

22年866真题：2个选择+1个计算，共计14分

折半查找以及折半查找树
散列查找（线性探测法、平方探测法）（必考）
自组织线性表三种规则

八、排序

22年866真题：1个选择+1个简答+1个计算+1个代码，共计32分

基于比较的算法，至少需要比较次数？
直接插入排序思想和每一步结果
希尔排序每一步结果
冒泡排序每一步结果
快速排序每一步结果及代码
简单选择排序每一步结果
堆排序每一步结果及代码
如何插入和删除堆的元素？
归并排序的每一步结果及代码
基数排序的每一步结果
内部排序的比较（时间复杂度、空间复杂度、稳定）
如何将奇数偶数（正数负数）分开？
输出第K大的元素
如何在链表上进行各种排序？