1.以下关于集合类 ArrayList 、 LinkedList 、 HashMap 描述错误的是：C
A HashMap实现Map接口，它允许任何类型的键和值对象，并允许将null用作键或值
B ArrayList和LinkedList均实现了List接口
C 添加和删除元素时，ArrayList的表现更佳
D ArrayList的访问速度比LinkedList快
解析：
ArrayList和LinkedList区别
ArrayList 内部使用的动态数组来存储元素，LinkedList 内部使用的双向链表来存储元素。
- ArrayList ：
如果ArrayList要添加元素时使用尾插法添加到数组最后，如果数组长度不够还需要考虑扩容。
如果需要扩容的话，并且不是第一次（oldCapacity > 0）扩容的时候，内部执行的 Arrays.copyOf() 方法是耗时的关键，需要把原有数组中的元素复制到扩容后的新数组当中。
get(int index) 方法的时间复杂度为 O ( 1 ) ，因为是直接从底层数组根据下标获取的，和数组长度无关。(ArrayList最大优点)
根据最坏的打算（不管需要不需要扩容，System.arraycopy() 肯定要执行），所以时间复杂度为 O ( n ) 。
remove(int index) 方法将指定位置上的元素删除，考虑到需要复制底层数组，所以时间复杂度为 O ( n ) 。
- LinkedList：
get(int index) 方法的时间复杂度为 O ( n ) ，因为需要循环遍历整个链表。
下标小于链表长度的一半时，从前往后遍历；否则从后往前遍历，这样从理论上说，就节省了一半的时间。
如果下标为 0 或者 list.size() - 1 的话，时间复杂度为 O ( 1 ) 。这种情况下，可以使用 getFirst() 和 getLast() 方法，时间复杂度为 O ( 1 ) 。
add(E e) 方法默认将元素添加到链表末尾，所以时间复杂度为 O ( 1 ) 。
add(int index, E element) 方法将新的元素插入到指定的位置，需要先通过遍历查找这个元素，然后再进行插入，所以时间复杂度为 O ( n ) 。
（ArrayList 更轻量级，不需要在每个元素上维护上一个和下一个元素的地址。）
2.ArrayList list = new ArrayList(20);中的list扩充几次( A )
A 0
B 1
C 2
D 3
解析：
ArrayList list=new ArrayList();
这种是默认创建大小为10的数组，每次扩容大小为1.5倍
ArrayList list=new ArrayList(20);
使用的ArrayList的有参构造函数，是指定数组大小的创建，创建时直接分配其大小，没有扩充。
一次性为创建了传入的数字的长度的数组，所以，扩充为0次。
3.以下说法错误的是（D）
A 虚拟机中没有泛型，只有普通类和普通方法
B 所有泛型类的类型参数在编译时都会被擦除
C 创建泛型对象时请指明类型，让编译器尽早的做参数检查
D 泛型的类型擦除机制意味着不能在运行时动态获取List中T的实际类型
解析：
虚拟机中没有泛型,只有普通类和普通方法,所有的泛型类,泛型方法的,在编译阶段就已经被处理成了普通类和普通方法(通过类型擦除进行处理),也就是讲泛型擦除成了Object或者边界类型(extend等)。
创建泛型的时候,尽可能早的指出泛型的类型,争取让编译器检查出错误,而不是在jvm运行的时候抛出类不匹配的异常。
即使是泛型,也可以在运行时,动态的(利用反射机制)动态的获取到泛型的实际类型（Object）。
4.已知二叉树的前序序列为BCDEFAG，中序序列为DCFAEGB，请问后序序列为_C_
A、 DAFEGCB
B、 DAEGFCB
C、 DAFGECB
D、 DAEFGCB
解析：
5.二叉树的根节点计为第1层结点，则第9层最多有多少个结点？B
A 18
B 256
C 128
D 64
解析：
第一层：2^0
第二层：2^1
第三层：2^2
……
第n层：2^n
所以，第九层为2^9 = 256
6.将一颗有 100 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根节点编号为 1 ，则编号为 98 的节点的父节点编号为（C）
A 47
B 48
C 49
D 50
解析：
Parent = child / 2
98 / 2 = 49
7.用不带头结点的单链表存储队列,其队头指针指向队头结点,队尾指针指向队尾结点,则在进行出队操作时(C)
A 仅修改队头指针
B 仅修改队尾指针
C 队头、队尾指针都可能要修改
D 队头、队尾指针都要修改
解析：
队列为先进先出。进队使用尾插，修改尾节点，出队使用头删，修改头节点。
- 队列长度不为1时
- 队列长度为1时，头节点和尾节点都指向同一个节点，如果要删除这个单个节点，头节点和尾节点都需要修改。
8.在Java中，HashMap中是用哪些方法来解决哈希冲突的？C
A 开放地址法
B 二次哈希法
C 链地址法
D 建立一个公共溢出区
解析：
解决hash冲突的方法：
- 闭散列：也叫开放定址法
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
二次探测：再散列法(二次哈希法):再次使用一个不同的哈希算法再计算一次 (第一次%16换另一个数进行%运算)
- 开散列法：又叫链地址法 ( 开链法 ) ，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子 集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
9.在Java中，关于HashMap类的描述，以下错误的是（ B ）
A HashMap使用键/值得形式保存数据
B HashMap 能够保证其中元素的顺序
C HashMap允许将null用作键
D HashMap允许将null用作值
解析：
HasMap为什么存储数据无序，但每次输出却相同：
HashMap底层是数组+链表的结构，每个数组默认大小是16，即0-15，在put方法存放值的时候，会根据key值大小来计算存放位置。
示例：存放{5，18，2，4，32，45，9，29}：
10.下面有关List接口、Set接口和Map接口的描述，错误的是？（A）
A 他们都继承自Collection接口
B List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置
C Set是一种不包含重复的元素的Collection
D Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个value
解析：
List、Queue和Set继承Collection接口，HashMap和TreeMap己成Map接口。
11.对关键字{25,15,30,10,50,3,5,60}序列进行快速排序，第一趟从小到大一次划分结果为（B ）
A {3，5，10，15} 25{50，30，60}
B {5，15，3，10} 25 {50，30，60}
C {3，15，10，5} 25 {50，30，60}
D {5，15，3，10} 25 {30，50，60}
解析：
快排示例：
1.存放元素
2.将low中25存入tmp，high中60与tmp进行比较
high(60) > tmp(25), high--
3.high与tmp比较，5 < 25，将high中5赋值给low，判断low是否小于tmp，5 < 25，low++
4.判断low是否小于tmp，15 < 25，low++
5.判断low是否小于tmp，30 > 25，将low中30赋值给high，
判断high是否大于tmp，30 > 25，high--
6.判断high是否大于tmp，3 < 25，将high中3赋值给low，
判断low是否小于tmp，3 < 25，low++
7. 判断low是否小于tmp，10 < 25，low++
8.判断low是否小于tmp，50 > 25，low中50赋值给high，
判断high是否大于tmp，50 > 25，high++
9.此时high与low相遇，将tmp放入相遇处，即完成第一次挖坑法快排
最终排序结果为{5，15，3，10} 25 {50，30，60}
12.下列算法中不属于稳定排序的是：(C)
A 插入排序
B 冒泡排序
C 快速排序
D 归并排序
解析：
如何定义是否为稳定排序：
- 设关键字Ki=Kj，且排序前的序列中Ki领先于Kj，若排序后Ki仍然领先于Kj，则称这个排序方法是稳定的
稳定的排序：
- 插入排序、冒泡排序、归并排序
不稳定的排序：
- 希尔排序、堆排序、快速排序
不确定的排序：
- 简单选择排序（插入版稳定，交换版不稳定）
13.下列各排序法中，最坏情况下的时间复杂度最低的是（C）
A 希尔排序
B 快速排序
C 堆排序
D 冒泡排序
解析：
各大排序时间复杂度对比：
| 排序方法 | 最好 | 最坏 | 平均 |
|---|---|---|---|
| 冒泡 | O(N) | O(N^2) | O(N^2) |
| 插入 | O(N) | O(N^2) | O(N^2) |
| 选择 | O(N^2) | O(N^2) | O(N^2) |
| 希尔 | O(N^1.3) | O(N^1.5) | O(N^1.3) ~ O(N^1.5) |
| 堆排 | O(N^logN) | O(N^logN) | O(N^logN) |
| 快排 | O(N^logN) | O(N^2) | O(N^logN) |
| 归并 | O(N^logN) | O(N^logN) | O(N^logN) |
14.假设你只有100MB的内存，需要对1GB的数据进行排序，最合适的算法是（A）
A 归并排序
B 插入排序
C 冒泡排序
D 快速排序
解析：
内存只有100Mb，而数据却有1Gb，所以肯定没法一次性放到内存去排序，只能用外部排序，而外排序通常是使用多路归并排序，即将原文件分解成多个能够一次性装入内存的部分（如这里的100Mb），分别把每一部分调入内存完成排序（根据情况选取适合的内排算法），然后对已经排序的子文件进行多路归并排序。