数据结构面试题

1、数据结构三要素？

        逻辑结构、物理结构、数据运算

2、数组和链表的区别？

• 数组的特点： 数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。数组的插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移。删除数据时，这个数据后面的数据都要往前移动。但数组的随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到给地址的数据。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间。并且数组不利于扩展，数组定义的空间不够时要重新定义数组。
• 链表的特点： 链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。不指定大小，扩展方便。链表大小不用定义，数据随意增删。
• 数组的优点：随机访问性强；查找速度快。
• 数组的缺点:  插入和删除效率低；可能浪费内存；内存空间要求高，必须有足够的连续内存空间；数组大小固定，不能动态拓展。
• 链表的优点:  插入删除速度快；内存利用率高，不会浪费内存；大小没有固定，拓展很灵活。
• 链表的缺点: 不能随机查找，必须从第一个开始遍历，查找效率低。

3、排序有哪些分类？

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序；

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序；

比较排序：冒泡排序、快速排序、归并排序；

非比较排序：基数排序、基数排序、桶排序；

内部排序：插入排序、归并排序、选择排序、交换排序、计数排序、桶排序、基数排序；

外部排序：暂时不知；

4、冒泡排序（Bubble Sort）

算法步骤：

• 从第一个元素开始，比较相邻的两个元素。如果前一个元素比后一个元素大（如果是升序排序的话），则交换它们的位置。
• 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

5、插入排序（Insertion Sort）

算法步骤：

1. 从第一个元素开始，该元素可以认为已经被排序。
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
5. 将新元素插入到该位置后。
6. 重复步骤2~5，直到所有元素均排序完毕。

6、希尔排序（Shell Sort）

算法步骤：

1. 选择增量序列：首先，需要选择一个增量序列t1，t2，…，tk，其中ti > tj, tk = 1。这个序列的选择对希尔排序的性能至关重要。常用的增量序列有Hibbard增量序列、Sedgewick增量序列等。
2. 分组与预排序：按照当前的增量ti，将待排序序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。此时，整个序列是“基本有序”的。
3. 逐步缩小增量并重复排序：每排序完一次子序列（即增量为ti的一趟排序）后，更新增量为ti-1，并重复步骤2，进行下一趟排序，直到增量减小到1。此时，整个序列已经基本有序，可以对整个序列进行一次直接插入排序，得到最终排序结果。

7、选择排序（Selection Sort）

算法步骤：

1. 遍历待排序序列，设立一个指针，初始指向序列的第一个元素。
2. 从当前指针位置开始，依次与后面的元素比较，找到最小（或最大）的元素，并记录其位置。
3. 将找到的最小（或最大）元素与当前指针位置的元素进行交换。
4. 将指针向后移动一位，重复步骤2和步骤3，直到指针移动到序列的倒数第二个元素。
5. 此时，最后一个元素已经是序列中的最大（或最小）元素，排序完成。

8、快速排序（Quick Sort）

算法步骤：

1. 从序列中选取一个元素作为基准（pivot）。
2. 将序列中小于基准的元素放在基准的左边，大于基准的元素放在基准的右边。这个操作称为分区（partition）操作，完成后基准元素处于序列的中间位置。此时，该基准元素在排序后的最终位置已经确定。
3. 递归地对基准左边和右边的两个子序列进行快速排序。

9、归并排序（Merge Sort）

算法步骤：

1. 分解：将待排序的序列划分为若干个长度为1的子序列，每个子序列自然有序。
2. 递归进行归并：递归地将相邻的子序列两两归并，得到若干个有序的较长子序列，直到最终合并为一个完整的有序序列。

10、堆排序（Heap Sort）

算法步骤：

1. 建堆：将无序序列构造成一个大顶堆（或小顶堆）。此时，整个序列的最大值（或最小值）就是堆顶的根节点。
2. 堆调整：将堆顶元素与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个序列重新构造成一个堆，这样会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列了。

11、计数排序（Counting Sort）

首先，扫描待排序数组，确定数组的最大值和最小值；

然后，建立一个与最大值和最小值范围相对应的计数数组，并统计每个元素出现的次数；

最后，根据计数数组的信息，将待排序数组中的元素放到正确的位置上。

12、桶排序（Bucket Sort）

