本文共 3714 字，大约阅读时间需要 12 分钟。

逻辑结构与物理结构的区别

在计算机科学中，逻辑结构和物理结构是概念上的区别。逻辑结构描述的是数据和操作的抽象表示，而物理结构则描述了这些数据和操作在存储和执行中的实际位置。逻辑结构不考虑计算机内存的具体位置，而物理结构则关注存储器和处理器中的具体地址。

算法的特点

算法的特点可以总结为：明确性、可执行性、有限性、准确性。明确性是指算法运算对象、输入、输出和步骤都明确规定；可执行性是指算法可以在有限的时间和计算资源内完成；有限性是指算法的操作次数和数据规模是有限的；准确性是指算法不会产生错误的输出或无限循环。

常见的数据结构

常见的数据结构包括数组、链表、栈、队列、树（如二叉树）、图、哈希表和堆等。每种数据结构有其适用场景，例如数组适合固定长度的数据存储，链表适合动态大小的插入删除，栈和队列适合括号匹配和队列处理。

单链表结构和顺序存储结构的区别

单链表是一种线性存储结构，由若干节点组成，每个节点包含数据和指向下一个节点的指针。而顺序存储结构则是一种更高层次的概念，它指的是数据按照某种顺序排列，并支持按一定规则进行插入、删除和查询操作。

线性链表

线性链表是一种线性存储结构，由一系列节点组成，每个节点不仅包含数据，还包含指向下一个节点的指针。线性链表的常见实现方式是单链表和双链表。单链表仅包含前指针或尾指针，而双链表包含前后两个指针，支持双向遍历。

数组和链表的区别

数组是按顺序排列的零基次数组存储方式，其大小是固定的，只能通过间接存储Location来访问元素。而链表是一种多态性存储方式，支持动态增长和缩短，可以通过单独的指针访问任何元素。数组的优点是操作快捷，链表的优点是操作灵活。

判断一个链表是否有环，以及如何找到这个环

要判断链表中是否存在环，可以用 Floyd的轮询算法。选择链表的头指针，使用两个指针，一个正常遍历，另一个从头指针开始，跳过一个元素。若两个指针相遇则链表有环，否则无环。找到环的位置可以使用类似方法，让此相遇点作为环的起始节点。

单链表和双链表的区别

单链表是一种线性存储结构，由若干节点组成，每个节点包含数据和指向下一个节点的指针。单链表只能前向遍历，而双链表可以既支持前向又支持后向遍历。因此，双链表的指针结构包含前、当前、后指针，而单链表则只有当前指针。

头指针和头结点的区别

在链表中，头指针是链表的开始位置，由操作系统分配并初始化。头结点则是一个特殊的节点，包含数据和其他信息，如链表的长度和最后一个节点的地址。头指针和头结点可以是同一个节点的不同指针，或者分属不同的节点。

简述KMP算法

KMP算法是一种在线字符串匹配算法，主要思想是利用最长前缦（LPS）数组。首先预处理目标字符串，构建LPS数组，记录每个位置最长的前缦长度。匹配过程中，当遇到匹配失败时，根据LPS数组跳过重复部分，继续匹配，直到找到目标字符串的所有位置。

栈和队列的区别

栈是一种先进后出（FILO）的数据结构，支持在单个端点上进行操作，而队列是一种先进先出（FIFO）的数据结构，支持在两个端点上进行操作。栈通常用于括号匹配、算术显示器之类的应用，而队列常用于任务队列和进程调度。

栈和队列的相同之处和不同之处

栈和队列的相同之处在于都是线性存储结构，支持数据的插入和删除。它们的不同之处在于，栈是先进后出，而队列是先进先出。此外，栈通常实现为数组形式，而队列有时会使用环形数组结构。

两个栈实现队列，两个队列实现栈

要实现两个栈模拟队列，可以将两个栈顶部都作为对接点，当第一个栈为空时，peek的元素转移到第二个栈的顶部。当第一个栈不为空时，-pop的操作。这种方法需要额外的空间。两个队列实现栈的方法是，始终将第一个队列视为空，第二个队列作为栈，使用类似的对接点方法。

树和二叉树的相关概念

树是一个由节点组成的受限免疫图，每个节点最多有一个父节点，除根外。二叉树是一种树，每个节点最多有两个子节点。这棵树的每个内部节点有两个孩子节点，根节点称为二叉树的根，叶子节点没有子节点。

二叉平衡树

二叉平衡树是在二叉搜索树基础上增加了平衡条件的平衡树，例如红黑树和AVL树。这些树通过左右子树的高度差不超过1来保持平衡，避免树的高度过高导致效率低下。二叉平衡树通过重新定义子树的高度和平衡因素来维持性能。

二叉搜索树

二叉搜索树是一种二叉树，其中每个节点都有一个键值，并且左边的子树满足小于等于父节点，右边的大于等于父节点。这是高效的查找结构，用于记录按顺序排列的数据。2-3搜索树是额外结构的优化版本。

