itgle.com

9、已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（）A．○(n)B．○(m*n)C．○(min(m,n))D．○(max(m,n))

题目

9、已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（）

A．○(n)

B．○(m*n)

C．○(min(m,n))

D．○(max(m,n))

相似考题

1.（ 1 ）下列叙述中，正确的是A ）对长度为 n 的有序链表进行查找，最坏情况下需要的比较次数为 nB ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ n/2 ）C ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ log 2 n ）D ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ n log 2 n ）

2.在一个长度为n的单链表L中,删除链表中*p的前驱结点的时间复杂度为O(n)。()此题为判断题(对，错)。

3.建立一个长度为n的有序单链表的时间复杂度为()。A、O(n)B、O(1)C、O(n)2D、O(log2n)

4.在一个长度为n的循环链表中,删除其元素值为x的结点的时间复杂度为O(n)。()此题为判断题(对，错)。

更多“9、已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（）”相关问题

  • 第1题：

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

    A、O(m+n)

    B、O(n)

    C、O(m)

    D、O(1)


    参考答案：D

  • 第2题：

    下列叙述中正确的是( )。

    A．对长度为n的有序链表进行查找，最坏情况下需要的比较次数为n

    B．对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(n／2)

    C．对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(log2(下标)n)

    D．对长度为n的有序链表进行对分查找，最坏情况—卜需要的比较次数为(nlog2(下标)n)


    正确答案：C
    解析：二分法查找只适用于顺序存储的有序表，对于长度为n的有序线性表，最坏情况只需比较log2n次。

  • 第3题：

    将长度为m的单链表连接在长度为n的单链表之后,单链表的长度为()。

    A、m+n

    B、m*n


    参考答案：A

  • 第4题：

    下列叙述中正确的是

    A．对长度为n的有序链表进行查找，最坏情况下需要比较的次数为n

    B．对长度为n的有序链表进行对分查找，最坏情况下需要比较的次数为n/2

    C．对长度为n的有序链表进行对分查找，最坏情况下需要比较的次数为log2n

    D．对长度为n的有序链表进行对分查找，最坏情况下需要比较的次数为nlog2n


    正确答案：A
    解析：有序链表中定位元素需要通过指针逐个查找，所以对分查找的意义不大。选项A正确。

  • 第5题：

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

    A.堆排序

    B.有序链表查找

    C.希尔排

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


    正确答案：D

  • 第6题：

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


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

  • 第7题：

    以顺序查找方法从长度为n的顺序表或单链表中查找一个元素时，平均查找长度为（），时间复杂度为（）


    正确答案:(n+1)/2；O(n)

  • 第8题：

    在一个长度为n（n＞1）的单链表上，设有头和尾两个指针，执行（）操作与链表的长度有关。

    • A、删除单链表中的第一个元素
    • B、删除单链表中的最后一个元素
    • C、在单链表第一个元素前插入一个新元素
    • D、在单链表最后一个元素后插入一个新元素

    正确答案:B

  • 第9题：

    用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（）和（）。


    正确答案:O（1）；O（n）

  • 第10题：

    填空题
    设长度为n的链队列用单循环链表表示，若只设头指针，则入队和出队操作的时间复杂度分别为（）和（）；若只设尾指针，则入队和出对操作的时间复杂度分别为（）和（）。

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

  • 第11题：

    判断题
    已知两个定义域的基数分别为m和n，则它们的笛卡儿积中的元组数为m+n。
    A

    对

    B

    错


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

  • 第12题：

    单选题
    下列叙述中正确的是（　　）。
    A

    对长度为n的有序链表进行查找，最坏情况下需要的比较次数为n

    B

    对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为（n/2）

    C

    对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为（log2n）

    D

    对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为（nlog2n）


    正确答案： B
    解析：
    对于顺序查找，在最坏的情况下查找的是链表的最后一个元素，或者查找的元素不在表中，此时需要比较n次，A项正确。对分查找只适用于顺序存储的有序表，对于长度为n的有序线性表，最坏情况只需比较log2n次，BCD三项错误。答案选择A选项。

  • 第13题：

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

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

    B．(m+n+1)

    C．O(m+n)

    D．不确定


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

  • 第14题：

    （ 1 ）下列叙述中正确的是

    A ）对长度为 n 的有序链表进行查找，最坏清况下需要的比较次数为 n

    B ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ n/2 ）

    C ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ log 2 n ）

    D ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ nlog 2 n ）


    正确答案：C

  • 第15题：

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

    A.O(1)

    B.O(n)

    C.O(m)

    D.O(m+n)


    参考答案：C

  • 第16题：

    设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)。

  • 第17题：

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

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

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

  • 第18题：

    已知两个定义域的基数分别为m和n，则它们的笛卡儿积中的元组数为m+n。


    正确答案:错误

  • 第19题：

    设长度为n的链队列用单循环链表表示，若只设头指针，则入队和出队操作的时间复杂度分别为（）和（）；若只设尾指针，则入队和出对操作的时间复杂度分别为（）和（）。


    正确答案:O(n）；O(1)；O(1)；O(1)

  • 第20题：

    用循环链表表示的队列长度为n，若只设头指针，则出对和入对的时间复杂度分别是（）和（）；若只设尾指针，则出队和入队的时间复杂度分别是（）和（）。


    正确答案:0（1）；0（n）；0（n）；0（1）

  • 第21题：

    填空题
    用循环链表表示的队列长度为n，若只设头指针，则出对和入对的时间复杂度分别是（）和（）；若只设尾指针，则出队和入队的时间复杂度分别是（）和（）。

    正确答案： 0（1）,0（n）,0（n）,0（1）
    解析： 暂无解析

  • 第22题：

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

    O（1）

    B

    O（n）

    C

    O（m）

    D

    O（m+n）


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

  • 第23题：

    填空题
    以顺序查找方法从长度为n的顺序表或单链表中查找一个元素时，平均查找长度为（），时间复杂度为（）

    正确答案： (n+1)/2,O(n)
    解析： 暂无解析

  • 第24题：

    填空题
    用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（）和（）。

    正确答案： O（1）,O（n）
    解析： 在带头指针的循环链表中，出队即是删除开始结点，这只需修改相应指针；入队即是在终端结点的后面插入一个结点，这需要从头指针开始查找终端结点的地址。

相关内容