1. 确定桶的数量和大小：首先，需要确定桶的数量以及每个桶的大小范围。桶的数量可以基于待排序数组的长度和数据分布来决定。每个桶的大小范围则是根据数据的最大值和最小值来划分的。
2. 分配数据到桶中：遍历待排序数组，根据每个元素的值将其放入对应的桶中。这个过程需要根据桶的大小范围来判定每个元素应该放入哪个桶。
3. 桶内排序：对每个桶内的元素进行排序。这里可以使用其他排序算法，如插入排序、归并排序或快速排序等，对桶内的元素进行进一步的排序。
4. 合并桶中的数据：最后，按照桶的顺序，将桶内的元素依次合并起来，形成最终的排序结果。

13、基数排序（Radix Sort）

1. 确定最大位数：首先，需要找到待排序数组中的最大值，确定其位数。这将决定需要进行多少轮排序。
2. 从最低位开始排序：基数排序从最低位（个位）开始，对数组进行排序。在每一轮排序中，可以使用稳定的排序算法（如计数排序或桶排序）对相应位上的数字进行排序。
3. 逐渐向高位排序：完成最低位的排序后，继续向更高位（十位、百位等）进行排序。每一轮排序都会根据当前位的数字值对数组进行重排。
4. 合并排序结果：经过多轮排序后，数组中的元素将按照从最低位到最高位的顺序排列。由于每一轮排序都是稳定的，所以最终得到的数组将是一个有序数组。

14、数组和链表的区别？

从逻辑结构上来看，数组必须实现定于固定的长度，不能适应数据动态增减的情况，即数组的大小一旦定义就不能改变。当数据增加是，可能超过原先定义的元素的个数；当数据减少时，造成内存浪费；链表动态进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。

从内存存储的角度看；数组从栈中分配空间（用new则在堆上创建），对程序员方便快速，但是自由度小；链表从堆中分配空间，自由度大但是申请管理比较麻烦。

从访问方式类看，数组在内存中是连续的存储，因此可以利用下标索引进行访问；链表是链式存储结构，在访问元素时候只能够通过线性方式由前到后顺序的访问，所以访问效率比数组要低。

15、线性表的存储结构？

线性表存储结构可细分为顺序存储结构和链式存储结构

顺序存储结构：将数据依次存储在连续的整块物理空间中，这种存储结构称为顺序存储结构（简称顺序表）；

链式存储结构：数据分散的存储在物理空间中，通过一根线保存着它们之间的逻辑关系，这种存储结构称为链式存储结构（简称链表）；

16、头指针和头节点？

头结点：

• 定义：在单链表的开始结点之前设立的一个节点，称为头结点。
• 数据域：可以不存储任何信息，也可以存储链表长度等附加信息。
• 指针域：存储指向第一个结点的指针。
• 作用：
  • 方便链表操作，如插入、删除元素等。
  • 减少代码量，因为通过头结点可以更容易地处理链表的各种操作，特别是当需要操作第一个结点时。
  • 使得链表的某些操作（如遍历、查找等）更为统一和简洁。

头指针：

• 定义：指向链表第一个结点的指针。
• 作用：
  • 具有标识作用，通常用头指针来命名链表。
  • 提供链表的访问入口，通过头指针可以访问链表的第一个节点，进而遍历整个链表。

17、栈（stack）和队列（queue）的区别？

1. 访问规则：栈是一种后进先出（LIFO，Last In First Out）的数据结构，即最后一个被添加到栈中的元素总是第一个被移出。而队列则是一种先进先出（FIFO，First In First Out）的数据结构，即队列中第一个被添加的元素总是第一个被移出。
2. 操作方式：栈的主要操作包括压栈（push，向栈顶添加元素）和弹栈（pop，从栈顶移除元素）。而队列的主要操作则包括入队（enqueue，在队列尾部添加元素）和出队（dequeue，从队列头部移除元素）。
3. 使用场景：由于栈的后进先出特性，它常被用于实现函数调用和递归等场景，因为这些操作通常需要后创建的对象先处理。而队列的先进先出特性则使其在需要按特定顺序处理元素的场景中非常有用，如打印任务、网络数据包处理等。
4. 数据结构：栈通常使用数组或链表来实现。在数组实现中，栈底通常在数组的起始位置，栈顶在数组的末尾；而在链表实现中，栈顶的元素位于链表的头部。队列也可以使用数组或链表来实现，但在数组实现中，通常需要一个额外的变量来记录队列的头部和尾部位置；在链表实现中，队列的头部和尾部可以通过链表的头部和尾部节点来追踪。

