3.对于顺序存储的线性表，其算法的时间复杂度为O(1)的运算应该是（）。
A.将n个元素从小到大排序
B.删除第i(1<=i<=n)个元素
C.改变第i(1<=i<=n)个元素
D在第i(1<=i<=n)个元素后插入一个新元素
顺序存储即顺序表，链式存储即链表
首先排除B和D，因为第i个元素不是最后一个元素，如果在表尾插入和删除元素，时间复杂度是为O(1)
删除第i个元素需要把i后面的元素都往前移
插入第i个元素需要把i后面的元素都往后移
所以BD排除
对于A选项，对n个元素排序最小也要O(n)，相关的排序算法类似冒泡算法等这里不做叙述
对于顺序表，是随机存取的，所以找第i个元素可以直接找，修改的时间复杂度为O(1)，故选C
作者在做这题的时候看成链式表了…
5.设线性表中有2n个元素，（）在单链表上实现要比在顺序表上实现效率更高。
A.删除所有值为x的元素
B.在最后一个元素的后面插入一个新元素
C.顺序输出前k个元素
D.交换第i个元素和第2n-i-1个元素的值（i=0,…,n-1）
选A，单链表是链式存储，删除只需要修改前结点的指针，顺序表删除的话需要移动大量的数据，所有对于本题来说单链表实现的效率更高
B选项需要先遍历单链表找到最后一个元素，顺序表可以直接读取最后一个元素
C选项单链表和顺序表效率相同
D选项在找到第2n-i-1的值时，单链表需要遍历，顺序表可以直接读取，所以单链表效率更低
7.给定有n个元素的一维数组，建立一个有序单链表的最低时间复杂度是（）
A.O(1)
B.O(n)
C.O(n2)
D.O(nlog2n)
本题的关键字是有序，即这个单链表的元素是有序的
本题可以有两个方向进行：
①直接插入排序，时间复杂度是O(n2)
②先排序数组，在插入单链表，排序数组的时间复杂度最好是O(nlog2n)
故选D
8.将长度为n的单链表链接在长度为m的单链表后面，其算法的时间复杂度采用大O形式表示应该是()
A.O(1)
B.O(n)
C.O(m)
D.O(n+m)
思路是，遍历m，找到m的尾结点，把指针域指向n链表的首结点，故算法的时间复杂度是O(m)
可以联想的是，如果m链表有尾指针的话，那么算法时间复杂度就是O(1)
10.在一个长度为n的带头结点的单链表h上，设有尾指针r，则执行（）操作与链表的表长有关。
A.删除单链表中的第一个元素
B.删除单链表中的最后一个元素
C.在单链表第一个元素前插入一个新元素
D.在单链表最后一个元素后插入一个新元素
首先排除A、C，因为第一个元素跟表长没有关系，D选项因为有尾指针，所以不用遍历单链表
B选项需要遍历单链表，所以跟表长有关
注意：
尾指针是指向尾结点的，不是尾结点的指针域
19.一个链表最常用的操作是在末尾插入结点和删除结点，则选用（）最节省时间
A.带头结点的双循环链表
B.单循环链表
C.带尾指针的单循环链表
D.单链表
插入和删除都要改变相邻结点的指针域，肯定是双循环链表最节省时间
BCD都要遍历
20.设对n（n>1）个元素的线性表运算只有4种：删除第一个元素；删除最后一个元素；在第一个元素之前插入新元素；在最后一个元素之后插入新元素，则最好使用（）
A.只有尾结点指针没有头结点指针的循环单链表
B.只有尾结点指针没有头结点指针的非循环双链表
C.只有头结点指针没有尾结点指针的循环双链表
D.既有头结点指针又有尾结点指针的循环单链表
对于A，删除最后一个元素时需要遍历单链表，所以时间复杂度是O(n)
对于B，因为没有头指针，所以需要遍历到最后一个元素，尾结点的指针指向头结点，时间复杂度是O(n)
C最四个运算的时间复杂度都尾O(1)
对于D，删除最后一个的时候还是需要遍历
错题的原因主要是对概念还比较模糊，其实答案都比较简单…
