数据结构与算法（面试向）
数据结构与算法（面试向）
一、基础知识
1.1 时间复杂度和空间复杂度概念是啥？
时间复杂度描述算法执行时间随输入规模增长的渐近趋势，通常用基本操作的执行次数来估计。根据分析目标，可以讨论最好、平均和最坏时间复杂度；面试中若没有特别说明，通常重点关注最坏时间复杂度。
空间复杂度描述算法所需存储空间随输入规模增长的渐近趋势。分析时需要说明是否只计算辅助空间，例如原地算法通常指除输入数据和递归调用栈外只使用
1.2 数据的四种存储结构是什么？
顺序存储：把逻辑上相邻的元素存储在物理位置相邻的存储单元中。其存储密度高、局部性好，但需要连续空间，扩容时可能需要整体搬迁，并可能存在预留容量浪费。
链式存储：使用指针表示元素之间的逻辑关系。其不要求连续存储，插入和删除灵活，但需要额外的指针空间，缓存局部性也较差。
索引存储：维护由关键字和地址组成的索引表。其检索速度较快，但会产生额外空间开销，修改数据时还需要维护索引。
哈希存储：根据关键字计算元素的存储地址。理想情况下增删改查的平均时间复杂度为
，但冲突严重时最坏可退化为 ，因此需要合理设计哈希函数、负载因子与冲突处理方式。
1.3 简单介绍一下哈希表？
哈希表又称散列表，是根据关键字直接计算存储位置的数据结构。
常见的哈希冲突解决方法有：
- 开放地址法：发生冲突时，按照探测序列寻找下一个可用槽位。
- 链地址法：每个桶维护一个链表或其他容器，将冲突元素存入同一个桶。
- 再哈希法：发生冲突时，使用另一个哈希函数计算新的探测位置。
二、线性表
2.1 请你对比顺序表和链表的区别？
- 访问方式：顺序表支持按下标随机访问，时间复杂度为
；链表只能沿指针顺序访问，按下标访问为 。 - 存储结构：顺序表中逻辑相邻的元素在物理位置上也相邻；链表中的结点可以分散存储。
- 增删改查：无序顺序表按值查找为
；有序且使用二分查找时为 ，但维护有序性仍可能使插入、删除达到 。链表按值查找为 ；在已经获得插入位置或目标结点及其前驱的情况下，插入、删除可以达到 。
2.2 请你对比一下栈和队列？
栈按“后进先出”的规则处理元素，插入和删除操作都在栈顶进行。
队列在一端插入、另一端删除，按“先进先出”的规则处理元素。
2.3 请你说几个典型的栈和队列的应用？
栈可以用于括号匹配、后缀表达式求值、函数调用、深度优先搜索等。
队列可以用于任务调度、缓冲区管理、消息传递、广度优先搜索等。
2.4 你了解的队列有哪些种类呢？
循环队列：把顺序队列的存储空间看成首尾相连，front指向队头，rear指向下一个可插入位置。只使用两个指针时无法直接区分队空和队满，可以选择牺牲一个存储单元、增加元素计数或增加状态标记。
双端队列：两端都允许插入和删除，可以模拟栈或普通队列。
优先队列：通常使用堆实现。查看最大值或最小值为
2.5 你了解的栈有哪些特殊实现或应用？
共享栈：两个栈共享一个数组，一个从左向右增长，另一个从右向左增长，使两个栈能够动态共享空间。
双栈队列：使用一个输入栈和一个输出栈模拟队列。入队时压入输入栈；出队时，只有输出栈为空才把输入栈的元素全部转移到输出栈。单次操作最坏为
三、字符串
3.1 请你说说字符串匹配算法KMP
朴素字符串匹配的最坏时间复杂度为
以常见的LPS写法为例，next[i]表示模式串前缀P[0..i]的最长相等真前缀与真后缀长度。比较文本串和模式串时，若字符相同，则两个指针同时后移；若字符不同且模式串指针j > 0，则令j = next[j - 1]，文本串指针不回退；若j = 0，则只移动文本串指针。不同教材对next数组的下标和初值定义可能不同，代码中的跳转公式需要与定义保持一致。
3.2 你还知道什么字符串相关的数据结构和算法？
Trie字典树：可以进行字符串查找，并解决公共前缀、词频统计等问题。
AC自动机：结合Trie和失配指针，可以同时匹配多个关键词，常用于敏感词检测、关键词检测和特征匹配。
四、树
4.1 满二叉树和完全二叉树有什么区别？
满二叉树要求除叶结点外，每个结点都有两个孩子，并且所有叶结点处于同一层。若树高为
完全二叉树只允许最后一层不满，并且最后一层的结点必须从左到右连续排列。它可以看作从同高度满二叉树的最后一层自右向左删除若干结点得到。
4.2 树和二叉树能够怎么存储？
- 双亲表示法：用数组存储结点，每个结点记录其双亲在数组中的位置。
- 孩子表示法：每个结点对应一个链表，链表中记录其所有孩子。
- 孩子兄弟表示法：一个指针指向第一个孩子，另一个指针指向下一个兄弟，可以把普通树转换为二叉树表示。
- 二叉链表：二叉树结点保存左、右孩子指针，是最常用的二叉树链式表示。
- 顺序存储：适合完全二叉树。若下标从0开始，结点
的左右孩子通常位于 和 。
4.3 简要说说二叉搜索树、AVL树和红黑树
- 二叉搜索树：左子树的所有键值小于根结点，右子树的所有键值大于根结点。其查找、插入和删除的时间复杂度与树高有关；平均为
，但按有序顺序插入时可能退化为链表，达到 。 - AVL树：一种严格平衡的二叉搜索树，任意结点左右子树高度之差的绝对值不超过1。其查询性能稳定，但插入、删除后可能需要进行旋转调整。
- 红黑树：一种近似平衡的二叉搜索树。根结点和NIL叶结点为黑色；红色结点的孩子必须为黑色；从任一结点到其后代NIL叶结点的所有路径包含相同数量的黑色结点。这些约束保证树高为
。相比AVL树，红黑树平衡要求较松，插入、删除时通常调整更少。
4.4 简要说说B树？
B树是一种多路平衡搜索树，结点中可以保存多个关键字和多个孩子指针，所有叶结点位于同一层。通过提高每个结点的分支数，B树能够显著降低树高，减少磁盘或外存访问次数，因此适合用作文件系统和数据库索引。
4.5 简要说说B+树？
B+树是在B树基础上发展出的多路平衡搜索树。非叶结点只保存关键字和孩子指针，完整记录全部存放在叶结点中；叶结点通常还通过链表顺序连接。因此B+树的单个内部结点能够容纳更多索引项，树高更低，并且特别适合范围查询和顺序访问。
4.6 简要说说哈夫曼树？
给定一组带权叶结点，如果构造出的二叉树具有最小的带权路径长度WPL，则称该二叉树为哈夫曼树。
构造时，每次选择权值最小的两个结点合并为一个新结点，再把新结点放回候选集合中，反复执行直到只剩一个根结点。
典型应用是哈夫曼编码。它是一种前缀编码，任意字符的编码都不是另一个字符编码的前缀，因此解码时不会产生歧义。
五、图
5.1 有什么求最短路径的算法？
BFS：可以求无权图或所有边权相同图的单源最短路径，使用邻接表时复杂度为
Dijkstra：使用贪心思想解决非负权图的单源最短路径。使用邻接表和优先队列时，时间复杂度通常为
Floyd：使用动态规划解决任意两点之间的最短路径，时间复杂度为
Bellman-Ford：解决允许负权边的单源最短路径，时间复杂度为
SPFA：通过队列减少Bellman-Ford中的部分无效松弛，但最坏时间复杂度仍为
A*：使用启发式函数引导从起点到目标点的搜索。若启发式函数满足可采纳性等条件，可以保证找到最短路径；其实际效率高度依赖启发式函数质量。
5.2 有什么求最小生成树的算法？
Prim：从一个起始顶点出发，每次选择连接当前生成树和树外顶点的最小权边。使用邻接矩阵时为
Kruskal：把边按权值从小到大排序，依次加入不会形成环的边，通常使用并查集判断连通性。时间复杂度主要来自边排序，为
六、排序算法
| 排序方法 | 平均时间 | 最坏时间 | 最好时间 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 插入排序 | 稳定 | ||||
| 选择排序 | 不稳定 | ||||
| 冒泡排序 | 稳定 | ||||
| 希尔排序 | 取决于增量序列 | 常见上界 |
取决于增量序列 | 不稳定 | |
| 归并排序 | 稳定 | ||||
| 快速排序 | 平均 |
不稳定 | |||
| 堆排序 | 不稳定 |
6.1 插入排序
该算法将待排序元素分为已排序区和未排序区，每次从未排序区取出一个元素，插入已排序区的适当位置，直到所有元素都有序。
它是一种稳定排序，平均和最坏时间复杂度为
6.2 选择排序
选择排序将元素分为已排序区和未排序区，每次找到未排序区中的最小元素，与未排序区的第一个元素交换，再把该位置加入已排序区。
它通常是不稳定排序，时间复杂度始终为
6.3 冒泡排序
从左到右依次比较相邻元素，如果前一个比后一个大，就交换它们。每轮结束后，未排序部分的最大元素会移动到末尾。
它是一种稳定排序，平均和最坏时间复杂度为
6.4 希尔排序
希尔排序是对直接插入排序的改进。先选择一个较大的间隔gap，把间隔为gap的元素分为一组，每组进行插入排序，再逐渐缩小gap，直到gap = 1。
希尔排序的时间复杂度取决于增量序列，不能统一写成固定的平均复杂度；常见简单增量序列的最坏时间复杂度可达到
6.5 归并排序
归并排序采用分治思想，将数组不断分割为更小的子数组，再把有序子数组逐层合并，最终得到完整有序序列。
其最好、平均和最坏时间复杂度均为
6.6 快速排序
快速排序采用分治思想。它选择一个基准元素，通过分区操作把序列划分到基准两侧，再递归排序左右子序列。存在重复元素时，可以使用三路快速排序把元素划分为小于、等于和大于基准的三部分。
其平均时间复杂度为
6.7 简述一下快速排序和归并排序的优缺点
快速排序在内存数组上通常具有较好的缓存局部性和较小的常数开销，因此实际运行速度往往较快，但其最坏时间复杂度为
归并排序的时间复杂度始终为