编程面试的 8 大数据结构和练习面试题

什么是数据结构？

常用数据结构

数组

堆栈

队列

链表

图表

树木

特里树

哈希表

瑞士计算机科学家 Niklaus Wirth 于 1976 年写了一本书，书名是：

算法+数据结构=程序

40多年后，这个等式仍然成立。这就是为什么软件工程候选人必须展示他们对数据结构的理解以及应用。

几乎所有问题都要求候选人展现对数据结构的深刻理解。无论你是刚毕业（大学或编程训练营毕业），还是拥有数十年经验，都无关紧要。

有时面试问题会明确提到数据结构，例如“给定一个二叉树”。有时则是隐含的，例如“我们想要跟踪与每位作者相关的书籍数量”。

即使你只是想提高目前的工作效率，学习数据结构也至关重要。让我们先从基础知识开始。

如果您正在寻找有关编码面试的数据结构资源，请查看基于交互式和挑战的课程：掌握编码面试的数据结构，其中包含 Python、Java、C++ 和 JavaScript 的数据结构面试课程。

对于更高级的问题，请参阅《Grokking the Coding Interview: Patterns for Coding Questions》。

什么是数据结构？

简而言之，数据结构是一种以特定布局存储数据的容器。这种“布局”使得数据结构在某些操作中高效，而在其他操作中低效。你的目标是理解数据结构，以便能够选择最适合当前问题的数据结构。

为什么我们需要数据结构？

由于数据结构用于以有组织的形式存储数据，并且数据是计算机科学中最重要的实体，因此数据结构的真正价值是显而易见的。

无论您要解决什么问题，您都必须以某种方式处理数据 - 无论是员工工资、股票价格、购物清单，还是简单的电话簿。

根据不同的场景，数据需要以特定的格式存储，我们有一些数据结构可以满足我们以不同格式存储数据的需求。

常用数据结构

让我们首先列出最常用的数据结构，然后再更详细地介绍它们：

1. 数组
2. 堆栈
3. 队列
4. 链表
5. 树木
6. 图表
7. 尝试（它们实际上是树，但最好还是单独调用它们）。
8. 哈希表

数组

数组是最简单且使用最广泛的数据结构。其他数据结构（例如堆栈和队列）都源自数组。

下面是一个大小为 4 的简单数组的图像，包含元素（1、2、3 和 4）：

每个数据元素都被赋予一个正数值，称为“索引”，该值对应于该元素在数组中的位置。大多数语言将数组的起始索引定义为 0。

以下是两种类型的数组：

• 一维数组（如上图）
• 多维数组（数组中的数组）

数组的基本操作

• 插入 - 在给定索引处插入元素
• 获取 - 返回给定索引处的元素
• 删除 - 删除给定索引处的元素
• Size——获取数组中元素的总数

常见的数组面试问题

• 查找数组的第二个最小元素
• 数组中第一个不重复的整数
• 合并两个已排序的数组
• 重新排列数组中的正值和负值

堆栈

我们都熟悉著名的“撤消”选项，它几乎存在于每个应用程序中。有没有想过它是如何工作的？原理是：将之前的工作状态（数量限制为特定值）按顺序存储在内存中，最后一个状态会首先出现。这不能仅通过数组来实现。这时，堆栈就派上用场了。

一个实际生活中的堆栈示例可能是一堆垂直放置的书。为了取出位于中间的书，你需要移除所有放置在其上方的书。这就是 LIFO（后进先出）方法的工作原理。
下图显示了包含三个数据元素（1、2 和 3）的堆栈，其中 3 位于顶部，将首先被移除：

堆栈的基本操作：

• Push - 在顶部插入一个元素
• Pop - 从堆栈中移除后返回顶部元素
• isEmpty - 如果堆栈为空，则返回 true
• Top - 返回顶部元素，但不从堆栈中删除

常见的 Stack 面试问题

• 使用堆栈评估后缀表达式
• 对堆栈中的值进行排序
• 检查表达式中的括号是否平衡

队列

与 Stack 类似，Queue 是另一种线性数据结构，它以顺序方式存储元素。Stack 和 Queue 之间唯一显著的区别是，Queue 不是使用 LIFO 方法，而是使用 FIFO 方法，即先进先出 (FIFO) 方法。

一个完美的现实生活中排队的例子：一群人在售票处排队等候。如果有新人加入，他会从队尾加入，而不是从队首加入——而站在队首的人会第一个拿到票，从而离开队伍。

下面是一个包含四个数据元素（1、2、3 和 4）的队列图像，其中 1 位于顶部，将首先被删除：

队列的基本操作

