求带权为2，3，5，7，8的最优二叉树T。

题目

求带权为2，3，5，7，8的最优二叉树T。

相似考题

1.在()中，任意一个结点的左、右子树的高度之差的绝对值不超过1。A.完全二叉树B.二叉排序树C.线索二叉树D.最优二叉树

2.假设一棵平衡二叉树的每个结点都表明了平衡因子b,试设计一个算法,求平衡二叉树的高度。

3.二叉树在线索化后，仍不能有效求解的问题是()。A、前序线索二叉树中求前序后继B、中序线索二叉树中求中序前驱C、中序线索二叉树中求中序后继D、后序线索二叉树中求后序后继

4.（ 4 ）霍夫曼算法是求具有最 【 4 】 带权外部路径长度的扩充二叉树的算法。

更多“求带权为2，3，5，7，8的最优二叉树T。”相关问题

  • 第1题：

    求下列运输问题的最优解(目标函数求最小值)。


    参考答案：

  • 第2题：

    给出叶赋权m叉树的定义,并求叶赋权分别为2,3,5,7,8的最优2叉树。


    答案：定义：设G=（V,E）是一颗根数，若max deg+（v）=m，则称G是m叉树（m-ary tree）。
    对于2，3，5，7，8先组合两个最小的权2+3=5，嘚，5，5，7，8，在所得序列中再组合5+5=10，重新排列后为7，8，10，在组合7+8=15，得10，15，最后组合10+15=25。
    2     3     5     7     8
           5     5     7     8
                 10    7     8
                 10          15
                               25
    所求的最优二叉树如下：


  • 第3题：

    二叉树的基本操作主要有()

    A、遍历

    B、求二叉树的深度

    C、求某个节点的左子女

    D、求某个节点的左子女


    参考答案：ABCD

  • 第4题：

    霍夫曼算法是求具有最【 】带权外部路径长度的扩充二叉树的算法。


    正确答案：小
    小 解析：霍夫曼算法是用来求具有最小带权外部路径长度的扩充二叉树的算法。

  • 第5题：

    用Huffman(霍夫曼)算法求带权的2，3，5，7，8的最优二叉树T，那么T的权为(32)， T中有(33)片树叶，共有(34)个结点。

    A．45

    B．50

    C．55

    D．60


    正确答案：C
    解析：霍夫曼算法的步骤是这样的：.从各个节点中找出最小的两个节点，给它们建一个父节点，值为这两个节点之和。.然后从节点序列中去除这两个节点，加入它们的父节点到序列中。重复上面两个步骤，直到节点序列中只剩下唯一一个节点。这时一棵最优二叉树就已经建成了，它的根就是剩下的这个节点。更据题目要求：所构成的树为：由图上可知；T的权为：2*3+3*3+5*2+7*2+8*2=55T中共有5片树叶9个节点

  • 第6题：

    ●在 (59) 中，任意一个结点的左、右子树的高度之差的绝对值不超过 1。

    (59)

    A．完全二叉树

    B．二叉排序树

    C．线索二叉树

    D．最优二叉树


    正确答案：A

  • 第7题：

    设T是正则二叉树，有6个叶子结点，那么树T的高度最多可以是(22)；最小可以是(23)；树T的内结点数是(24)。如果T又是Huffman最优树，且每个叶子结点的权分别是1，2，3，45，5，6，则最优树T的非叶子结点的权之和是(25)；权为1的叶子结点的高度是(26)。(注：树的根结点高度为1)

    A．7

    B．6

    C．5

    D．4


    正确答案：B

  • 第8题：

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

  • 第9题：

    （ ）是由权值集合{8，5，6，2}构造的哈夫曼树（最优二叉树）。


    答案：C
    解析：
    本题考查二叉树应用知识。构造最优二叉树的哈夫曼算法如下：①根据给定的n个权值{W1，W2，...，Wn}，构成n棵二叉树的集合F={T1，T2，...，Tn}，其中每棵二叉树Ti中只有一个带权为Wi的根结点，其左右子树均空。②在F中选取两棵权值最小的二叉树作为左、右子树构造一棵新的二叉树，置新构造二叉树的根结点的权值为其左、右子树根结点的权值之和。③从F中删除这两棵树，同时将新得到的二叉树加入到F中。重复②、③，直到F中只含一棵树时为止。这棵树便是最优二叉树(哈夫曼树)。根据题中给出的权值集合，构造哈夫曼树的过程如下图所示。

  • 第10题：

    关于钙化MR表现的描述，错误的是（）

    • A、T1加权为高信号
    • B、T2加权为低信号
    • C、T1加权为低信号
    • D、特殊情况钙化颗粒小，与蛋白结合时，T1加权为高信号
    • E、钙化组织的质子密度极少

    正确答案:A

  • 第11题：

    在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。


    正确答案:错误

  • 第12题：

    单选题
    二叉树在线索化后，仍不能有效求解的问题是（）
    A

    前序线索二叉树中求前序后继

    B

    中序线索二叉树中求中序后继

    C

    中序线索二叉树中求中序前趋

    D

    后序线索二叉树中求后序后继


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

  • 第13题：

    哈夫曼树又称为最优二叉树。()

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


    正确答案：正确

  • 第14题：

    带权路经长度最小的树称为()

    A、满二叉树

    B、完全二叉树

    C、哈夫曼树

    D、线索二叉树


    参考答案：C

  • 第15题：

    编写递归算法,求以二叉链表存储的二叉树的深度。


    参考答案：

  • 第16题：

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

    A．结点数

    B．叶结点数

    C．非叶结点数

    D．度为二的结点数


    正确答案：B

  • 第17题：

    关于哈夫曼树、最优二叉树、哈夫曼算法，有以下说法：

    ①最优二叉树的形态不唯一，但是其WPL值是唯一确定的。

    ②哈夫曼树一定是最优二叉树，但最优二叉树不一定由哈夫曼算法来构造。

    则______。

    A．①正确②错误

    B．①错误②正确

    C．都对

    D．都错


    正确答案：C
    解析：假设有n个权值{w1，w2，…，wn)，构造一棵有n个叶子结点的二叉树，则称带权路径长度WPL最小的二叉树为最优二叉树，亦称哈夫曼树。值得注意的是，最优二叉树的形态不唯一，但是其WPL值是唯一确定的。这好比一个班里，张三、李四和王五体型各异但身高一样，而且是最高的，显然最高的身高值只有一个。用哈夫曼算法构造出来的哈夫曼树一定是最优二叉树，定性地说，在哈夫曼算法中，每次构造新树时都是将权值最小的树尽量放在离根最远的地方，而将权值大的尽量放在离根近的地方，从而使得WPL最小。因此，哈夫曼树一定是最优二叉树。值得特别注意的是，哈夫曼算法可以确保构造出来的树是最优二叉树，但是最优二叉树并不一定非得用哈夫曼算法来构造。例如，给定权值{2，3，4，7，8，9}，可以构造出两棵最优二叉树T1、T2，如图3-72所示。显然它们的WPL都是80，所以T1、T2都是是最优二叉树。T1是用哈夫曼算法构造出来的，但T2却不是用哈夫曼算法构造出来的，而是用上文中提及的构造哈夫曼树最容易犯的错误想法构造出来的一棵树。从上面的例子可以看出，哈夫曼算法只是构造最优二叉树的“充分条件”，而不是“必要条件”。至于为什么将哈夫曼树称为最优二叉树，原因可能是由于哈夫曼最早给出了带有一般规律的构造最优二叉树的哈夫曼算法，为了纪念他，就用哈夫曼树来称呼所有的最优二叉树。

  • 第18题：

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


    正确答案：B

  • 第19题：

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

    A.

    B.

    C.

    D.


    正确答案：A

  • 第20题：

    某二叉树的先序遍历序列为c a b f e d g,中序遍历序列为a b c d e f g,则该二叉树是（ ）。

    A.完全二叉树
    B.最优二叉树
    C.平衡二叉树
    D.满二叉树

    答案：C
    解析：
    本题考查数据结构基础知识。二叉树的遍历主要有四种：前序遍历（先根遍历、先序遍历）：遵循“根-左-右”的递归遍历思想，根一定是当前子二叉树先序遍历序列的第一个元素；中序遍历（中根遍历）：遵循“左-根-右”的递归遍历思想，根位于是当前子二叉树中序遍历序列的中部位置，左边是当前根的左二叉树，右边是当前根的右二叉树；后序遍历（后根遍历）：遵循“左-右-根”的递归遍历思想，根一定是遍历序列的最后一个元素；层次遍历：遵循从上到下，直左而右的遍历思想，根一定是遍历序列的第一个元素。根据题意，本二叉树为：



    平衡二叉树或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。本题的二叉树满足平衡二叉树的特点要求，故本题选择C选项

  • 第21题：

    整数规划的最优解是先求相应的线性规划的最优解然后取整得到（ ）


    答案：错
    解析：

  • 第22题：

    求最大值的整数规划问题中，其松弛问题的最优解是整数规划问题最优解的上界。


    正确答案:正确

  • 第23题：

    判断题
    在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。
    A

    对

    B

    错


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

  • 第24题：

    填空题
    霍夫曼算法是求具有最（）带权外部路径长度的扩充二叉树的算法。

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

相关内容