小测验：数据结构与算法
你能忽悠二叉树吗？
本测验将考察你对数据结构（栈、列表、树等）、算法以及时间复杂度的掌握程度。
20 道题……开始！
哪种数据结构最适合LIFO（后进先出）的访问模式？
栈最适合LIFO访问模式。队列最适合FIFO（先进先出）访问模式。
无论输入规模如何，运行时间始终相同的算法的时间复杂度是什么？
O(1) 表示常数时间复杂度。这意味着无论输入规模如何，算法的运行时间始终相同。
如果单链表没有保存长度字段，通过遍历计算其长度的时间复杂度是多少？
要计算单向链表的长度，必须从头到尾遍历每个节点，因此时间复杂度为 O(n)。
在平衡二叉搜索树中查找元素的平均时间复杂度是多少？
在平衡二叉搜索树中，查找的平均时间复杂度为O(log n)，因为每一层都将搜索空间减半。
归并排序始终以 O(n log n) 的最坏情况复杂度运行，因为它反复将数组分成两半并合并排序后的子数组。
广度优先搜索（BFS）通常使用什么数据结构来实现？
要按层处理节点，应该先处理刚加入的还是较早加入的节点？
BFS 使用队列逐层探索节点，以广度优先的方式（按“行”）处理节点。
哪种遍历会通过发现指向递归栈中尚未退出的顶点的边，检测有向图中的环？
区分已经访问过的顶点与当前递归路径上尚未退出的顶点。
深度优先搜索（DFS）通常用于检测图中的环，它通过维护一个递归栈来跟踪已访问的节点。
堆排序在最坏情况下的时间复杂度为 O(n log n)，因为它需要构建一个堆并反复提取最大元素。
在散列分布均匀且负载合适时，查找平均需要检查多少个桶？
哈希表在访问元素时的平均时间复杂度为 O(1)，前提是有一个良好的哈希函数，能够最小化冲突。
考虑添加元素、移除最新元素，以及只查看最新元素的操作。
栈的主要操作是压栈（添加元素）、出栈（移除元素）和查看栈顶（查看顶部元素而不移除）。
哪种贪心单源最短路径算法通常使用优先队列，每次选择尚未确定最短路径且暂定距离最小的顶点，并要求边权非负？
注意“贪心”“最小暂定距离”和“非负边权”这些条件。
迪杰斯特拉算法常用于在具有非负边权重的图中寻找最短路径。它使用优先队列来高效地确定最短距离。
AVL树和红黑树是自平衡树的类型，它们确保每次插入或删除后树保持平衡。
在递归函数中，基例是必要的，当满足特定条件时停止递归调用，从而防止无限递归。
队列的两个基本操作是入队（在队尾添加元素）和出队（从队首移除元素）。
如果存在有向环，还能把每个前置任务都排在依赖它的任务之前吗？
拓扑排序可以在有向无环图（DAG）上进行。这种排序在任务调度问题中非常有用。
画出递归调用树，看看相同的子问题被重复计算多少次。
朴素递归实现斐波那契数列的时间复杂度为 O(2^n)，因为每个斐波那契数都有大量重复计算。
哪种结构把当前最高或最低优先级的元素放在最容易取出的位置？
优先队列最常使用堆来实现，因为它可以高效地提取最高或最低优先级的元素。
中序、前序和后序是二叉树的三种常见深度优先遍历顺序，每种顺序访问节点的次序不同。广度优先遍历也很常见，但它属于不同的遍历类别。
考虑父节点与子节点的大小关系，以及完全二叉树的高度。
在最小堆中，根节点始终是最小的元素，树的高度为 O(log n)，这使得插入和提取操作高效。
如果标准冒泡排序仅在左侧键严格大于右侧键时交换相邻元素，它是否稳定？
在题目指定的严格比较条件下，键相等的元素不会彼此交换次序，因此冒泡排序是稳定的。如果实现也交换键相等的元素，就可能失去稳定性。