• Enqueue() - 在队列末尾插入元素
• Dequeue() - 从队列开头删除一个元素
• isEmpty() - 如果队列为空，则返回 true
• Top() - 返回队列的第一个元素

常见的队列面试问题

• 使用队列实现堆栈
• 反转队列的前 k 个元素
• 使用队列生成从 1 到 n 的二进制数

链表

链表是另一种重要的线性数据结构，它乍一看可能与数组相似，但在内存分配、内部结构以及插入和删除的基本操作的执行方式上有所不同。

链表就像一个由节点组成的链条，每个节点都包含数据等信息，以及指向链中后续节点的指针。链表有一个头指针，指向链表的第一个元素。如果链表为空，则头指针指向 null 或空值。

链表用于实现文件系统、哈希表和邻接表。
以下是链表内部结构的直观表示：

以下是链表的类型：

• 单向链表（单向）
• 双向链表（双向）

链表的基本操作：

• InsertAtEnd - 在链接列表的末尾插入给定元素
• InsertAtHead - 在链接列表的开始/头部插入给定元素
• 删除 - 从链接列表中删除给定元素
• DeleteAtHead-删除链接列表的第一个元素
• 搜索 - 从链接列表中返回给定元素
• isEmpty - 如果链接列表为空，则返回 true

常见的链表面试问题

• 反转链接列表
• 检测链接列表中的循环
• 返回链表倒数第 N 个节点
• 从链接列表中删除重复项

图表

图是一组以网络形式相互连接的节点。节点也称为顶点。一对 (x,y) 称为边，表示顶点 x 连接到顶点 y。边可能包含权重/成本，表示从顶点 x 到 y 所需的成本。

图表类型：

• 无向图
• 有向图

在编程语言中，图形可以用两种形式表示：

• 邻接矩阵
• 邻接表

常见的图遍历算法：

• 广度优先搜索
• 深度优先搜索

常见的 Graph 面试问题

• 实现广度和深度优先搜索
• 检查图是否是树
• 计算图中边的数量
• 找到两个顶点之间的最短路径

树木

树是一种由顶点（节点）和连接顶点的边组成的分层数据结构。树与图类似，但树与图的关键区别在于树中不存在环路。

树广泛应用于人工智能和复杂算法中，为解决问题提供有效的存储机制。

这是一张简单树的图像，以及树数据结构中使用的基本术语：

树木的种类如下：

• N叉树
• 平衡树
• 二叉树
• 二叉搜索树
• AVL树
• 红黑树
• 2–3树

其中，二叉树和二叉搜索树是最常用的树。

常见的 Tree 面试问题

• 查找二叉树的高度
• 在二叉搜索树中查找第 k 个最大值
• 查找距离根“k”的节点
• 查找二叉树中给定节点的祖先

特里树

Trie 又称“前缀树”，是一种树状数据结构，已被证明在解决字符串相关问题方面非常有效。它提供快速检索，主要用于词典搜索、搜索引擎自动建议，甚至用于 IP 路由。

下面说明了“top”、“thus”和“their”三个单词在 Trie 中的存储方式：

单词以从上到下的方式存储，其中绿色节点“p”、“s”和“r”分别表示“top”、“thus”和“their”的末尾。

常见的 Trie 面试问题：

• 计算 Trie 中的单词总数
• 打印 Trie 中存储的所有单词
• 使用 Trie 对数组元素进行排序
• 使用 Trie 从字典中形成单词
• 构建T9词典

哈希表

哈希算法用于唯一标识对象，并将每个对象存储在预先计算的唯一索引（称为其“键”）中。因此，对象以“键值”对的形式存储，这些项的集合称为“字典”。可以使用该键搜索每个对象。基于哈希算法，存在不同的数据结构，但最常用的数据结构是哈希表。

哈希表一般使用数组实现。

散列数据结构的性能取决于以下三个因素：

• 哈希函数
• 哈希表的大小
• 碰撞处理方法

下图展示了哈希值在数组中的映射方式。该数组的索引是通过哈希函数计算得出的。

常见的哈希面试问题

• 查找数组中的对称对
• 追踪旅程的完整路径
• 判断一个数组是否是另一个数组的子集
• 检查给定数组是否不相交

以上是参加编码面试之前一定要了解的 8 种数据结构。

如果您正在寻找有关编码面试的数据结构资源，请查看基于交互式和挑战的课程：掌握编码面试的数据结构，其中包含 Python、Java、C++ 和 JavaScript 课程。

对于更高级的问题，请参阅《Grokking the Coding Interview: Patterns for Coding Questions》。

祝你好运，学习愉快！:)