18、什么是二叉树？平衡二叉树？

看这个：二叉树知识点最详细最全讲解-CSDN博客

19、如何唯一确定一棵二叉树？

        中序 + 先序/后序/层序

20、图的存储方式有哪些？每一种方式优缺点？

21、树的存储结构？

22、图的遍历和树的遍历方式都是什么？

23、图的遍历与树的遍历有什么区别？

24、关键路径和关键活动是什么？

25、什么叫平衡二叉树？

26、什么叫搜索二叉树？

27、什么叫红黑树？

28、数据结构的4种逻辑结构各有什么特点？

（1）集合结构：结构中的数据元素之间除了同属于一种类型外，无其他关系。
（2）线性结构：结构中的数据元素之间存在一对一的关系。
（3）树形结构：结构中的数据元素之间存在一对多的关系。
（4）图状结构或网状结构:结构中的数据元素之间存在多对多的关系。

29、数据结构中的存储结构有哪几种？各有什么有优缺点？

30、什么是数据结构？C语言、数据结构、算法以及程序之间的关系是什么？

数据结构是指所有数据元素以及数据元素之间的关系，可以看作是相互之间存在着某种特定关系的集合，因此可以我们将数据结构看成是带结构的数据元素的集合。此外，在通常情况下，选择合适的数据结构可以带来提高运行效率或者存储效率。

数据结构、算法以及程序之间的关系是：数据结构 + 算法 = 程序。
算法不一定要求能够在计算机上直接运行，但程序必须要求能在计算机中运行。C语言只是对算法或者数据结构的描述，描述数据结构和算法不局限于C语言，也可以是C++语言和其他的计算机语言甚至也可以用人的自然语言。

31、常见数据结构？

 数组 ；栈；队列；链表；图；树；前缀树；哈希

32、解决哈希冲突的方法

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。

1） 线性探测法

2） 平方探测法

3） 伪随机序列法

4） 拉链法

33、什么是KMP算法？

在一个字符串中查找是否包含目标的匹配字符串。其主要思想是每趟比较过程让子串先后滑动一个合适的位置。当发生不匹配的情况时，不是右移一位，而是移动（当前匹配的长度– 当前匹配子串的部分匹配值）位。

34、什么是B树？

根据B类树的特点，构造一个多阶的B类树，然后在尽量多的在结点上存储相关的信息，保证层数尽量的少，以便后面我们可以更快的找到信息，磁盘的I/O操作也少一些，而且B类树是平衡树，每个结点到叶子结点的高度都是相同，这也保证了每个查询是稳定的。

B树和B+树的区别，以一个m阶树为例。

1. 关键字的数量不同；B+树中分支结点有m个关键字，其叶子结点也有m个，其关键字只是起到了一个索引的作用，但是B树虽然也有m个子结点，但是其只拥有m-1个关键字。
2. 存储的位置不同；B+树中的数据都存储在叶子结点上，也就是其所有叶子结点的数据组合起来就是完整的数据，但是B树的数据存储在每一个结点中，并不仅仅存储在叶子结点上。
3. 分支结点的构造不同；B+树的分支结点仅仅存储着关键字信息和儿子的指针（这里的指针指的是磁盘块的偏移量），也就是说内部结点仅仅包含着索引信息。
4. 查询不同；B树在找到具体的数值以后，则结束，而B+树则需要通过索引找到叶子结点中的数据才结束，也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径。

感谢博主：线性表的存储结构详解_为什么在线性表中结点所占存储量和结构本身所占存储量是一样的-CSDN博客

感谢博主：https://xgqngu.blog.csdn.net/article/details/112134686

感谢博主：数据结构常见面试题，一网打尽！_数据结构面试题-CSDN博客

感谢博主：数据结构面试题（史上最全基础面试题，精心整理100家互联网企业面经） - 知乎

感谢博主：数据结构面试常见问题总结-CSDN博客