头指针是指向链表第一个节点的指针，即使链表为空也始终存在，用于标识链表，是链表的必要元素。

而头结点是为了操作统一和方便而设置的，位于第一个元素节点之前，其数据域一般没有意义但可以存放链表长度。有了头结点，插入和删除第一个元素节点的操作与其他节点一致，但头结点不是链表的必要元素。

5.栈和队列的区别和内存结构

栈：

        栈的定义是：只允许在表的末端进行插入和删除的线性表，允许插入和删除的一端叫做栈顶，不允许插入和删除的一端叫做栈底。

        栈的存储结构通常分为基于数组存储表示的顺序存储结构和基于链表的链式存储结构。

        顺序栈的内存结构：存放栈中元素的数组、栈顶指针、最大容纳元素个数

        链式栈的内存结构：栈顶指针

队列：

        队列的定义是：只允许在表的一端插入，在另一端删除的线性表。允许插入元素的一端称为队尾，允许删除的一端称为队首。

        队列的存储结构通常分为基于数组的存储表示和基于链表的存储表示。

        顺序存储结构利用一个一维数组作为存储结构，并设置头指针和尾指针两个指针来指示队首和队尾的位置。

        链式队列由队首指针和队尾指针构成。

6.有一个循环队列Q，里面的编号是0到n-1，头尾指针分别是f，p，现在求Q中元素的个数？

(p-f+n)%n

7. 如何区分循环队列是队空还是队满？队列内元素个数？

front 表示队头指针（指向队列内首元素）

rear 表示队尾指针（指向队列内尾元素的下一个位置）

m 表示队列的容量（包括那个留空的位置）

队空： front=rear

队满： front=(rear+1)%m

队列内元素个数： (rear - front + m) % m

8.堆、大顶堆、小顶堆实现及应用

（1）堆的定义

        堆是一种完全二叉树。完全二叉树的定义：所有节点从上往下，从左往右的依次排列，不能有空位置，是为完全二叉树。

（2）大顶堆

        每个结点的值都大于或等于其左右孩子结点的值。大顶堆常用于实现优先队列，且可用于构建堆排序算法。

（3）小顶堆

        每个结点的值都小于或等于其左右孩子结点的值。小顶堆常用于问题如：查找流中的前 K 个最小元素。

建堆过程：

9.哈希表的概念、构造方法，哈希冲突的解决办法？

（1）哈希表的概念

哈希表（Hash Table）是一种用于存储键值对（key-value pairs）的数据结构。它通过使用哈希函数将键映射到表中的位置，从而实现快速的数据存取。

（2）构造方法

直接定址法

Hash        直接根据数据的值来映射到地址         Hash(key)=a * key+b (a、b为常数)

数字分析法

        根据数据的某些数字（比如百位和十位数字）来映射到地址。

平方取中法

        若关键字比较短，则可先对关键字值求平方，然后取运算结果的中间几位为哈希地址。

折叠法

        将关键字值分割成位数相同的几个部分，然后取这几部分的叠加和（舍去进位）作为哈希地址。

除留余数法

        H（key)=key%13

（3）解决哈希冲突的方法

开放定址法: 当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。
再哈希法：当发生哈希冲突时使用另一个哈希函数计算地址值，直到冲突不再发生。这种方法不易产生聚集，但是增加计算时间，同时需要准备许多哈希函数。
链地址法：将所有哈希值相同的Key通过链表存储。key按顺序插入到链表中

建立公共溢出区：采用一个溢出表存储产生冲突的关键字。如果公共溢出区还产生冲突，再采用处理冲突方法处理。

10.判断链表是否有环 ★★★★★★★

方法一：穷举遍历

从第一个节点开始，每遍历一个节点，都要从头遍历新节点之前的所有节点，如果遇到相同节点，则说明被遍历过两次，则存在环；反之，所有节点都遍历过都没遇到，则不存在环。

方法二：快慢指针

从头开始设置两个指针，快指针每次走2步，慢指针每次走1步，如果快指针先碰到尾，则无环，否则两个指针指向的节点相同，则有环。（相当于操场，跑的快的一定会和跑的慢的再次追上）

方法三：Set集合大小变化

用 set 遍历链表，把节点放入set里，每次访问下个节点时，如果set长度不变，则跳出，说明有环。否则set长度+1，继续遍历。

11.平衡二叉树、二叉排序树、完全二叉树、二叉搜索树的区别及如何构造

