一、选择合适的存储结构：

默认的单链表不带头结点，尾结点。

 

默认的循环单链表带尾指针，不带头指针。(一般对循环单链表只设尾指针不设头指针，其原因是，如果设的是头指针，对表尾进行操作需要O(n)的时间复杂度，而若设的是尾指针r，那么r->next即为头指针，对表头与表尾进行操作都只需要O(1)的时间复杂度。)

 

默认

 

1、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用 _______存储方式最节省运算时间。
A．单链表
B．仅有头指针的单循环链表
C．双链表
D．仅有尾指针的单循环链表

A:单链表只能单向遍历，只能由链表头向链表尾遍历，因此要找到最后一个元素必须遍历整个表。

B:查找到最后一个元素需要时间O(n)，比D慢

C:没有指定双链表是否含有尾指针，默认插入元素时，需要从头撸到尾部，再执行插入，时间复杂度为O(n)。想要在头部或尾部快速执行插入和删除元素，需要增加头指针或尾指针，可以看java.util.LinkedList的实现，它就是一个双链表，底层使用了last始终指向链表的最后一个元素，方便插入和删除元素。

D:要插入结点，只要改变一下指针即可，要删除头结点，只要将指针移动到头结点即可。

2、设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间。

A.单链表
B.单循环链表
C.带尾指针的单循环链表
D.带头结点的双循环链表

在链表的末尾插入结点或删除尾结点时，需要修改其相邻结点的指针域，因此需要寻找尾结点和尾结点的前驱节点。
A、B：对于单链表或单循环链表，寻找尾结点的时间复杂度均为O(n)；
C ：对于带尾指针的单循环链表，可以直接通过尾指针定位到尾结点进行插入，时间复杂度为O(1)，但在删除时还是需要遍历表来找到尾结点的直接前驱结点，时间复杂度为O(n)；
D：对于带头结点的双循环链表，可以通过时间复杂度O(1)直接定位到尾结点或尾结点的前驱节点

3.若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式()

A.单链表
B.双向链表
C.单循环链表
D.顺序表

这里是问第i个要插入前驱，只能是双循环链表，不然找前驱花时间。

一般顺序表查看更好，链表删除与插入更好，虽然这里还要取其前驱的值，但是我们知道顺序表相当与数组，可以知道把下标减一就是前驱。

线性表中最常用的操作是取第i个元素，所以，应选择随机存取结构即顺序表，同时在顺序表中查找第i个元素的前趋也很方便。
单链表和单循环链表既不能实现随机存取，查找第i个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能实现随机存取。

4.

若线性表最常用的操作是存取第i个元素及其前趋的值,则采用( )存储方式节省时间。

A.单链表

B.双链表

C.单循环链表

D.顺序表

一般顺序表查看更好，链表删除与插入更好，虽然这里还要取其前驱的值，但是我们知道顺序表相当与数组，可以知道把下标减一就是前驱。

 

二、计算题：

1.对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。删除一个元素时平均要移动表中的（n-1）/2个元素。

s=0+1+2+3+....+n-1=n(n-1)/2

avr=s/n=(n-1)/2

2.某线性表用带头结点的循环单链表存储，头指针为head，当head->next->next->next = head成立时，线性表的长度可能是（）

A.0

B.1

C.2

D.3

对于此题：头结点不算一个长度：head用h代替

0：对一个空循环单链表有 h = h , h->n=h , h->n->n=h , h->n->n->n=h

1: h=头 h->n = 1 h->n->n=头 h->n->n->n = 1

2:h=头 h->n = 1 h->n->n=2 h->n->n->n = h

3:h=头 h->n = 1 h->n->n=2 h->n->n->n = 3

3.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为O(n) O(n)

 

三、指针操作题：

1.设单循环链表中结点的结构为（data, next），且rear是指向非空的带头结点的单循环链表的尾结点的指针。若想删除链表的首元结点，则应执行的操作是()。

A. s = rear; rear = rear->next; free(s);

B. s = rear->next; rear->next = s->next; free(s);

C. s = rear->next ->next ; rear = rear->next->next; free(s);

D. s = rear->next->next; rear->next->next = s->next; free(s);

首先需要明白：

头指针指向头结点，头结点不是第一个结点。

头结点的指针指向第一个结点，第一个结点又叫首元结点。

题目中为循环单链表，那么有下面关系：

尾指针指向尾结点

尾结点的指针指向头结点：rear->next

第一个结点/首元结点：rear->next->next 是要被删除的结点

2.

四、概念理解：

1.线性表中的所有数据元素的数据类型必须相同。√
2.顺序存储结构属于静态结构，链式结构属于动态结构。×：静态链表