常用数据结构的理解与选型
哪些公司问过
答案要点
- 数组:随机访问 O(1),插入删除 O(n);链表:已知前驱节点(或双向链表)时插入删除 O(1),访问 O(n)
- 栈(后进先出):函数调用、括号匹配;队列(先进先出):任务调度、BFS
- 哈希表:平均 O(1) 查找,冲突用链地址法或开放寻址,注意负载因子
- 树:BST 最坏 O(n),AVL、红黑树保证 O(log n);B+ 树用于数据库索引;堆用于取最值、优先队列
- 选型依据:访问模式(查找、插入删除、有序)、数据规模和内存,回答要说明理由
易错点
- 只罗列名称,不说复杂度和场景
- 选了一种结构却说不出选它的理由
- 把哈希表说成总是 O(1),忽略冲突和扩容
- 不知道数据库索引为什么用 B+ 树
面试官常见追问
- 数组和链表怎么选?
- 哈希表的适用场景是什么?
- 跳表是什么,有什么用?
- B 树和 B+ 树有什么区别?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。