1、下面关于线性表的叙述中，正确的是

A、线性表采用顺序存储，必须占用一片连续的存储单元。

B、线性表采用顺序存储，便于进行插入和删除操作。

C、线性表采用链接存储，不必占用一片连续的存储单元。

D、线性表采用链接存储，便于插入和删除操作。

解析

顺序存储是按索引值从小到大存放在一片相邻的连续区域

采用链接存储，便于插入和删除操作，如果采用顺序存储，插入和删除时需要大量移动元素，参考数组的元素删除

线性表采用链接存储，在结点中存储link信息，不需占用连续存储单元

采用链接存储，便于插入和删除操作

2、下面的叙述中正确的是：

A、线性表在链式存储时，查找第i个元素的时间与i的数值无关。

B、线性表在顺序存储时，查找第i个元素的时间与i的数值成正比。

C、线性表在顺序存储时，查找第i个元素的时间与i的数值无关。

D、线性表在链式存储时，插入第i个元素的时间与i的数值成正比。

解析

线性表在链式存储时，查找第i个元素的时间与i的数值无关。 因为存储空间是不连续的，需要从头或者尾结点开始查找元素，i越大，时间越长，时间不可能与i无关

线性表在顺序存储时，查找第i个元素的时间与i的数值成正比。 因为存储空间是连续的，直接由i可以得到元素位置

线性表在顺序存储时，查找第i个元素的时间与i的数值无关。 因为存储空间是连续的，直接由i可以得到元素位置

线性表在链式存储时，插入第i个元素的时间与i的数值成正比。 因为存储空间是不连续的，插入第i个元素不需要移动其他元素。但是在插入之前从头搜索到第i个元素的指针，所以插入时间跟i相关

3、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(1),在给定值为x的结点后插入一个新结点的时间复杂度为O(n)。

解析

已知结点后插入，不需要移动其他结点位置，所以为O(1) 2. 先要查找到值为x的结点，需要O(n),再插入，不需要移动其他结点位置，需要O(1)，总共需要O(n) O(1)=O(n)

4、带头结点head的循环链表的尾结点tail的特点是: _____

答案： tail->next=head​

​​

​