Exam 版 (精华区)

发信人: fenggao (kk), 信区: Exam
标  题: t2
发信站: 哈工大紫丁香 (Sat Dec  6 08:50:37 2003), 站内信件


数据结构模拟试题（50分）
一、 填空题（15分，每题3分）
1．假设用于通信的电文由8个字母组成，其频率分别为0.07，0.19,0.02,0.06,0.32,0.03
,0.21, 0.10, 为这8个字母设计哈夫曼编码，其中编码长度最大的字母的编码是     位。

2．  已知二叉树按中序遍历所得到的结点序列为DCBGEAHFIJK，按后序遍历所得到的结点
序列为DCEGBFHKJIA，按先序遍历所得到的结点序列为      。
3．设哈希表长度为11，哈希函数H(k)=k MOD 11, 若输入顺序为（18,10,21,9,6,3,16,25
,7）,处理冲突方法为线性探测再散列，请构造哈希表。
         0     1    2    3    4    5    6    7     8    9   10     
  
 
4．给出一组关键字 T=(20，4，34，5，16，33，18，29，2，40，7)，要求从小到大进行
排序，试给出快速排序(选第一个记录为枢轴)第一趟排序结果      。
5．若待排序列已基本有序，要使它完全有序，则从关键码比较和移动次数考虑，应当使用
的排序方法是      。

二、简答题（19分）
1．试求按关键字序列(12,20,9,11,30,45,22,8,90)插入生成的二叉排序树。（3分）
2．已知一个图的邻接矩阵如下：
v1  v2  v3  v4  v5
v1   0   0   0   0   1
v2   1   0   0   0   0
v3   1   0   0   0   1
v4   0   1   0   0   1
v5   0   0   0   0   0
1) 从顶点v2出发，求它所有可能的深度优先遍历序列。（2分）
2) 从顶点v4出发，求它所有可能的广度优先遍历序列。（2分）
3) 求它所有可能的拓扑排序序列。（3分）
3．判别序列（12，70，33，65，24，56，48，92，86，35）是否为堆（堆
顶元素为序列中元素的最小值），如果不是，则把它调整为堆。（5分）
4．简述线性结构、树型结构和图状结构的联系与区别。（4分）

三．程序设计题（16分，每题8分）
1． 已知两个带头结点的单链表la和lb分别表示两个集合A和B，其元素递增排列，请编写
算法求C=AB，要求C也用带头结点的单链表存储，其元素递增排列，并利用原表（
即表la和表lb）的结点空间。
2．试写一算法，求以二叉链表表示的二叉树中所有叶子结点数。

--

※ 来源:．哈工大紫丁香 bbs.hit.edu.cn [FROM: 210.46.77.132]