关于红黑树和AVL树，以下哪种说法不正确（）。A、两者都属于自平衡二叉树B、两者查找，插入，删除的时间复杂度相同C、包含n个内部节点的红黑树的高度是O（log（n））D、JDK的TreeMap是一个AVL的实现

题目

关于红黑树和AVL树，以下哪种说法不正确（）。

  • A、两者都属于自平衡二叉树
  • B、两者查找，插入，删除的时间复杂度相同
  • C、包含n个内部节点的红黑树的高度是O（log（n））
  • D、JDK的TreeMap是一个AVL的实现
相似考题

1.在二叉排序树中插入一个结点的时间复杂度为()。A、O(1)B、O(n)C、O(log2n)D、O(n2)

2.红黑树中已经有n个数据，寻找某个key是否存在的时间复杂度为()A.o(logn)B.o(n)C.o(n二次方)D.o(1)

3.关于红黑树和AVL树，以下哪种说法不正确()A.两者都属于自平衡二叉树B.两者查找,插入，删除的时间复杂度相同C.包含n个内部节点的红黑树的高度是O(log(n))D.JDK的TreeMap是一个AVL的实现

4.设平衡二叉排序树(AVL树)的节点个数为n，则其平均检索长度为A．O(1)B．O(log2n)C．O(n)D．O(n log2n)

