常见数据结构面试问题|集1-yiteyi-C++库

什么是数据结构？ 数据结构是一种组织数据的方式，以便有效地使用数据。不同类型的数据结构适用于不同类型的应用程序，有些数据结构对特定任务高度专业化。例如，B-树特别适合于数据库的实现，而编译器实现通常使用哈希表来查找标识符。（来源：维基页面 )

null

什么是线性和非线性数据结构？

线性的： 如果一个数据结构的元素形成一个序列或一个线性列表，则称其为线性结构。示例：数组。链表、堆栈和队列
非线性： 如果节点的遍历本质上是非线性的，则称数据结构为非线性的。示例：图形和树。

在不同的数据结构上可以执行哪些不同的操作？

插入 ? 在给定的数据项集合中添加新数据项。
删除 ? 从给定的数据项集合中删除现有数据项。
穿越 ? 仅访问每个数据项一次，以便对其进行处理。
搜索 ? 如果数据项存在于给定的数据项集合中，请找出该数据项的位置。
分类 ? 以某种顺序排列数据项，即数字数据按升序或降序排列，字母数字数据按字典顺序排列。

数组与链表有何不同？

数组的大小是固定的，链表的大小是动态的。
在元素数组中插入和删除新元素的成本很高，而插入和删除都可以在链表中轻松完成。
链接列表中不允许随机访问。
链表的每个元素都需要为指针留出额外的内存空间。
阵列具有更好的缓存局部性，这会在性能上产生很大的差异。

什么是堆栈，在哪里可以使用它？ 堆栈是一种线性数据结构，其顺序为LIFO（后进先出）或FILO（先进后出），用于访问元素。堆栈的基本操作包括： 推，弹出，偷看

Stack的应用：

什么是队列，它与 堆栈以及它是如何实现的？ 队列是一个线性结构，它遵循 F 第一我 N F 第一 O ut（FIFO）用于访问元件。主要包括以下对队列的基本操作：排队 , 前后堆栈和队列的区别在于删除。在堆栈中，我们删除最近添加的项目；在队列中，我们删除最近添加最少的项目。队列和堆栈都可以使用数组和链表实现。

什么是中缀、前缀、后缀符号？

中缀符号： 十、 + Y–运算符写入其操作数之间。这是我们写表达式的惯常方式。一种表达方式，如

   A * ( B + C ) / D

后缀符号（也称为“反向波兰符号”）： X Y + 运算符在其操作数之后写入。上面给出的中缀表达式等价于

   A B C + * D/

前缀符号（也称为“波兰语符号”）： +X Y 运算符写在操作数之前。上面给出的表达式相当于

   / A * + B C D

在这些符号之间转换：点击这里

什么是链表及其类型？

链表是一种线性数据结构（如数组），其中每个元素都是一个单独的对象。列表中的每个元素（即节点）都由两项组成——数据和对下一个节点的引用。链表的类型：

单链表： 在这种类型的链表中，每个节点存储列表中下一个节点的地址或引用，最后一个节点的下一个地址或引用为空。例如1->2->3->4->NULL
双链接列表： 在这里这里有两个与每个节点相关联的参考，一个参考点指向下一个节点，另一个参考点指向前一个节点。例如：空23->空
循环链表： 循环链表是一种链表，其中所有节点都连接成一个圆。结尾没有空值。循环链表可以是单循环链表或双循环链表。例如1->2->3->1[最后一个节点的下一个指针指向第一个]

图的BFS和DFS使用哪些数据结构？