●设A和B是两个单链表，其表中元素有序递增。请分析算法的时间复杂度。其时间复杂度为 (40) 。(40) A．O(m+n-1)B．(m+n+1)C．O(m+n)D．不确定

题目

●设A和B是两个单链表，其表中元素有序递增。请分析算法的时间复杂度。其时间复杂度为 (40) 。

(40) A．O(m+n-1)

B．(m+n+1)

C．O(m+n)

D．不确定

相似考题

1.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为()A、O(m+n)B、O(n)C、O(m)D、O(1)

2.●在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是 (53) 。(53) A．O(1)B．O(n)C．O(nlogn)D．O(n2)

3.已知一个长度为n的单链表中的所有结点是有序(递增)的,以下叙述中正确的是()。A.插入一个结点使之有序的算法的时间复杂度为O(1)B.删除最大值结点使之有序的算法的时间复杂度为O(1)C.找最小值结点的算法的时间复杂度为O(1)D.以上都不对

4.在有序双向链表中定位删除一个元素的平均时间复杂度为()A.O(1)B.O(N)C.O(logN)D.O(N*logN)

更多“●设A和B是两个单链表，其表中元素有序递增。请分析算法的时间复杂度。其时间复杂度为 (40) 。(40) A．O(m+n-1)B．(m+n+1)C．O(m+n)D．不确定”相关问题

  • 第1题：

    将长度为n的单链表链接到长度为m的单链表之后的算法的时间复杂度是()。

    A.O(1)

    B.O(n)

    C.O(m)

    D.O(m+n)


    参考答案：C

  • 第2题：

    在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是(53)。

    A．O(1)

    B．O(n)

    C．O(nlogn)

    D．O(n2)


    正确答案：B
    解析：本题主要考核有序单链表上的插入操作及算法分析。对数据结构的任何操作都不能改变其原有的结构特性。因此，在有序单链表中插入一个新结点后，仍然要保持它的有序性。插入操作的关键是查找插入位置，主要时间也是花在插入位置的查找上。n个结点的单链表，有，n+1个可能插入的位置，即第一个结点之前和每一个结点之后。在第一个结点之前插入，需比较一次；在第一个结点之后插入需比较两次；……；在第，n个结点之后插入需查找次。如果在每一个位罩上作插入的概率相等，即则在有序单链表上查找插入位置的平均比较次数为：

  • 第3题：

    设A和B是两个单链表，其表中元素有序递增。请分析算法的时间复杂度。其时间复杂度为(40)。

    A．O(re+n-1)

    B．(m+n+1)

    C．O(m+n)

    D．不确定


    正确答案：C
    解析：设A表和B表的长度分别为m和n，则该算法的时间复杂度为O(m+n)。

  • 第4题：

    设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为_______。

    A.O(1)

    B.O(log2n)

    C.O(n)

    D.O(n2)


    正确答案：C

  • 第5题：

    下面算法的时间复杂度为()

    A.O(1)

    B.O(n)

    C.O(n*n)

    D.O(n!)


    正确答案：B

  • 第6题：

    设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n表示，则该算法的时间复杂度为(1)。

    A．O(lgn)

    B．O(nlgn)

    C．O(n)

    D．O(n2)


    正确答案：B
    解析：运用数学递推公式，可以推算出数量级O(nlgn)。

  • 第7题：

    设有n个元素的向量，逐个输入其中的元素值，建立一个有序单链表的时间复杂度是(51)。

    A．O(1)

    B．O(n)

    C．O(n2)

    D．O(nlog2n)


    正确答案：C
    解析：由于需要进行逐个查找插入位置，逐个输入其中的元素值，所以建立一个有序单链表的时间复杂度为：1+2+3+…+n-1=n*(n-1)/2=O(n2)。

  • 第8题：

    设图G采用邻接表存储，则拓扑排序算法的时间复杂度为( )

    A．O(n)

    B．O(n+e)

    C．O(n2)

    D．O(n×e)


    正确答案：B

  • 第9题：

    将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为()。

    A.O(n)
    B.0(1)
    C.O(m)
    D.O(m+n)

    答案：C
    解析：
    要将长度为n的单链表接在长度为m的单链表之后，必须从单链表的头结点沿链找到长度为m的单链表的最后一个结点，所以时间复杂度为O(m)。

  • 第10题：

    建立一个长度为n的有序单链表的时间复杂度为()


    答案：C
    解析：
    建立有序单链表的时间复杂度是O(n)，对单链表插入节点时，先遍历单链表，找到插入位置，将节点插入。

  • 第11题：

    统计单链表中元素个数的时间复杂度是（）。


    正确答案:O(n)

  • 第12题：

    单选题
    将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为（）。
    A

    O（1）

    B

    O（n）

    C

    O（m）

    D

    O（m+n）


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

  • 第13题：

    对于一个链串s,查找第i个元素的算法的时间复杂度为()。

    A.O(1)

    B.О(n)

    C.O()

    D.以上都不对


    参考答案：B

  • 第14题：

    下面程序段的时间复杂度是(9)。for(i=0，k=0；＜n；1++){ k+=A[i][j]； for(j=1；j＜m；j++) A[i][j]=1}

    A．O(n)

    B．O(m+n+1)

    C．O(m+n)

    D．O(m*n)


    正确答案：D
    解析：时间复杂度是解决问题的时间和问题的规模之间的关系，即解决问题所耗费的时间随问题规模增长成怎样的增长对应关系。本题中最内部的循环的执行次数为m*n，所以整段程序的复杂度为O(m*n)。

  • 第15题：

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

    A．O(n)

    B．O(nlogn)

    C．O(n2)

    D．O(logn)


    正确答案：C

  • 第16题：

    设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为____。

    A.O(1)

    B.O(n)

    C.O(n2)

    D.O(log2n)


    正确答案：D

  • 第17题：

    设表的长度为n。在下列结构所对应的算法中，最坏情况下时间复杂度最低的是（）

    A.堆排序

    B.有序链表查找

    C.希尔排

    D.循环链表中寻找最大项


    正确答案：D

  • 第18题：

    对于n元素的向量，将其建立为一个有序单链表的时间复杂度为( )。

    A．O(1)

    B．O(n)

    C．O(n2)

    D．O(nlog2n)


    正确答案：C
    解析：为n个元素建立一个单链表的时间复杂度为O(n)，在对其元素有序的过程中，还需要相同的时间复杂度，因此建立一个有序单链表的时间复杂度为O(n2)。

  • 第19题：

    在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是()

    A.O(1)

    B.O(n)

    C.O(n2)

    D.O(nlogn)


    正确答案： B

  • 第20题：

    ●(37)有n个结点的有序单链表中插入一个新结点并保持有序的运算的时间复杂度为(37)。

    (37)A.O(1)

    B. O(logn)

    C.O(n)

    D. O(n2)


    正确答案：C

  • 第21题：

    设一个有序的单链表中有n个节点，现要求插入一个新节点后使得单链表仍然保持有序，则该操作的时间复杂度为()。


    答案：C
    解析：
    对单链表进行插入节点的操作，就是对单链表进行查找，找到节点需要插入的位置，然后修改指针，将节点插入单链表。

  • 第22题：

    将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为（）。

    • A、O（1）
    • B、O（n）
    • C、O（m）
    • D、O（m+n）

    正确答案:C

  • 第23题：

    填空题
    统计单链表中元素个数的时间复杂度是（）。

    正确答案： O(n)
    解析： 暂无解析

相关内容