算法面试题：数据结构基础

1. 数组和链表的区别是什么？

• 数组随机访问速度快，插入删除开销大。
• 链表插入删除高效，但随机访问需要遍历。

2. 栈和队列的应用场景有哪些？

• 栈：函数调用、深度优先遍历、括号匹配。
• 队列：广度优先遍历、消息队列、任务调度。

3. 二叉树与二叉搜索树有什么不同？

• 二叉树每个节点最多两个子节点。
• 二叉搜索树左小右大，支持快速查找。

4. 什么是平衡树？

• 平衡树保持高度平衡，避免最坏情况退化。
• 常见类型：AVL 树、红黑树。

5. 图的表示方式有哪些？

• 邻接矩阵和邻接表。
• 邻接表适合稀疏图。
• 邻接矩阵适合稠密图。

6. 什么是哈希表？

• 哈希表通过哈希函数实现常数时间查找。
• 需要解决冲突，如链地址法、开放地址法。

7. 如何选择数据结构？

• 根据访问模式、插入删除频率、空间开销选择。
• 例如需要快速查找可选哈希表，需要有序遍历可选树结构。

8. 你如何解释复杂度分析？

• 时间复杂度描述算法运行时间增长情况。
• 空间复杂度描述算法使用的额外内存。
• 常见阶：O(1)、O(log n)、O(n)、O(n log n)、O(n^2)。