计算机保研面试题-数据结构_保研面试常见问题基数排序

1. 快速排序算法，归并排序算法的复杂度（简单介绍各种排序）算法的特点

（1）插入排序：
 
a、直接插入排序：比如将X插入有序序列L当中，首先找到X在序列L当中的插入位置第K个（下标为0）。然后将
L【k~n-1】中的元素全部向后移动一个位置，最后将X插入到L【k】当中。复杂度：N^2 稳定 顺序存储和链式
存储
 
b、折半插入排序：首先，用二分法查找出元素X所在位置K，然后将L【k~n-1】全部向后移动一个位置。最后将
X插入到L【k】。复杂度：N^2 稳定
 
c、希尔排序：首先，将待排序序列按照相隔某个增量的规则分割成多个子序列，比如增量为2，分为13579，
246810。然后，对每个子序列进行直接插入排序。最后，增量依次减少，重复上述操作，直到增量为1.。复杂
度：最坏N^2
 
（2）交换排序
 
a、冒泡排序：首先，从后往前两两比较相邻的两个元素，如果为逆序，就交换两个元素，直到比较到第一个元
素，这次比较的结果时第一个元素为最小的元素。然后，重复上述步骤，不过第一个元素可以不参加比较，结果
第二个位置时第二小的元素。最后，重复上述步骤，直到序列全部排列好。复杂度：N^2 稳定
 
b、快速排序：再一个序列L当中，还有一个左指针i指向最左边的元素，一个右指针j指向最右边的元素，首
先，选取第一个元素为基准，从后面开始往前搜索，如果右指针所指元素大于等于基准元素，j指针向左移动一
个位置，如果小于基准元素，就将j指的元素和i指的元素交换一下。再从前往后开始搜索。然后，比较左指针i
所指元素，如果比基准元素小，i指针就向右移动一个位置。否则就将i，j所指元素交换，再从后往前搜索。重
复以上操作，直到将序列分为左右两部分，左边都比基准元素小，右边都比基准元素大。最后，按照同样的方法
对各个子序列页进行快速排序，直接每个子序列只有一个元素就是排列完成。复杂度：Nlog(N) 不稳定
 
（3）选择排序
 
a、简单选择排序：假设序列表为L【1~n】。第i躺排序就是从L【i~n】中选择最小的元素来与L【i】交换，每
一趟排序都可以确定一个元素的最终位置，经过i-1趟就可以使得序列变得有序。复杂度：N^2 不稳定
 
b、堆排序：这里选择大顶堆。首先，将无序序列构成一个大顶堆，然后，将堆顶元素与末位元素交换，将最大
的数放在序列最后。并且将此时的堆顶元素向下调整，使其满足大顶堆，最后，继续交换堆顶元素和末尾第i个
元素，比较n-1次就可 复杂度：Nlog(N) 不稳定
 
（4）归并排序和基数排序
 
a、基数排序：首先将所有数位统一，按照最低位优先原则，将所有数按照个位大小，从小到大排序，接着将所
有数按照十位大小从小到达排序，不过十位相同的数，个位小的在前面，高位不够的补0，然后再比较百位千位
等一直到最高位，最后，直到比较到最高位才算结束 复杂度：D(N+k) 稳定
 
b、归并排序：首先，假定待排序序列有n个元素，可以看成时n个含有一个元素的子表，然后两两归并，得到
【n/2】个长度为2或1的子表，再进行两两排序，重复上述操作，直到合成长度为n的有序表 复杂度：Nlog(N)
 稳定

2、为什么要稳定排序？

稳定排序可以让第一个关键字排序的结果服务于第二个关键字排序中数值相等的那些数。
 
比如成绩一样的按上次成绩靠前的排在前面

3、 堆实现及应用

4、Dijkstra

Dijkstra算法属于最短路算法，目的是求从一个顶点到另一个顶点的最短路径。
 
1 所有点分为两个集合S 和T ，S 集合最开始只包括源点p，剩余点都位于集合T 。S 集合表示已经计算出最
短路径的点集合，T 集合表示尚未计算出最短路径的点集合。
 
2 每次从集合T 中选出一个与集合S 距离最短的点v ，将点v 加入集合S。通过点v 对集合T 中的点进行松
弛，即更新T 中点的最短距离。
 
3 不断重复此步骤2，直至T集合中无法找出与集合S相邻的点。
 
时间复杂度：
 
基于集合的写法（适用于稠密图）O（N^2），在T集合中要删除V个点，又要遍历集合找出与集合S距离最短的点
基于优先队列写法（适用于稀疏图）O（Elog（N）），集合T要删除V个点，要遍历该点的N个邻居进行松弛操作，更新邻居log（V）
 
 
注意：带负权边时不可用
 
