文档介绍：第二次作业
一、选择题
1、设有编号为1, 2, 3, 4的4辆列车，顺序进入一个栈结构的站台，下列不可能的出栈顺序为 D 。
A. 1234 B. 1243 C. 1324 D. 1423
2、4个元素按A, B, C, D顺序进入S栈，执行两次Pop(S, x)运算后，栈顶元素的值是 B 。
A. A B. B C. C D. D
3、从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列
A 命令。
A. x=top; top=top->next; B. top=top->next; x=top->data;
C. x=top->data; D. x=top->data; top=top->next;
//题中说用x保存被删除的结点，应该是保存的结点位置而不是元素
4、向顺序栈中输入元素时 B 。
A. 先存入元素，后移动栈顶指针 B. 先移动栈顶指针，后存入元素
C. 谁先谁后无关紧要 D. 同时进行
5、设有一个顺序栈，元素A, B, C, D, E, F依次进栈，如果6个元素出栈的顺序是B, D, C, F, E, A，则栈的容量至少为 A 。
A. 3 B. 4 C. 5 6. 6
//ABCDEF进栈时栈的最大高度分别为：
6、设已将元素A, B, C依次入栈，元素D正等待进栈。那么下列4个序列中不可能出现的出栈顺序为 A 。
A. CADB B. CBDA（B出栈后D入栈） C. CDBA（C出栈后D入栈） D. DCBA（D先入栈然后一起出栈）
7、栈和队列的相同之处是 C 。

8、设栈S 和队列Q 的初始状态为空,元素e1，e2，e3，e4，e5 和e6 依次通过栈，一个元素出栈后即进入队列Q,若6 个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S 的容量至少应该是 C 。
A. 6 B. 4 C. 3 D. 2
9、队列通常采用的两种存储结构是 A
A. 顺序存储结构和链式存储结构
C. 链表存储结构和线性存储结构
10、循环队列SQ队满的条件是。
A. SQ->rear==SQ->front B. (SQ->rear+1)%MAXLEN==SQ->front
B. SQ->rear==0 D. SQ->front==0
//选项B应该是队空的情况，队满时应该满足：(SQ->rear+2)%MAXLEN==SQ->front
11、若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为 B 。
A. 5和1 B. 4和2 C. 2和4 D. 1和5
//循环队列中，删除操作front指针后移，插入操作rear指针后移
12、链栈与顺序栈相比，有一个较为明显的优点是 A 。
A. 通常不会出现满栈的情况 B. 通常不会出现栈空的情况
C. 插入操作更加方便 D. 删除操作更加方便
13、设用一个大小为M=60的顺序表A[M]表示一个循环队列，如果当前的尾指针rear=32，头指针front=15，则当前循环队列的元素的个数为。
A. 42 B. 16 C. 17 D. 41
//循环队列中，front指向第一个元素，rear指向最后一个元素，因此本题中元素个数应该为32-15+1=18个
（rear-front+n+1）%n
14、串是一种特殊的线性表，其特殊性体现在 B 。
A. 可以顺序存储 B. 数据元素是一个字符
C. 可以链式存储 D. 数据元素可以是多个字符
15、设主串的长度为n，模式串的长度为m，则串匹配的KMP算法的时间复杂度为 C 。
A. O(m) B. O(n) C. O(m+n) D. O(m×n)
16、已知串S=“abab”，其Next数组值为。
A. 0123 B. 0121 C. 0112 D. 0122
//0101