A.单循环链表

B.双向链表

C.单链表

D.顺序表

正确答案：顺序表

19、线性链表不具有的特点是（）。

A.插入与删除时不必移动元素

B.所需空间与线性表长度成正比

C.不必事先估计所需存储空间大小

D.随机访问

正确答案：随机访问

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

A.n/2

B.（n+1）/2

C.n

D.（n-1）/2

正确答案：n/2

21、链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高。

A.正确

B.错误

正确答案：正确

22、在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。

A.2

B.3

C.4

D.5

正确答案：4

23、具有线性关系的集合中，若a，b是集合中的任意两个元素，则必有aA.正确

B.错误

正确答案：错误

第三章单元测试

1、设abcdef以所给次序进栈，若在进栈操作时允许退栈，则下列得不到的序列为（）

A.dcefba

B.bcafed

C.fedcba

D.cabdef

正确答案：cabdef

2、若已知一个栈的进栈序列是1，2，3……n，其输出序列是p1，p2，p3，pn，若p1=3，则p2为（）

A.可能是2

B.可能是1

C.一定是1

D.一定是2

正确答案：可能是2

3、假定循环队列的队首和队尾指针分别为front和rear，则判断队满的条件为（）。

A.front= =rear

B.front = = 0

C.front+1 = = rear

D.（rear＋1） mod MAXSIZE = = front

正确答案：（rear＋1） mod MAXSIZE = = front

4、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。

A.正确

B.错误

正确答案：正确

5、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。

A.rear-front-1

B.rear-front

C.（rear-front+m）%m

D.rear-front+1

正确答案：（rear-front+m）%m

6、不论栈是用数组实现，还是用链表实现，入栈和出栈的时间复杂度均为O（n）。

A.正确

B.错误

正确答案：错误

7、若栈采用顺序存储方式存储，两栈共享空间A[1..m]，top[i]代表第i个栈（i=1，2）的栈顶，栈1的底在A[1]，栈 2的底在A[m]，则栈满的条件是（）。

A.|top[2]-top[1]|=0

B.top[1]+top[2]=m

C.top[1]=top[2]

D.top[1]+1=top[2]

正确答案：top[1]+1=top[2]

8、输入序列为ABC，若出栈的顺序为CBA时，经过的栈操作为（）。

A.push，pop，push，pop，push，pop

B.push，push，push，pop，pop，pop

C.push，push，pop，pop，push，pop

D.push，pop，push，push，pop，pop

正确答案：push，push，push，pop，pop，pop

9、栈和队都是（）。

A.限制存取点的非线性结构