在有n个子叶节点的哈夫曼树中，其节点总数为(39)。A．不确定B．2n-1C．2n+1D．2n

题目

在有n个子叶节点的哈夫曼树中，其节点总数为(39)。

A．不确定

B．2n-1

C．2n+1

D．2n

相似考题

1.以下说法错误的是 ( )A.一般在哈夫曼树中，权值越大的叶子离根结点越近B.哈夫曼树中没有度数为1的分支结点C.若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-1个结点D.若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树

2.若用n个权值构造一颗最优二叉树(哈夫曼树)，则该二叉树的结点总数为()A.2nB.2n-1C.2n+1D.2n+2

3.下面关于哈夫曼树的叙述中，正确的是()A.哈夫曼树一定是完全二叉树B.哈夫曼树一定是平衡二叉树C.哈夫曼树中权值最小的两个节点互为兄弟节点D.哈夫曼树中左孩子节点小于父节点、右孩子节点大于父节点

4.已知哈夫曼树有100个叶子,则其结点总数是()。

参考答案和解析
正确答案：B
解析：哈夫曼树是最优二叉树，它是一类带权路径长度(WPL)最短的树。二叉树结点总数为：M=N0+N1+N2(N0、N1、N2分别表示度为0、1、2的结点)。哈夫曼树在构建过程中，没有度为1的结点且有N0=N2+1，故M=2N0-1，这里N0=n。
更多“在有n个子叶节点的哈夫曼树中,其节点总数为(39)。A.不确定B.2n－1C.2n＋1D.2n ”相关问题

  • 第1题：

    下面关于哈夫曼树的叙述中，正确的是(58)。

    A．哈夫曼树一定是完全二叉树

    B．哈夫曼树一定是平衡二叉树

    C．哈夫曼树中权值最小的两个结点互为兄弟结点

    D．哈夫曼树中左孩子结点小于父结点、右孩子结点大于父结点


    正确答案：C
    解析：哈夫曼树又称最优二叉树或最优搜索树，是一种带权路径长度最短的二叉树。具有以下特征：
      (1)当叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。即哈夫曼树不一定是完全二叉树。
      (2)在最优二叉树中，权值越大的叶子离根越近。
      (3)最优二叉树的形态不唯一，但WPL最小。
      哈夫曼树的构造：
      (1)根据给定的n个权值{w1，w2，…，wn}构造n棵二叉树的集合F={Tl，T2，…，Tn}，其中Ti中只有一个权值为wi的根结点，左右子树为空；
      (2)在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右予树上根结点的权值之和。
      (3)将新的二叉树加入到F中，删除原两棵根结点权值最小的树；
      (4)重复(2)和(3)直到F中只含一棵树为止，这棵树就是哈夫曼树。
    平衡二叉树是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。而哈夫曼树并未要求左右两个子树的高度差的绝对值不超过1，根据其构造可知，是从上往下顺序排下来的，且左孩子结点大于父孩子结点。

  • 第2题：

    在有n个叶子结点的哈夫曼树中，其结点总数为

    A．不确定

    B．2n

    C．2n+l

    D．2n-1


    正确答案：D
    解析：哈夫曼树又称为最优二叉树，它的结点总数和二叉树相同为2n-1。

  • 第3题：

    哈夫曼树的带权路径长度WPL等于______。

    A．除根以外的所有节点的权植之和

    B．所有节点权值之和

    C．各叶子节点的带权路径长度之和

    D．根节点的值


    正确答案：C
    解析：Huffman树又称为最优树，是一类带权路径长度最短的树。
      节点的带权路径长度为从该节点到树根之间的路径长度与该节点权的乘积。树的路径长度为树中所有节点的带权路径长度之和，记为，其中n为带权叶子节点数目，为叶子节点的权值，lk为叶予节点到根的路径长度。

  • 第4题：

    有m个叶子节点的哈夫曼树，其节点总数是( )。

    A．2m

    B．2m+1

    C．2m-1

    D．2(m+1)


    正确答案：C
    解析：由于哈夫曼树所有的分支节点均为双分支节点，根据二叉树的性质，双分支节点等于叶子节点的个数减1，因此总节点数为m+m-1=2m-1。

  • 第5题：

    下列关于哈夫曼树的叙述错误的是

    A．一棵哈夫曼树是带权路径长度最短的二叉树

    B．一棵哈夫曼树中叶节点的个数比非叶节点的个数大1

    C．一棵哈夫曼树节点的度要么是0，要么是2

    D．哈夫曼树的根节点的权值等于各个叶节点的权值之和


    正确答案：C
    解析：哈夫曼树中节点的度可以是0，1，2。

  • 第6题：

    在有n个叶子节点的哈夫曼树中，其节点总数为

    A．不确定

    B．2n

    C．2n+1

    D．2n-1


    正确答案：D
    解析：哈夫曼树又称为最优二叉树，它的节点总数和二叉树相同为2n-1。

  • 第7题：

    设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有(51)个结点。

    A．n0+1

    B．2n0-1

    C．2n0

    D．3n0


    正确答案：B
    解析：设共有n个结点，则有n=n0+n1+n2(其中n1为有一个孩子的结点，n2为有两个孩子的结点)，n1=0，所以有n=n0+n2；所有结点的入度和为n-1，出度和为2n2，所以有n-1=2n2。将n=n0+n2和n-1=2n2联合解之得n=2n0-1。

  • 第8题：

    在有n个叶子的哈夫曼树中，叶子结点总数为（），分支结点总数为（）。


    正确答案:n；n-1

  • 第9题：

    设给定权值总数有n个，其哈夫曼树的结点总数为（）

    • A、不确定
    • B、2n
    • C、2n+1
    • D、2n-1

    正确答案:D

  • 第10题：

    单选题
    设给定权值总数有n个，其哈夫曼二叉树的结点总数为（  ）。
    A

    不确定

    B

    2n

    C

    2n+1

    D

    2n-l


    正确答案： D
    解析：

  • 第11题：

    填空题
    N（n>0）个节点的哈夫曼树恰含（）个度为1的节点。

    正确答案： 0
    解析： 暂无解析

  • 第12题：

    单选题
    有n个叶子的哈夫曼树的结点总数为（）。
    A

    不确定

    B

    2n

    C

    2n+1

    D

    2n-1


    正确答案： A
    解析： 暂无解析

  • 第13题：

    在有n个叶子的哈夫曼树中，其节点总数为( )。

    A．不确定

    B．2n

    C．2n+1

    D．2n-1


    正确答案：D
    解析：由于哈夫曼树所有的分支节点均为双分支节点，根据二叉树的性质，双分支节点等于叶子节点的个数减1，因此总节点数为n+n-1=2n-1。

  • 第14题：

    在有n个叶子结点的哈夫曼树中，其结点总数为

    A．不确定

    B．2n

    C．2n+1

    D．2n-1


    正确答案：D
    解析：哈夫曼树又称为最优二叉树，它的结点总数和二叉树相同为2n-1。

  • 第15题：

    ● 若用n个权值构造一棵最优二叉树 （哈夫曼树）， 则该二叉树的结点总数为 （59） 。


    正确答案：B

  • 第16题：

    以下关于哈夫曼树的叙述,正确的是(60)。A.哈夫曼树一定是满二叉树,其每层结点数都达到最大值SX

    以下关于哈夫曼树的叙述，正确的是（60）。

    A.哈夫曼树一定是满二叉树，其每层结点数都达到最大值

    B.哈夫曼树一定是平衡二叉树，其每个结点左右子树的高度差为-1、0或1

    C.哈夫曼树中左孩子结点的权值小于父节点、右孩子节点的权值大于父节点

    D.哈夫曼树中叶子节点的权值越小则距离树根越远、叶子结点的权值越大则距离树根越近


    正确答案：D
    给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。所以D选项的说法正确。

  • 第17题：

    最优二叉树(哈夫曼树)、最优查找树均为平均查找路径长度∑wl最小的树，其中对于最优二叉树，n表示(31)；对于最优查找树，n表示(32)；构造这两种树均(33)。

    A．节点数

    B．叶节点数

    C．非叶节点数

    D．度为2的节点数


    正确答案：B
    解析：(31)～(33)(31)假设有n个权值{w1,w2,…，wn)，是构造一棵有n个叶子节点的二又树，每个叶子节点带权wi，则其中带权路径长度WPL=∑wili最小的二又树称做最优二又树或哈夫曼树。所以最优二叉树中n表示叶节点。(32)如果只考虑查找成功的情况，则使查找性能达到最佳的判定树是其带权内路径长度之和值PH=∑wili，取最小值的二叉树为最优查找树。其中n为二叉树上节点的个数(即有序表的长度)；li为第i个节点在二叉树上的层次数；节点的权wi=cpi(i=1～n)，其中pi为节点的查找概率，c为某个常量。因此最优查找树中n表示所有节点数。(33)构造哈夫曼树和最优查找树均需对n个关键字进行动态插入。

  • 第18题：

    若一棵哈夫曼(Huffman)树共有9个顶点，则其叶子节点的个数为(15)。

    A．4

    B．5

    C．6

    D．7


    正确答案：B
    解析：哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法，根据这种方法构造出来的二叉树称为哈夫曼树。假设有n个权值，则构造出的哈夫曼树有n个叶子节点。N个权值分别设为w1，w2，…，wn，则哈夫曼树的构造规则如下。第一步：将w1，w2，…，wn看成是有n棵树的森林；第二步：在森林中选出两个根节点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根节点权值为其左右子树根节点权值之和；第三步：从森林中删除选取的两棵树，并将新树加入森林：第四步：重复第二步和第三步，直到森林中只剩一棵树为止，该树即为所求的哈夫曼树。从以上构造过程可知，哈夫曼树是严格的二叉树，没有度数为1的分支节点。n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新节点，最后求得的哈夫曼树中共有2n-1个节点。

  • 第19题：

    最优二叉树(或哈夫曼树)是指权值为w1，w2，…，wn的n个叶结点的二叉树中带权路径长度最小的二叉树。( )是哈夫曼树(叶结点中的数字为其权值)。



    答案：A
    解析：
    本题考查数据结构基础知识。
    哈夫曼树又称为最优二叉树，是一类带权路径长度最短的树。
    树的带权路径长度(WPL)为树中所有叶子结点的带权路径长度之和，记为

    其中n为带权叶子结点数目，wk为叶子结点的权值，lk为根到叶子结点的路径长度。
    选项A所示二叉树的WPL=(2+4)*3+5*2+7*1=35
    选项B所示二叉树的WPL=(2+4+5+7)*2=36
    选项C所示二叉树的WPL=(5+7)*3+4*2+2*1=46
    选项D所示二叉树的WPL=(4+5)*3+7*2+2*1=43

  • 第20题：

    N（n>0）个节点的哈夫曼树恰含（）个度为1的节点。


    正确答案:0

  • 第21题：

    有n个叶子的哈夫曼树的结点总数为（）。

    • A、不确定
    • B、2n
    • C、2n+1
    • D、2n-1

    正确答案:D

  • 第22题：

    填空题
    在有n个叶子的哈夫曼树中，叶子结点总数为（），分支结点总数为（）。

    正确答案： n,n-1
    解析： 暂无解析

  • 第23题：

    单选题
    设给定权值总数有n个，其哈夫曼树的结点总数为（）
    A

    不确定

    B

    2n

    C

    2n+1

    D

    2n-1


    正确答案： B
    解析： 暂无解析

相关内容