A. 可以随机访问任一结点 C. 不必事先估计存储空间

B. 插入、删除不需要移动元素

D. 所需空间与其长度成正比

答题：

A. B. C. D. （已提交）

参考答案： A

问题解析：

10. ( 单选题 ) 以下关于链表的叙述中，不正确的是（ ）。

A. 结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构 B. 逻辑上相邻的元素物理上不必相邻

C. 可以通过计算直接确定第 i 个结点的存储地址 D. 插入、删除运算操作方便，不必移动结点

答题： A. B. C. D. （已提交）

参考答案： C 问题解析：

11. ( 单选题 )要求线性表的存储空间大小固定， 且插入和删除操作不需要移动 元素，采用的存储结构是（）。 A. 单链表 B. 静态链表 C. 双链表

D. 顺序表

答题：

A. B. C. D. （已提交）

参考答案： B

问题解析：

12. ( 单选题 ) 不带头结点的单链表 head 为空的判定条件是（

A. head==NULL B. head->next==NULL C. head->next==head D. head!=NULL

）

答题：

A. B. C. D. （已提交）

参考答案： A

问题解析：

13. ( 单选题 )某线性表最常用的操作是在最后一个结点之后插入一个结点或 删除第一个结点，故采用（）存储方式最节省运算时间。 A. 单链表 B. 仅有头结点的单循环链表

C. 双链表 D. 仅有尾指针的单循环链表

答题：

A.

B.

C.

D. （已提交）

参考答案： D 问题解析： 14. ( 单选题 )

如果含有 n 个元素的某表最常用的操作是取第 i(2 ≤i ≤n) 个结

点及其前趋结点，则采用（

A. 单链表 B. 双链表 ）存储方式最节省时间。 C. 单循环链表 D. 顺序表

答题：

A. B. C. D. （已提交）

参考答案： D

问题解析：

15. ( 单选题 )在一个长度为 n(n>1) 的带头结点的单链表 head 上，另设有尾指 针 r( 指向尾结点 ) ，执行（ ）操作与链表的长度有关。

A. 删除单链表中的第一个元素 B. 删除单链表中的尾结点

C. 在单链表的第一个元素前插入一个新结点 D. 在单链表的最后一个元素后插入一个新结点

答题： A. B. C. D. （已提交）

参考答案： B

问题解析：

16. ( 单选题 )将长度为 n 的单链表链接到长度为 m的单链表之后的算法的时间 复杂度是（） A. O(1) B. O(n) C. O(m) D. O(m+n)

答题：

A. B. C. D. （已提交）

参考答案： C 问题解析：

17. ( 单选题 )已知一个长度为 n 的单链表中的所有结点是有序 ( 递增 ) 的，以下 叙述中正确的是（）。

A. 插入一个结点使之有序的算法的时间复杂度为 O(1) B. 删除最大值结点使之有序的算法的时间复杂度为 O(1) C. 找最小值结点的算法的时间复杂度为 O(1) D. 以上都不对

答题：

A. B.

C. D. （已提交）

参考答案： C 问题解析：

18. ( 单选题 ) 在一个双链表中，删除 p 结点 ( 非尾结点 ) 的操作是（

A. p->prior->next=p->next; p->next->prior=p->prior; B. p->prior=p->prior->prior; p->prior->prior=p; C. p->next->prior=p; p->next=p->next->next; D. p->next=p->prior->prior; p->prior=p->prior->prior;

）。

答题：

A. B.

C.

D. （已提交）

参考答案： A 问题解析：

19. ( 单选题 ) 非空循环单链表 head 的尾结点 p 满足（

A. p->next==NULL B. р==NULL C. p->next==head D. p== head

）。

答题：

A.

B.

C.

D. （已提交）

参考答案： C 问题解析：

在长度为 n 的（ ）上删除第一个元素，其算法的时间复杂度 20. ( 单选题 )

为 O(n) 。

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

答题：

A. B. C. D. （已提交）

参考答案： A 问题解析：

第三章 栈、队列

1. ( 单选题 )若元素 a、 b 、 c、 d、 e、 f 依次进栈，允许进栈、出栈操作交替 进行，但不允许连续 3 次出栈，则不可能得到的出栈序列是（ ）。

A. dcebfa B. cbdaef C. bcaefd D. afedcb

答题：

A. B. C. D. （已提交）

参考答案： D 问题解析：

2. ( 单选题 ) 一个栈的进栈序列是 a、b、c、d、 e，则不可能的栈的输出序列是（ ）。 A. edcba B. decba C. dceab D. abcde

答题： A. B. C. D. （已提交）

参考答案： C 问题解析：

3. ( 单选题 )已知一个栈的进栈序列是 1,2,3, ?, n ，其输出序列的第一个元 素是 i(1 ≤i ≤n) ，则第 j (1 ≤j ≤n) 个出栈元素是（ ）。

A. i

B. n-i

C.

j-i+1 D. 不确定

答题：

A. B.

C. D. （已提交）

参考答案： D 问题解析：

4. ( 单选题 ) 已知一个栈的进栈序列是 1, 2, 3, ..., n p2, ..., pn ，若 p1=n，则 pi 的值（ ）。

A. i B. n-i C. n-i+1 D. 不确定

，其输出序列是 p1,

答题：

A. B. C. D. （已提交）

参考答案： C 问题解析：

5. ( 单选题 )设有 5 个元素，其进栈序列是 a、b、c、d、e，其输出序列是 c、 e、d、b、a，则该栈的容量至少是（）。 A.1 B.2 C.3 D.4

答题：

A. B. C. D. （已提交）

参考答案： D

问题解析：

6. ( 单选题 ) 表达式 (a+a*b) *a+c* b/a 的后缀表达式是（

A. aab* +a* cb* a/+ B. aa* b+a* cb * a/+ C. aab* a*cb* +a/+ D. aab*+acb*a/+*

）

答题：

A. B.

C.

D. （已提交）

参考答案： A

问题解析：

7. ( 单选题 ) 若一个栈用数组 data[1..n]存储，初始栈顶指针 top 为 n+1, 则以

下元素 x 进栈的正确操作是（ ）。

A. top++ ; top++ ; data[top]=x; B. data[top]=x;

C. top--; top--; data[top]=x; D. data[top]=x;

答题：

A. B. C. D. （已提交）

参考答案： C 问题解析：

8. ( 单选题 )若一个栈用数组 data[1..n] 存储，初始栈顶指针 top 为 n，则以 下元素 x 进栈的正确操作是（ ）。

A. top++; top++; data[top]=x; B. data[top]=x;

C. top--; top ― data[top]=x; D. data[top]=x;