10、若关键字的输入序列为20,9,2 ,11,13,30,22,16,17,15,18,10。 （1）试从空树开始顺序输入各关键字建立平衡二叉树。画出每次插入时二叉树的形态，若需要平衡化旋转则做旋转并注明旋转的类型； （2）计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度； （3）基于上面建树的结果，画出从树中删除22，删除2，删除10与9后树的形态和旋转类型。

题目

10、若关键字的输入序列为20,9,2 ,11,13,30,22,16,17,15,18,10。 （1）试从空树开始顺序输入各关键字建立平衡二叉树。画出每次插入时二叉树的形态，若需要平衡化旋转则做旋转并注明旋转的类型； （2）计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度； （3）基于上面建树的结果，画出从树中删除22，删除2，删除10与9后树的形态和旋转类型。

相似考题

1.引入线索二叉树的目的是()。A、加快查找结点的前驱或后继的速度B、为了能方便地找到双亲C、为了能在二叉树中方便地进行插入与删除D、使二叉树的遍历结果唯一

2.阅读以下说明和C语言函数，将应填入(n)处的字句写在答题纸的对应栏内。【说明】一棵非空二叉树中“最左下”结点定义为：若树根的左子树为空，则树根为“最左下”结点；否则，从树根的左子树根出发，沿结点的左子树分支向下查找，直到某个结点不存在左子树时为止，该结点即为此二叉树的“最左下”结点。例如，下图所示的以 A为根的二叉树的“最左下”结点为D，以C为根的子二叉树中的“最左下”结点为C。二叉树的结点类型定义如下：typedef stmct BSTNode{int data；struct BSTNode*lch,*rch；//结点的左、右子树指针}*BSTree；函数BSTree Find Del(BSTree root)的功能是：若root指向一棵二叉树的根结点，则找出该结点的右子树上的“最左下”结点*p，并从树于删除以*p为根的子树，函数返回被删除子树的根结点指针；若该树根的右子树上不存在“最左下”结点，则返回空指针。【函数】BSTrce Find_Del(BSTreeroot){ BSTreep,pre；if ( !root ) return NULL； /*root指向的二叉树为空树*/(1)； /*令p指向根结点的右子树*/if ( !p ) return NULL；(2)； /*设置pre的初值*/while(p-＞lch){ /*查找“最左下”结点*/pre=p；p=(3)；}if ((4)==root) /*root的右子树根为“最左下”结点*/pre-＞rch=NULL；else(5)=NULL； /*删除以“最左下”结点为根的子树*/reurn p；}

3.在查找算法中，可用平均查找长度(记为ASL)来衡量一个查找算法的优劣，其定义为：此处Pi为表中第i个记录被查找的概率，Ci为查找第i个记录时同关键字比较的次数，n为表中记录数。以下叙述中均假定每一个记录被查找的概率相等，即Pi=//n(i=1，2，…，n)。当表中的记录连续存储在一个一维数组中时，可采用顺序查找与折半查找方法(折半查找要求表是按关键字有序排列的)。顺序查找时的ASL为(19)，折半查找时的ASL为(20)。记录的关键字有序时，用二叉排序树查找记录，在最坏的情况下，ASL为(21)。当二叉排序树是一棵平衡树时，ASL为(22)。在平衡树上删除一个结点后可以通过旋转使其平衡，最坏的情形下需(23)次旋转。A．O(1)B．O(log2n)C．O(log2n2)D．O(nlog2n)E．O(n)

4.若某非空二叉树的先序序列和后序序列正好相同,则该二叉树的形态是什么?为什么?

更多“10、若关键字的输入序列为20,9,2 ,11,13,30,22,16,17,15,18,10。 （1）试从空树开始顺序输入各关键字建立平衡二叉树。画出每次插入时二叉树的形态，若需要平衡化旋转则做旋转并注明旋转的类型； （2）计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度； （3）基于上面建树的结果，画出从树中删除22，删除2，删除10与9后树的形态和旋转类型。”相关问题

  • 第1题：

    若某二叉树的后序遍历序列为KBFDCAE，中序遍历序列为BKEFACD，则该二叉树为 （58）。

    A.A

    B.B

    C.C

    D.D


    正确答案：A
    本题考查二叉树的遍历。二叉树的主要遍历方式有：前序遍历、中序遍历、后序遍历、层次遍历。如果已知中序遍历，并知道前序遍历与后序遍历中的任意一个，便可得到一棵唯一的二叉树。具体是怎么做的呢？利用的是遍历的特点。中序遍历的顺序是：左、根、右。而后序遍历的顺序是：左、右、根。回到题目里面来，从“后序遍历序列为KBFDCAE”，可以得知，二叉树的根结点为：E（此时已经可以排除选项C与选项D了）。继续分析，由“中序遍历序列为BKEFACD”，可以得知，二叉树的左子树包括结点：BK。右子树包括结点：FACD。重复上面的步骤，对左子树与左子树看成独立的两棵树进行分析。在后序遍历中，左子树的结点BK的顺序为“KB”，所以B是根结点；右子树的结点FACD的顺序为“FDCA”，所以右子树的根结点为A。当分析到这一步时，已经可以得到本题答案为A。

  • 第2题：

    若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是()。


    A.二叉排序树
    B.哈夫曼树
    C.堆
    D.AVL树


    答案：C
    解析：
    根据堆排序的定义，所有结点的孩子结点的值要么都大于该结点的值，要么都小于该结点的值，所以从堆的任一结点出发到根的路径上所经过的结点序列按其关键字有序。

  • 第3题：

    画出对长度为10的有序表进行折半查找的判定树（以序号1，2，……10表示树结点），并对上述序列进行折半查找，求等概率条件下，成功查找的平均查找长度。
    （1）

    （2）ASL=（1x1+2x2+3x4+4x3）/10=29/10
    略

  • 第4题：

    在任意一棵非空二叉树中，删除某结点后又将其插入，则所得二叉排序树与删除前原二叉树排序树相同。


    正确答案:错误

  • 第5题：

    某个二叉查找树（即二叉排序树）中进行查找时，效率最差的情形是该二叉查找树是（）。

    • A、完全二叉树
    • B、平衡二叉树
    • C、单枝树
    • D、满二叉树

    正确答案:C

  • 第6题：

    在结点数确定的二叉排序树上进行查找的平均查找长度与二叉树的形态有关，最差的情况是二叉排序树为（）树的时候。


    正确答案:单支树

  • 第7题：

    先序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的（）；先序遍历二叉树的（），先序遍历二叉树的（）。


    正确答案:根结点；左子树；右子树

  • 第8题：

    中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，中序遍历二叉树的（）；访问二叉树的（），中序遍历二叉树的（）。


    正确答案:左子树；根结点；右子树

  • 第9题：

    单选题
    二叉树的前序、中序和后序遍历法最适合采用__（1）__来实现。查找树中，由根结点到所有其他结点的路径长度的总和称为__（2）__，而使上述路径长度总和达到最小的树称为__（3）__。它一定是__（4）__。在关于树的几个叙述中，只有__（5）__是正确的。空白（4）处应选择（）
    A

    B-树

    B

    平衡树

    C

    非平衡树

    D

    穿线树


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

  • 第10题：

    填空题
    序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的（）；先序遍历二叉树的（），先序遍历二叉树的（）。

    正确答案： 根结点,左子树,右子树
    解析： 暂无解析

  • 第11题：

    判断题
    在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。
    A

    对

    B

    错


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

  • 第12题：

    单选题
    某个二叉查找树（即二叉排序树）中进行查找时，效率最差的情形是该二叉查找树是（）。
    A

    完全二叉树

    B

    平衡二叉树

    C

    单枝树

    D

    满二叉树


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

  • 第13题：

    在某个二叉查找树（即二叉排序树）中进行查找时，效率最差的情形是该二叉查找树是(59) 。

    A.完全二叉树

    B.平衡二叉树

    C.单枝树

    D.满二叉树


    正确答案：C
    本题考查数据结构基础知识。非空二叉查找树中的结点分布特点是左子树中的结点均小于树根，右子树中的结点均大于树根。因此，在二叉查找树中进行查找时，走了一条从树根出发到所找到结点的路径，到达一个空的子树则表明查找失败。根据定义，高度为h的满二叉树中有2h-l个结点，每一层上的结点数都达到最大值。完全二叉树的最高层只要求结点先占据左边的位置。例如，高度为3的满二叉树如下图(a)所示，具有6个结点的完全二叉树如下图(b)所示。在平衡二叉树中，任何一个结点的左子树高度与右子树高度之差的绝对值不大于1。单枝树中给每个结点只有1个子树。例如，具有3个结点的单枝树如下图所示。显然，在结点数确定后，二叉查找树的形态为单枝树时查找效率最差。

  • 第14题：

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

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

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



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

  • 第15题：

    在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。


    正确答案:错误

  • 第16题：

    若从二叉树的根结点到其它任一结点的路径上所经过的结点序列按其关键字递增有序，则该二叉树是（）。

    • A、二叉排序树
    • B、赫夫曼树
    • C、堆
    • D、平衡二叉树

    正确答案:C

  • 第17题：

    二叉树的前序、中序和后序遍历法最适合采用__（1）__来实现。查找树中，由根结点到所有其他结点的路径长度的总和称为__（2）__，而使上述路径长度总和达到最小的树称为__（3）__。它一定是__（4）__。在关于树的几个叙述中，只有__（5）__是正确的。空白（4）处应选择（）

    • A、B-树
    • B、平衡树
    • C、非平衡树
    • D、穿线树

    正确答案:C

  • 第18题：

    折半查找所对应的判定树，既是一棵二叉查找树，又是一棵理想平衡二叉树


    正确答案:正确

  • 第19题：

    序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的（）；先序遍历二叉树的（），先序遍历二叉树的（）。


    正确答案:根结点；左子树；右子树

  • 第20题：

    填空题
    中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，中序遍历二叉树的（）；访问二叉树的（），中序遍历二叉树的（）。

    正确答案： 左子树,根结点,右子树
    解析： 暂无解析

  • 第21题：

    填空题
    在结点数确定的二叉排序树上进行查找的平均查找长度与二叉树的形态有关，最差的情况是二叉排序树为（）树的时候。

    正确答案： 单支树
    解析： 暂无解析

  • 第22题：

    单选题
    若已知某二叉树的中序和后序遍历序列分别BCAEFD和CBFEDA，则该二叉树的先序序列为（）。
    A

    ABCDEF

    B

    ABDCEF

    C

    ABDCFE

    D

    ACBDFE


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

  • 第23题：

    单选题
    若从二叉树的根结点到其它任一结点的路径上所经过的结点序列按其关键字递增有序，则该二叉树是（）。
    A

    二叉排序树

    B

    赫夫曼树

    C

    堆

    D

    平衡二叉树


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

  • 第24题：

    判断题
    在任意一棵非空二叉树中，删除某结点后又将其插入，则所得二叉排序树与删除前原二叉树排序树相同。
    A

    对

    B

    错


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

相关内容