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;