（1）区别

        平衡二叉树：平衡二叉树是一种特殊的二叉排序树，它要求每个节点的左右子树的高度差不超过1。这样可以保证树的高度大致是log(n)，从而保证搜索、插入和删除操作的时间复杂度为O(log(n))。

        二叉排序树：二叉排序树是一种特殊的二叉树，它满足以下性质：每个节点的左子树上所有节点的值均小于它的根节点的值，每个节点的右子树上所有节点的值均大于它的根节点的值。二叉排序树不一定是平衡的。

        完全二叉树：完全二叉树是指除最后一层外，每一层上的节点数都达到最大值，在最后一层上只缺少右边的若干节点。这样的树有固定的性质，例如节点按层序编号后，若节点i有子节点，则其左子节点为2i，右子节点为2i+1。

        二叉搜索树：二叉搜索树与二叉排序树是同一种数据结构，通常是指左子树上所有节点的值小于根节点的值，右子树上所有节点的值大于根节点的值。

（2）如何构造

平衡二叉树：

以中序遍历的方式插入节点，每次插入后检查是否破坏了平衡。
如果破坏了平衡，进行以下旋转操作来恢复平衡：
左左情况（LL）：执行右旋转。
右右情况（RR）：执行左旋转。
左右情况（LR）：先对左子树进行左旋转，再对当前节点进行右旋转。
右左情况（RL）：先对右子树进行右旋转，再对当前节点进行左旋转。

二叉排序树：

从空树开始，每个新节点根据其值与当前节点比较，决定它是当前节点的左子节点还是右子节点。
重复上述过程，直到新节点插入到合适的位置。

完全二叉树：

按层序遍历的顺序添加节点，如果某一层的节点未达到最大数，则下一层不再添加节点。
可以通过数组来实现完全二叉树，其中数组的第i个元素对应二叉树的第i个节点。

二叉搜索树：

二叉搜索树的构造与二叉排序树相同，通过比较节点值来决定新节点的位置。
通常情况下，插入操作会保持二叉搜索树的性质，但如果需要，也可以在插入后进行平衡操作来构造平衡二叉搜索树（AVL树）。

12.如何由遍历序列构造一颗二叉树？/已知先序序列和后序序列能否重现二叉树？（笔试常考）

        若是 前序+中序 或者 中序+后序，则可。

        前序+中序：

        先序中我们可以锁定当前第一个点为根，中序中找到这个点，去把子树分割成左子树和右子树两个部分，再依次递归下去即可

        中序+后序：

        在后序遍历中找到根节点（最后一个元素），然后在中序遍历中找到根节点的位置，以此将中序遍历分为左子树和右子树的元素，再递归地对左右子树进行相同操作，最终重建整棵二叉树。

13.B树是什么?在数据库中有什么应用？（B数和B+树的区别）

         在数据库查询中，以树存储数据。树有多少层，就意味着要读多少次磁盘IO。所以树的高度越矮，就意味着查询数据时，需要读IO的次数就越少。（众所周知，读IO是一件费事的操作）当数据量大的时候，用AVL树（平衡二叉树）存的话，就算AVL是平衡树，但是也扛不住数据量大，数据量大，AVL树的树高肯定很高，那么读取数据的IO次数也会多。B树的一个结点可以装多个值，读取时，是把整个结点读到内存，然后在内存中，对结点的值进行处理，在内存中处理速度肯定比磁盘快。所以只要树的高度低，IO少，就能够提升查询效率，这是B树的好处之一。

        B树的缺点是：不利于范围查找(区间查找)，如果要找 0~100的索引值，那么B树需要多次从根结点开始逐个查找。

        B+树和B树最大的不同是：B+树内部有两种结点，一种是索引结点，一种是叶子结点。B+树的索引结点并不会保存记录，只用于索引，所有的数据都保存在B+树的叶子结点中。而B树则是所有结点都会保存数据。

        B+树的叶子结点都会被连成一条链表。叶子本身按索引值的大小从小到大进行排序。即这条链表是从小到大的。因此可以直接通过遍历链表实现范围查找。

14. 红黑树原理是什么？建立过程？

（1）红黑树的原理

红黑树通过以下五个性质来保持平衡：

每个节点非红即黑。
根节点是黑色的。
每个叶子节点（NIL节点，树尾端的虚拟节点）是黑色的。
如果一个节点是红色的，则它的子节点必须是黑色的（不能有两个连续的红色节点）。
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

（2）建立过程

树的创建： 开始时，树是空的，随后通过插入操作逐步建立。

节点插入：

按照二叉搜索树的方法插入新节点，并将其设置为红色。
插入后，为了维持红黑树的性质，可能需要对新节点进行重新着色和树的旋转操作。

重新着色和旋转：

重新着色：这是最简单的情况，只需改变一些节点的颜色。
旋转：分为左旋和右旋。旋转的目的是在不破坏二叉搜索树特性的前提下，改变树的结构，以此来维护红黑树的性质。

15.二分搜索和单纯的线性搜索的区别/时间复杂度

