Java开发校招面试考点汇总第八篇：数据结构

1、B树、B+树、B*树
https://blog.****.net/u014138443/article/details/89741129

1.1时间复杂度
红黑树插入操作的平均时间复杂度为O(logn)，最坏时间复杂度为O(logn)
B+树插入操作的平均时间复杂度为O(logn)，最坏时间复杂度为O(logn)

2、● 你知道哪些排序算法，这些算法的时间复杂度分别是多少

快选希堆不稳定
插选希堆复杂度固定

直接插入排序：
将第i个记录插入到前面i-1个已经排序的记录中
最好情况为顺序
最坏情况为逆序
适用于待排序记录数目较少且基本有序的情况

希尔排序：
最好情况：基本有序，对中等规模（N<1000）的序列有较高序列

冒泡排序：
最好情况是顺序
问题：最好情况的时间复杂度为什么是O(N)
答案：https://www.cnblogs.com/melon-h/archive/2012/09/20/2694941.html
最坏情况是逆序

快速排序：
最坏情况是正序或逆序
最好情况是排序混乱、每趟将序列一分为二，类似于折半

简单选择：
最好情况是待排序记录是正序排列
最坏情况是第一个记录最大，其余记录从小到大

3、● 请你解释一下，内存中的栈(stack)、堆(heap) 和静态区(static area) 的用法。
通常我们定义一个基本数据类型的变量，一个对象的引用，还有就是函数调用的现场保存都使用内存中的栈空间；而通过new关键字和构造器创建的对象放在堆空间；程序中的字面量（literal）如直接书写的100、"hello"和常量都是放在静态区中。栈空间操作起来最快但是栈很小，通常大量的对象都是放在堆空间，理论上整个内存没有被其他进程使用的空间甚至硬盘上的虚拟内存都可以被当成堆空间来使用。
String str = new String(“hello”);
上面的语句中变量str放在栈上，用new创建出来的字符串对象放在堆上，而"hello"这个字面量放在静态区。

4、java集合(ArrayList/Vector/LinkedList/HashSet/TreeSet/ArrayDeque/PriorityQueue/HashMap/HashTable/TreeM)

https://blog.****.net/u014138443/article/details/89848744