数据结构-考研复试面试题-汇总大合集

数据结构-考研复试面试题-汇总大合集
写在前面的话：第二次写文章，本篇文章涉及内容主要包括数据结构与算法，包含市面上最热门的面试题，加以总结，用于本人的专业课面试复习，包括一些个人理解和总结，
如果能帮到你，欢迎点赞，如有写的不妥当的欢迎指出（WeChat：YEZHENGJIE）

参考主要书目：《数据结构》严蔚敏，以及辅导教材书 王道《数据结构》，天勤《数据结构高分笔记》

1、常见的数据结构

a、数组：顺序存储，随机访问 链表：链表存储，顺序访问
b、栈，分为栈顶和栈底，遵循先进后出原则
c、队列 ，一个线性表，像排队一样，受约束控制，遵循先进先出原则
d、树：二叉树、平衡二叉树、大顶堆，小顶堆等
e、图：最短路径，关键路径

2、数组和链表的区别，请详细解释。

从逻辑结构来看：

a) 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费；数组可以根据下标直接存取。

b) 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项，非常繁琐）链表必须根据next指针找到下一个元素

从内存存储来看：

a) (静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小

b) 链表从堆中分配空间, 自由度大但是申请管理比较麻烦

从上面的比较可以看出，如果需要快速访问数据，很少或不插入和删除元素，就应该用数组；相反， 如果需要经常插入和删除元素就需要用链表数据结构了。

3、排序算法有哪些？

排序算法有很多，每种算法有不同的时间和空间复杂度，效率也有差别，那么针对使用上也有不同的场合。

下面列一些常见的算法：插入排序，冒泡排序，选择排序，快速排序，堆排序，归并排序，基数排序，希尔排序等。

4、怎么理解哈希表,哈希表是什么

摘自百度：散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。

也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数

5、快速排序的改进

只对长度大于k的子序列递归调用快速排序,让原序列基本有序，然后再对整个基本有序序列用插入排序算法排序。实践证明，改进后的算法时间复杂度有所降低，且当k取值为 8 左右时,改进算法的性能最佳。

选择基准元的方式

对于分治算法，当每次划分时，算法若都能分成两个等长的子序列时，那么分治算法效率会达到最大。也就是说，基准的选择是很重要的。选择基准的方式决定了两个分割后两个子序列的长度，进而对整个算法的效率产生决定性影响。最理想的方法是，选择的基准恰好能把待排序序列分成两个等长的子序列。

方法1 固定基准元

如果输入序列是随机的，处理时间是可以接受的。如果数组已经有序时，此时的分割就是一个非常不好的分割。

方法2 随机基准元

这是一种相对安全的策略。由于基准元的位置是随机的，那么产生的分割也不会总是会出现劣质的分割。在整个数组数字全相等时，仍然是最坏情况，时间复杂度是O(n^2）

实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n）。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn）的期望时间复杂度。

方法3 三数取中

引入的原因：虽然随机选取基准时，减少出现不好分割的几率，但是还是最坏情况下还是O(n^2），要缓解这种情况，就引入了三数取中选取基准。

分析：最佳的划分是将待排序的序列分成等长的子序列，最佳的状态我们可以使用序列的中间的值，也就是第N/2个数。可是，这很难算出来，并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为基准元而得到。事实上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为基准元。

6、用循环比递归效率高吗？

递归和循环两者完全可以互换。不能完全决定性地说循环地效率比递归的效率高。

递归算法

优点：代码简洁、清晰，并且容易验证正确性。

缺点：它的运行需要较多次数的函数调用，如果调用层数比较深，需要增加额外的堆栈处理（还有可能出现堆栈溢出的情况），比如参数传递需要压栈等操作，会对执行效率有一定影响。
但是，对于某些问题，如果不使用递归，那将是极端难看的代码。在编译器优化后，对于多次调用的函数处理会有非常好的效率优化，效率未必低于循环。

循环算法

优点：速度快，结构简单。

缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环。

7、解决哈希冲突的方法

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。

1） 线性探测法

2） 平方探测法

3） 伪随机序列法

4） 拉链法

8、请简述KMP算法

在一个字符串中查找是否包含目标的匹配字符串。

其主要思想是每趟比较过程让子串先后滑动一个合适的位置。

当发生不匹配的情况时，不是右移一位，而是移动（当前匹配的长度– 当前匹配子串的部分匹配值）位。

9、B树和B+树的区别，以一个m阶树为例。

关键字的数量不同：B+树中分支结点有m个关键字，其叶子结点也有m个，其关键字只是起到了一个索引的作用，但是B树虽然也有m个子结点，但是其只拥有m-1个关键字。

存储的位置不同：B+树中的数据都存储在叶子结点上，也就是其所有叶子结点的数据组合起来就是完整的数据，但是B树的数据存储在每一个结点中，并不仅仅存储在叶子结点上。

分支结点的构造不同：B+树的分支结点仅仅存储着关键字信息和儿子的指针（这里的指针指的是磁盘块的偏移量），也就是说内部结点仅仅包含着索引信息。

查询不同:B树在找到具体的数值以后，则结束，而B+树则需要通过索引找到叶子结点中的数据才结束，也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径。