西南大学网络与继续教育学院课程考试试题卷类别：网教 专业：计算机教育 课程名称【编号】： 数据结构【0012】 A 卷大作业 满分：100 分答案必须做在答题卷上，做在试题卷上不予记分。一、大作业题目1. 设无向图 G（如图所示），给出该图的最小生成树上边的集合，并计算最小生成树各边上的权值之和。2. 请画出下图的邻接矩阵和邻接表。(3)、已知序列{15,18,60,41,6,32,83,75,95}。请给出采用冒泡排序法对该序列作升序排序时的每一趟的结果。(4)、字符 a, b, c, d, e 出现的概率分别为：0.12, 0.40, 0.15, 0.08, 0.25，采用哈夫曼算法构造哈夫曼树进行编码。(5)、已知线性表的关键字集合{87, 25, 310, 08, 27, 132, 68, 95, 187, 123,70, 63, 47}，已知哈希函数为 H(k)=k MOD 13，采用链地址法处理冲突，设计出该开哈希表的结构。二、大作业要求选作 2 题，满分 100 分。- 1 - 2.4.答：哈夫曼算法就是找到一个最优二叉树，使得其权值和最小。先将 a b c d e 的概率乘以 100 得 12，4，15，8，25.将这几个数按从小到大的顺序排列一下，4，8，12，15，25.4+8=12，添加到这个序列里，将原来的 4，8 划去。12+12=24，添加到序列里，将原来的 12，12 划去，依次类推，15+24=39，39+25=64.故得到一个层次为 4 的哈夫曼树，按照左 1 右 0 编码（也可以左 0 右 1）得 a:110 b:1111 c:10 d:1110 e:0- 2 -