高频面试题之数据结构

　　几乎所有问题都要求面试官对数据结构有深刻的理解。无论您是工作场所的新手（刚毕业于大学还是编程班），您都是具有数十年经验的工作场所资深人士。
　　即使对于一些非常基本的任务，学习数据结构也是必须的。让我们从一些基本概念开始。



　　什么是数据结构？

　　简而言之，数据结构是一个以特定布局存储数据的容器。这种“布局模式”确定数据结构对于某些操作是有效的并且对于其他操作是低效的。首先，我们需要了解各种数据结构，以便在处理实际问题时选择最合适的数据结构。

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

　　数据是计算机科学中最关键的实体，数据结构可以以有组织的形式存储数据。因此，数据结构的价值是不言而喻的。
　　无论你如何解决问题，你都需要处理数据——是否涉及员工工资、股票价格、购物清单，或者只是一个简单的电话簿问题。
　　数据需要根据不同的场景以特定格式存储。有许多数据结构可以满足以不同格式存储数据的需要。

　　通用数据结构

　　首先列出一些最常见的数据结构，我们将逐一解释：

　　排列
　　堆
　　队列
　　链接列表
　　树
　　数字
　　字典树（这是一种有效的树结构，但值得单独描述）
　　哈希表（哈希表）

　　排列

　　数组是最简单的、也是使用最广泛的数据结构。堆栈、队列和其他数据结构都是从数组派生的。
　　每个数据元素都与一个正值相关联，我们称之为索引，它指示数组中每个元素的位置。大多数语言将初始索引定义为零。
　　以下是两种类型的数组：
　　一维数组（如上所示）
　　多维数组（数组数组）
　　数组的基本操作
　　插入——在指定的索引位置插入一个元素
　　获取——返回指定索引位置的元素
　　删除——删除指定索引位置的元素
　　大小——获取数组中所有元素的数量
　　在采访中经常被问到有关阵列的问题
　　寻找数组中的第二个最小元素
　　找到数组中不重复的第一个整数
　　合并两个有序数组
　　重新排列数组中的正负值

　　堆

　　着名的撤销操作几乎可以在任何应用程序中使用。但你有没有想过它是如何工作的？该问题的解决方案是按照优先级最后状态的顺序将历史工作状态存储在存储器中。使用数组无法做到这一点。但是使用堆栈，这变得非常方便。将堆栈视为一系列垂直堆叠的书籍。为了获得中间书，您需要删除放在其上的所有书籍。这就是LIFO（Last In，First Out）的工作原理。

　　堆栈的基本操作

　　按——在顶部插入一个元素
　　Pop——返回并删除堆栈的顶部元素
　　isEmpty——如果堆栈为空，则返回true
　　顶部——返回顶部元素但不删除它
　　在面试过程中有关堆栈的常见问题
　　使用堆栈计算后缀表达式
　　对堆栈的元素进行排序
　　确定表达式是否用括号平衡

　　队列

　　像堆栈一样，队列是另一种顺序存储元素的线性数据结构。堆栈和队列之间的最大区别是堆栈是LIFO（后进先出），队列是FIFO，即FIFO。
　　队列的基本操作
　　排队（）？——？在队列末尾插入一个元素
　　出列（）？——删除队列头的元素
　　isEmpty（）——如果队列为空，则返回true
　　最佳（）？——返回队列的第一个元素
　　在面试过程中经常询问有关队列的问题
　　使用队列来表示堆栈
　　反转队列的前k个元素
　　使用队列生成从1到n的二进制数
　　链接列表
　　链表是另一个重要的线性数据结构。乍一看，它可能有点像数组，但它在内存分配、的内部结构和数据插入和删除的基本操作方面有所不同。
　　链表就像一个节点链，每个节点包含数据和指向后续节点的指针。
　　链表还包含一个指向列表第一个元素的标题指针，但是当列表为空时，它指向null或什么都不是。
　　链表通常用于实现文件系统、哈希表和邻接表。

　　内部结构相连

　　链表包括以下类型：

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

　　链表的基本操作：
　　InsertAtEnd  - 将指定的元素插入列表的末尾
　　InsertAtHead  - 在链接列表的开头/头部插入指定的元素
　　删除 - 从链接列表中删除指定的元素
　　DeleteAtHead  - 删除链表的第一个元素
　　搜索 - 从链接列表返回指定的元素
　　isEmpty  - 如果列表为空，则为true
　　在访谈期间有关链表的常见问题
　　反向列表
　　检测链表中的循环
　　返回列表底部的第N个节点
　　删除链接列表中的重复项
　　数字
　　图是一组以网络形式相互连接的节点。节点也称为顶点一对节点（x，y）称为边，表示顶点x连接到顶点y。边可以包含权重/成本，显示从顶点x到y的成本。
　　图表类型
　　无向图
　　有向图
　　在编程语言中，图形可以用两种形式表示：
　　邻接矩阵
　　邻接表
　　常见的图遍历算法
　　广度优先搜索
　　深度优先搜索
　　在访谈期间有关地图的常见问题
　　实施广度和深度优先搜索
　　检查图形是否为树
　　计算图表的边数
　　找到两个顶点之间的最短路径

　　树

　　树结构是由顶点（节点）和连接它们的边组成的分层数据结构
　　树类似于图形，但区分树和图形的一个重要特征是树中没有环。
　　树结构广泛用于人工智能和复杂算法，以提供解决问题的有效存储机制。
　　树数据结构中使用的基本术语
　　Root  - 根节点
　　父 - 父节点
　　子 - 孩子节点
　　叶 - 叶节点
　　兄弟姐妹 - 兄弟节点
　　以下是树结构的主要类型
　　N-ary树
　　平衡树
　　二叉树
　　二进制搜索树
　　AVL树
　　红黑树
　　2-3棵树
　　其中，二叉树和二叉搜索树是最常用的树。
　　关于采访中树形结构的常见问题
　　找到二叉树的高度
　　在二叉搜索树中找到第k个最大值
　　找到根节点距离为k的节点
　　在二叉树中查找给定节点的祖先节点

　　字典树

　　字典树，也称为“前缀树”，是一种特殊的树状数据结构，对解决与字符串相关的问题非常有效。它提供快速检索，主要用于搜索字典中的单词，自动在搜索引擎中提供建议，甚至用于IP路由。

　　关于面试中词典树的常见问题
　　计算字典树中的单词总数
　　打印存储在词典树中的所有单词
　　使用字典树对数组的元素进行排序
　　使用字典树从字典中形成单词
　　构建T9字典（字典树+ DFS）

　　哈希表

　　散列是一种唯一标识对象并将每个对象存储在一些预先计算的唯一索引（称为“密钥”）中的过程。因此，对象以键值对的形式存储，并且这些键值对的集合称为“字典”。您可以使用键搜索每个对象。基于散列有许多不同的数据结构，但最常见的数据结构是散列表。散列表通常使用数组实现。

　　散列数据结构的性能取决于三个因素
　　哈希函数
　　哈希表的大小
　　碰撞处理方法
　　关于哈希结构的常见问题在访谈中
　　在数组中查找对称键值对
　　跟踪遍历的完整路径
　　查找数组是否是另一个数组的子集
　　检查给定的数组是否不相交