DSA面试题

数据结构是以结构化和系统化的方式定义、存储和检索数据的方法。数据结构可能包含不同类型的数据项。

可用的数据结构可能因编程语言而异。常用的数据结构包括列表、数组、栈、队列、图、树等。

算法是一个逐步的过程，它定义了一组指令，这些指令按一定顺序执行以获得所需的输出。

一个问题可以用多种方法解决。因此，对于给定的问题，可以推导出许多解决方案算法。我们分析可用的算法以找到并实现最合适的算法。

算法通常根据两个因素进行分析：时间和空间。也就是说，算法需要多少执行时间和多少额外空间。

算法的渐进分析是指定义其运行时性能的数学界限/框架。使用渐进分析，我们可以很好地得出算法的最佳情况、平均情况和最坏情况。

渐进分析可以提供算法执行时间的三个级别的数学约束：

• 最佳情况由Ω(n)表示。
• 最坏情况由Ο(n)表示。
• 平均情况由Θ(n)表示。

线性数据结构具有顺序排列的数据项。下一个数据项可以在下一个内存地址中找到。它以顺序方式存储和访问。数组和列表是线性数据结构的示例。

以下操作通常在任何数据结构上执行：

• 插入 - 添加数据项

• 删除 - 删除数据项

• 遍历 - 访问和/或打印所有数据项

• 搜索 - 查找特定数据项

• 排序 - 按预定义顺序排列数据项

开发算法有三种常用方法：

• 贪心算法 - 通过选择下一个最佳选项来寻找解决方案

• 分治法 - 将问题分解为尽可能小的子问题，并独立地解决这些子问题

• 动态规划 - 将问题分解为尽可能小的子问题，并组合地解决这些子问题

以下问题使用贪心算法方法找到它们的解决方案：

• 旅行商问题
• Prim最小生成树算法
• Kruskal最小生成树算法
• Dijkstra最小生成树算法
• 图 - 地图着色
• 图 - 顶点覆盖
• 背包问题
• 作业调度问题

以下问题使用分治算法方法找到它们的解决方案：

• 归并排序
• 快速排序
• 二分查找
• Strassen矩阵乘法
• 最近对（点）

以下问题使用分治算法方法找到它们的解决方案：

• 斐波那契数列
• 背包问题
• 汉诺塔
• Floyd-Warshall算法求所有对最短路径
• Dijkstra算法求最短路径
• 项目调度

链表是由链接（即指针或引用）连接的数据项列表。大多数现代高级编程语言不提供直接访问内存位置的功能，因此它们不支持链表或以内置函数的形式提供。

在数据结构中，栈是一种抽象数据类型 (ADT)，用于以后进先出 (LIFO) 的方式存储和检索值。

栈遵循 LIFO 方法，添加和检索数据项只需要 O(n) 时间。在我们需要以与它们到达的相反顺序访问数据时使用栈。栈通常用于递归函数调用、表达式解析、图的深度优先遍历等。

以下操作可以在栈上执行：

• push() - 向栈中添加项目

• pop() - 删除栈顶项目

• peek() - 获取栈顶项目的 value，但不删除它

• isempty() - 检查栈是否为空

• isfull() - 检查栈是否已满

队列是一种抽象数据结构，有点类似于栈。与栈相反，队列的两端都是开放的。一端始终用于插入数据（入队），另一端用于删除数据（出队）。队列遵循先进先出 (FIFO) 方法，即首先存储的数据项将首先被访问。

由于队列遵循 FIFO 方法，因此当我们需要按数据项到达的确切顺序处理它们时，我们使用队列。每个操作系统都维护着各种进程的队列。优先级队列和图的广度优先遍历是一些队列的例子。

以下操作可以在栈上执行：

• enqueue() - 将项目添加到队列的尾部

• dequeue() - 从队列的头部删除项目

• peek() - 获取头部项目的 value，但不删除它

• isempty() - 检查栈是否为空

• isfull() - 检查栈是否已满

线性搜索试图在一个顺序排列的数据类型中找到一个项目。这些顺序排列的数据项（称为数组或列表）可以在递增的内存位置访问。线性搜索将预期数据项与列表或数组中的每个数据项进行比较。线性搜索的平均情况时间复杂度为 O(n)，最坏情况复杂度为 O(n²)。目标数组/列表中的数据不需要排序。

二分查找仅适用于已排序的列表或数组。此搜索选择中间值，将整个列表分成两部分。首先比较中间值。

此搜索首先将目标值与列表的中间值进行比较。如果找不到，则决定是否。

冒泡排序是一种基于比较的算法，其中比较每一对相邻元素，如果元素未按顺序排列则交换元素。由于时间复杂度为 O(n²)，因此它不适用于大型数据集。

