正确答案：可随机访问任一个元素

4、带头结点的单链表L为空的条件是（）

A.L==NULL

B.L->；next==NULL

C.L->；next==L

D.L->；next->；next==NULL

正确答案：L->；next==NULL

5、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（）

A.p->；next=s；s->；next=p->；next

B.s->；next=p->；next；p->；next=s

C.p->；next=s；p->；next=s->；next

D.p->；next=s->；next；p->；next=s

正确答案：s->；next=p->；next；p->；next=s

6、在长度为n的顺序表的表尾插入一个新元素的时间复杂度为（）

A.O（n；）

B.O（1；）

C.O（n²；）

D.O（logn；）

正确答案：O（1；）

7、单链表中，增加头结点的目的是为了（）

A.使单链表至少有一个结点

B.标示表结点中首结点的位置

C.方便运算的实现

D.说明单链表是线性表的链式存储实现

正确答案：方便运算的实现

8、线性表的逻辑顺序与物理顺序总是一致的（）。

A.正确

B.错误

正确答案：错误

9、取线性表的第i个元素的时间同i的大小有关（）。

A.正确

B.错误

正确答案：错误

10、线性表的长度是线性表所占用的存储空间的大小（）。

A.正确

B.错误

正确答案：错误

第三章单元测试

1、设有六列火车，编号为1，2，3，4，5，6，顺序开进一个栈式结构的站台，问下列输出序列中，哪个是不可能出现的（）。

A.1，2，3，4，5，6

B.6，5，4，3，2，1

C.3，1，2，6，5，4

D.3，2，1，6，5，4

正确答案：3，1，2，6，5，4

2、栈和队列都是运算受限的线性表。（）

A.正确

B.错误

正确答案：正确

3、当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是top==1。（）

A.正确

B.错误

正确答案：错误

4、元素a， b， c， d， e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（）。

A.3

B.4

C.5

D.6

正确答案：4

5、已知循环队列存储在一维数组A[0..n-1] 中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（）。

A.0， 0

B.0， n-1

C.n-1， 0

D.n-1， n-1

正确答案：0， n-1

6、数组Q[n]用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n，计算队列中元素个数的公式为（）。

A.r-f

B.（n+f-r）%n

C.n+r-f

D.（n+r-f）%n

正确答案：（n+r-f）%n

7、若一个栈以向量V[1..n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是（）。