一、单项选择题
01．关于线性表的顺序存储结构和链式存储结构的描述中，正确的是（ )。
Ⅰ.线性表的顺序存储结构优于其链式存储结构
Ⅱ.链式存储结构比顺序存储结构能更方便地表示各种逻辑结构
Ⅲ.若频繁使用插入和删除结点操作，则顺序存储结构更优于链式存储结构
IV.顺序存储结构和链式存储结构都可以进行顺序存取
A.Ⅰ、Ⅱ、Ⅲ
B.Ⅱ、IV
C.Ⅱ、Ⅲ
D.Ⅲ、IV
02.对于一个线性表，既要求能进行较快速地插入和删除，又要求存储结构能反映数据之间
的逻辑关系，则应该用( ) 。
A.顺序存储方式 B.链式存储方式 C．散列存储方式 D.以上均可以
03．链式存储设计时，结点内的存储单元地址（ ).
A.一定连续 B.一定不连续 C.不一定连续 D.部分连续，部分不连续
04.下列关于线性表说法中，正确的是（)。
Ⅰ.顺序存储方式只能用于存储线性结构
Ⅱ.在一个设有头指针和尾指针的单链表中，删除表尾元素的时间复杂度与表长无关
Ⅲ．带头结点的单循环链表中不存在空指针
IV.在一个长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度为O(n)
V．若用单链表来表示队列，则应该选用带尾指针的循环链表
A.Ⅰ、Ⅱ、 B.Ⅰ、Ⅲ、IV、V
C. IV、V D.Ⅲ、IV、V
05．设线性表中有2n个元素，()在单链表上实现要比在顺序表上实现效率更高。
A．删除所有值为x的元素
B．在最后一个元素的后面插入一个新元素
C.顺序输出前k个元素
D.交换第i个元素和第2n-i-1个元素的值(i=0,…, n-1 )
06、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入结点
s，则执行（ ).
A. s->next=p->next ; p->next=s; B. p->next=s->next; s->next=p;
C. q->next=s ; s->next=p; D.p->next=s;s->next=q;
07．给定有n个元素的一维数组，建立一个有序单链表的最低时间复杂度是()。
A.O(1) B.O(n) C. O(n2) D.O(nlogzn)
08．将长度为n的单链表链接在长度为m的单链表后面，其算法的时间复杂度采用大О形
式表示应该是().
A. O(1) B. O(n) C.O(m) D.O(n+m)
09．单链表中，增加一个头结点的目的是（).
A.使单链表至少有一个结点 B.标识表结点中首结点的位置
C.方便运算的实现 D.说明单链表是线性表的链式存储
10.在一个长度为n的带头结点的单链表h上，设有尾指针r，则执行( )操作与链表的表
长有关。
A.删除单链表中的第一个元素
B.删除单链表中的最后一个元素
C.在单链表第一个元素前插入一个新元素
D.在单链表最后一个元素后插入一个新元素
11．对于一个头指针为head 的带头结点的单链表，判定该表为空表的条件是();对于不
带头结点的单链表，判定空表的条件为().
A. head==NULL
B. head->next==NULL
C. head->next==head
D. head !=NULL
12．在线性表a0, a1,…, a100中，删除元素a50需要移动()个元素。
A.0 B.50 C.51 D．0或50
13.通过含有n(n>1)个元素的数组a,采用头插法建立单链表L，则L中的元素次序( )
A.与数组α的元素次序相同 B.与数组a的元素次序相反
C.与数组a的元素次序无关 D.以上都错误
14.下面关于线性表的一些说法中，正确的是（).
A.对一个设有头指针和尾指针的单链表执行删除最后一个元素的操作与链表长度无关
B.线性表中每个元素都有一个直接前驱和一个直接后继
C.为了方便插入和删除数据，可以使用双链表存放数据
D.取线性表第i个元素的时间与i的大小有关
15．在双链表中向p所指的结点之前插入一个结点q的操作为（)。
A. p->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior;
B. q->prior=p->prior; p->prior->next=q; q->next=p; p->prior=q->next;
C. q->next=p; p->next=q; q->prior->next=q;q->next=p ;
D. p->prior->next=q; q->next=p; q->prior=p->prior; p->prior=q;
16．在双向链表存储结构中，删除p所指的结点时必须修改指针（ ).
A. p->prior->next=p->next; p->next->prior=p->prior;
B. p->prior=p->prior->prior; p->prior->next=p;
C. p->next->prior=p; p->next=p->next->next;
D. p->next=p->prior->prior; p->prior=p->next->next;
18．在双链表的两个结点之间插入一个新结点，需要修改()个指针域。
A.1 B.3 C.4 D.2
19、在长度为n的有序单链表中插入一个新结点，并仍然保持有序的时间复杂度是( )。
A. O(1) B.O(n)
C.O(n) D. O(nlogn)
20.与单链表相比，双链表的优点之一是（).
A.插入、删除操作更方便 B.可以进行随机访问
C.可以省略表头指针或表尾指针 D.访问前后相邻结点更灵活
21．对于一个带头结点的循环单链表工，判断该表为空表的条件是（)。
A．头结点的指针域为空 B.L的值为NULL
C．头结点的指针域与工的值相等 D.头结点的指针域与工的地址相等
22.对于一个带头结点的双循环链表工，判断该表为空表的条件是（)。
A. L->prior==L&&L->next==NULL
B. L->prior==NULL& &L->next==NULL
C. L->prior==NULL&&L->next==L
D.L->prior==L& &L->next==
23.一个链表最常用的操作是在末尾插入结点和删除结点，则选用(）最节省时间。
A.带头结点的双循环链表 B.单循环链表
C.带尾指针的单循环链表 D.单链表
24.设对n(n>1)个元素的线性表的运算只有4种:删除第一个元素;删除最后一个元素;
在第一个元素之前插入新元素;在最后一个元素之后插入新元素，则最好使用（)。
A．只有尾结点指针没有头结点指针的循环单链表
B.只有尾结点指针没有头结点指针的非循环双链表
C.只有头结点指针没有尾结点指针的循环双链表
D.既有头结点指针又有尾结点指针的循环单链表
25．设有两个长度为n的循环单链表，若要求两个循环单链表的头尾相接的时间复杂度为
O(1)，则对应两个循环单链表各设置一个指针，分别指向（)
A.各自的头结点 B．各自的尾结点
C.各自的首结点 D.一个表的头结点,另一个表的尾结点
26.设有一个长度为n的循环单链表，若从表中删除首元结点的时间复杂度达到O(n)，则
此时采用的循环单链表的结构可能是().
A.只有表头指针，没有头结点 B.只有表尾指针，没有头结点
C.只有表尾指针，带头结点 D.只有表头指针，带头结点
