嵌入式面试2022年嵌入式经典面试题汇总数据结构
【嵌入式面试】2022年嵌入式经典面试题汇总（数据结构）
📜作者：
📺专栏：《 》
📣格言： 没有不可治愈的伤痛，没有不可结束的沉沦。所有失去的，会以另一种方式归来。
前言
2022年秋招我面试嵌入式MCU开发方向，经过了多场的笔试与面试，在准备的过程中看了非常多的资料，我的汇总的笔记一直写在有道云笔记中，没有分享出来。现在已经到了23年春招了，特此整理后分享出来。资料看过了觉得不错就保存下来了，如果有不对的地方，欢迎批评指正，侵权联删！
1、链表与顺序存储结构（顺序表）的区别？
（1）存储顺序区别：链表使用动态开辟的数组方式存储，物理上不连续，逻辑上连续，一般存储顺序是随机非连续的；而顺序表是连续存储的空间，达到物理上一定连续；
（2）随机访问上：链表访问方式是O（N），而顺序表是O（1）（用下标访问），此处顺序表优势更大；
（3）可扩展性上：链表没有容量的概念，可以随意申请堆空间进行插入，扩展性大；静态顺序表是在定义时开辟空间，不支持扩容；
（4）任意位置插入或者删除元素上：链表只需修改指针指向，在删除是释放空间；而顺序表需要搬移元素，效率低O(N)下；
（5）缓存利用率：链表利用率低，顺序表利用率高。
2、内核链表与单/双循环链表的区别？
2.1 内核链表
（1）内核链表的数据取出是根据指针域的首地址计算出数据域的首地址，再根据数据域的地址取值的。即数据域地址 = 指针域地址 - 数据域到指针域的偏移量；
（2）内核链表是去除节点中的具体数据，只保留逻辑的双向指针，形成一条只包含逻辑的链表；
（3）只有逻辑，不包括数据，对任意类型的数据进行操作时，只需要之前的逻辑上在写一个函数，使用更便利；
（4）小结构体定义为变量而不是指针：变量有空间，指针没有空间。
2.2 单/双循环链表
（1）链表中包括指针和数据的逻辑链表；
（2）在链表中进行不同类型的数据条件遍历时需要重构函数，并且操作不便利。
3、栈和队列的区别？
（1）栈先进先后；
（2）队列先进先出。
4、红黑二叉树【平衡二叉树】，平衡树是什么？
（1）红黑树:是一种自平衡的二叉查找树。是一种特殊的二叉查找树。红黑树的每一个节点上都有存储位表示节点的颜色。每一个节点可以是红色或者黑色。
红黑树不是高度平衡的，它的平衡是通过红黑规则进行实现的。
（2）平衡树：每个结点都有两个子节点。
（3）平衡二叉树：任意节点的子树的高度差都小于等于 1。
5、二叉查找树【二叉排序树】（BST）具备的特性？
（1）左子树上所有结点的值均小于或等于它的根结点的值。
（2）右子树上所有结点的值均大于或等于它的根结点的值。
（3）左、右子树也分别为二叉排序树。
结语
数据结构自己遇到的面试题比较少，因此可以参考我发的或者网上的其他资料。