证明： 层次         该层结点       该层关键字       该层结点指针数
        1              1              k1                k1+1
        2             k1+1            k2               k1+k2+1
        3            k1+k2+1          k3              k3+k2+k1+1
…              …             …                …
h           k1+….+k(n-1)+1    kn         
则第h层是叶子结点层，无关键字。空指针=叶子结点数= k1+….+k(n-1)+1
第一层到第(h-1)层关键字总数为k1+….+k(n-1)  于是命题得证
１７. B+树掌握概念就行，既适合动态查找也适合顺序查找
１８. 哈希表：概念，构造方法，处理冲突的办法，同义词，查找成功和不成功时的平均查找时间，二次聚集等均要掌握
１９. 再哈希：（参看04年作图题）
２０. 链地址：成功ASLsuc=[(第一列的结点数*1)+（二列结点数*2）….]/表长
不成功ASL=个单链表表长之和/表长
２１. 线性探测再散列：
0  1  2   3    4   5   6   7   8   9   10
   4     12   49  38   13  24  32  31
           ASLsuc=(5*1+3*2)/8=11/8
           ASLunsuc=(1+2+1+8+7+6+5+4+3+2+1)/11 (可以参看相关的习题中的练习，熟悉其计算方法)
 第十章：1.所有的排序算法均要掌握
             不稳定的简单排序—简单选择排序
2. 对不稳定算法，要求能举出例子说明为什么不稳定。基数排序应用在整型和字符型的情况下。Shell排序的复杂度不要求掌握
3. 在堆排序中，想得到一个递增序列用大顶堆，反之用小顶堆
历届真题----大题
1.<99>  图的深度优先遍历
2.<99>  以孩子兄弟链表为存储结构，设计递归和非递归算法求树的深度
3.<01>  设计算法将不带头结点的单链表逆置
4.<01>  设计算法按层次顺序遍历二叉树
应参考历届的算法，注意总结！推荐两本习题均是人邮出版的。〈数据结构课程辅导与习题解析〉和〈数据结构500题〉，感觉很适合考北交，书中习题大多数是针对考研来设计的，而且分析很详细。大家应注意理解解题的过程，这是最主要的！碰到没见过的题目，或者经常容易犯错的地方，还有就是经典的算法等最好用专门的本子记下来，这样也可加深记忆，可经常翻阅！我去年基本上就是按这些资料复习的，其于的我也只做了清华大学李春葆的习题和西电的考研习题，感觉一般。这次辅导班老师讲了很多以前考过的和没考过的算法，大家一定要全部认真理解，不管考过没考过都很有可能会出现在06年的试题中。还有就是请大家关注06的辅导班，这很重要。
    由于从没用过Word，所以编辑有点烂，希望大家能原谅，到时自己去修正了！