最短路算法还有Floyd算法 （适合多源最短路径）
 
思想
 
a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 　　
 
b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
 
时间复杂度为N^3
 
注意：可用于带负权值的边，但是不允许包含带负权值边组成的回路。
 
应用：
 
从一个城镇到另一个城镇有许多道路可以选择，但是用dijkstra算法可以找出路程最短的那条路
 
网络层协议中开放最短路径优先协议OSPF，计算最短路由用的是该算法。

5、最小生成树等

包含算法游prim算法，kruskal算法
 
目的：生成树中边的权值之和最小的生成树
 
Prim算法：
 
首先，从图中任意取出一个顶点加入集合T中
 
然后，选择一个与当前集合T中顶点权值最小的顶点，并将该顶点加入T集合。比如说，集合T当中有点a、b，和
点a和b相连的边只有ac和bd，ac的权值为1，bd的取值为6，那么就将点c加入到集合T当中。
 
最后，重复上述操作，直到图中所有顶点加入集合T
 
时间复杂度：N^2 用优先队列是 Elog（n）
 
注意：适用于稠密图
 
Kruskal算法：
 
首先，将每个顶点自成一个连通分量
 
然后，按照所有边按照权值的从小到大排列，选取没有被选过并且权值最小的边
 
如果这条边依附的两个点在两个不同的连通分量上，那么就将这条边加入集合T，这条边上的两个点就属于一个
连通分量了，否则就选择下一条边
 
最后，重复上述操作，直到所有的点都在同一个连通分量上
 
时间复杂度：Elog(E)
 
注意：适用于边稀疏而点多的图
 
应用：
 
用最少的资金给小区所有用户安装上煤气管道

6、邻接表和邻接矩阵（如何存储大数据）

邻接矩阵是表示图中顶点直接邻接关系的方阵，如果有n个顶点，那就是一个N*N的方阵。普通图中矩阵A【ij】的
值为1表示点i和点j相连，为0表示不相连，带权图中矩阵的A【ij】的值表示i到j的权值，如果aij等于0或者∞，
可能表示两点不相连
 
邻接表：为图中的每个顶点都关联一个链表，链表中记录这个顶点的所有邻边。
 
在无向图中一条边被记录两次，有向图中记录依次
 
注意：稠密图用邻接矩阵，稀疏图用邻接表

7、哪些图算法用到了动态规划思想

Floyd算法是DP思想

8、判断链表是否有环

快慢指针法， 快指针一次走两步， 慢指针一次走一步。如果环的入口在X XX处,当前慢指针走到入口处，那么快
指针一定在环当中。假设他们的距离为K KK那么再走K KK步，慢指针就追上快指针了。
 
判断环的位置在哪里（这里没写清楚）
 
