B.栈不能对输入序列部分或全局求逆。

C.当top等于数组最大下标时则栈满。

D.top=-1时为空栈，元素进栈时指针top不断减1。

正确答案：栈不能对输入序列部分或全局求逆。；top=-1时为空栈，元素进栈时指针top不断减1。

8、已知一个栈的进栈序列是a1，a2，a3....an.其输出序列为1，2，3...n，若a3=1则a1为（）

A.可能是2

B.可能是3

C.不可能是2

D.一定是2

E.不可能是3

正确答案：可能是3；不可能是2；一定是2

9、栈的特点是（）

A.先进后出

B.进优于出

C.先进先出

D.出优于进

正确答案：先进后出

10、设循环队列的容量为20，序号从0到19，经过一系列的入队和出队后，front=5，rear=10，问队列中有多少个元素（采用节省一个队列存储空间的方式）。

A.7

B.6

C.5

D.4

正确答案：5

11、一个队列的入队序列是1，2，3，4，则队列的出队序列是（）

A.1，4，3，2

B.4，3，2，1

C.1，2，3，4

D.3，2，4，1

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

12、一般情况下，将递归算法转换成等价的非递归算法应该设置（）

A.栈

B.栈或队列

C.队列

D.数组

正确答案：栈

13、设用链表作为栈的存储结构则退栈操作（）

A.必须判别栈是否为满

B.对栈不作任何判别

C.判别栈元素的类型

D.必须判别栈是否为空

正确答案：必须判别栈是否为空

第四章单元测试

1、KMP算法的特点是在模式匹配时指示主串的指针不会变小。

A.正确

B.错误

正确答案：正确

2、空串与空格串是相同的。

A.正确

B.错误

正确答案：错误

3、串的长度是指串中不同字符的个数。

A.正确

B.错误

正确答案：错误

4、设有两个串P和Q，其中Q是P的子串，把Q在P中首次出现的位置作为子串Q在P中的位置的算法称为模式匹配算法。

A.正确

B.错误

正确答案：正确

5、设模式串（子串）的长度为m，目标串（主串）的长度为n。当n≈m且处理只匹配一次的模式时，简单模式匹配（BF）算法所花费的时间代价也可能会比KMP算法更节省。

A.正确

B.错误

正确答案：正确

6、串是一种特殊的线性表，下列不能体现其特殊性的是（）

A.数据元素是字符型数据

B.可以链接存储

C.可以顺序存储

D.数据元素可以是非字符数据

正确答案：可以链接存储；可以顺序存储；数据元素可以是非字符数据

7、以下说法中错误的是（）

A.串的长度必须大于零

B.串中的元素只能是字母

C.空串就是空白串

D.串是一种特殊的线性表

正确答案：串的长度必须大于零；串中的元素只能是字母；空串就是空白串

8、两个串相等必须有（）

A.串中的各位置字符任意

B.串中各位置字符均对应相等

C.串长度任意

D.串长度相等

E.串长度不相等

正确答案：串中各位置字符均对应相等；串长度相等

9、若串S=”software”，其子串的数目是（）