2023新年真题，数据结构与算法面试题

1. 什么是数据?什么是数据结构?

数据是描述客观事物的符号，能够被计算机识别，并且给计算机处理的符号集合

数据结构是计算机内部组织数据的方式

2. 大O表示法

大O符号，又称为渐进符号，是用于描述函数渐近行为的数学符号。更确切地说，它是用另一个通常更简单的函数来描述一个函数数量级的渐近上界。

时间复杂度，是一个用于度量一个算法的运算时间的一个描述，本质是一个函数，它描述的只是代码执行时间随数据规模增长的变化趋势

3. 顺序表和链表

逻辑结构和物理结构，逻辑上都是相邻的元素，但是物理上，顺序表是相邻的，链表一般都是不相邻的

访问元素的时候，对于按值查找，都是O(n)，有序的话是O(log2n)

空间分配的情况，若顺序表是静态分配，空间固定，过多元素会溢出，若是动态分配，扩容存在时间消耗;链表的话则自由灵活

4. 链表反转

方式一：使用栈结构来反转，时间和空间开销不立理想

方式二：使用三指针来反转，效率高

5. 链表升序合并

方法一：递归，时间空间复杂度为O(n+m)

方法二：迭代，时间复杂度为O(n+m)，空间复杂度为O(1)

6. 栈和队列

队列是一端进行插入另一端进行删除的线性表

栈是表尾进行插入和删除的线性表

它们都可以用数组和链表来实现

7. 栈和队列的应用

前缀表达式和后缀表达式

8. 判断循环队列是否为空?

方法一：入队tag=1，出队tag=0

方法二：记录元素数量num

方法三：少用一个空间，(rear+1%maxsize=front

9. 各种二叉树的区别

完全二叉树和满二叉树：除了最后一层外，其他任何一层的节点数均达到最大值，且最后一层也只是在最右侧缺少节点

二叉排序树和二叉搜索树：都是一样的，节点值大于左子节点的数值，小于右边子节点的数值

平衡二叉树(AVL)：任意结点的左、右子树高度差的绝对值不超过1

10. 重建二叉树

根据前，中遍历次序构造二叉树和根据中，后序列构造二叉树，只需要找到头节点，然后递归找到左右子树就行了

至于为什么不能不能根据前，后序列构造出二叉树，是因为，我们只知道最开始头节点的位置，其余元素不清楚是划分到左子树还是右子树

以上就是“2023新年真题，数据结构与算法面试题”，你能回答上来吗?如果想要了解更多的Java面试题相关内容，可以关注星辉Java官网。