具有n个叶子的二叉树，每个叶子的权值为wi（1≤i≤n）其中带权路径最小的二叉树被称为（）。

题目

具有n个叶子的二叉树，每个叶子的权值为wi（1≤i≤n）其中带权路径最小的二叉树被称为（）。

相似考题

1.某二叉树中有 n 个度为 2 的结点，则该二叉树中的叶子结点为A) n+1B) n-1C) 2nD) n/2

2.设一棵完全二叉树共有700个结点,则在该二叉树中有( )个叶子结点（提示：1、n1=1,n为偶数；n1=0,n为奇数；2、n0=n2+13、n=n0+n1+n2)

3.某二叉树中有个度为2的结点，则该二叉树中的叶子结点数为（ ）。A．n+1B．n-1C． 2nD． n/2

4.任意一棵具有n个结点的二叉树,若它有m个叶子,则该二叉树上度数为1的结点为n－2m＋1个。()此题为判断题(对，错)。

参考答案和解析
正确答案:哈夫曼树（最优二叉树）
更多“具有n个叶子的二叉树，每个叶子的权值为wi（1≤i≤n）其中带权路径最小的二叉树被称为（）。”相关问题

  • 第1题：

    某二叉树中度为2的结点有n个,则该二叉树中有【 】个叶子结点。


    正确答案：n+1
    在任意一棵二叉树中,度为O多结点(即叶子结点)总是比度为2多结点多一个。

  • 第2题：

    某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为

    A．n+l

    B．n-1

    C．2n

    D．n/2


    正确答案：A
    解析：对于任何一棵二叉树T，如果其终端结点(叶子)数为n1，度为2的结点数为n2，则n1=　n2+1。所以该二叉树的叶子结点数等于n+1。

  • 第3题：

    如果将给定的一组数据作为叶子数值,所构造出的二叉树的带权路径长度最小,则该树称为()。

    A.平衡二叉树

    B.完全二叉树

    C.二叉树

    D.哈夫曼树


    参考答案：D

  • 第4题：

    哈夫曼树是带权叶子数目固定的二叉树中带权路径长度最小的。()

    此题为判断题(对，错)。


    参考答案：正确

  • 第5题：

    某二叉树中有n个度为2的节点，则该二叉树中的叶子节点为( )。

    A．n+1

    B．n-1

    C．2n

    D．n/2


    正确答案：A
    解析：对任何一棵二叉树T，如果其叶子节点数为n0，度为2的节点数为n2，则n0=n2+1，即叶子节点数总是比度为2的节点数多1。

  • 第6题：

    最优二叉树(或哈夫曼树)是指权值为 W1， W2，。。。，Wn 的 n 个叶结点的二叉树中带权路径长度最小的二叉树。（ ）是哈夫曼树(叶结点中的数字为其权值)。

    A.

    B.

    C.

    D.


    正确答案：A

  • 第7题：

    含有n个叶子结点的最优二叉树中共有分支结点数是()。

    A.n-2
    B.n-1
    C.2n-1
    D.2n+1

    答案：B
    解析：
    最优二叉树，又叫哈夫曼树.根据哈夫曼树的构造方法.可以得出非叶子节点都有双分支，分支结点数等于叶子结点减1。这样，n个叶子结点的最优二叉树中共有分支结点数是n-l。

  • 第8题：

    如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（）。

    A平衡二叉树

    B完全二叉树

    C二叉树

    D哈夫曼树


    D
    略

  • 第9题：

    一棵二叉树的第i（i≥1）层最多有（）个结点；一棵有n（n>0）个结点的满二叉树共有（）个叶子结点和（）个非终端结点。


    正确答案:2i-1；（n+1）/2；（n-1）/2

  • 第10题：

    n个节点的完全二叉树，编号为i的节点是叶子结点的条件是（）

    • A、i<n
    • B、2*i<=n
    • C、2*i+1>n
    • D、2*i>n

    正确答案:D

  • 第11题：

    填空题
    哈夫曼树又称为（），它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL（）。

    正确答案： 最优二叉树,最小的二叉树
    解析： 暂无解析

  • 第12题：

    填空题
    具有n个叶子的二叉树，每个叶子的权值为wi（1≤i≤n）其中带权路径最小的二叉树被称为（）。

    正确答案： 哈夫曼树（最优二叉树）
    解析： 暂无解析

  • 第13题：

    某二叉树中有n个度为2的结点,则该二叉树中的叶子结点数为（ ）。

    A．n+1

    B．n-1

    C．2n

    D．n/2


    正确答案：A

  • 第14题：

    某二叉树中有n个叶子结点，则该二叉树中度为2的结点数为()。

    A.n+1

    B.n-1

    C.2n

    D.n/2


    正确答案：B

  • 第15题：

    证明:任何一棵满二叉树中的分支数B满足B=2(n0－1),其中n0为叶子结点个数。


    参考答案：

  • 第16题：

    某二叉树中有n个度为2的结点则该二叉树中的叶子结点数为 A．n+1 B．n-1 C．2n D．n/2


    正确答案：A

  • 第17题：

    关于满二叉树、完全二叉树有以下说法：

    ①满二叉树不仅是一种特殊形态的二叉树，而且是一种特殊的完全二叉树。

    ②具有n个结点的满二叉树的高度为+1。

    ③具有n个结点的完全二叉树的高度为+1。

    ④具有n个结点的满二叉树的高度为log2(n+1)。

    ⑤具有n个结点的满二叉树共有叶子结点。

    其中______最全面、最准确。

    A．①②④

    B．③④⑤

    C．①③④⑤

    D．全对


    正确答案：D
    解析：若二叉树的每一层的结点数都是最大结点数，也就是说每一层都是满的，那么此时的二叉树便成为一棵满二叉树。若二叉树除最后一层外都是满的，而且最后一层的结点都连续紧挨靠左，那么称此时的二叉树为完全二叉树。所谓的“完全”，指的是在给其结点按层次自上而下、同一层自左至右编号时，n个结点(设完全二叉树结点总数为n)与同深度的满二叉树中编号从1到n的结点一一对应。因此，①正确。显然，③是正确的。注意到，满二叉树是特殊的二叉树，因此②也正确。值得指出的是，②和③中的n分别满足不同的条件，因此，②和③都正确。设具有n个结点的满二叉树的高度为h，那么根据二叉树的性质有n=2h-1，从而有h=log2(n+1)，叶子结点的个数为n-2h-1-1=2h-1=(n+1)/2，因此④和⑤都正确。值得指出的是②和④是等价的，只是表述不同而已。综上所述，由于题干要求选最全面、最准确的，因此选D。

  • 第18题：

    最优二叉树(或哈夫曼树)是指权值为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

  • 第19题：

    哈夫曼树又称为（），它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL（）。
    最优二叉树；最小的二叉树
    略

  • 第20题：

    具有n个结点的完全二叉树若按层次从上到下，从左到右对其编号（根结点为1），则编号最大的分支结点序号是（），编号最小的分支结点序号是（），编号最大的叶子结点序号是（），编号最小的叶子结点序号是（）


    正确答案:[n/2]；1；n；[n/2]+1

  • 第21题：

    深度为k的完全二叉树至少有（）个结点，至多有（）个结点，具有n个结点的完全二叉树按层序从1开始编号，则编号最小的叶子的序号是（）。


    正确答案:2k-1；2k-1；2k-2+1

  • 第22题：

    填空题
    深度为k的完全二叉树至少有（）个结点，至多有（）个结点，具有n个结点的完全二叉树按层序从1开始编号，则编号最小的叶子的序号是（）。

    正确答案： 2k-1,2k-1,2k-2+1
    解析： 暂无解析

  • 第23题：

    填空题
    一棵二叉树的第i（i≥1）层最多有（）个结点；一棵有n（n>0）个结点的满二叉树共有（）个叶子结点和（）个非终端结点。

    正确答案： 2i-1,（n+1）/2,（n-1）/2
    解析： 暂无解析

相关内容