红黑树

红黑树是一种二叉平衡树，每个节点标记为红色或黑色，根据插入顺序和操作保持二叉树的平衡。其特殊性在于：插入一个节点时，需要调整颜色使其子树不超过高度差1。如果插入后左高度差太大，就旋转使其更平衡。

图的相关概念

图是一种数学概念，由节点和边组成，节点表示对象，边表示关系。无向图的边没有方向，向量图有方向。图中的通路可能以多条或单条边存在。图的存储结构通常使用邻接矩阵或邻接表。

邻接矩阵与邻接表的区别

邻接矩阵使用二维数组表示图，节点用索引表示，1表示有边，0表示无边。 neighbor矩阵的空间复杂度较高，但访问相邻节点时间复杂度很低。邻接表存储每个节点相邻的列表，占用内存更多，但遍历速度快。对于小规模的图，邻接矩阵更高效，渐大规模图，邻接矩阵的空间和时间成本更高。

深度优先遍历与广度优先遍历

深度优先遍历（DFS）是一个高效率遍历算法，按层递归深入。DFS适合查找路径或时序遍历。广度优先遍历（BFS）是一种层序搜索，按队列输出，解决最短路径问题。两种算法的时间效率依据问题方差和效率要求来定。

最小生成树的算法（普利姆算法，克鲁斯卡尔算法）

最小生成树是连接所有节点，不含环的子图，总权重最小。普利姆算法基于随机选择边的方法，每次选择权重较小的边添加到生成树中并剪枝回环。克鲁斯卡尔算法基于并查集，依次选择最小的边，不影响连通性。两者时间复杂度均为O(E log E)。

什么时候最小生成树唯一

当图中除了传统边及其权重，所有边的权重都唯一且满足三角不等式时，树结构才唯一。这样的前提保证边父节点为lowest的选择不会出现矛盾，如果一个新的边权重等于当前边的，并且不破坏连通性，那么生成树不唯一。

Dijkstra算法与Prim算法的区别

Dijkstra算法用于单源最短路径，由优先队列选择下一个最便宜的边展开，适合图更新较频繁的环境。Prim算法通过逐边选择不形成环的最小边，同样用于最短路径但初始图需要调整。两者时间复杂度均为O(E log E)，各有不同侧重。

拓扑排序的概念和实现

拓扑排序是任务调度的一种依赖性排序方式，任务可以按顺序排成队，保证先依赖、后支持。实现方法是构建逆向图，找出所有入度为零的任务作为入口，依次处理，用队列或栈辅助，并在处理完孩子时降低父节点的入度。适用于不成环有向图。

关键路径的概念

关键路径是最长路径，决定项目完成时间。它通过优先处理关键任务来改变节点的入度。当所有入度为一的节点后，最长路径即为关键路径。关键路径分析的作用是优化项目管理，使资源利用最大化。关键路径长度直接影响项目结束时间。

各种排序的概括与总结

排序算法主要有三类：基本排序（如冒泡、选择、插入）、快速排序、归并排序。此外还有希恩排序、归并树、OB Livni等。每种算法的效率根据不同情况而定，选择时间复杂度和空间复杂度均衡的实现。

各种查找方法

查找方法分为序遍历线表、二叉树、图等。如果是线性结构，可以按确定位置访问；非线性的，可以通过比较和跳转找到目标。二叉树查找需要树的高度较低，可用递归或迭代实现。

快速排序的优化

快速排序优化的关键是减少sorted枯椎选择的时间。将数组分成三个部分：左边较小的一部分，右边较大的一部分，还有中间项。优化方法包括选择枯椎的位置、记录最小值和最大值。优化后的快速排序可达到O(n log n)的预期时间。

B树和B+树的区别（以m阶数为例）

B树的阶数m决定了每个节点能存储数量的最小m张叶子和内部节点。B+树要求每个叶子节点都能形成完整的叶片，而内部节点的最小叶数约为m/2。B+树的内部节点不允许有叶子，是为了加速磁盘IO，时间复杂度为O(n log n)。

哈希表（概念、构造方法、冲突解决）

哈希表是一种数据结构，通过开放地址法实现快速查找，采用某种函数将键映射为存储位置，解决冲突的方法有线性探测和二次探测。链表结构的冲突解决效率一般较低，但插入和删除速度极快。

循环比递归效率更高吗？

在处理大数据量时，循环使用_visible保存栈空间，执行速度更快。但在处理递归问题时，递归深度较大可能带来性能开销。不过一般循环比递归在时间复杂度相同的情况下更有优势。

贪心算法和动态规划、分治法的区别

贪心算法每一步取局部最优，可能不会得到全局最优，简单且快速。动态规划在汇总子问题结果，根据问题分解，得到最优解。分治法通过递归地分割问题，解决子问题并合并结果。每种方法的核心是处理问题结构的不同特点。