插入排序将列表分成两个子列表，已排序和未排序。它一次取一个元素，并在已排序的子列表中找到它适当的位置并插入到那里。插入后的输出是一个已排序的子列表。它迭代地处理未排序子列表的所有元素，并按顺序将它们插入到已排序的子列表中。

选择排序是一种原地排序技术。它将数据集分成两个子列表：已排序和未排序。然后，它从未排序的子列表中选择最小元素，并将其放入已排序的列表中。这个过程会一直迭代，直到未排序子列表中的所有元素都被放入已排序的子列表中。

两种排序技术都维护两个子列表，已排序和未排序，并且都一次取一个元素并将其放入已排序的子列表中。插入排序对当前手头的元素进行操作，并将其放置在已排序数组中的适当位置，同时保持插入排序的特性。而选择排序则从未排序的子列表中搜索最小值，并将其与当前手头的元素替换。

归并排序是一种基于分治编程方法的排序算法。它不断将列表分成更小的子列表，直到所有子列表都只有一个元素。然后，它以排序的方式合并它们，直到所有子列表都被合并。它的运行时间复杂度为Ο(n log n)，需要Ο(n)的辅助空间。

希尔排序可以说是插入排序的一种变体。希尔排序根据某个间隔变量将列表分成更小的子列表，然后使用插入排序对每个子列表进行排序。在最佳情况下，它的性能可以达到Ο(n log n)。

快速排序使用分治法。它使用“枢轴”将列表分成更小的“分区”。小于枢轴的值排列在左分区中，大于枢轴的值排列在右分区中。每个分区都使用快速排序递归排序。

图是一组对象的图形表示，其中某些对象对通过链接连接。相互连接的对象由称为顶点的点表示，连接顶点的链接称为边。

深度优先搜索算法 (DFS) 以深度优先的方式遍历图，并使用堆栈来记住在任何迭代中遇到死锁时要开始搜索的下一个顶点。

广度优先搜索算法 (BFS) 以广度优先的方式遍历图，并使用队列来记住在任何迭代中遇到死锁时要开始搜索的下一个顶点。

树是一个最小连接图，没有循环和回路。

二叉树有一个特殊条件，即每个节点最多可以有两个子节点。

二叉搜索树是一种二叉树，它有一个特殊的规定：节点的左子节点的值必须小于其父节点的值，而节点的右子节点的值必须大于其父节点的值。

树的遍历是访问树中所有节点的过程。因为所有节点都通过边（链接）连接，所以我们总是从根（头部）节点开始。我们使用三种方法来遍历树：

• 中序遍历
• 前序遍历
• 后序遍历

• 中序遍历：10 14 19 27 31 35 42
• 前序遍历：27 14 10 19 35 31 42
• 后序遍历：10 19 14 31 42 35 27

AVL树是高度平衡的二叉搜索树。AVL树检查左右子树的高度，并确保高度差不大于1。这个差值称为平衡因子。

BalanceFactor = height(left-sutree) − height(right-sutree)

生成树是图G的一个子集，它包含所有顶点，并具有尽可能少的边数。生成树没有环，也不能断开连接。

这取决于图的连接方式。一个完全无向图最多可以有n^n-1个生成树，其中n是节点数。

该算法将图视为森林，并将每个节点视为单个树。只有当树的成本在所有可用选项中最小且不违反MST属性时，树才会连接到另一个树。

普里姆算法将节点视为一棵树，并不断地从给定图中向生成树添加新节点。

在加权图中，最小生成树是指权重小于相同图的所有其他生成树的生成树。

堆是一种特殊的平衡二叉树数据结构，其中根节点键与其子节点进行比较并相应地排列。在最小堆中，父节点的键值小于其子节点，而在最大堆中，父节点的值大于其子节点。

递归函数是指直接或间接调用自身的函数。每个递归函数都遵循递归特性：基本情况，函数停止调用自身；递推关系，函数在每次迭代中试图满足基本情况。

汉诺塔是一个数学游戏，它由三个塔（桩）和多个环组成。所有环的大小都不同，并彼此堆叠，其中大圆盘总是在小圆盘的下方。目标是从一个桩将圆盘塔移动到另一个桩，而不破坏其特性。

斐波那契数列通过将前两个数字相加来生成后续数字。例如：0 1 1 2 3 5 8 13。

哈希是一种将一系列键值转换为数组索引范围的技术。通过使用哈希表，我们可以创建一个关联数据存储，其中可以通过提供其键值来查找数据索引。

插值查找是二分查找的改进变体。该搜索算法基于所需值的探测位置。

前缀表示法：* + a b + c d

后缀表示法：a b + c d + *