更多“关于红黑树和AVL树，以下哪种说法不正确（）。A、两者都属于自平衡二叉树B、两者查找，插入，删除的时间复杂度相同C、包含n个内部节点的红黑树的高度是O（log（n））D、JDK的TreeMap是一个AVL的实现”相关问题

  • 第1题：

    下列说法中错误的是：()

    A.插入排序某些情况下复杂度为O(n)

    B.排序二叉树元素查找的复杂度可能为O(n)

    C.对于有序列表的排序最快的是快速排序

    D.在有序列表中通过二分查找的复杂度一定是O(log2n)


    正确答案：C

  • 第2题：

    设有n个结点的AVL树，其平均查找长度为()。

    A、Ο(1)

    B、Ο(log2n)

    C、Ο(n)

    D、Ο(nlog2n)


    参考答案：B

  • 第3题：

    建堆是将所有元素按照初始顺序填充到一个()中。

    A.二叉树

    B.平衡二叉树

    C.红黑树

    D.完全二叉树


    正确答案：D

  • 第4题：

    设平衡的二叉排序树(AVL树)的结点个数为n，则其平均检索长度为

    A．O(1)

    B．O(log2n)

    C．O(n)

    D．O(nlog2n)


    正确答案：B
    解析：平衡二叉树又称AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1，若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡酌。因为AVL树上任何结点的左右子树的深度之差都不超过1，则可以证明它的深度和log2n是同数量级的(N为结点个数)。因此，它的平均查找长度也和log2n同数量级。

  • 第5题：

    设平衡的二叉排序树(AVL树）的结点个数为n,则其平均检索长度为

    A．O

    B．O(log2n)

    C．O(n)

    D．O(nlog2n)


    正确答案：B
    解析：平衡二叉树又称AVL树,它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1,若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。因为AVL树上任何结点的左右子树的深度之差都不超过1,则可以证明它的深度和log2n是同数量级的(N为结点个数）。因此,它的平均查找长度也和log2n同数量级。

  • 第6题：

    设平衡的---X排序树(AVL树)的结点个数为n，则其平均检索长度为

    A．O(1)

    B．O(log2n)

    C．O(n)

    D．O(nlog2n)


    正确答案：B
    解析：平衡的二叉排序树是对二叉排序树的一种平衡化处理。结点的平衡因子定义为其右于树高度减去左予树高度，若任意结点的平衡因子均取值-1，或0，或1，则此二叉排序树为平衡的二叉排序树(AVL)。平衡二叉树的检索方法与一般的二叉树完全一样，其优点是总能保持检索长度为O(1og2n)。

  • 第7题：

    设平衡的二叉排序树(AVL树)的结点个数为n，则其平均查找长度的数量级为 ______。

    A．O(1)

    B．0(log2n)

    C．O(n)

    D．0(nlog2n)


    正确答案：B
    解析：平衡二叉树又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。因为AVL树上任何结点的左右子树的深度之差都不超过1，则可以证明它的深度和logN是同数量级的(N为结点个数)。由此，它的平均查找长度也和logN同数量级。

  • 第8题：

    下面关于数据结构的叙述中，正确的叙述是 ______。

    A．顺序存储方式的优点是存储密度大，且插入、删除运算效率高

    B．链表中的每一个节点都恰好包含一个指针

    C．包含n个节点的二叉排序树的最大检索长度为log2n

    D．将一棵树转换为二叉树后，根节点没有右子树


    正确答案：D

  • 第9题：

    一棵有n个节点的完全二叉树的高度是（）

    • A、n/2
    • B、log2n
    • C、（log2n）/2
    • D、（log2n）+1

    正确答案:D

  • 第10题：

    从二叉搜索树中查找一个元素时，其时间复杂度大致为（）

    • A、O（n）
    • B、O（1）
    • C、O（log2n）
    • D、O（n2）

    正确答案:C

  • 第11题：

    向二叉搜索树中插入一个元素时，其时间复杂度大致为（）。

    • A、O（1）
    • B、O（log2n）
    • C、O（n）
    • D、O（nlog2n）

    正确答案:B

  • 第12题：

    单选题
    从具有n个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为（）。
    A

     O（n）

    B

     O（1）

    C

     O（log2n）

    D

     O（n2）


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

  • 第13题：

    在二叉排序树中插入一个结点的时间复杂度为()。

    A、O(1)

    B、O(n)

    C、O(log2n)

    D、O(n)


    参考答案：B

  • 第14题：

    从二叉搜索树中查找一个元素时，其时间复杂度大致为______。

    A．O(n)

    B．O(1)

    C．O(log2n)

    D．O(n2)


    正确答案：C

  • 第15题：

    设平衡的二叉排序树(AVL树)的结点个数为n，则其平均检索长度为

    A．O(1)

    B．O(log2n)

    C．O(n)

    D．O(n log2n)


    正确答案：B
    解析：平衡二叉树又称AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1，若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。因为AVL树上任何结点韵左右子树的深度之差都不超过1，则可以证明它的深度和log2n是同数量级的(N为结点个数)。因此，它的平均查找长度也和log2n同数量级。

  • 第16题：

    设平衡的二叉排序树(AVL树)的节点个数为n，则其平均检索长度为______。

    A．O(1)

    B．O(log2n)

    C．O(n)

    D．O(nlog2n)


    正确答案：B

  • 第17题：

    从具有n个结点的二叉查找树中查找一个元素时，在最坏情况下进行成功查找的时间复杂度为(51)。

    A．O(n)

    B．O(1)

    C．O(log2n)

    D．O(n2)


    正确答案：A
    解析：当二叉查找树严重不平衡时，二叉查找树有n层，最坏情况就是把n个结点都比较一遍才查找成功。

  • 第18题：

    设平衡的二叉排序树(AVL树)的结点个数为n，则其平均查找长度的数量级为________。

    A．O(1)

    B．O(log2n)

    C．O(n)

    D．O(nlog2n)


    正确答案：B
    解析：平衡二叉树又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。因为AVL树上任何结点的左右子树的深度之差都不超过1，则可以证明它的深度和logN是同数量级的(N为结点个数)。由此，它的平均查找长度也和logN同数量级。

  • 第19题：

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

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

    ②具有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。

  • 第20题：

    关于AVL(平衡二叉树)，下列说法错误的是()。

    A.左子树与右子树高度差最多为1
    B.插入操作的时间复杂度为0(logn)
    C.平衡二叉树是二叉排序树中的一种
    D.使用平衡二叉树的目的是为了节省空间

    答案：D
    解析：
    平衡二叉树是平衡二又排序树的简称。它或者是一棵空树，或者是具有下列性质的二叉树：①左、右子树的高度之差不超过1；②左、右子树也是平衡二叉树；平衡二叉树没有节省空间，引入其目的是防止排序二叉树左、右子树高度失衡。

  • 第21题：

    二叉树__（1）__。在完全二叉树中，若一个结点没有__（2）__，则它必定是叶结点。每棵树都能唯一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子树是N在原树里对应结点的__（3）__，而N的右子树是它在原树里对应结点的__（4）__。二叉排序树的平均检索长度为__（5）__。 空白（5）处应选择（）

    • A、O（n2）
    • B、O（n）
    • C、O（log2n）
    • D、O（nlog2n）

    正确答案:C

  • 第22题：

    从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致为（　）。

    • A、 O（n）
    • B、 O（1）
    • C、 O（log2n）
    • D、 O（n2）

    正确答案:C

  • 第23题：

    单选题
    某二叉树为单枝树（即非叶子节点只有一个孩子节点）且具有n个节点（n>1）则该二叉树（）。
    A

    共有n层，每层有一个节点

    B

    共有log2n层，相邻两层的节点数正好相差一倍

    C

    先序遍历序列与中序遍历序列相同

    D

    后序遍历序列与中序遍历序列相同


    正确答案： D
    解析： 题考查数据结构中二叉树的基本概念和运算。 若二叉树为单枝树，那么n个节点就分布在n层上。遍历序列则与遍历方法和二叉树的形态有关。例如，对于三个节点的单枝二叉树(A、B、C的层次依次增高)，其形态可为： [*] 考查它们的先序、中序和后序遍历序列，先序遍历序列都为A、B、C，而中序和后序遍历序列则有所不同。

相关内容