全屏显示专题章节

1. 一个栈的输入序列为1234，则下列序列中不可能是栈的输出序列的是( )。

A. 1243　　 B. 2134　　 C. 1432　　D. 4312

【解答】由于借助于栈从输入序列1，2，…，n得到的输出序列P₁，P₂，…，P_n不可能出现i＜j＜k时有P_j≤P_k≤P_i，则由D项的4312可知：i=2、j=3、k=4时有P_i=3、P_j=1、P_k=2，即有P_j≤P_k≤P_i，故选D。

2. 若一个栈的输入序列是1，2，3，…，n，则输出序列的第一个元素是n，则第i个输出元素是( )。

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

【解答】若栈输出的第一个元素为n，则由栈顶至栈底顺序存放的必然是n，n-1，…，2，1，故第i个输出元素是n-i+1，因此选B。

3. 设栈S和队列Q的初始状态为空，元素e₁、e₂、e₃、e₄、e₅和e₆依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e₂、e₄、e₃、e₆、e₅、e₁，则栈S的容量至少应该是( )。

A. 6　　B. 4　　C. 3　　D. 2

【解答】由于出栈的输出序列即为队的输入和输出序列，故可不考虑队列；当e₂、e₄、e₃出栈后的情况见图3-3，由此可知栈S的容量至少为3，故选C。

4. 一般情况下，将递归算法转换成等价的非递归算法应该设置( )。

A. 堆栈　　B. 队列　　C. 堆栈或队列　　 D. 数组

【解答】堆栈的用途之一就是将递归转化为非递归，故选A。

5. 若用单链表来表示队列，则应该选用( )。

A. 带尾指针的非循外链表　　C. 带尾指针的循环链表B. 带头指计的非循环链表　　D. 带头指针的循环链表

【解答】设尾指针为rear，则通过rear可以访问队尾，则通过rear-＞next可以访问队头，故选B。

6. 若用一个大小为6的数组来实现循环队列，且rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear利front的值分别为多少?

A. 1和5　　B. 2和4　　 C. 4和2　　D. 5和1

【解答】出队使front指针加1，入队使rear指针加1。图3-4(a)为循环队列的初始情况，图3-4(b)为删除一个元素后又加入两个元素的情况，故选B。

7. 假定一个顺序循环队列的队首和队尾指针分别用front和rear表示，则判队空的条件是( )。

A. front+1==rear　 B. front==rear+1　C. front==0　D. front==rear

【解答】队空的条件为:front==rear，故选D。

8. 假定一个顺序循环队列存储于数组A[n]中，其队首和队后指针分别用front和rear表示，则判断队满的条件是( )。

A. (rear-1)%n==front　　　　B. (rear+1)%n==front

C. rear==(front-1)%n　　　　D. rear==(front+1)%n

【解答】队满的条件为: (rear+1)%n==front,故选B。

9. 已知字符串的内容为b%-y-3*y^2，请利用栈的进栈和退栈操作，将其转换成by-%3y2^*-,试给出进栈和退栈的操作序列。

【解答】通过栈的进栈(push)和退栈(pop)得到所需的字串操作如图3-11所示。

10. 利用栈和队列的基本运算，设计一个算法，判断读入一个以"\n"为结束标识的字符序列是否为“回文”。“回文”是正读和反读都相同的字符序列。例如，“Level”和“abba”是回文，而“LeLe”则不是回文。

(1) 由于栈的操作特征是“先进后出”，因此，将字符序列全部存入栈中再读出，字符序列一定是逆序的，相当于“反读”。

(2) 队的操作特征是“先进先出”，因此，将字符序列全部存入队列中不规则读出，字符序列一定是原来的顺序，相当于“正读”。

(3) 利用栈和队的上述特点，将读入的字符序列同时存入栈s和队q，再同时读出进行比较。若对应的字符相同，则表明字符序列是“回文”；只要出现不相同的情况，就证明此字符序列不是“回文”。

(4) 算法实现如下：

11. 设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带表头结点的单循环链表中,每个结点有两个域：ch和next，其中ch域为字符类型。

【解答】本题使用一个栈stack进行判定，将“(”、“[”或“{”入栈；当遇到“}”、“] ”、“)”时，检查当前栈顶元素是否所对应的“{”、“[”、“(”。若是，则退栈；否则，返回表示不配对。当整个算术表达式检查完毕时，若栈为空，则表示括号配对正确；否则，不配对。算法设计如下：

12. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，如图3-6所示，请写出相应的入队列和出队列算法。

【解答】在队列中插入一个结点的操作是在队尾进行的，所以在循环链表的尾部插入一个结点，算法设计如下：

在队列中删除一个结点是在队首进行的，所以应删除循环链表的第一个数据结点。算法设计如下：

void Delqueue(LinkList *rear)

注意：循环队列为空时的示意图如图3-7所示，即rear指向头结点。

13. 请利用两个栈S₁和S₂来模拟一个队列。已知栈的三个运算定义如下：PUSH(S_T，X)：元素X入S_T栈；POP(S_T，X)：S_T栈顶元素出栈，赋给变量X；Empty(S_T)：判S_T栈空否。那么如何用栈的运算来实现该队列的三个运算：Enqueue：插入一个元素入队列；Dequeue：删除一个元素出队列；Queue_empty：判队列入空 (请写明算法的思想及必要的注释)。

【解答】由于队列是先进先出，而栈是先进后出，所以只有经过两个栈，即先在第一个栈里先进后出，再经过第二栈后进先出来实现队的先进先出。因此，用两个栈模拟一个队列运算，就是在输出时，如果作为输出的栈已空，则从输入栈将已输入到输入栈的所有数据压入输出栈中，然后由输出栈输出数据；如果作为输出的栈不空，则就从输出栈输出数据。显然，只有在输入、输出栈均为空时队列才为空。

一个栈S₁用来插入元素，另一个栈S₂用来删除元素，删除元素时应将前一栈S₁中的所有元素读出，然后进入到第二个栈S₂中。算法描述如下：