答案为自己整理的，欢迎批评指正。
公共题
选择题（每题5分）
1. 若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（ ）
A：9 B：11 C：12 D：不确定
2.下列排序算法中，其时间复杂度和记录的初始排列无关的是（ ）
A：插入排序 (预先排序，运行时间为O(N)) B：堆排序 C：快速排序 (最坏情形O(N2)) D：冒泡排序 (最坏情形O(N2), 最优O(N))
3.已知中序遍历的序列为abcdef，高度最小的可能的二叉树的叶子是（ ）
A：ace B：acf C：adf
D：cdf
4.参加百年阿里培训的n位同学结伴去西湖旁边为游人指路，两人一组，他们打算先让体重之和恰好为102公斤的同学一组，请给出一个算法找到这样的组合，或者确定他们中不存在这样的组合，其中最优的算法时间复杂度为？（假设体重均为整数） （ ）
A：O(log(n)) B：O(n) C：O(n log(n)) D：O(n^2)
5.众所周知数据结构中非常基本的树结构包括二叉查找树（BST）。当我们把如下序列：10，5，19，4，13，7，6，3，1按顺序建立一棵BST时，树的最大深度是？（令根节点深度为0，执行不进行平衡的基本插入） （ ）
A：5 B：4 C：3 D：2
6.阿里巴巴启用了新的办公大厦，这里的一切都充满了现代感；工程师们打算在娱乐区用大小相等的圆形材料分割出一些空间，使用A,B,C三个圆形材料，最多可以将空间分为八个区域（包括圆形以外的区域），如果给你五个圆形材料，你最多可以帮助工程师们分出多少个空间？ （ ）
A：20 B：22 C：26 D：32
综合题（每题15分）
1） 分析MergeSort的原理以及算法复杂度，并用最擅长的编程语言实现Merge Sort。
MergeSort利用分治法的原理，依次减小问题的规模。时间复杂度为O(nlog(n)), 空间复杂度为O(N);
- void Mergesort(int *p, int n)
- {
- void Msort(int *p, int *temp, int left, int right);
- int *temp;
- if(n <= 0 || p == NULL)
- return;
- temp = (int *)malloc(sizeof(int) * n);
- if(temp == NULL)
- return;
- Msort(p, temp, 0, n-1);
- free(temp);
- }
- void Msort(int *p, int *temp, int left, int right)
- {
- void Merge(int *p, int *temp, int left, int rightbegin, int right);
- int leftend = (right + left)/2;
- int rightbegin = leftend+1;
- if(left < right)
- {
- Msort(p, temp, left, leftend);
- Msort(p, temp, rightbegin, right);
- Merge(p, temp, left, rightbegin, right);
- }
- }
- void Merge(int *p, int *temp, int left, int rightbegin, int right)
- {
- int TempArray = rightbegin;
- int pos = left;
- int begin = left;