9 : 100 16: 00 17: 01
(4)（3分)huffman编码常用来译码，请用语言叙述写出其译码的过程。
以哈夫曼的根结点出发，用待译码的二进制位串中逐位取码，与二叉树份之上标明的“0”，“1”相匹配，确定一条到达叶子结点的路径，一旦到达叶子结点，则译出一个字符。
【山东大学 1998 七、】【山东工业大学 2000 七、 (11分)】
第7章 图
2．n个顶点的无向连通图最少有多少条边？n个顶点的有向连通图最少有多少条边？ 【山东大学 2000 一、3 (4分)】
答：n个顶点的无向连通图最少有n-1条边；
n个顶点的有向连通图最少有n条边。
15．下面的邻接表表示一个给定的无向图
（1）给出从顶点v1开始,对图G用深度优先搜索法进行遍历时的顶点序列； 答：无向图如下所示： V1 V2
V3 V4
V5 V6
从顶点v1开始，深度优先搜索法进行遍历时的顶点序列为：v1 v2 v4 v6 v5 v3 （2）给出从顶点v1开始,对图G用广度优先搜索法进行遍历时的顶点序列。【复旦大学1998六(10分)) 答：从顶点v1开始，广度优先搜索法进行遍历时的顶点序列为：v1 v2 v3 v4 v5 v6
15题图
17．设G=(V,E)以邻接表存储，如图所示，试画出图的深度优先和广度优先生成树。
234?1 5?1342 124? 31235? 4 524? 【北京轻工业学院 1998 八 （6分）】
答：深度优先： 广度优先：
1 2 1
3 2
3 4
5 4 5
6
6
（6）．写出将无向图的邻接表转换成邻接矩阵的算法。（8分） 【山东大学 1998 六、18分】 24．考虑右图：
(1)从顶点A出发，求它的深度优先生成树
A 2 A 5
D 6 4 D C B B
C E 1 E 3 3 5
F G 1 F G
(2)从顶点E出发，求它的广度优先生成树 A D
B
C
E
F G
（3）根据普利姆(Prim) 算法，
求它的最小生成树【上海交通大学 1999 六 (12分)】 答： A D B
C E
F G 27．已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。【哈尔滨工业大学 1999 九 （8分）】
20 1 2 5 11 9 6 3 10 14 6 10
4 6 5 18
27题图
48．下图是带权的有向图G的邻接表表示法，求：
（1）．以结点V1出发深度遍历图G所得的结点序列；V1 V2 V5 V3 V8 V6 V7 V4
（2）．以结点V1出发广度遍历图G所得的结点序列；V1 V2 V4 V6 V3 V5 V7 V8 （3）．从结点V1到结点V8的最短路径；V1 V2 V5 V7 V8 （4）．从结点V1到结点V8的关键路径。V1 V6 V5 V3 V8
【青岛海洋大学 1999 四（10分）】
第9章 查找
3. 如何衡量hash函数的优劣？简要叙述hash表技术中的冲突概念，并指出三种解决冲突的方法。 【南京航空航天大学 1996 九、2 （6分）】 答：衡量hash函数的优劣：
1、 哈希函数尽可能简单，以便提高转换速度
2、 对关键字计算出的地址，应在哈希地址集中大致均匀分布，以减少空间浪费。 3、 使产生冲突的可能性降到尽可能地小。
冲突概念：经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突(Collision)。
解决冲突的方法：
① 开放定址法 ② 再哈希法 ③ 链地址法
48. 用序列(46,88,45,39,70,58,101,10,66,34)建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度.【北京邮电大学 1999 七 （10分）】 答：二叉排序树为： 46 45 88
39 70 101
10 58
34 66
平均查找长度：（1*1+2*2+3*3+4*2+5*2）/10 = 3.2
49. 依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树【华中理工大
学 2000 五 （10分）】
(1) 试画出生成之后的二叉排序树;
30
15 68
10 28 35
50
12 20
24 55 46
(2) 对该二叉排序树作中序遍历，试写出遍历序列; 遍历序列：10 12 15 20 24 28 30 35 46 50 55 68
(4) 假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。
平均查找长度：（1*1+2*2+3*3+4*3+5*3）/12 = 41/12
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库数据结构习题（答案）(3)在线全文阅读。
相关推荐：