"数据结构复习要点：算法思想、Huffman编码、散列地址处理"

数据结构复习要点.doc 中总结了数据结构的必考点，包括主要算法思想、存储结构及性能指标。以下是其中的几个例子： 1. Huffman树 假设一个用于通信的电文仅由5个字母 c1, c2, c3, c4, c5 组成，其出现的频率分别为{4, 6, 2, 8, 7}。题目要求 （1）画出Huffman树 （2）为这5个字母设计不等长的Huffman编码，写出各字母的编码（设编码左分支为0、右分支为1）。例如，根据出现的频率，我们可以得到Huffman树如下所示，然后根据树的路径来得到每个字母的编码： 27 / \ c1:4 23 / \ c3:2c5:7 c2:6c4:8 编码为：c1: 000, c3: 1000, c5: 1001, c2: 01, c4: 11 （3）求此电文带权路径长度。带权路径长度是指每个叶子结点的权值乘以到根结点的路径长度再求和，对于本例即为： 4*3 + 6*2 + 2*3 + 8*2 + 7*2 = 57 2. 二叉树遍历 给定二叉树结点的先根序列为ABDECFGH，中根序列为DEBAFCHG，则二叉树中的叶子结点为23。 3. 散列表 题目给出了一个待散列存储的数据集合{32, 75, 29, 63, 48, 94, 25, 46, 18, 70, 56}，散列地址空间为HT[13]，要求采用除留余数法构造散列函数和链接法（或线性探查法）处理冲突，求出每个元素的散列地址，最后得到的散列表，并求平均查找长度。或者已知哈希表地址空间为0..14，哈希函数为H(k)=k mod 13，采用线性探测法处理冲突，将给定的数依次存入该散列表中，并求出在等概率下的平均查找长度。 以上是数据结构复习要点中的几个例题，通过对这些问题的练习与归纳，可以更好地掌握数据结构的基本概念、算法思想和性能分析。