标签题目
数据结构相关面试题第 2 页
红黑树的核心性质是什么？
红黑树的核心性质是什么？这道腾讯牛客题的关键是围绕“红黑树核心性质”讲清概念、机制、取舍和边界。红黑树是近似平衡二叉搜索树，核心性质包括：节点红或黑，根节点黑，所有 NIL 叶子黑，红节点不能有红孩子，从任一节点到所有后代 NIL 叶子的黑节点数相同。
如何用回溯法生成全排列？
如何用回溯法生成全排列？这道腾讯牛客题的关键是围绕“回溯生成全排列”讲清概念、机制、取舍和边界。用回溯生成全排列，维护当前路径 path 和 used 标记。每一层选择一个未使用元素加入路径，递归到长度为 n 时收集一个排列，然后撤销选择继续尝试。
如何判断单链表是否有环？
如何判断单链表是否有环？这道腾讯牛客题的关键是围绕“链表判环与快慢指针”讲清概念、机制、取舍和边界。判断链表是否有环，常用 Floyd 快慢指针。慢指针每次走一步，快指针每次走两步；如果链表有环，快指针最终会在环内追上慢指针；如果无环，快指针会先走到 null。
为什么数据库索引常用 B+ 树，B 树、B+ 树和二叉树有什么区别？
为什么数据库索引常用 B+ 树，B 树、B+ 树和二叉树有什么区别？这道腾讯牛客题的关键是围绕“数据库索引为什么常用 B+ 树”讲清概念、机制、取舍和边界。数据库索引常用 B+ 树，是因为它适合磁盘页和范围查询。B+ 树分叉多、树高低，非叶子节点只存 key 和子页指针，叶子节点顺序保存数据或主键并通过链表相连，能减少随机 I/O 并高效范围扫描。
二叉树有哪些基本性质和特点？
二叉树有哪些基本性质和特点？这道腾讯牛客题的关键是围绕“二叉树基本性质”讲清概念、机制、取舍和边界。二叉树每个节点最多有两个孩子，可分为普通二叉树、满二叉树、完全二叉树、平衡二叉树和二叉搜索树等。常见性质包括第 i 层最多 2^(i-1) 个节点，深度为 h 的二叉树最多 2^h-1 个节点。
平衡二叉树失衡后如何通过旋转恢复平衡？
平衡二叉树失衡后如何通过旋转恢复平衡？这道腾讯牛客题的关键是围绕“平衡二叉树旋转维护”讲清概念、机制、取舍和边界。平衡二叉树常以 AVL 为例，要求任一节点左右子树高度差不超过 1。插入或删除导致失衡后，根据 LL、RR、LR、RL 四种情况做单旋或双旋恢复平衡。
快速排序的过程、时间复杂度和常见优化方式是什么？
快速排序的过程、时间复杂度和常见优化方式是什么？这道腾讯牛客题的关键是围绕“快速排序流程与优化”讲清概念、机制、取舍和边界。快速排序的过程是选 pivot，执行 partition，把小于 pivot 的元素放左侧、大于 pivot 的元素放右侧，然后递归排序左右子区间。平均时间 O(n log n)，最坏 O(n^2)，递归栈平均 O(log n)。
什么是平衡二叉树，如何实现基本的平衡维护？
什么是平衡二叉树，如何实现基本的平衡维护？这道腾讯牛客题的关键是围绕“平衡二叉树旋转维护”讲清概念、机制、取舍和边界。平衡二叉树常以 AVL 为例，要求任一节点左右子树高度差不超过 1。插入或删除导致失衡后，根据 LL、RR、LR、RL 四种情况做单旋或双旋恢复平衡。
常见排序算法中哪些是稳定排序？
常见排序算法中哪些是稳定排序？这道腾讯牛客题的关键是围绕“排序稳定性”讲清概念、机制、取舍和边界。排序稳定性指相等 key 的元素在排序后仍保持原来的相对顺序。常见稳定排序包括冒泡排序、插入排序、归并排序、计数排序、基数排序和桶排序的稳定实现；常见不稳定排序包括快速排序、堆排序、选择排序和希尔排序。
树和堆这两种数据结构有什么区别？
树和堆这两种数据结构有什么区别？这道腾讯牛客题的关键是围绕“树与堆数据结构区别”讲清概念、机制、取舍和边界。树是一类层级数据结构，每个节点可以有子节点；堆通常是满足堆序性质的完全二叉树，是树的一种特殊形式。最大堆父节点不小于子节点，最小堆父节点不大于子节点。
已有一百万个关键词时，如何设计输入联想推荐，支持前缀匹配、热度排序、更新、内存控制和低延迟返回？
一百万关键词的输入联想可以用 Trie/压缩 Trie/FST 或有序数组前缀检索做候选召回，再用每个前缀的 TopK 热词缓存、实时热度增量、敏感过滤和多级缓存实现低延迟、可更新、可控内存的推荐服务。