数据结构复习要点.doc

1

熟悉主要算法思想、存储结构及性能指标

举例：

1. 假定用于通信的电文仅由 5 个字母 c1,c2,c3,c4,c5 组成，各字母在电文中出现

的频率分别为{4 ,6, 2, 8, 7 }。

（1）画出 human 树；

（2）为这 5 个字母设计不等长的 human 编码，写出各字母的编码(设编码左分

支为 0、右分支为 1。可在图中直接标出)。

2

试求出每一元素的散列地址，画出最后得到的散列表，求平均查找长度。

（或已知哈希表地址空间为 0..14，哈希函数为 H(k)=k mod 13，采用线性探

测法处理冲突。将下面各数依次存入该散列表中，并求出在等概率下的平均查

找长度。

240, 29, 345, 189, 100, 20, 21, 35, 3, 208, 78, 99, 45,

350）

4. 画出与该树对应的二叉树，并写出该树的先根遍历序列和后根遍历序列

或给出树的边集集合，要求写出树的二叉链表结构，再求其先根遍历序列和后

根遍历序列

5. 已知一个连通图的边集为｛（１，２）３，（１，３）６，（１，４）８，

3

EBACDFHG，

请回答下列问题：

(1)画出此二叉排序树；

(2)若将此二叉排序树看作森林的二叉链表存储，请画出对应的森林。

2. 画出与如图所示森林对应的二叉树，写出此森林的中序遍历序列。

3. 已 知带 权 图如 下所 示 ， 要建 立邻接 表 结构 ， 其中 边表 结 点的 结 构为 ：