前言
分数，排名，国家线都出来了，北斗学院成为了大赢家，也不知道各位准备的如何，本人初试成绩不太理想，之前就找厂工作去了，做内容审核还蛮有意思的，也经历了十亿级数据量的洗礼，发现了编程这个东西还是得在实践中提升，没有经历那样的数据量在书本上学来的技术根本就没办法去解决问题，扯远了，后面看到排名和国家线感觉自己还有机会，所以就又又又辞职回来准备复试，所以复试的博客也准备更起来了！
数据结构与算法十二问
其实数据结构面试不太好问问题我这边总结了十二条比较常见的问题，回答的时候可以适当的去延伸一下，比如面试官问你二叉树是什么，你可以把你所知道的都说出来，
像：
二叉树是每个结点最多有两个子树的树结构，二叉树是递归定义的，其结点有左右子树之分，通常包含：满二叉树、完全二叉树、平衡二叉树、二叉搜索树等。
其中满二叉树是xxxx
完全二叉树是xxxx
二叉搜索树是xxx
平衡二叉树是在二叉搜索树上优化了xxxx
延伸：
还有B树是xxx
B+树是XXX
MySQL的数据结构是xxx
。。。
请介绍一下贪心算法
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
例如活动安排问题，找零钱问题都可以采用贪心算法
请介绍一下动态规划算法
将问题分解成多个子问题，通过备忘录的形式记录下子问题的解，在遇到重复的子问题可以利用备忘录，同时记录下最优解，每次子问题的解和记录下的最优解比较，若更好则替换，最后获得全局最优解，是自底向上的。
「回溯算法」需要记录每一个步骤、每一个选择，用于回答所有具体解的问题；
「动态规划」需要记录的是每一个步骤、所有选择的汇总值（最大、最小或者计数）；
「贪心算法」由于适用的问题，每一个步骤只有一种选择，一般而言只需要记录与当前步骤相关的变量的值。
请介绍一下分治算法
将问题划分成n个子问题，然后递归解决，最后合并，例如归并排序，是自顶向下的
循环的效率比递归高吗
不能说二者谁的效率更高，递归需要有递归出口，当调用次数多后，要增加额外的栈处理，对执行效率有一定影响，循环结构简单，速度快，但有些问题需要有递归解决
什么是顺序表
1.顺序表可以顺序存储，也可以随机存储
2.顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。
3.对于按值查找是顺序存储的顺序表，可以用折半查找，时间复杂度为O(log2n) 。无顺序时时间复杂度为O(n) 。
4.对于按序号查找，顺序表支持随机访问，时间复杂度仅为0(1)
5.顺序表一般在初始化时就分配了存储空间大小
6.数组就是顺序表
什么是链表
1.链表只能从表头顺序存储元素，所以一般用链表时不会保证顺序
2.用链式存储时，逻辑上相邻的元素，物理存储位置则不一定相邻，对应的逻辑关系是通过指针链接来表示的。
3.在插入删除操作时，只需要修改相关指针，时间复杂度仅为0(1)
4.链表在存储结点空间时可以动态分配空间，只要内存有空间，链表就可以分配
os：java金典八股文array和ArrayList的区别
栈和队列的区别
1.队列像倒的长方形，左边进去右边出来的管道，所以有先进先出的规则，具体应用像redis的list数据类型和kafka，rabbitMQ等各种消息队列
2.栈像立起来的水杯，上面进去上面出去，所以有后进先出的规则，具体应用像jvm的本地方法栈和虚拟机栈。
什么是二叉树
二叉树是每个结点最多有两个子树的树结构，二叉树是递归定义的，其结点有左右子树之分，通常包含：满二叉树、完全二叉树、平衡二叉树、二叉搜索树等。
满二叉树
如果二叉树中所有分支结点的度数都为2，并且叶子结点都在统一层次上，则二叉树为满二叉树，从图形形态上看，满二叉树外观上是一个三角形；从数学上看，满二叉树的各个层的结点数形成一个首项为1，公比为2的等比数列。如图：
完全二叉树
完全二叉树从根结点到倒数第二层满足满二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
二叉查找树
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它可以是一棵空树，也可以是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树
平衡二叉树
平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。
前序遍历
前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fkU0supD-1647070934147)(C:%5CUsers%5Clenovo%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20220224112401868.png)]
中序遍历
中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。
通常来说，对于二叉搜索树，我们可以通过中序遍历得到一个递增的有序序列。 我们将在另一张卡片（数据结构介绍 – 二叉搜索树）中再次提及。
后序遍历
后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。
层序遍历
层序遍历就是逐层遍历树结构。
什么是图
「图」的类型有三种类型：无向图、有向图、加权图。
深度优先搜索算法
利用栈，一条路走到底，在返回来，递归实现 dfs
广度优先搜索算法
利用队列，bfs，一个常见应用是找出从根结点到目标结点的最短路径。
时间复杂度 O(n^2) 级排序算法有哪些
冒泡排序，选择排序，插入排序
时间复杂度 O(nlogn) 级排序算法有哪些
希尔排序，堆排序，快速排序，归并排序
时间复杂度 O(n) 级排序算法有哪些
计数排序，基数排序，桶排序
最后
面试模拟互助
以上内容是第一期，如果对大家有用的话在做第二期吧
发起一个投票吧，下一篇博客大家是想看自我介绍还是操作系统
版权归原作者 钟兴宇 所有， 如有侵权，请联系我们删除。