小测验：数据结构与算法

栈最适合LIFO访问模式。队列最适合FIFO（先进先出）访问模式。

O(1) 表示常数时间复杂度。这意味着无论输入规模如何，算法的运行时间始终相同。

要计算单向链表的长度，必须从头到尾遍历每个节点，因此时间复杂度为 O(n)。

在平衡二叉搜索树中，查找的平均时间复杂度为O(log n)，因为每一层都将搜索空间减半。

归并排序始终以 O(n log n) 的最坏情况复杂度运行，因为它反复将数组分成两半并合并排序后的子数组。

BFS 使用队列逐层探索节点，以广度优先的方式（按“行”）处理节点。

深度优先搜索（DFS）通常用于检测图中的环，它通过维护一个递归栈来跟踪已访问的节点。

堆排序在最坏情况下的时间复杂度为 O(n log n)，因为它需要构建一个堆并反复提取最大元素。

哈希表在访问元素时的平均时间复杂度为 O(1)，前提是有一个良好的哈希函数，能够最小化冲突。

栈的主要操作是压栈（添加元素）、出栈（移除元素）和查看栈顶（查看顶部元素而不移除）。

迪杰斯特拉算法常用于在具有非负边权重的图中寻找最短路径。它使用优先队列来高效地确定最短距离。

AVL树和红黑树是自平衡树的类型，它们确保每次插入或删除后树保持平衡。

在递归函数中，基例是必要的，当满足特定条件时停止递归调用，从而防止无限递归。

队列的两个基本操作是入队（在队尾添加元素）和出队（从队首移除元素）。

拓扑排序可以在有向无环图（DAG）上进行。这种排序在任务调度问题中非常有用。

朴素递归实现斐波那契数列的时间复杂度为 O(2^n)，因为每个斐波那契数都有大量重复计算。

优先队列最常使用堆来实现，因为它可以高效地提取最高或最低优先级的元素。

中序、前序和后序是二叉树的三种常见深度优先遍历顺序，每种顺序访问节点的次序不同。广度优先遍历也很常见，但它属于不同的遍历类别。

在最小堆中，根节点始终是最小的元素，树的高度为 O(log n)，这使得插入和提取操作高效。

冒泡排序是一种稳定的排序算法，因为它在排序过程中保持了相等元素的相对顺序。