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