数据结构常见⾯试题，⼀⽹打尽！
（1） 红⿊树的了解（平衡树，⼆叉搜索树），使⽤场景
把数据结构上⼏种树集中的讨论⼀下：
1.AVLtree
定义：最先发明的⾃平衡⼆叉查树。在AVL树中任何节点的两个⼦树的⾼度最⼤差别为⼀，所以它也被称为⾼度平衡树。查、插⼊和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过⼀次或多次树旋转来重新平衡这个树。
节点的平衡因⼦是它的左⼦树的⾼度减去它的右⼦树的⾼度（有时相反）。带有平衡因⼦1、0或 -1的节点被认为是平衡的。带有平衡因⼦-2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因⼦可以直接存储在每个节点中，或从可能存储在节点中的⼦树⾼度计算出来。
⼀般我们所看见的都是排序平衡⼆叉树。
AVLtree使⽤场景：AVL树适合⽤于插⼊删除次数⽐较少，但查多的情况。插⼊删除导致很多的旋转，旋转是⾮常耗时的。AVL 在linux 内核的vm area中使⽤。
2.⼆叉搜索树
⼆叉搜索树也是⼀种树，适⽤与⼀般⼆叉树的全部操作，但⼆叉搜索树能够实现数据的快速查。
⼆叉搜索树满⾜的条件：
1.⾮空左⼦树的所有键值⼩于其根节点的键值
2.⾮空右⼦树的所有键值⼤于其根节点的键值
3.左右⼦树都是⼆叉搜索树
⼆叉搜索树的应⽤场景：如果是没有退化称为链表的⼆叉树，查效率就是lgn，效率不错，但是⼀旦退换称为链表了，要么使⽤平衡⼆叉树，或者之后的RB树，因为链表就是线性的查效率。二叉树的基本性质
3.红⿊树的定义
红⿊树是⼀种⼆叉查树，但在每个结点上增加了⼀个存储位表⽰结点的颜⾊，可以是RED或者BLACK。通过对任何⼀条从根到叶⼦的路径上各个着⾊⽅式的限制，红⿊树确保没有⼀条路径会⽐其他路径长出两倍，因⽽是接近平衡的。
当⼆叉查树的⾼度较低时，这些操作执⾏的⽐较快，但是当树的⾼度较⾼时，这些操作的性能可能不⽐⽤链表好。红⿊树（red-black tree）是⼀种平衡的⼆叉查树，它能保证在最坏情况下，基本的动态操作集合运⾏时间为O(lgn)。
红⿊树必须要满⾜的五条性质：
性质⼀：节点是红⾊或者是⿊⾊； 在树⾥⾯的节点不是红⾊的就是⿊⾊的，没有其他颜⾊，要不怎么叫红⿊树呢，是吧。
性质⼆：根节点是⿊⾊； 根节点总是⿊⾊的。它不能为红。
性质三：每个叶节点（NIL或空节点）是⿊⾊；
性质四：每个红⾊节点的两个⼦节点都是⿊⾊的（也就是说不存在两个连续的红⾊节点）； 就是连续的两个节点不能是连续的红⾊，连续的两个节点的意思就是⽗节点与⼦节点不能是连续的红⾊。
性质五：从任⼀节点到其每个叶节点的所有路径都包含相同数⽬的⿊⾊节点。从根节点到每⼀个NIL节点的路径中，都包含了相同数量的⿊⾊节点。
红⿊树的应⽤场景：红⿊树是⼀种不是⾮常严格的平衡⼆叉树，没有AVLtree那么严格的平衡要求，所以它的平均查，增添删除效率都还不错。⼴泛⽤在C++的STL中。如map和set都是⽤红⿊树实现的。
4.B树定义
B树和平衡⼆叉树稍有不同的是B树属于多叉树⼜名平衡多路查树（查路径不只两个），不属于⼆叉搜索树的范畴，因为它不⽌两路，存在多路。
B树满⾜的条件：
（1）树种的每个节点最多拥有m个⼦节点且m>=2，空树除外（注：m阶代表⼀个树节点最多有多少个查路径，m阶=m路，当m=2则是2叉树,m=3则是3叉）；
（2）除根节点外每个节点的关键字数量⼤于等于ceil(m/2)-1个⼩于等于m-1个，⾮根节点关键字数必须>=2;（注：ceil()是个朝正⽆穷⽅向取整的函数 如ceil(1.1)结果为2)
（3）所有叶⼦节点均在同⼀层、叶⼦节点除了包含了关键字和关键字记录的指针外也有指向其⼦节点的指针只不过其指针地址都为null对应下图最后⼀层节点的空格⼦
（4）如果⼀个⾮叶节点有N个⼦节点，则该节点的关键字数等于N-1;
（5）所有节点关键字是按递增次序排列，并遵循左⼩右⼤原则；
B树的应⽤场景：构造⼀个多阶的B类树，然后在尽量多的在结点上存储相关的信息，保证层数尽量的少，以便后⾯我们可以更快的到信息，磁盘的I/O操作也少⼀些，⽽且B类树是平衡树，每个结点到叶⼦结点的⾼度都是相同，这也保证了每个查询是稳定的。
5.B+树
B+树是B树的⼀个升级版，B+树是B树的变种树，有n棵⼦树的节点中含有n个关键字，每个关键字不保存数据，只⽤来索引，数据都保存在叶⼦节点。是为⽂件系统⽽⽣的。
相对于B树来说B+树更充分的利⽤了节点的空间，让查询速度更加稳定，其速度完全接近于⼆分法查。为什么说B+树查的效率要⽐B树更⾼、更稳定；我们先看看两者的区别
（1）B+跟B树不同，B+树的⾮叶⼦节点不保存关键字记录的指针，这样使得B+树每个节点所能保存的关键字⼤⼤增加；
（2）B+树叶⼦节点保存了⽗节点的所有关键字和关键字记录的指针，每个叶⼦节点的关键字从⼩到⼤链接；
（3）B+树的根节点关键字数量和其⼦节点个数相等;
（4）B+的⾮叶⼦节点只进⾏数据索引，不会存实际的关键字记录的指针，所有数据地址必须要到叶⼦节点才能获取到，所以每次数据查询的次数都⼀样；
特点：
在B树的基础上每个节点存储的关键字数更多，树的层级更少所以查询数据更快，所有指关键字指针都存在叶⼦节点，所以每次查的次数都相同所以查询速度更稳定;
应⽤场景： ⽤在磁盘⽂件组织 数据索引和数据库索引。
6.Trie树（字典树）
trie，⼜称前缀树，是⼀种有序树，⽤于保存关联数组，其中的键通常是字符串。与⼆叉查树不同，键不是直接保存在节点中，⽽是由节点在树中的位置决定。⼀个节点的所有⼦孙都有相同的前缀，也就是这个节点对应的字符串，⽽根节点对应空字符串。⼀般情况下，不是所有的节点都有对应的值，只有叶⼦节点和部分内部节点所对应的键才有相关的值。
在图⽰中，键标注在节点中，值标注在节点之下。每⼀个完整的英⽂单词对应⼀个特定的整数。Trie 可以看作是⼀个确定有限状态⾃动机，尽管边上的符号⼀般是隐含在分⽀的顺序中的。
键不需要被显式地保存在节点中。图⽰中标注出完整的单词，只是为了演⽰ trie 的原理。
trie树的优点：利⽤字符串的公共前缀来节约存储空间，最⼤限度地减少⽆谓的字符串⽐较，查询效率⽐哈希表⾼。缺点：Trie树是⼀种⽐较简单的数据结构.理解起来⽐较简单，正所谓简单的东西也得付出代价.故Trie树也有它的缺点,Trie树的内存消耗⾮常⼤.
其基本性质可以归纳为：
根节点不包含字符，除根节点外每⼀个节点都只包含⼀个字符。
从根节点到某⼀节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有⼦节点包含的字符都不相同。
典型应⽤是⽤于统计，排序和保存⼤量的字符串（但不仅限于字符串），所以经常被搜索引擎系统⽤于⽂本词频统计。字典树与字典很相似，当你要查⼀个单词是不是在字典树中,⾸先看单词的第⼀个字母是不是在字典的第⼀层，如果不在，说明字典树⾥没有该单词，如果在就在该字母的孩⼦节点⾥是不是有单词的第⼆个字母，没有说明没有该单词，有的话⽤同样的⽅法继续查.字典树不仅可以⽤来储存字母，也可以储存数字等其它数据。
（2） 红⿊树在STL上的应⽤
STL中set、multiset、map、multimap底层是红⿊树实现的，⽽unordered_map、unordered_set 底层是哈希表实现的。
multiset、multimap： 插⼊相同的key的时候，我们将后插⼊的key放在相等的key的右边，之后不管怎么进⾏插⼊或删除操作，后加⼊的key始终被认为⽐之前的⼤。
（3） 了解并查集吗？（低频）
什么是合并查问题呢？
顾名思义，就是既有合并⼜有查操作的问题。举个例⼦，有⼀⼈，他们之间有若⼲好友关系。如果两个⼈有直接或者间接好友关系，那么我们就说他们在同⼀个朋友圈中，这⾥解释下，如果Alice是Bob好友的好友，或者好友的好友的好友等等，即通过若⼲好友可以认识，那么我们说Alice和Bob是间接好友。随着时间的变化，这⼈中有可能会有新的朋友关系，这时候我们会对当中某些⼈是否在同⼀朋友圈进⾏询问。这就是⼀个典型的合并－查操作问题，既包含了合并操作，⼜包含了查操作。
并查集，在⼀些有N个元素的集合应⽤问题中，我们通常是在开始时让每个元素构成⼀个单元素的集合，然后按⼀定顺序将属于同⼀组的元素所在的集合合并，其间要反复查⼀个元素在哪个集合中。
并查集是⼀种树型的数据结构，⽤于处理⼀些不相交集合（Disjoint Sets）的合并及查询问题。
并查集也是使⽤树形结构实现。不过，不是⼆叉树。每个元素对应⼀个节点，每个组对应⼀棵树。在并查集中，哪个节点是哪个节点的⽗亲以及树的形状等信息⽆需多加关注，整体组成⼀个树形结构才是重要的。类似森林
（4） 贪⼼算法和动态规划的区别
贪⼼算法：局部最优，划分的每个⼦问题都最优，得到全局最优，但是不能保证是全局最优解，所以对于贪⼼算法来说，解是从上到下的，⼀步⼀步最优，直到最后。
动态规划：将问题分解成重复的⼦问题，每次都寻左右⼦问题解中最优的解，⼀步步得到全局的最优解.重复的⼦问题可以通过记录的⽅式，避免多次计算。所以对于动态规划来说，解是从⼩到上，从底层所有可能性中到最优解，再⼀步步向上。
分治法：和动态规划类似，将⼤问题分解成⼩问题，但是这些⼩问题是独⽴的，没有重复的问题。独⽴问题取得解，再合并成⼤问题的解。
例⼦：⽐如钱币分为1元3元4元，要拿6元钱，贪⼼的话，先拿4，再拿两个1，⼀共3张钱；实际最优却是两张3元就够了。
（5） 判断⼀个链表是否有环，如何到这个环的起点
给定⼀个单链表，只给出头指针h：
1、如何判断是否存在环？
2、如何知道环的长度？
3、如何出环的连接点在哪⾥？
4、带环链表的长度是多少？
（6） 实现⼀个strcpy函数（或者memcpy），如果内存可能重叠呢
——⼤家⼀般认为名不见经传strcpy函数实现不是很难，流⾏的strcpy函数写法是：
1. char *my_strcpy(char *dst,const char *src)
2. {
3.    assert(dst != NULL);
4.    assert(src != NULL);
5.    char *ret = dst;
6.    while((* dst++ = * src++) != '\0')
7.        ;
8.    return ret;
9. }
1
2
3
4
5
6
7
8
9
如果注意到：
1，检查指针有效性；
2，返回⽬的指针des；
3，源字符串的末尾 ‘\0’ 需要拷贝。
内存重叠
内存重叠：拷贝的⽬的地址在源地址范围内。所谓内存重叠就是拷贝的⽬的地址和源地址有重叠。
在函数strcpy和函数memcpy都没有对内存重叠做处理的，使⽤这两个函数的时候只有程序员⾃⼰保证源地址和⽬标地址不重叠，或者使⽤memmove函数进⾏内存拷贝。
memmove函数对内存重叠做了处理。
strcpy的正确实现应为：
1. char *my_strcpy(char *dst,const char *src)
2. {
3.    assert(dst != NULL);
4.    assert(src != NULL);
5.    char *ret = dst;
6.    memmove(dst,src,strlen(src)+1);
7.    return ret;
8. }
1
2
3
4
5
6
7
8
memmove函数实现时考虑到了内存重叠的情况，可以完成指定⼤⼩的内存拷贝
（7） 快排存在的问题，如何优化
快排的时间复杂度
时间复杂度最快平均是O（nlogn），最慢的时候是O(n2)；辅助空间也是O(logn)；最开始学快排时最疑惑的就是这个东西不知道怎么得来的，⼀种是通过数学运算可以的出来，还有⼀种是通过递归树来理解就容易多了
这张图⽚别⼈博客那⾥弄过来的，所谓时间复杂度最理想的就是取到中位数情况，那么递归树就是⼀个完全⼆叉树，那么树的深度也就是最低为Logn，这个时候每⼀次⼜需要n次⽐较，所以时间复杂度nlogn，当快排为顺序或者逆序时，这个数为⼀个斜⼆叉树，深度为n，同样每次需要n次⽐较，那那么最坏需要n2的时间
优化：
1.当整个序列有序时退出算法；
2.当序列长度很⼩时（根据经验是⼤概⼩于 8），应该使⽤常数更⼩的算法，⽐如插⼊排序等；
3.随机选取分割位置；
4.当分割位置不理想时，考虑是否重新选取分割位置；
5.分割成两个序列时，只对其中⼀个递归进去，另⼀个序列仍可以在这⼀函数内继续划分，可以显著减⼩栈的⼤⼩（尾递归）：
6.将单向扫描改成双向扫描，可以减少划分过程中的交换次数
优化1：当待排序序列的长度分割到⼀定⼤⼩后，使⽤插⼊排序
原因：对于很⼩和部分有序的数组，快排不如插排好。当待排序序列的长度分割到⼀定⼤⼩后，继续分割的效率⽐插⼊排序要差，此时可以使⽤插排⽽不是快排
优化2：在⼀次分割结束后，可以把与Key相等的元素聚在⼀起，继续下次分割时，不⽤再对与key相等元素分割
优化3：优化递归操作
快排函数在函数尾部有两次递归操作，我们可以对其使⽤尾递归优化
优点：如果待排序的序列划分极端不平衡，递归的深度将趋近于n，⽽栈的⼤⼩是很有限的，每次递归调⽤都会耗费⼀定的栈空间，函数的参数越多，每次递归耗费的空间也越多。优化后，可以缩减堆栈深度，由原来的O(n)缩减为O(logn)，将会提⾼性能。
（8） Top K问题（可以采取的⽅法有哪些，各⾃优点？）
1.将输⼊内容（假设⽤数组存放）进⾏完全排序，从中选出排在前K的元素即为所求。有了这个思路，我们可以选择相应的排序算法进⾏处理，⽬前来看快速排序，堆排序和归并排序都能达到O(nlogn)的时间复杂度。
2.对输⼊内容进⾏部分排序，即只对前K⼤的元素进⾏排序（这K个元素即为所求）。此时我们可以选择冒泡排序或选择排序进⾏处理，即每次冒泡（选择）都能到所求的⼀个元素。这类策略的时间复杂度是O(Kn)。
3.对输⼊内容不进⾏排序，显⽽易见，这种策略将会有更好的性能开销。我们此时可以选择两种策略进⾏处理：
⽤⼀个桶来装前k个数，桶⾥⾯可以按照最⼩堆来维护
a)利⽤最⼩堆维护⼀个⼤⼩为K的数组，⽬前该⼩根堆中的元素是排名前K的数，其中根是最⼩的数。此后，每次从原数组中取⼀个元素与根进⾏⽐较，如⼤于根的元素，则将根元素替换并进⾏堆调整（下沉），即保证⼩根堆中的元素仍然是排名前K的数，且根元素仍然最⼩；否则不予处理，取下⼀个数组元素继续该过程。该算法的时间复杂度是O(nlogK)，⼀般来说企业中都采⽤该策略处理top-K问题，因为该算法不需要⼀次将原数组中的内容全部加载到内存中，⽽这正是海量数据处理必然会⾯临的⼀个关卡。
b)利⽤快速排序的分划函数到分划位置K，则其前⾯的内容即为所求。该算法是⼀种⾮常有效的处理⽅式，时间复杂度是O(n)（证明可以参考算法导论书籍）。对于能⼀次加载到内存中的数组，该策略⾮常优秀。
（9） Bitmap的使⽤，存储和插⼊⽅法
BitMap从字⾯的意思
很多⼈认为是位图，其实准确的来说，翻译成基于位的映射。
在所有具有性能优化的数据结构中，⼤家使⽤最多的就是hash表，是的，在具有定位查上具有O(1)的常量时间，多么的简洁优美。但是数据量⼤了，内存就不够了。
当然也可以使⽤类似外排序来解决问题的，由于要⾛IO所以时间上⼜不⾏。
所谓的Bit-map就是⽤⼀个bit位来标记某个元素对应的Value， ⽽Key即是该元素。由于采⽤了Bit为单位来存储数据，因此在存储空间⽅⾯，可以⼤⼤节省。
其实如果你知道计数排序的话（算法导论中有⼀节讲过），你就会发现这个和计数排序很像。
bitmap应⽤
1）可进⾏数据的快速查，判重，删除，⼀般来说数据范围是int的10倍以下。
2）去重数据⽽达到压缩数据
1
2
还可以⽤于爬⾍系统中url去重、解决全组合问题。
BitMap应⽤：排序⽰例
假设我们要对0-7内的5个元素(4,7,2,5,3)排序（这⾥假设这些元素没有重复）。那么我们就可以采⽤Bit-map的⽅法来达到排序的⽬的。要表⽰8个数，我们就只需要8个Bit（1Bytes），⾸先我们开辟1Byte的空间，将这些空间的所有Bit位都置为0(如下图：)
然后遍历这5个元素，⾸先第⼀个元素是4，那么就把4对应的位置为1（可以这样操作 p+(i/8)|(0×01<<(i%8)) 当然了这⾥的操作涉及到Big-ending和Little-ending的情况，这⾥默认为Big-ending。不过计算机⼀般是⼩端存储的，如intel。⼩端的话就是将倒数第5位置1），因为是从零开始的，所以要把第五位置为⼀（如下图）：
然后再处理第⼆个元素7，将第⼋位置为1,，接着再处理第三个元素，⼀直到最后处理完所有的元素，将相应的位置为1，这时候的内存的Bit位的状态如下：
然后我们现在遍历⼀遍Bit区域，将该位是⼀的位的编号输出（2，3，4，5，7），这样就达到了排序的⽬的。
bitmap排序复杂度分析
Bitmap排序需要的时间复杂度和空间复杂度依赖于数据中最⼤的数字。
bitmap排序的时间复杂度不是O(N)的，⽽是取决于待排序数组中的最⼤值MAX，在实际应⽤上关系也不⼤，⽐如我开10个线程去读byte 数组，那么复杂度为:O(Max/10)。也就是要是读取的，可以⽤多线程的⽅式去读取。时间复杂度⽅⾯也是O(Max/n)，其中Max为byte[]数组的⼤⼩，n为线程⼤⼩。
空间复杂度应该就是O(Max/8)bytes吧

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。