正确答案：仅有尾指针的单循环链表

5、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）。

A.O（n）

B.O（0）

C.O（1）

D.O（n^2）

正确答案：O（n）

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

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

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

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

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

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

7、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）。

A.head→next==NULL

B.head==NULL

C.head→next==he

D.head!=NULL

正确答案：head→next==NULL

8、静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

A.正确

B.错误

正确答案：正确

9、顺序表适宜于顺序存取，而链表适宜于随机存取。

A.正确

B.错误

正确答案：错误

10、线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。

A.正确

B.错误

正确答案：正确

第三章单元测试

1、栈和队列都是（）。

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

B.顺序存储的线性结构

C.链式存储的非线性结构

D.限制存取点的线性结构

正确答案：限制存取点的线性结构

2、设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后随即进入队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（）。

A.3

B.6

C.4

D.2

正确答案：3

3、设计一个判别表达式中括号是否匹配出现的算法，采用（）的数据结构最佳。

A.栈

B.顺序表

C.队列

D.单链表

正确答案：栈

4、表达式a*（b+c）-d的后缀表达式是（）。

A.abc*+d-

B.cb+a*d-

C.abc+*d-

D.abcd+*-

正确答案：abc+*d-

5、递归过程或函数调用时，处理参数及返回地址需要用一种（）的数据结构。

A.栈

B.队列

C.多维数组

D.线性表

正确答案：栈

6、最大容量为n的循环队列，队尾指针为rear，队头指针为front，则队空的条件是（）。

A.rear==front

B.（rear+1）%n==front

C.rear+1==front

D.（rear-l）%n==front

正确答案：rear==front

7、用带头结点的单链表表示队长大于1的队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（）。

A.仅修改队头指针

B.仅修改队尾指针

C.队头、队尾指针都要修改

D.队头，队尾指针都可能要修改

正确答案：仅修改队头指针

8、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度分别为（）。