难道这就是传说中的错题集？

数据结构

第2章 线性表

1. 给定有n个元素的一维数组，建立一个有序单链表的最低时间复杂度为（）。

A. $O(1)$
B. $O(n)$
C. $O(n^2)$
D. $O(nlog_2n)$

错解：没错解，压根不会算
💡正解：D

解析：
要建立一个有序单链表，有两种主要的方法：

1. 先建立链表，然后依次插入建立有序表：这种方法的时间复杂度为$O(n^2)$。这是因为每插入一个元素，都需要遍历链表来找到插入位置，这相当于直接插入排序的过程。
2. 先将数组排好序，然后建立链表：这种方法的时间复杂度为O(nlog2n)。首先， 数组排序的最短时间复杂度是$O(nlog_2n)$。然后，建立链表的时间复杂度为$O(n)$，因为需要遍历排序后的数组来创建链表节点。因此，总的时间复杂度是$O(nlog_2n)$。

故最低时间复杂度为$O(nlog_2n)$

2. 将长度为n的单链表链接在长度为m的单链表后，其算法时间复杂度为（）。

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

错解：B
💡正解：C

解析：
先从头遍历长度为m的链表，找到该链表的尾节点，将其next指针指向n链表的首节点即可，故时间复杂度为$O(m)$。