（1）二分搜索：

含义：二分搜索又叫二分查找，在保证元素是有序排列的情况下（前提），每次将有效的查找范围分为两半，并且每次将范围减少一半，其中每次通过将要查找的值key与有效范围中间的值比较来判断是否已经找到该值，或者需要在剩下的哪一半中继续查找。
适用场景：
二分搜索适用于有序数组。
适用于大量数据，尤其是当数据量非常大且已经排序时。
时间复杂度：
最坏情况：O(log n)，其中n是数组中的元素个数。每次比较大约减少一半的搜索区间。
平均情况：O(log n)。
最好情况：O(1)，即第一次比较就找到了目标值。

（2）线性搜索：

含义：线性搜索是一种顺序搜索算法，它从数组的第一个元素开始，逐个检查每个元素，直到找到目标值或检查完所有元素。
适用场景：
线性搜索适用于未排序的数组或列表。
它适用于小数据量或者对时间效率要求不高的情况。
时间复杂度：O(n)

16. 插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法的基本思想是什么？时间复杂度？是否稳定？★★★★★★

1.冒泡排序

        冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

2.选择排序

        首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

3.插入排序

        插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

4.希尔排序

         希尔排序（Shell Sort）是一种改进的插入排序算法，它通过比较距离较远的元素来工作，其核心理念是使数组中任意间隔为h的元素都是有序的。希尔排序是第一个突破O(n^2)时间复杂度的排序算法，其时间复杂度依赖于所选择的间隔序列。以下是基本步骤：

选择间隔序列： 选择一个间隔序列t1, t2, …, tk，其中t1 > t2 > … > tk > 1，最后一个间隔通常是1。间隔序列的选择对算法的性能有很大影响，但并没有一个统一的标准。

分组： 根据间隔序列，将数组分成若干组，所有距离为h的元素被分为同一组。

插入排序： 对每一组使用插入排序。由于每一组的数据量相对较小，插入排序在这种情况下的效率较高。

缩小间隔： 完成所有分组的插入排序后，缩小间隔（例如，对间隔序列中的下一个值重复步骤2和3）。

重复排序： 当间隔缩小到1时，整个数组就被完全排序了。

5.归并排序

        归并排序（Merge Sort）是一种经典的排序算法，它采用分治策略（Divide and Conquer）将数据分割成越来越小的半子表，再对半子表排序，最后用归并（Merge）操作将排好序的半子表合并成一个序列。以下是基本步骤：

分解（Divide）： 将待排序的n个元素的序列分解成两个子序列，每个子序列包含n/2个元素。

递归排序（Conquer）： 分别对两个子序列进行归并排序。

合并（Merge）： 将两个已排序的子序列合并成一个有序序列。

6.快速排序

        快速排序（Quick Sort）是一种高效的排序算法，采用分治策略（Divide and Conquer）来对序列进行排序。快速排序的基本思想是选择一个基准元素（pivot），通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后递归地对这两部分数据分别进行快速排序。以下是基本步骤：

选择基准（Pivot）： 在数据集中选择一个元素作为基准（通常选择第一个元素、最后一个元素或者中间元素）。

分区（Partitioning）： 重新排列数组，所有比基准小的元素摆放在基准前面，所有比基准大的元素摆放在基准的后面（相等的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。

递归排序（Recursion）： 递归地将小于基准元素的子序列和大于基准元素的子序列排序。

7.堆排序

        堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。以下是基本步骤（以进行升序排序为例）：

建立最大堆（Build Max Heap）： 将无序的输入数据构造成一个最大堆。

堆调整（Heapify）： 将堆的根节点（最大值）与堆的最后一个节点交换，然后破坏堆结构。将剩余的n-1个节点重新构造成一个最大堆。

重复堆调整： 重复步骤2，每次调整都会将最大元素放到正确的位置，直到堆中只剩下一个节点。

8.计数排序

        计数排序（Counting Sort）是一种非比较型的整数排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间排序算法，计数排序的时间复杂度为O(n+k)，其中n是待排序元素的个数，k是输入数据的范围。以下是基本步骤：

找出待排序数组中最大和最小的元素： 确定计数数组的大小范围。

创建计数数组： 根据最大和最小元素的差值，创建一个大小为k的计数数组，初始化所有值为0。

计数： 遍历待排序数组，计算每个元素出现的次数，存入计数数组中。

累加计数数组： 对计数数组进行变形，每个位置存储小于等于该位置索引值的元素的总数。

输出结果： 根据累加后的计数数组，从后往前遍历原数组，将每个元素放到结果数组的正确位置上。

17.最小生成树和最短路径用什么算法来实现？（迪杰斯特拉、弗洛依德、普利姆、克鲁斯卡尔）算法的基本思想是什么？算法的时间复杂度？如何进行优化？★★★★★★★

