考虑规模为n的二叉搜索树中，put, get, del, in 四个方法的时间复杂度数量级。四个方法中，有（）个方法在最差情况下，具有O（n)的时间复杂度A．1B．2C．3D．4

题目

考虑规模为n的二叉搜索树中，put, get, del, in 四个方法的时间复杂度数量级。四个方法中，有（）个方法在最差情况下，具有O（n)的时间复杂度

A．1

B．2

C．3

D．4

相似考题

1.下列排序方法中,在最坏情况下算法的时间复杂度为 O(n^2)的有________。A、堆排序B、快速排序C、希尔排序D、冒泡排序

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

3.从二叉搜索树中查找一个元素时，其时间复杂度大致为______。A．O(n)B．O(1)C．O(log2n)D．O(n2)

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

更多“考虑规模为n的二叉搜索树中，put, get, del, in 四个方法的时间复杂度数量级。四个方法中，有（）个方法在最差情况下，具有O（n)的时间复杂度”相关问题

  • 第1题：

    对n个结点的二叉树进行遍历，错误的说法是( )。

    A．不同遍历方法的时间复杂度一样

    B．用中序遍历的方式时间复杂度为O(n)

    C．后序遍历的空间复杂度为O(n)

    D．遍历的时间复杂度和空间复杂度都为O(n2)


    正确答案：D
    解析：遍历二叉树的算法中的基本操作是访问结点，不论按哪种次序进行遍历，对含n个结点的二叉树，时间复杂度都为O(n)，所需的辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n，则空间复杂度也为O(n)。

  • 第2题：

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

    A．O(n)

    B．O(1)

    C．O(log2n)

    D．O(n2)


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

  • 第3题：

    用归并排序方法，在最坏情况下的时间复杂度为( )。

    A．O(n+1)

    B．O(n2)

    C．O(log2n)

    D．O(nlog2n)


    正确答案：D
    解析：一个完整的归并排序需要进行[log2n)次，实现归并排序需要和代派序列元素个数等量的辅助空间，其时间复杂度为O(nlog2n)。

  • 第4题：

    直接选择排序的平均时间复杂度为(17)。最好情况下时间复杂度为O(n)的排序算法是(18)。在最好和最花情况下的时间复杂度均为O(nlogn)且稳定的排序方法是(19)。

    A．O(n)

    B．O(nlogn)

    C．O(n2)

    D．O(logn)


    正确答案：C

  • 第5题：

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

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

    正确答案:C

  • 第6题：

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

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

    正确答案:B

  • 第7题：

    在时间复杂度为O（n2）的所有排序方法中，（）排序方法是不稳定的。


    正确答案:直接选择

  • 第8题：

    在时间复杂度为O（nlog2n）的所有排序方法中，（）排序方法是稳定的。


    正确答案:归并

  • 第9题：

    填空题
    在时间复杂度为O（nlog2n）的所有排序方法中，（）排序方法是稳定的。

    正确答案： 归并
    解析： 暂无解析

  • 第10题：

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

    O（n）

    B

    O（1）

    C

    O（log2n）

    D

    O（n2）


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

  • 第11题：

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

     O（n）

    B

     O（1）

    C

     O（log2n）

    D

     O（n2）


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

  • 第12题：

    填空题
    在时间复杂度为O（n2）的所有排序方法中，（）排序方法是不稳定的。

    正确答案： 直接选择
    解析： 暂无解析

  • 第13题：

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

    A．O(1)

    B．O(n)

    C．

    D．O(n2)


    正确答案：C
    解析：从一棵二叉搜索树中查找一个元素时，大约需要树的寓度次比较，即时间复杂度大致为。

  • 第14题：

    用堆排序方法，在最坏情况下的时间复杂度为( )。

    A．O(n+1)

    B．O(n2)

    C．O(log2n)

    D．O(n log2n)


    正确答案：D

  • 第15题：

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

    A．0(n)

    B．O(1)

    C．0(log2n)

    D．O(n2)


    正确答案：C
    解析：如果二叉搜索树为平衡二叉树，查找一个元素的最坏时间复杂度为O(log2n)。

  • 第16题：

    具有n个顶点e条边的无向图，若用邻接矩阵作为存储结构，则深度优先或广度优先搜索遍历的时间复杂度为(48)；若用邻接表作为存储结构，则深度优先或广度优先搜索遍历时的时间复杂度为(49)；深度优先或广度优先搜索遍历的空间复杂度为(50)。

    A．O(n2)

    B．O(n)

    C．O(n-1)

    D．O(n+1)


    正确答案：A

  • 第17题：

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

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

    正确答案:C

  • 第18题：

    根据n个元素建立一棵二叉搜索树时，其时间复杂度大致为（）。

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

    正确答案:D

  • 第19题：

    对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（n）。


    正确答案:正确

  • 第20题：

    单选题
    插入排序是一种简单实用的工具，在对数组排序时，我们可能用二分查找，对要插入的元素快速找到在已经排好元素序列中的位置。下面的描述中正确的是（）。
    A

    二分查找的时间复杂度为O（lgN），因此排序的时间复杂度为O（N*lgN）

    B

    二分查找的时间复杂度为O（N），因此排序的时间复杂度为O（N*lgN）

    C

    二分查找的时间复杂度为O（lgN），因此排序的时间复杂度为O（N*N）

    D

    二分查找的时间复杂度为O（N），因此排序的时间复杂度为O（N*N）


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

  • 第21题：

    单选题
    根据n个元素建立一棵二叉搜索树时，其时间复杂度大致为（）。
    A

    O（n）

    B

    O（log2n）

    C

    O（n2）

    D

    O（nlog2n）


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

  • 第22题：

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

     O（n）

    B

     O（1）

    C

     O（log2n）

    D

     O（n2）


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

  • 第23题：

    判断题
    对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（n）。
    A

    对

    B

    错


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

  • 第24题：

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

    O（1）

    B

    O（log2n）

    C

    O（n）

    D

    O（nlog2n）


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

相关内容