Q1主动回忆难度 2
1/12
算法与数据结构 · 中级 02
记忆强度
算法与数据结构中级题库第 2 组，共 12 张卡片。
算法与数据结构 · 中级 02
给定单向链表，需要先判断从头节点出发是否会重复访问某个节点；
计数排序、桶排序和基数排序都不是单纯依靠元素两两比较来确定顺序，因此在满足特定输入条件时，时间复杂度可以低于比较排序的 O(n log n) 下界。
图由顶点和边组成，可以是有向或无向、带权或无权，也可能包含环、自环和多个互不连通的分量。
二分查找并不只是“取中点后排除一半”，其正确性取决于循环不变量：在每次循环开始时，尚未排除的区间仍然包含所有可能答案。
哈希摘要算法把任意长度输入映射为固定长度输出，通常希望具备确定性、输入微小变化导致输出显著变化、难以从摘要反推出原文，以及难以找到碰撞等性质。
递归是函数直接或间接调用自身，把原问题缩小为结构相同的子问题。
散列表先通过散列函数把键映射到桶下标，但键空间通常远大于桶数组，因此不同键映射到同一位置是必然现象，而不是实现错误。
数据流中位数问题要求元素逐个到达后，随时返回当前中位数，又不能在每次查询前重新排序。
回溯是一种系统枚举候选解的深度优先搜索方法。
选择排序算法不能只看平均时间复杂度。
二分查找不是“看到数组就折半”，而是利用搜索空间上的单调性：当某个位置满足条件后，其一侧全部满足，另一侧全部不满足。
二叉查找树要求任意节点左子树中的键都小于该节点，右子树中的键都大于该节点；