首先，假设链表有环，然后还是使用快指针和慢指针，快指针一次走两步，慢指针一次走一步。假设他们在C CC点
相遇，C CC 点距离 b bb 的距离为 y yy 。这时候让慢指针退 y yy 步，那么由于快指针是慢指针速度的两
倍，那么快指针会退到 C ′ C^{'}C 这个位置。起点a aa 和 b bb 之间的距离为 x xx。
也就是说，从起点走 x xx 步，慢指针走到了 b bb 点，快指针走到了 C ′ C^{'}C 点，快指针走的距离为 2 
x 2x2x 的距离。不管快指针转了几圈，从入口开始转，转 x xx 的距离，就会转到 C ′ C^{'}C 点。 那么从
 C CC 点出发，不管转几圈，走 x xx 的距离就会走到入口 b bb 点。所以，从快慢指针相遇点开始，一个指针
从起点出发，另一个指针从 C CC 点出发，两个指针一起走 他们相遇的点就是入口，恰好走了 x xx 步。

9、平衡二叉树和二叉排序树

二叉排序树
 
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
 
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
 
（3）左、右子树也分别为二叉排序树；
 
平衡二叉树AVL
 
特殊的二叉排序树
 
它或者为空树，或者其左右子树都是平衡二叉排序树，而且其左右的子数高度之差绝对值不超过1

10、哈希表的冲突解决方式（散列表）

散列表：建立关键字与存储地址之间的映射关系
 
散列函数：把查找表中的关键字映射成该关键字对应的地址的函数
 
冲突：散列函数可能会把两个或者两个以上的关键字映射在同一地址
 
处理冲突的方法：
 
开放定址法：线性探测法、平方探测法、
 
再哈希法：再散列法
 
链地址法
 
开放定址法：（再寻一块空间）
 
线性探测法：若两个关键字对应同一个地址，就为其中一个关键字再找一个地址，顺序查看表中下一个单元（如
果找到末尾还没找到空闲单元就从最前面开始找）直到找出一个空闲单元（会存在堆积现象）
 
平分探测发：若两个关键字对应同一个地址，就为其中一个关键字再找一个地址，再当前位置的基础上，每次移
动步长是上一次移动的步长的平方倍，向后查找，找到末端就从最前端往后查找（避免出现堆积现象）
 
再散列法：用第一个散列函数产生冲突时，再用第二个散列函数计算关键字的位置。
 
拉链法（连接法）：
 
在散列表中，每一个关键字映射的地址都会带一个链表。在查找时先通过散列函数找到存储地址，再遍历存储地
址后面的链表来找到真正的地址

11、堆排序的复杂度

建堆时间为O(n)，有n-1次向下调整的操作，每次调整的时间复杂度为O(h)，堆排序在最好、最坏、平均情况下的
时间复杂度都是O(nlogn)

12、排序算法（分为内排序和外排序）都是在内存中吗？

排序算法分为两类，内部排序和外部排序；
 
内部排序是：指再排序期间全都存放再内存中的排序；包含：选择排序，插入排序，交换排序，归并排序，基数排
序。
 
外部排序是：指再排序期间，元素无法同时存在内存，排序过程中不断再内存和外存之间移动。主要是多路归并排
序

13、霍夫曼树（哈夫曼树）的时间复杂度，哈夫曼树的定义，怎么求，应用

14、二叉树遍历时间复杂度

非递归遍历、递归遍历时间复杂度为O(n)，空间复杂度O(n)
 
Morris遍历，时间复杂度为O(n)，空间复杂度O(1)
 
由于不管是先序遍历还是中序遍历以及后序遍历，我们都需要利用一个辅助栈来进行每个节点的存储打印，所以每
个节点都要进栈和出栈，不过是根据那种遍历方式改变的是每个节点的进栈顺序，所以时间复杂度为O(n)，同样空
间复杂度也为O(n)，n为结点数。
 
二叉排序树
 
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
 
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
 
（3）左、右子树也分别为二叉排序树；

15、排序算法的稳定性:冒泡、插入、归并、基数是稳定的

稳定的排序算法有：插入排序，冒泡排序，归并排序，基数排序
 
不稳定的排序算法有：希尔排序，快速排序，选择排序，堆排序，

16、图和树的含义和区别

树：是n个结点的有限集合，当n=0时是一棵空树
 
当不是空树的时候应该满足：有且只有一个根
 
当n>1，其余结点可以分为m个有限集合，这每个集合也可以当作是一棵树，是根的子树
 
图：是由个数大于0且有限个数的顶点和顶点和顶点之间的边组成
 
区别：
 
（1）树是图，但是图不一定是树；
 
（2）树一定要有一个根节点，但是图没有
 
（3）树是无环图，但是图可以有循环也可没有循环
 
（4）树是分层模型结构，图是网络结构
 
（5）如果树有n个顶点，那么一定要有n-1条边；再图中边的数量不取决于顶点的数量

17、A*算法

18、如何判断一个单链表是否是循环链表

（要给出一个比遍历更快的方法，貌似是两个指针一个每次前进1步、一个每次前进2步，相遇则循环）

19、介绍下平衡二叉树，B树，B+树

B树：
 
是一种平衡的多分树，普遍m阶的B树，它必须满足如下条件：
 
（1）B树有根结点，内部结点，和叶子结点
 
（2）根节点（非叶子结点）的子节点数量2<=n<=m
 
（3）内部结点的子节点数量⌈ m/2⌉<=n<=m
 
（4）所有结点中元素的数量都要比子节点的数量少1
 
（5）所有叶子结点都出现在统一水平，没有任何信息（高度一致）
 
（6）具有k个子节点的非叶节点包含k -1个键。？？
 
B+树的特征：
 
（1）有m个子树的中间节点包含有m个元素（B树中是m-1个元素），每个元素不保存数据，只用来索引；
 
（2）所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键
字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)；
 
（3）所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树
的非终节点也包含需要查找的有效信息)；
 
为什么说B+树比B树更适合数据库索引？
 
1）B+树的磁盘读写代价更低
 
B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点
的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也
就越多。相对来说IO读写次数也就降低了；
 
2）B+树查询效率更加稳定
 
　　由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必
须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当；
 
3）B+树便于范围查询（最重要的原因，范围查找是数据库的常态）
 
B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题，正是为了解决这个问题，B+树应用而生。
B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不
支持这样的操作或者说效率太低；不懂可以看看这篇解读-》范围查找
 
补充：B树的范围查找用的是中序遍历，而B+树用的是在链表上遍历；
 
B树和二叉查找树的性能对比？
 
B树包括B+树的设计思想都是尽可能的降低树的高度，以此降低磁盘IO的次数，因为一个索引节点就表示一个磁
盘页，页的换入换出次数越多，表示磁盘IO次数越多，越低效。
 
B树算法减少定位数据所在的节点时所经历的磁盘IO次数，从而加快存取速度。
 
假设一个节点可以容纳100个值，那么3层的B树可以容纳100万个数据。（根节点100值，第二层可以存储99个
节点（k-1），也就是99*100 个值，第三层可以存储
 
（99*100-1）*100）结果是近似100万个数据。而如果使用二叉查找树，则需要将近20层，也就是进行20次磁
盘IO，性能差距如此之大。
 
如mongoDB数据库使用，单次查询平均快于Mysql（但侧面来看Mysql至少平均查询耗时差不多）。
 
为什么数据库索引不用红黑树而用B+树？
 
红黑树当插入删除元素的时候会进行频繁的变色与旋转（左旋，右旋），来保证红黑树的性质，浪费时间。
 
但是当数据量较小，数据完全可以放入内存中，不需要进行磁盘IO，这时候，红黑树时间复杂度比B+树低。
 
比如TreeSet TreeMap 和HashMap （jdk1.8）就是使用红黑树作为底层数据结构。
 
题目1： Mysql数据库用过吧？l里面的索引是基于什么数据结构。
 
答：主要是基于Hash表和B+树
 
题目2： 很好请你说一下B+树的实现细节是什么样的？B-树和B+树有什么区别？联合索引在B+树中如何存储？
 
答: 首先，数据库使用树型结构来增加查询效率，并保持有序。那么，为什么不使用二叉树来实现数据结构呢，二叉树算法时间复杂度是lg(N)，查询速度和比较次数都是较小的。
 
所以，B+树对比B-树有如下好处：
 
（1）io次数少：B+树中间节点只存索引，不存在实际的数据，所以可以存储更多的数据。索引树更加的矮胖，io次数更少。
 
（2）性能稳定：B+树数据只存在于叶子节点，查询性能稳定
 
（3）范围查询简单：b+树不需要中序遍历，遍历链表即可。

20、分治思想和动态规划思想中的联系与区别

分治和动态规划：
 
共同点：两者都是把大问题转换成小问题/子问题来解决，并且当最优子问题组合成最优大问题，关键点在于找到
子问题的划分。
 
不同点：分治算法，采用递归写法，当子问题之间没有重复的时候，是很好的方法，但当子问题之间存在重复的时
候，分治方***重复计算子问题很多次，碰到一次算一次，因为分治是自上而下的，往下走的过程中，每次碰到相
同的子问题都要重复计算，时间复杂度很高。动态规划，专门针对这种存在重复子问题的分解算法，并且每一个大
问题都可以由它的子问题的最优解来表示；因此，动态规划采用自下而上的方法，先计算最小的子问题的最优解，
再一层层组合成大问题的最优解，计算过程中不存在子问题的重复计算。

21、红黑树的概念与性质介绍

​
概念：红黑树(Red-Black Tree，简称R-B Tree)是一棵特殊的二叉查找树（二叉搜索树），即所有左孩子都小于
根节点，右孩子都大于根节点的树。其次，红黑树是一棵基本平衡的树。最大深度小于等于最小深度的2倍。
 
 红黑树的特性: 红黑树是特殊的AVL树，遵循红定理和黑定理 红定理：不能有两个相连的红节点 。黑定理：根
节点必须是黑节点，而且所有节点通向NULL的路径上，所经过的黑节点的个数必须相等。
 
　　基本操作是添加、删除和旋转。在对红黑树进行添加或删除后，会用到旋转方法。旋转的目的是让树保持红黑
树的特性。旋转包括两种：左旋 和 右旋。
 
　　红黑树的应用比较广泛，主要是用它来存储有序的数据，它的查找、插入和删除操作的时间复杂度是O(lgn)。
 
顺口溜：根节点必黑，新增是红色，只能黑连黑，不能红连红； 爸叔通红就变色，爸红叔黑就旋转，哪边黑往哪
边转。
 
​

22、红黑树的应用

1、java8 hashmap中链表转红黑树。
 
优势：时间复杂度从O(n)-->O(logn) ，且自旋开销较其他树较低（不用整体平衡）。
 
2、epoll在内核中的实现，用红黑树管理事件块（文件描述符）。
 
优势：
 
（1）因为内核态需要维护一个长久存放fd的数据结构，而fd变动十分频繁，且需要支持快速查询，且所以红黑
树很适合。
 
（2）红黑树可以判断是否是重复的fd
 
3、Java的TreeMap实现
 
相对与hashMap优势，内部key保持有序，且支持自定义排序比较器。
 
适用场景，对数据需要排序统计
 
4、linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块
 
CFS 背后的主要想法是维护为任务提供处理器时间方面的平衡（公平性）。这意味着应给进程分配相当数量的
处理器
 
 
 
任务存储在以时间为顺序的红黑树中（由 sched_entity 对象表示），对处理器需求最多的任务 （最低虚拟
执行时vruntime）存储在树的左側，处理器需求最少的任务（最高虚拟执行时）存储在树的右側。 为了公平。
调度器然后选取红黑树最左端的节点调度为下一个以便保持公平性。
 
任务通过将其执行时间加入到虚拟执行时， 说明其占用 CPU 的时间，然后假设可执行。再插回到树中。这
样，树左側的任务就被给予时间执行了，树的内容从右側迁移到左側以保持公平。
 
因此，每一个可执行的任务都会追赶其它任务以维持整个可执行任务集合的执行平衡。
 
CFS 不直接使用优先级而是将其用作同意任务运行的时间的衰减系数。低优先级任务具有更高的衰减系数。而
高优先级任务具有较低的衰减系数。
 
这意味着与高优先级任务相比，低优先级任务同意任务运行的时间消耗得更快。 这是一个绝妙的解决方式，能
够避免维护按优先级调度的运行队列。
 
 
 
优势：优先级保证下没有O(1)出色，但之所以没有用队列是为了保证其公平性

是一个模式匹配算法，查找子串是否在主串当中。
 
当发现字符串不匹配的时候，并不会从头开始比较，通过计算子串（模式串）自身来获得一个next数组，然后在匹
配过程中通过next数组来决定下一个匹配位置，并从这个位置直接开始比较，它的时间复杂度降到了O(m+n)，也
就是2个字符串的长度之和。

拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性
序列。且该序列必须满足下面两个条件：
 
 
 
每个顶点出现且只出现一次。
 
若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
 
应用：工厂里产品的生产线上,一个产品由若干个零部件组成。有些零部件生产时,也存在这这关系:先后关系,即一
个部件必须在完成后才能生产另一个部件;部件间无先后关系,即这两个部件可以同时生产。

从源点到汇点的所有路径中，具有最大路径长度的路径
 
,因为图中每个活动都是必须的，只有最长的工期完成后，项目才真正完成了

1 查找：数据库中需要按照区间来查找数据，散列表，平衡二叉树都不满足条件，所以要用B+树。
 
2 查找效率：如果我们要求区间的数据。我们只需要拿区间的起始值，在树中查找，当查找到某个叶子节点之后，
我们再顺着链表往后遍历，直到链表中的结点数据值大于区间的终止值为止。所有遍历到的数据，就是符合区间值
的所有数据。
 
数据过多构成查找树索引，会消耗大量内存，所以将索引存在硬盘中，但是相应的查找时间页下降了，就把索引构
建成 m 叉树，树的高度就会降低。磁盘IO变少了，查找数据的效率也就提高了。
 
3 删除效率：频繁的数据删除，就会导致某些节点中，子节点的个数变得非常少，势必会影响索引的效率。在 B+
 树中，如果某个节点的子节点个数小于 m/2 ，我们就将它跟相邻的兄弟节点合并。提高效率

哈夫曼树：在含有n个带权叶节点的二叉树中，其中带权路径长度最小的二叉树是哈夫曼树
 
哈夫曼树的构建：
 
1 将n个结点分别作为n棵只含有一个结点的二叉树，构成森林F
 
2 在森林中选出两棵根节点的权值最小的树作为新结点的左，右子树，且新结点的权值是左右子树根节点权值之
和。注意，左子树的权值应小于右子树的权值。
 
4 从森林中删除这两棵树，同时把新树加入到森林中。
 
5 重复2，3步骤，直到森林中只有一棵树为止，此树便是哈夫曼树。
 
哈夫曼编码：
 
树中从根到每个叶子节点都有一条路径，对路径上的各分支约定指向左子树的分支表示”0”码，指向右子树的分支
表示“1”码，取每条路径上的“0”或“1”的序列作为各个叶子节点对应的字符编码，即是哈夫曼编码。