第三、四章-栈及队列、串.doc

第三章 栈和队列

一、 基础知识题

1、单选题
（1）栈的插入和删除操作在 进行。
A．栈顶 B．栈底 C．任意位置 D．指定位置

（2）当利用大小为n的数组顺序存储一个栈时，假定用top= =n表示栈空，则向这个栈插入一个元素时首先应执行 语句修改top指针。
A．top++ B．top-- C．top=0 D．top

（3）若让元素1，2，3依次进栈，则出栈次序不可能出现 种情况。
A．3，2，1 B．2，1，3 C．3，1，2 D．1，3，2

（4）在一个顺序存储的循环队列中，队头指针指向队头元素的 位置。
A．前一个 B．后一个 C．当前 D．后面

（5）当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为 。
A．n-2 B．n-1 C．n D．n+1

（6）假定一个不带表头结点的链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为 。
A．front = = rear B．front ! = NULL
C．rear! = NULL D．front = = NULL

2、填空题
（1）队列的插入操作在 进行，删除操作在 进行。

（2）栈又称为 的表，队列又称为 的表。

（3）向一个顺序栈插入一个元素时，首先使 后移一个位置，然后把待插入元素
到这个位置上。

（4）从一个栈删除一个元素时，需要前移一位 。

（5）在一个循环队列Q中，判断队空的条件为 ，判断队满的条件为 。

（6）在一个顺序栈中，若栈顶指针等于 ，则为空栈；若栈顶指针等于 ，则为满栈。

（7）向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给 ，然后把新结点的存储位置赋给 。

（8）向一个循环队列中插入一个元素时，需要首先移动 ，然后再向所指位置
新插入的元素。

（9）当用长度为n的数组顺序存储一个栈时，若用top= =n表示栈空，则表示栈满的条件为 。

（10）向一个栈顶指针为top的链式栈中插入一个新结点* p时，应执行 和
的操作。

（11）从一个栈顶指针为top的非空链式栈中删除结点，并不需要返回栈顶的值和回收结点时应执行 的操作。

（12）中缀表达式3*（x+2）—5所对应的后缀表达式为 。

（13）后缀表达式“45*32+—”的值为 。

（14）设一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少为多少？

二、 算法设计题
1、 试写一个判断表达式中开、闭括号是否配对出现的算法。
2、 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。

第四章 串

一 算法设计题
1、 编写对串求逆的递推算法。
2、 编写算法，求得所有包含在串s中而不包含在串t中的字符（s中重复的字符只选一个）构成的新串r，以及r中每个字符在s中第一次出现位置。