DSA 问题与答案（面试题）
数据结构是一种以结构化和系统化的方式定义、存储和检索数据的方法。数据结构可能包含不同类型的数据项。
数据结构的可用性可能因编程语言而异。常见的数据结构包括列表、数组、堆栈、队列、图、树等。
算法是一个逐步的过程，它定义了一组按特定顺序执行以获得所需输出的指令。
一个问题可以通过多种方式解决。因此，对于给定的问题，可以推导出许多解决算法。我们分析现有的算法，以找到并实现最合适的算法。
算法分析通常基于两个因素：时间和空间。即算法的执行时间和额外空间。
算法的渐近分析是指定义其运行时性能的数学边界/框架。利用渐近分析，我们可以很好地推导出算法的最佳情况、平均情况和最坏情况。
渐近分析可以为算法的执行时间提供三个级别的数学绑定。 −
- 最佳情况用 Ω(n) 符号表示。
- 最坏情况用 Ο(n) 符号表示。
- 平均情况用 Θ(n) 符号表示。
线性数据结构的数据项按顺序排列。下一次访问可以位于下一个内存地址。它以顺序方式存储和访问。数组和列表是线性数据结构的示例。
以下操作通常可在任何数据结构上执行 −
插入 − 添加数据项
删除 − 移除数据项
遍历 − 访问和/或打印所有数据项
搜索 − 查找特定数据项
排序 −按预定义顺序排列数据项
开发算法的常用方法有三种 −
贪婪方法 − 通过选择下一个最佳选项来寻找解决方案
分而治之 − 将问题分解为尽可能小的子问题，并独立求解
动态规划 −将问题分解为最小可能的子问题，并将它们组合起来求解
以下问题使用贪婪算法方法 − 求解
- 旅行商问题
- Prim 最小生成树算法
- Kruskal 最小生成树算法
- Dijkstra 最小生成树算法
- 图 - 地图着色
- 图 - 顶点覆盖
- 背包问题
- 作业调度问题
以下问题使用分治算法 − 来求解
- 归并排序
- 快速排序
- 二分查找
- 施特拉森矩阵乘法
- 最近对（点）
以下问题使用分治算法 − 来求解
- 斐波那契数列
- 背包问题
- 汉诺塔问题
- 所有对最短路径作者：Floyd-Warshall
- Dijkstra 最短路径算法
- 项目进度安排
链表是通过链接（即指针或引用）连接的数据项列表。大多数现代高级编程语言不提供直接访问内存位置的功能，因此，它们不支持链表，或者无法以内置函数的形式使用。
在数据结构中，堆栈是一种抽象数据类型 (ADT)，用于按照后进先出的方式存储和检索值。
堆栈遵循后进先出 (LIFO) 方法，数据项的添加和检索仅需 n 次。当需要以相反的顺序或数据到达的顺序访问数据时，会使用堆栈。堆栈常用于递归函数调用、表达式解析、图的深度优先遍历等。
以下操作可以在堆栈上执行 −
push() − 向堆栈中添加一个元素
pop() − 删除堆栈顶部元素
peek() − 返回堆栈顶部元素的值但不将其删除
isempty() − 检查堆栈是否为空
isfull() −检查堆栈是否已满
队列是一种抽象的数据结构，有点类似于堆栈。与堆栈不同，队列两端开放。一端始终用于插入数据（入队），另一端用于移除数据（出队）。队列遵循先进先出原则，即先存储的数据项将首先被访问。
由于队列遵循先进先出（FIFO）原则，因此当我们需要按照数据项到达的顺序进行处理时，可以使用队列。每个操作系统都维护各种进程的队列。优先级队列和图的广度优先遍历是队列的一些示例。
以下操作可以在堆栈 − 上执行
enqueue() − 将一个项目添加到队列尾部
dequeue() − 从队列前端移除一个项目
peek() − 返回前端项目的值但不移除它
isempty() − 检查堆栈是否为空
isfull() −检查堆栈是否已满
线性搜索尝试在顺序排列的数据类型中查找项。这些顺序排列的数据项称为数组或列表，可在递增的内存位置访问。线性搜索将预期数据项与列表或数组中的每个数据项进行比较。线性搜索的平均时间复杂度为 Ω(n)，最坏情况复杂度为 Ω(n2)。目标数组/列表中的数据无需排序。
二分查找仅适用于已排序的列表或数组。此搜索选择中间值，将整个列表分成两部分。首先比较中间值。
此搜索首先将目标值与列表的中间值进行比较。如果未找到，则判断是否匹配。
冒泡排序是一种基于比较的算法，它会比较每对相邻元素，如果它们顺序不对，则交换元素。由于时间复杂度为 Ω (n2)，它不适用于处理大量数据。
插入排序将列表分为两个子列表：已排序子列表和未排序子列表。它每次取出一个元素，在已排序子列表中找到合适的位置并将其插入到该位置。插入后的输出是一个已排序子列表。它迭代地处理未排序子列表中的所有元素，并按顺序将它们插入到已排序子列表中。
选择排序是一种就地排序技术。它将数据集分成两个子列表：已排序和未排序。然后，从未排序子列表中选择最小元素并将其放入已排序列表中。此过程将一直迭代，直到未排序子列表中的所有元素都被放入已排序子列表中。
这两种排序技术都维护两个子列表：已排序和未排序，并且每次都取出一个元素并将其放入已排序子列表中。插入排序对当前元素进行排序，并将其放置在已排序数组的适当位置，同时保持插入排序的属性。而选择排序则从未排序的子列表中搜索最小值，并将其替换为当前元素。
合并排序是一种基于分治法的排序算法。它不断将列表划分为更小的子列表，直到所有子列表都只有一个元素。然后，它以有序的方式合并它们，直到所有子列表都被处理。它的运行时复杂度为 Ω(n log n)，并且需要 Ω(n) 的辅助空间。
希尔排序可以说是插入排序的一种变体。希尔排序根据某个gap变量将列表划分为更小的子列表，然后使用插入排序对每个子列表进行排序。在最佳情况下，它的执行速度可达Ο(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。这个差值称为平衡因子。
平衡因子 = height(left-sutree) − height(right-sutree)
生成树是图 G 的一个子集，其所有顶点都被尽可能少的边覆盖。生成树没有环，也不能断开连接。
这取决于图的连通性。完全无向图最多可以有 nn-1 个生成树，其中 n 是节点数。
该算法将图视为一片森林，将每个节点视为一棵独立的树。一棵树只有在所有可用选项中成本最低且不违反 MST 属性的情况下才会连接到另一棵树。
Prim 算法将节点视为一棵树，并不断从给定的图中向生成树添加新节点。
在加权图中，最小生成树是指权重小于同一图中所有其他生成树的生成树。
堆是一种特殊的平衡二叉树数据结构，其中根节点的键与其子节点进行比较并进行相应的排序。最小堆是指父节点的键值小于其子节点，而最大堆是指父节点的键值大于其子节点。
递归函数是指直接调用自身或调用一个函数，而该函数又调用自身的函数。每个递归函数都遵循递归属性：减去基本条件，即函数停止调用自身；以及渐进方法，即函数在每次迭代中尝试满足基本条件。
汉诺塔是一个数学谜题，由三个塔（桩）和多个环组成。所有环的大小不同，相互堆叠，大圆盘始终位于小圆盘下方。目标是将圆盘塔从一个桩移动到另一个桩，同时不破坏其属性。
斐波那契数列通过将两个前一个数字相加来生成后续数字。例如 − 0 1 1 2 3 5 8 13。
哈希是一种将键值范围转换为数组索引范围的技术。通过使用哈希表，我们可以创建一个关联数据存储，通过提供键值即可找到数据索引。
插值搜索是二分搜索的一种改进变体。此搜索算法作用于所需值的探测位置。
前缀表示法 − * + a b + c d
后缀表示法 − a b + c d + *
