Question

数据结构面试题

Answer 1

1. 数据结构的定义。

2. 栈的两个应用：括号匹配和表达式的计算。是怎么应用的？表达式计算用的是哪种表达方式？有什么好处?

3. 字符串匹配算法：朴素的匹配算法、KMP算法。

4. 二叉树前序、中序、后序递归遍历算法。二叉树前序非递归遍历算法。

5. 堆，建堆算法，堆的插入和删除算法，堆排序。

6. 哈希。哈希函数的有哪些种？余数的取法？ 处理冲突的方法？ 闭散列方法有哪些？

7. 二叉搜索树的搜索、插入、删除。时间复杂度。

8. 二叉平衡树的插入结点的原理，有哪几种旋转方式？分别适用于哪种情况。分析二叉平衡树的时间复杂度。

9. 红黑树的定义，红黑树的性能分析和与二叉平衡树的比较。

10. 图有哪些储存表示。

11. 链表插入排序、链表归并排序。

12. 常见的有哪几种排序算法，试比较其时间复杂度，以及是否稳定，及各自使用的情形。

13. 常用分配排序有哪几种？ 基数排序的定义，分类及原理。

14. 外部排序的过程。

15. B树、B+树、Trie的概念及用途，添加删除结点的原理。