顺序查找的时间复杂度为_二叉排序树的查找效率

数据结构-准备复试问答题 　　1. 排序算法 　　八大排序算法的特点表格： 排序算法时间复杂度空间复杂度是否为稳定排序是否为原地排序适用场景冒泡排序O(n^2)O(1)稳定原地小规模数据排序选择排序O(n^2)O(1)不稳定原地小规模数据排序插入排序O(n^2)O(1)稳定原地小规模数据排序，对已经基本有序的数据排序效率高希尔排序O(nlogn)~O(n^2)O(1)不稳定原地中等规模数据排序归并排序O(nlogn)O(n)稳定非原地大规模数据排序快速排序O(nlogn)~O(n^2)O(logn)~O(n)不稳定原地大规模数据排序堆排序O(nlogn)O(1)不稳定原地大规模数据排序计数排序O(n+k)O(n+k)稳定非原地数据范围小，且数据较为集中 　　备注：n为待排序数据的数量，k为待排序数据的范围。 　　2. 稳定的且最优时间复杂度 为O(nlogn) 　　稳定的：插入，冒泡，归并，基数 　　只有归并满足O(nlogn) 　　3. 对线性表进行操作，其时间复杂度为O(1)的情况。 　　顺序表的下标查询，链表的增加和删除 　　4. 二叉树里面有多少个空指针？ 　　对于一个有n个节点的二叉树，最多有n+1个空指针（Null指针）。 　　5. 有什么方法可以加快二叉树的查询？ 　　二叉树的查询速度主要取决于树的结构，如果树的结构不平衡，查询速度可能会很慢。因此，为了加快二叉树的查询，我们需要考虑如何构建平衡的二叉树。以下是几种常见的加快二叉树查询速度的方法： 　　1. 平衡二叉树：例如AVL树、红黑树等。这些树具有自平衡的能力，可以确保树的高度不会过高，从而保证查询效率。 2. 哈希表：哈希表可以在O(1)的时间内完成查询，但是对于动态数据集，哈希表需要扩容和重新哈希，这可能导致一段时间内查询效率下降。 3. 优化查询顺序：如果我们能够预先知道查询顺序，可以将数据按照查询顺序构建成一棵二叉搜索树，这样可以大大提高查询效率。 4. 基于二叉树的索引结构：例如B树、B+树等。这些索引结构可以将数据按照某种方式组织起来，以便更快地查询数据。 　　6. 二叉排序树查找的时间复杂度，如果是平衡树又是多少 　　Lgn-n， lgn。 　　7. 最小生成树的算法有哪些以及这两个算法采用的数据结构 　　最小生成树（Minimum Spanning Tree，MST）是连接一个无向图的所有节点，并使得所有边的权值之和最小的树形子图。最小生成树的算法有很多，其中比较常用的有 Prim 算法和 Kruskal 算法。 普里姆算法（Prim Algorithm） 　　普里姆算法是一种贪心算法，它从一个节点出发，每次选择当前节点到其它节点之间的最短边，直到所有节点都被连通为止。可以采用堆来实现优化，堆可以维护当前节点到其它未加入最小生成树的节点的最短距离，每次选择距离最短的节点加入最小生成树。普里姆算法的时间复杂度为 O(ElogV)，其中 E 是边的数量，V 是节点的数量。 克鲁斯卡尔算法（Kruskal Algorithm） 　　克鲁斯卡尔算法也是一种贪心算法，它按照边的权值从小到大的顺序逐个加入到最小生成树中，直到所有节点都被连通为止。克鲁斯卡尔算法采用并查集来维护当前边连接的两个节点是否在同一连通分量中，如果不在同一连通分量中则加入最小生成树。克鲁斯卡尔算法的时间复杂度为 O(ElogE)，其中 E 是边的数量。 　　8. 快速排序 　　快速排序采用分治的思想，将待排序序列分成两部分，然后对这两部分分别进行递归排序。在一趟排序中，快速排序通过选取一个基准值，将待排序序列分成两部分，一部分小于基准值，一部分大于等于基准值。通过这种分割，快速排序能够减少比较的次数，从而提高排序的效率。 此外，快速排序的实现也非常简单，只需要通过递归实现分治过程，通过交换素来实现分割，代码量较少，因此也是一个常用的排序算法。 　　9. 快排最坏情况时间复杂度，什么情况是最坏的 　　N^2, 基本有序 　　10. 那在这种最坏的情况怎么样做可以提高效率? 　　随机选择枢纽素 　　11. 为什么快排最后要退化成O（n²）还叫快排 　　最坏情况并不常见，而且可以通过随机化选择枢纽素减少发生的概率 　　12. 为什么快排平均性能最好？ 　　快速排序之所以被称为”快速”排序，是因为在排序过程中它能够比其他排序算法更快地完成排序。 快速排序采用分治的思想，将待排序序列分成两部分，然后对这两部分分别进行递归排序。在一趟排序中，快速排序通过选取一个基准值，将待排序序列分成两部分，一部分小于基准值，一部分大于等于基准值。通过这种分割，快速排序能够减少比较的次数，从而提高排序的效率。 此外，快速排序的实现也非常简单，只需要通过递归实现分治过程，通过交换素来实现分割，代码量较少，因此也是一个常用的排序算法。 综合来看，快速排序具有比较高的时间复杂度和空间复杂度，并且在大多数情况下能够比其他排序算法更快地完成排序，因此被称为”快速”排序。 　　13. 基数排序，时间复杂度和空间复杂度 　　O(d*(n+r)),O(r)………d组，n个素，r个队列 　　14. 既然基数排序是线性的，为什么很多数据的时候不选择基数排序 　　实现较难，受数据分布影响大，占用空间较大 　　15. 堆排序复杂度 　　O(nlogn)， O（1） 　　16. 冒泡排序的最好和最坏情况复杂度，平均情况复杂度，以及平均情况复杂度怎么来的 　　冒泡排序的最好情况是，待排序的序列已经有序，此时只需要进行一次扫描，没有任何素的交换操作，时间复杂度为O(n)。 冒泡排序的最坏情况是，待排序的序列是逆序的，每次比较都需要进行交换操作，时间复杂度为O(n^2)。 冒泡排序的平均情况复杂度为O(n^2)。平均情况复杂度可以通过对比较次数和交换次数的分析得到。在冒泡排序中，每进行一轮扫描，最多会有n-1次比较和n-1次交换。如果待排序的序列是随机的，那么每个素有1/2的概率要进行交换，因此平均交换次数为n(n-1)/4，平均比较次数为n(n-1)/2。因此，总的平均时间复杂度为O(n^2)。 需要注意的是，虽然冒泡排序的时间复杂度较高，但是由于它的实现比较简单，对于小规模的数据集合排序效率还是比较高的。 　　17. 希尔排序 　　希尔排序是一种改进的插入排序，也称为缩小增量排序。它的基本思想是将待排序的序列划分成若干个子序列，对每个子序列进行插入排序，通过逐渐缩小子序列的长度，最终完成整个序列的排序。具体步骤如下： 选择一个增量序列，例如：n/2，n/4，n/8，…，1，其中n为待排序序列的长度。对于每个增量，将待排序序列分成若干个子序列，分别对每个子序列进行插入排序。逐渐缩小增量，重复上述过程，直到增量为1。 　　希尔排序的时间复杂度不是很容易分析，因为它的时间复杂度取决于增量序列的选择。最坏情况下的时间复杂度为O(n^2)，但是对于大部分实际应用中的数据集合，希尔排序的时间复杂度可以达到O(nlogn)甚至更优秀。 希尔排序是一种不稳定的排序算法，它的实现比较复杂，但是它的性能优异，在大规模数据集合排序时，它的效率要比简单的插入排序高很多。 　　18. 哪种查找比较快，时间复杂度 　　哈希查找，O(1) 　　19. 哈夫曼树，哈夫曼编码及其应用 　　哈夫曼树（Huffman Tree）是一种特殊的二叉树，用于实现一种有效的数据压缩算法，又称为最优二叉树（Optimal Binary Tree）。哈夫曼树的特点是，权值较小的节点位于树的底部，权值较大的节点位于树的顶部。哈夫曼树的构建过程是根据一组给定的权值，通过贪心算法来得到一棵树。构建过程中，每次从权值最小的两个节点中选取一个新节点作为它们的父节点，新节点的权值为两个子节点的权值之和。重复这个过程直到树的根节点被选出。 哈夫曼编码（Huffman Coding）是一种可变字长编码（Variable-Length Code），它将一个字符对应的二进制码表示为一串变长的0和1，使得出现频率高的字符对应的二进制码比出现频率低的字符对应的二进制码短，从而达到对数据的压缩目的。哈夫曼编码的构造过程与哈夫曼树的构建过程类似，先统计每个字符出现的频率，然后按照频率构建哈夫曼树，树的左边为0，右边为1，从根节点到叶子节点便构成了该字符的编码。 哈夫曼编码的应用非常广泛，例如在数据压缩、通信系统、加密等领域都有应用。哈夫曼编码的主要优点是能够在不损失信息的情况下将数据压缩到更小的体积，从而提高数据的传输效率和存储效率。 　　20. 为什么哈夫曼树权值最小，属于什么算法 　　贪心 　　21. 折半查找的要求，时间复杂度 　　有序序列，O(logn) 　　22. 堆排序过程+如何调整堆 　　从下往上调整，每次取堆顶 　　23. 迪杰斯特拉除了迪杰斯特拉算法还有什么成就 　　提出“goto有害论”； 　　提出信号量和PV原语； 　　创造Dijkstra最短路径算法和银行家算法； 　　24. 哈希表解决冲突的方法 　　开放定址法：线性探测法，平方探测法，双散列法 　　拉链法 　　25. 开放地址法如何删除关键字？之后再插入新的关键字遇到之前虚拟删除的那个空间如何处理？ 　　做标记，替代 　　26. 合并查找（并查集） 　　合并查找（Union-Find）是一种用于处理集合的数据结构，也称为并查集。它支持两个操作：查找和合并。主要用于解决一些经典问题，比如连通性问题、最小生成树问题等。 合并查找主要包含以下两个操作： 　　1. 查找（Find）：在查找一个素所属的集合时，合并查找会沿着这个素的祖先节点向上查找，直到找到根节点，即代表这个集合的节点。 2. 合并（Union）：将两个素所属的集合合并成一个集合，合并的方法有多种，常见的有按秩合并和按大小合并。 　　合并查找可以用于判断图是否连通、构建最小生成树等问题。在实现过程中，可以使用一个数组记录每个节点的父节点，若一个节点的父节点为其本身，则说明该节点是集合的代表节点，也即根节点。通过路径压缩和按秩合并等优化，可以有效提高合并查找的效率。 　　27. 二分查找的条件，链式结构要如何二分二叉查找 　　有序序列，二叉排序树 　　28. DFS路径唯一吗 　　一般不唯一 　　29. 如何快速找到一个单链表的三分之一处 　　双指针，一个每次走三步，一个每次走一步 　　30. 设计一种数据结构以及相关的操作来找出树叶子结点的个数 　　可以设计一个二叉树数据结构，并在节点中增加一个布尔型变量，用于表示该节点是否为叶子节点。以下是基于这个数据结构的操作： 　　1. 创建二叉树：可以使用链表实现。每个节点包含三个属性：左子节点、右子节点、是否为叶子节点。 2. 插入节点：在插入节点时，判断该节点是否有左右子节点，如果没有则标记为叶子节点。 3. 统计叶子节点数：遍历整棵树，统计叶子节点的数量。可以使用递归方式实现，对于每个节点，如果它是叶子节点，则数量加1；否则，遍历它的左右子节点。 4. 删除节点：在删除节点时，如果该节点是叶子节点，则直接删除；否则，需要将其左右子节点的叶子节点标记更新。 　　这样设计的时间复杂度是O(n)，因为需要遍历整棵树才能统计叶子节点数。 　　31. 常用的排序有哪些？ 　　冒泡，快速排序，归并排序 　　32. 时间复杂度为O（nlogn）且与初始排列无关的排序有哪些？ 　　归并和堆排 　　33. 给你一堆无序的数据，如何才能高效的找到其中间值？ 　　可以使用快速选择算法（QuickSelect）来高效地找到无序数据的中位数或第k小的素。 快速选择算法是快速排序算法的变种，它的基本思路是：选取一个枢轴素，将所有比枢轴素小的素放在左侧，所有比枢轴素大的素放在右侧，再根据枢轴素所在的位置，将待选范围缩小一半，递归地处理这个范围，直到找到第k小的素。 具体来说，我们可以选取一个随机素作为枢轴素，将小于等于它的素放在左侧，大于它的素放在右侧。然后比较枢轴素的位置和k的大小关系，若相等则找到了第k小的素，否则根据大小关系递归处理左侧或右侧部分。 快速选择算法的时间复杂度为O(n)，与快速排序相比，它只需要处理部分数据，因此效率更高。 　　窗体顶端 　　34. 完全图用深度和广度优先遍历所得到的生成树的度分别是多少 　　对于n个节点的完全图，每个节点的度数都为n-1，因为每个节点都与其他n-1个节点相连。因此，使用深度优先遍历或广度优先遍历得到的生成树的度数也应为n-1。 　　35. 完全图用dfs和bfs生成的生成树的高度差 　　Dfs形成链表，高度为n 　　Bfs形成n-1个节点的树，高度为2 　　36. 权值都为1的图怎样得到两个顶点的距离 　　Bfs 　　37. 循环链表队列只设置一个指针，应该放在头还是尾 　　队尾 　　38. 堆栈的区别 　　堆和栈都是计算机内存中的数据结构，它们有以下的区别： 　　1. 数据结构：栈是一种线性结构，而堆是一种树形结构。 2. 访问方式：栈是一种后进先出（LIFO）的结构，即最后放入的素最先被取出；堆是一种可以按照某种优先级访问素的数据结构。 3. 内存分配：栈的内存分配是静态的，一般在编译时就分配好了，程序在运行的时候不会再动态扩展；堆的内存分配是动态的，在程序运行的时候可以动态分配和释放内存。 4. 空间分配：栈的空间有限，一般只有几MB，所以存储的数据量比较小；堆的空间比较大，一般可以达到几十GB或者更大，可以存储大量的数据。 5. 数据类型：栈主要存储函数调用的上下文信息，如函数返回地址、局部变量等，一般存储的是基本数据类型，如整数、浮点数等；堆主要用来存储动态分配的对象，如数组、字符串等，可以存储任意数据类型。 6. 分配效率：栈的分配效率比较高，因为只需要移动指针就可以分配和释放内存；堆的分配效率比较低，因为需要搜索可用的内存块并进行分配和释放操作。 　　综上所述，堆和栈有不同的应用场景和使用方法，需要根据实际情况进行选择。 　　39. 怎么判断有向图有没有回路（环） 　　判断有向图是否有环的一种常用算法是拓扑排序。如果一个有向图能够进行拓扑排序，则该有向图一定是无环的。拓扑排序的具体实现步骤如下： 选择一个入度为0的顶点并输出。从图中删除该顶点及其所有出边。更新所有剩余顶点的入度，即删除了一个入度为0的顶点之后，与其相邻的顶点的入度减1。重复1-3步骤，直到所有顶点都输出。如果此时还有顶点没有输出，则说明该有向图存在环。 　　如果在拓扑排序的过程中出现了第4步骤的情况，则说明该有向图存在环。 　　40. b树在实际应用中为什么会设置很大的阶数，如1000阶？ 　　B树是一种多叉树，每个节点有多个子节点。B树通常应用于磁盘存储等场景，以提高磁盘I/O的效率。为了减少磁盘I/O次数，B树的阶数一般设置得很大，比如1000阶或更大。 假设磁盘中每个扇区可以存储k个数据，一个B树节点可以存储m个数据。如果阶数为1000，即一个节点最多有1000个子节点，那么每个节点就可以存储m*k个数据。这意味着，在查找或插入数据时，每次磁盘I/O可以读取的数据量非常大，从而可以大大降低I/O次数，提高效率。 此外，大阶数的B树也可以减少树的深度，从而降低了查找或插入数据的时间复杂度。因此，在实际应用中，为了提高B树的效率，往往会设置很大的阶数。 　　41. 有没有什么排序平均比快排要快的。 　　桶排序 　　42. 数据结构的逻辑结构有哪些 　　1. 线性结构：线性结构是最基本的数据结构之一，数据素之间呈线性关系，即一个接一个地排列在一起。线性结构包括顺序表、链表、栈和队列等。 2. 树形结构：树形结构是一种非线性结构，具有分层关系的结构。树形结构包括二叉树、多叉树、森林等。 3. 图形结构：图形结构是一种非线性结构，由顶点和边组成，顶点之间可以有多条边相连。图形结构包括有向图和无向图等。 4. 集合结构：集合结构是一种无序的结构，其素之间没有任何关系。集合结构包括集合和散列表等。 　　43. 无向连通图最多几条边，最少几条? 　　N*(n-1)/2, n 　　44. 图的存储方式有哪些?邻接矩阵和邻接表分别用于什么样的图? 　　邻接矩阵：边较多 　　邻接表：顶点较多 　　45. 图的两种存储方式以及增删结点的过程。 　　邻接矩阵改变对应位置的值， 　　临界表增加边表结点 　　46. 深度优先遍历的序列确定，如果确定好了存储方式，假如选定好具体的邻接矩阵和邻接表，遍历的序列还唯一吗 　　唯一 　　47. 强连通分量和强连通分量结点 　　在有向图中，如果对于任意两个结点u和v，从u到v和从v到u都有路径存在，则称这个有向图是强连通图。有向图中的极大强连通子图，称为强连通分量。极大指子图内任意两个点都是强连通的，不能再添加其他的点。 　　48. 围棋棋盘可以用什么数据结构来实现 　　二维数组 　　49. 有一个项目，项目包含多个模块，模块间耦合度比较高，依赖性比较复杂，我现在想要算出每个模块的编码顺序，应该用什么数据结构，具体算法是什么样的？ 　　这是一个非常经典的软件工程问题，通常被称为“模块构建顺序问题”（Module Dependency Problem）。它的本质是要确定一个项目中多个模块之间的依赖关系，并按照一定的规则将它们排序，使得在编译或构建过程中，每个模块的依赖关系都得到满足。 常见的解决方法是使用拓扑排序（Topological Sorting）算法。拓扑排序可以解决有向无环图（DAG）中的排序问题，其中每个节点表示一个模块，每条边表示一个模块之间的依赖关系。具体来说，拓扑排序算法将有向图中的节点按照依赖关系排序，使得每个节点在排列中出现的位置都在它的后继节点之后。 拓扑排序算法的实现可以使用图的遍历方式，如深度优先搜索（DFS）或广度优先搜索（BFS），也可以使用队列等数据结构来实现。具体步骤如下： 初始化：将所有入度为0的节点加入一个队列中。循环：从队列中取出一个节点，将其输出，并将其所有的后继节点的入度减1。如果某个后继节点的入度减为0，则将其加入队列中。直到队列为空，输出的序列就是拓扑排序的结果。 　　在这个问题中，每个模块可以表示为一个节点，模块之间的依赖关系可以表示为一条有向边。对于每个节点，可以使用邻接表等数据结构来存储它的后继节点。然后，就可以使用拓扑排序算法来解决这个问题，得到每个模块的编码顺序。 需要注意的是，如果输入的依赖关系存在环路，即存在循环依赖关系，那么该算法就无法处理。在实际应用中，需要通过检查环路或者使用其他算法来解决这种情况。 　　50. kmp算法，为何相比常规会有优化 　　KMP算法是一种字符串匹配算法，它的优化主要体现在匹配失败时如何跳过尽可能多的无效比较。 传统的字符串匹配算法（如朴素算法）会对每个字符都进行一次比较，如果匹配失败则回到模式串的第一个字符重新开始匹配。这种算法的时间复杂度是$O(mn)$，其中$m$是模式串的长度，$n$是文本串的长度。 KMP算法通过预处理模式串构建出一个next数组，next[i]表示当模式串中的第i个字符和文本串中的一个字符不匹配时，模式串应该向右移动的距离。当匹配失败时，只需要将模式串向右移动next数组所指的位置即可，这样可以避免对已经匹配过的字符进行重复比较，从而提高算法效率。 KMP算法的时间复杂度为$O(n)$，其中$n$是文本串的长度。相比传统算法的$O(mn)$，KMP算法的效率明显更高。这也是KMP算法相比其他字符串匹配算法更加优秀的原因之一。 　　51. 面试常问：什么是红黑树？ 　　红黑树是一种自平衡二叉查找树，它能够自动保持树的平衡，从而保证基本的动态集合操作（插入、删除、查找）在最坏情况下的时间复杂度为O(log n)。 红黑树是一种二叉查找树，它满足以下五个性质： 　　1. 每个节点要么是红色，要么是黑色。 2. 根节点是黑色的。 3. 每个叶子节点（NIL节点，空节点）是黑色的。 4. 如果一个节点是红色的，则它的子节点必须是黑色的（不能有两个相邻的红色节点）。 5. 从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点（即具有相同的黑高度）。 　　红黑树的平衡是通过一系列旋转和颜色变换来实现的，这些操作可以保证树的高度始终不会超过其节点数的两倍，从而保证了最坏情况下的O(log n)时间复杂度。 　　窗体顶端 　　52. 什么是优先队列 　　优先队列（Priority Queue）是一种特殊的队列数据结构，它每次取出的素都是当前队列中优先级最高的素，而不是按照素进入队列的顺序来取出素。通常优先队列中的素是带有权值或者优先级的，因此优先队列也被称为带权队列（Weighted Queue）或堆（Heap）。 优先队列可以用来解决很多实际问题，例如任务调度、事件驱动等等。在优先队列中，素的优先级通常通过比较素的关键字来确定。例如，如果优先级队列存储的是整数，那么可以通过比较整数的大小来确定优先级，优先级高的整数会被先取出。 在实现上，优先队列可以使用堆（Heap）来实现。堆是一种基于完全二叉树的数据结构，可以用数组来实现。由于堆满足一些特殊的性质，例如父节点的优先级大于子节点，因此可以使用堆来实现优先队列，从而实现高效的素取出操作。常见的堆包括二叉堆和斐波那契堆等。 　　53. 列举哈希表在计算机组成原理，操作系统，计算机网络，数据库中的应用 　　哈希表是一种常用的数据结构，可以在多个领域得到应用。下面列举一些哈希表在计算机组成原理、操作系统、计算机网络、数据库中的应用： 　　1. 计算机组成原理：哈希表常被用于高速缓存的实现中，如Cache和TLB（Translation Lookaside Buffer）。 2. 操作系统：哈希表常被用于文件系统中的索引结构，如NTFS、EXT4等文件系统均采用哈希表作为索引结构，以提高文件检索的效率。 3. 计算机网络：哈希表常被用于路由表的实现中，如IPv4和IPv6协议中的路由表均使用哈希表实现。 4. 数据库：哈希表常被用于关系数据库的实现中，如MySQL、PostgreSQL等关系数据库中的哈希索引可以显著提高关系查询的效率。此外，哈希表还可以被用于缓存系统的实现中，如Redis等缓存系统中的哈希表可以用于缓存键值对。