最小生成树: 普利姆、克鲁斯卡尔

最短路：迪杰斯特拉、弗洛依德，单源负权边时是Bellman Ford算法

迪杰斯特拉，克鲁斯卡尔，普利姆的基本思想是：贪心。

floyd是动态规划，也就是枚举中间点，i-j的距离可以被优化成经过中间点k,i-k-j

堆优化的迪杰斯特拉，克鲁斯卡尔，普利姆均为O(nlogn)

普通dji是O(n^2)

floyd为O(n^3)

18. 邻接表和邻接矩阵（如何存储大数据）

1.邻接表

邻接表是一种使用数组（或列表）存储图的方法，其中每个顶点对应一个列表（或链表），该列表包含所有与该顶点直接相连的其他顶点。

邻接表的存储方式：

顶点数组： 一个数组，每个元素代表图中的一个顶点。
链表（或数组）： 对于每个顶点，都有一个链表（或数组）存储与其相连的其他顶点。

存储大数据：

哈希表： 使用哈希表来存储顶点的邻接表，可以快速访问任何顶点的邻接表。
压缩技术： 对于链表，可以使用压缩技术（如指针压缩）来减少内存占用。

2.邻接矩阵

邻接矩阵是一个二维数组，其中每个元素表示图中两个顶点之间是否存在边。如果顶点i与顶点j之间有边，则矩阵的第i行第j列（或第j行第i列）的元素为1（有向图中）或边的权重（有权图中）；如果没有边，则为0。

邻接矩阵的存储方式：

二维数组： 一个二维数组，数组的行和列对应图的顶点，元素值表示顶点间的连接关系。

存储大数据：

稀疏矩阵表示： 使用三元组表、十字链表或压缩稀疏行（CSR）等稀疏矩阵存储方法来减少内存占用。
分布式存储： 对于非常大的图，可以将邻接矩阵分布在多个机器上。

19.介绍一下深度优先搜索和广度优先搜索是如何实现的？

1.深度优先搜索

        深度优先搜索是一种用于遍历或搜索树或图的算法。在这种算法中，搜索沿着一条路径深入直到它不能再深入为止，然后回溯到之前的分叉点，继续探索其他路径。

  实现关键步骤：

从一个未访问的顶点开始，访问该顶点并将其标记为已访问。
递归地访问所有未访问的邻接点。

2.广度优先搜索

        广度优先搜索是一种用于图遍历的算法，这种算法从起点开始，首先访问所有距离起点最近的顶点，然后再逐步向外扩展，直到访问所有顶点。

实现关键步骤：

从一个未访问的顶点开始，访问该顶点并将其标记为已访问。
将所有未访问的邻接点加入队列。
重复上述步骤，直到队列为空。

20.介绍一下字符串匹配算法：朴素的匹配算法和KMP算法。

1. 朴素的匹配算法

实现步骤：

对于文本中的每个位置i（从0到n-m，其中n是文本长度，m是模式长度），将模式与文本的子串（从位置i开始，长度为m）进行比较。
如果在某个位置i处，模式与文本的子串匹配，则返回位置i。
如果直到文本末尾都没有找到匹配的模式，则返回未找到。

时间复杂度：

        最坏情况下的时间复杂度为O(n*m)，其中n是文本长度，m是模式长度。

2. KMP算法

实现步骤：

预处理模式： 计算一个部分匹配表（也称为“失败函数”），这个表告诉我们在模式中的每个位置之前已经匹配的字符数。

        如何计算部分匹配表：

初始化一个长度与模式长度相同的数组prefix，其中prefix[0] = 0。
使用两个指针i和j，其中i是当前正在计算的部分匹配表的位置，j是当前匹配的长度。
遍历模式，对于每个位置i：
如果j > 0且模式在位置i的字符不等于位置j的字符，则将j设置为prefix[j-1]。
如果模式在位置i的字符等于位置j的字符，则增加j，并将prefix[i]设置为j。
重复上述过程，直到遍历完整个模式。

匹配过程： 使用部分匹配表在文本中进行模式匹配。

初始化两个指针i和j，其中i用于遍历文本，j用于遍历模式。
遍历文本，对于每个位置i：
如果j > 0且文本在位置i的字符不等于模式在位置j的字符，则将j设置为prefix[j-1]。
如果文本在位置i的字符等于模式在位置j的字符，则增加j。
如果j等于模式长度，说明找到了匹配，返回当前文本位置i减去模式长度加1。
如果遍历完文本仍未找到匹配，则返回-1。

时间复杂度：

        KMP算法的时间复杂度为O(n+m)，其中n是文本长度，m是模式长度。

有歧义评论区提出噢

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/881898