一、选择题，16*3分

1. 复杂度的概念
2.
3. 单链表头尾节点的特性
4. 汉诺塔次数递推
5.
6.
7.
8.
9.
10.
11.
12.
13.
14. 简单选择排序的比较次数和移动次数
15. 稳定性判定
16. 什么文件适合磁带储存

二、填空题，2分一空，共38分
1. 评价算法的两个重要概念
2.
3. 队列的几个复杂度
4. KMP算法复杂度
5.
6.
7.
8.
9. 伙伴系统求地址
10.

三、简答题，39分
1. 算术表达式转化二叉树 *12
2. 哈希表除余取留法、线性再探测、成功查找长度*12
3. demonstrate()函数，字符串常见assign/concat/substring/replace，求输出 *15

四、证明题：25分
1. （1）证2n-1个节点，只有0和2度的二叉树  *5
（2）. 证明叶子结点的层数li，满足求和：2的li -1 次方的倒数之和为1  *5  

2. （1）证明AVL树最少节点的递推公式*5
（2）证明通项公式，斐波那契数列，爱咋求咋求，查分方程，构造特征方程、数归暴力也行*5
（3）证明AVL树查找复杂度为O(logn)  *5