---

 

---

 

1.最坏情况下 insert sort, quick sort ,merge sort 的复杂度分别是多少？

A. O(n*n),O(nlogn),O(n*n)

B. O(n*n),O(n*n),O(nlogn)

C. O(n*n),O(nlogn),O(nlogn)

D. O(nlogn),O(nlogn),O(nlogn)

答案：B

【解析】：

1：简单选择  最好时间 O(n^2)      平均时间O(n^2)      最坏时间 O(n^2)

2：直接插入  最好时间 O(n)         平均时间O(n^2)      最坏时间 O(n^2)

3：冒泡排序  最好时间 O(n)         平均时间O(n^2)      最坏时间 O(n^2)

4：希尔排序  最好时间 O(n)         平均时间O(logn)     最坏时间 O(n^s) 1

5：快速排序  最好时间 O(nlogn)  平均时间O(nlogn)   最坏时间O(n^2) 

6：堆排序      最好时间 O(nlogn)  平均时间O(nlogn)   最坏时间O(nlogn) 

7：归并排序  最好时间 O(nlogn)  平均时间O(nlogn)   最坏时间O(nlogn) 

---

2.三个结点可以构成多少种二叉树（   ） 

A、5
B、6
C、7
D、4

答案：A

【解析】：3个结点的二叉树有5种形态：两层树：根左右；三层树： 根左（第二层）左（第三层）、根左（第二层）右（第三层）、根右（第二层）左（第三层）、根右（第二层）右（第三层）。

---

3...