数据结构考研，数据结构考研真题
最近有小伙伴面试，对数据结构和算法比较头疼，我整理了一波资料，帮助大家快速掌握数据结构和算法的面试！
Q1：数据结构和算法的知识点整理
Q2：链表，队列和栈的区别
链表是一种物理存储单元上非连续的一种数据结构，看名字我们就知道他是一种链式的结构，就像一群人手牵着手一样。链表有单向的，双向的，还有环形的。
Q3: 简述快速排序过程
- 选择一个基准元素,通常选择第一个元素或者最后一个元素,
- 通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大。
- 此时基准元素在其排好序后的正确位置
- 然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。
Q4：快速排序算法的原理
是对冒泡排序的⼀种改进，不稳定，平均/最好时间复杂度 O(nlogn)，元素基本有序时最坏时间复杂度O(n²)，空间复杂度 O(logn)
⾸先选择⼀个基准元素，通过⼀趟排序将要排序的数据分割成独⽴的两部分，⼀部分全部⼩于等于基准 元素，⼀部分全部⼤于等于基准元素，再按此⽅法递归对这两部分数据进⾏快速排序。
Q5：什么是 AVL 树？
AVL 树 是平衡⼆叉查找树，增加和删除节点后通过树形旋转重新达到平衡。右旋是以某个节点为中⼼， 将它沉⼊当前右⼦节点的位置，⽽让当前的左⼦节点作为新树的根节点，也称为顺时针旋转。同理左旋 是以某个节点为中⼼，将它沉⼊当前左⼦节点的位置，⽽让当前的右⼦节点作为新树的根节点，也称为 逆时针旋转。
Q6：什么是红⿊树？
红⿊树 是 1972 年发明的，称为对称⼆叉 B 树，1978 年正式命名红⿊树。主要特征是在每个节点上增加⼀个属性表示节点颜⾊，可以红⾊或⿊⾊。
Q7：B 树和B+ 树的区别？
B 树中每个节点同时存储 key 和 data，⽽ B+ 树中只有叶⼦节点才存储 data，⾮叶⼦节点只存储 key。InnoDB 对 B+ 树进⾏了优化，在每个叶⼦节点上增加了⼀个指向相邻叶⼦节点的链表指针，形成了带有顺序指针的 B+ 树，提⾼区间访问的性能。
Q8：排序有哪些分类？
排序可以分为内部排序和外部排序，在内存中进⾏的称为内部排序，当数据量很⼤时⽆法全部拷⻉到内存需要使⽤外存，称为外部排序。
数据结构考研(数据结构考研真题)