数据结构-资源试题库及解析《数据结构》期末考试试卷A卷-简答题7-配套说课稿.docx

大数据技术与应用专业教学资源库 《数据结构》课程说课稿 《数据结构》期末考试试卷A卷-简答题7 主讲：章万静  序号 PPT 说课稿 幻灯片 1 大家好。我是《数据结构》课程的主讲教师——章老师。 下面我们开始重点分析试卷A中的题目。 幻灯片 2 我们来看一下简答题。 幻灯片 3 简答题的第7题。 字符集为{a，b，c，d，e}，各字符出现的次数为{4，2，3，1，7}。以字符出现的次数为权值，构造一棵最优二叉树（哈夫曼树）。 这道题5分。 我们知道，在哈夫曼树中，所有叶子结点的带权路径长度之和最小，而且叶子结点的权值越小离根结点越远，叶子结点的权值越大离根结点越近。这样，相同的叶子结点构成的哈夫曼树有可能不唯一。 幻灯片 4 下面，我们来详细分析字符集为{a，b，c，d，e}，权值为{4，2，3，1，7}，是如何构成哈夫曼树的？。 第一步，从字符集{a，b，c，d，e}中，选择权值最小的两个结点d，b，权值分别为1,2，构建合并为一个分支结点3。然后将d，b从字符集中去掉，将分支结点3加入，构建新的集合。 第二步，从新的集合{a，c，e，3}中，选择权值最小的两个结点c和分支结点3，权值分别为3,3，构建合并为一个新的分支结点6。然后将c，分支结点3从集合中去掉，将新分支结点6加入，构建新的集合。 第三步，从新的集合{a，e，6}中，选择权值最小的两个结点a和分支结点6，权值分别为4,6，构建合并为一个新的分支结点10。然后将a，分支结点6从集合中去掉，将新分支结点10加入，构建新的集合。 第四步，从新的集合{ e，10}中，选择权值最小的两个结点e和分支结点10，权值分别为7,10，构建合并为一个新的分支结点17。然后将e，分支结点10从集合中去掉，将新分支结点17加入，构建新的集合。 新集合中只有一个分支结点17，所以哈夫曼树已经构建成功。这棵哈夫曼树就是由字符集{a，b，c，d，e}，权值{4，2，3，1，7}构建的最优二叉树。带权路径长度之和 WPL=1*4+2*4+3*3+4*2+7*1=36。 幻灯片 5 本次微课就介绍到这里，希望大家好好理解与掌握。谢谢观看。