内存连续与不连续的数据结构
哪些公司问过
答案要点
- 连续结构:元素地址相邻,首地址加偏移可 O(1) 随机访问,缓存友好
- 连续结构的代价:插入删除要移动元素,扩容需重新分配
- 不连续结构:节点分散,通过指针链接,访问 O(n),插入删除改指针,缓存不友好
- 连续:数组、vector、切片、字符串;不连续:链表、树、图;哈希表是桶数组加链表或树
- 二叉树可用数组实现,下标 i 的孩子为 2i+1、2i+2,适合完全二叉树
易错点
- 把哈希表说成完全不连续
- 忽略数组实现二叉树的可行性与空间浪费
- 不提缓存友好性
- 以为链表的插入一定比数组快,忽略查找的成本
面试官常见追问
- 数组能不能实现二叉树?
- 二叉树遍历用深度优先还是层次遍历?
- 为什么连续的内存对缓存友好?
- vector 和 list 怎么选?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。