保研面试数据结构问题夏令营预推免

数据结构：

1. O(n)的大O是什么意思？什么是时间复杂度? ★★★
2. 线性存储结构和链式存储结构的优点★★★
3. 解释一下顺序存储与链式存储★★★
4. 头指针和头结点的区别？★★
5. 栈和队列的区别和内存结构★★★
6. 有一个循环队列Q，里面的编号是0到n-1，头尾指针分别是f，p，现在求Q中元素的个数？★★
7. 如何区分循环队列是队空还是队满？★★★
8. 堆、大顶堆、小顶堆实现及应用 ★★
9. 哈希表的概念、构造方法、哈希有几种类型？哈希冲突的解决办法？★★★★
10. 判断链表是否有环（非常重要！）★★★★★★★
11. 平衡二叉树、二叉排序树、完全二叉树、二叉搜索树的区别及如何构造★★★
12. 如何由遍历序列构造一颗二叉树？/已知先序序列和后序序列能否重现二叉树？（笔试经常考）★★★
13. B树是什么?在数据库中有什么应用？（B数和B+树的区别）★★★
14. 红黑树原理是什么？建立过程？★★★
15. 二分搜索和单纯的线性搜索的区别/时间复杂度★★★
16. 插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序（必考）、堆排序、基数排 序等排序算法的基本思想是什么？时间复杂度？是否稳定？给一个例子，问冒泡和快速排序在最坏的情况下比较几次？（排序必考）★★★★★★
17. 最小生成树和最短路径用什么算法来实现？（迪杰斯特拉、弗洛依德、普利姆、克鲁斯卡尔） 算法的基本思想是什么？算法的时间复杂度？如何进行优化？（必考）★★★★★★★
18. 邻接表和邻接矩阵（如何存储大数据）★
19. 介绍一下深度优先搜索和广度优先搜索是如何实现的？★★★
20. 介绍一下字符串匹配算法：朴素的匹配算法和KMP算法。（如何实现要会用语言描述）★★★