- 1、本文档共6页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
大数据技术与应用专业教学资源库
《数据结构》课程说课稿
《数据结构》期末考试试卷E卷-简答题5
主讲:章万静
序号
PPT
说课稿
幻灯片 1
大家好。我是《数据结构》课程的主讲教师——章老师。
下面我们开始重点分析试卷E中的题目。
幻灯片 2
我们来看一下简答题。
幻灯片 3
简答题的第5题。
字符集为{a,o,i,u,e},各字符出现的次数为{4,2,3,1,7}。以各字符出现的次数为权值,构造一棵最优二叉树(哈夫曼树)。
这道题5分。
我们知道,在哈夫曼树中,所有叶子结点的带权路径长度之和最小,而且叶子结点的权值越小离根结点越远,叶子结点的权值越大离根结点越近。这样,相同的叶子结点构成的哈夫曼树有可能不唯一。
幻灯片 4
下面,我们来详细分析字符集为{a,o,i,u,e},权值为{4,2,3,1,7},是如何构成哈夫曼树的?。
第一步,从字符集{a,o,i,u,e}中,选择权值最小的两个结点u和o,权值分别为1,2,构建合并为一个分支结点3。然后将u,o从字符集中去掉,将分支结点3加入,构建新的集合。
第二步,从新的集合{a,i,e,3}中,选择权值最小的两个结点i和分支结点3,权值分别为3,3,构建合并为一个新的分支结点6。然后将i,分支结点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,o,i,u,e},权值{4,2,3,1,7}构建的最优二叉树。带权路径长度之和 WPL=1*4+2*4+3*3+4*2+7*1=36。
幻灯片 5
本次微课就介绍到这里,希望大家好好理解与掌握。谢谢观看。
您可能关注的文档
- 数据结构-3期(KC002)实训项目库万达停车场管理系统设计.docx
- 数据结构与算法设计教案05-06-2数据结构教案首页(40541P、40543D、40531P).doc
- 数据结构-资源试题库及解析《数据结构》期末考试试卷A卷-简答题1-配套说课稿.docx
- 数据结构-资源试题库及解析《数据结构》期末考试试卷A卷-简答题3-配套说课稿.docx
- 数据结构-资源试题库及解析《数据结构》期末考试试卷A卷-简答题4-配套说课稿.docx
- 数据结构-资源试题库及解析《数据结构》期末考试试卷A卷-简答题5-配套说课稿.docx
- 数据结构-资源试题库及解析《数据结构》期末考试试卷A卷-简答题6-配套说课稿.docx
- 数据结构-资源试题库及解析《数据结构》期末考试试卷A卷-简答题7-配套说课稿.docx
- 数据结构-资源试题库及解析《数据结构》期末考试试卷A卷-简答题8-配套说课稿.docx
- 数据结构-资源试题库及解析《数据结构》期末考试试卷B卷-简答题1-配套说课稿.docx
文档评论(0)