3.4 树的应用

3.4 树的应用


  3.4 树的应用
  考试大纲涉及本节的知识点有:等价类的问题、哈夫曼(Huffman)树和哈夫曼编码。
  一、选择题
  1.选择题题目…

3.4 树的应用

  3.4 树的应用

  考试大纲涉及本节的知识点有:等价类的问题、哈夫曼(Huffman)树和哈夫曼编码。

  一、选择题

  1.选择题题目部分
  ● 若一棵哈夫曼树共有9个顶点,则其叶子节点的个数为 (1)
  (1)A.4 B.5 C.6 D.7
  ● 根据使用频率,为5个字符设计的哈夫曼编码不可能是 (2)
  (2)A.111,110,10,01,00 B.000,001,010,011,1
  C.001,000,10,01,11 D.110,100,101,11,1
  ● 在度为m的哈夫曼树中,其叶节点个数为n,则非叶节点的个数为 (3)
  (3)A. B. C. D.

  ● 设有13个值,用它们组成一棵哈夫曼树,则该哈夫曼树共有 (4) 个节点。
  (4)A.12 B.13 C.25 D.26
  ● 由带权1、3、5、6、9的5个叶子节点生成的哈夫曼树的带权路径长度为 (5)
  (5)A.50 B.52 C.55 D.60
  2.选择题练习答案与分析
  题号(1)答案 B
  习题分析:
  2个叶子节点的哈夫曼树的构成,只需进行1次合并,即把2个叶子节点合并即可。合并的同时会产生1个根节点,所以一棵2个叶子节点的哈夫曼树共有3个节点。再比如3个叶子节点的哈夫曼树的构成,需要进行2次合并,第1次是把2个值较小的叶子节点合并,然后再把合并好的节点和第3个叶子节点合并。每进行1次合并会产生1个新的节点。所以1棵3个叶子节点的哈夫曼树共有5个节点。
  或者用另一种方法来算:从哈夫曼树的构造过程,可以知道哈夫曼树中无1度的节点。只有2度节点和0度节点(即叶子节点)。设此树中度为2的节点有n2个,度为0的节点有n0个。因为此树共有9个节点,所以此树的总度数为n1=8度。所以现在可以得出两个等量关系式:
  (1)树的总度数的等量关系8=n2×2;
  (2)树的总节点数的等量关系9=n2+n0。
  计算两式得n2=4,n0=5,即度为2的节点有4个,度为0的节点也就是叶子节点有5个,所以此题应选答案B。
  题号(2)答案 D
  习题分析:
  哈夫曼编码属于前缀编码,根据前缀编码的定义,任一字符的编码都不是另一字符编码的前缀。而选项D中,1是前面4个字符的前缀,明显违反了这一原则,所以不属于哈夫曼编码。
  题号(3)答案 B
  习题分析:
  在构造度为m的哈夫曼树的过程中,每次把m个子节点合并为一个父节点(第一次可能合并少于m个子节点),每次合并减少m-1个节点,从n个节点减少到最后只剩下一个父节点,共需 次合并,每次合并增加一个非叶节点。
  题号(4)答案 C
  习题分析:
  由哈夫曼树的性质可知,具有n个叶子节点的哈夫曼树共有2n-1个节点,所以本题中的哈夫曼树共有2×13-1=25个节点。
  题号(5)答案 B
  习题分析:
  构造的哈夫曼树如图3-11所示,该树的带权路径长度为52。
  

  3.训练自测表(如表3-5所示)

表3-5 选择题练习自测表

题    号

考  查  点

得    分

(1) 哈夫曼树中叶子节点的个数  
(2) 哈夫曼编码  
(3) 度为m的哈夫曼树  
(4)~(5) 哈夫曼树的构造  

3.4 树的应用

    关于作者: admin

    这里可以再内容模板定义一些文字和说明,也可以调用对应作者的简介!或者做一些网站的描述之类的文字活着HTML!

    为您推荐

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注

    评论列表 人参与

    联系我们

    联系我们

    8888-88888888

    在线咨询: QQ交谈

    邮箱: email@admin.com

    工作时间:周一至周五,9:00-17:30,节假日休息

    关注微信
    微信扫一扫关注我们

    微信扫一扫关注我们

    关注微博
    返回顶部