数据结构第3章栈和队列自测题答案(2)

因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。

② 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。

2. 设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。 答：至少有14种。

① 全进之后再出情况，只有1种：4,3,2,1

② 进3个之后再出的情况，有3种，3,4,2,1 3,2,4,1 3,2,1,4

③ 进2个之后再出的情况，有5种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2, 3,1,4 ④ 进1个之后再出的情况，有5种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3

3. 假设正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’ 和‘ababab’则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？

答：线性表是随机存储，可以实现，靠循环变量（j--）从表尾开始打印输出；

堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可； 队列是先进先出，不易实现。

哪种方式最好，要具体情况具体分析。若正文在机内已是顺序存储，则直接用线性表从后往前读取即可，或将堆栈栈顶开到数组末尾，然后直接用POP动作实现。（但堆栈是先减后压还是……）

若正文是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全部压入后再依次输出。

6

4. 顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？

答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。 采用循环队列是解决假溢出的途径。 另外，解决队满队空的办法有三：

① 设置一个布尔变量以区别队满还是队空； ② 浪费一个元素的空间，用于区别队满还是队空。 ③ 使用一个计数器记录队列中元素个数（即队列长度）。

我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。 判断循环队列队空标志是： f=rear 队满标志是：f=(r+1)%N

5. 设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 ① front=11，rear=19; ② front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？

答：用队列长度计算公式： (N＋r－f)% N

① L=（40＋19－11）% 40=8 ② L=（40＋11－19）% 40=32

五、阅读理解（每小题5分，共20分。至少要写出思路）

1. 写出下列程序段的输出结果（栈的元素类型SElem Type为char）。 void main( ){

7

Stack S; Char x,y; InitStack(S); X=’c’;y=’k’;

Push(S,x); Push(S,’a’); Push(S,y); Pop(S,x); Push(S,’t’); Push(S,x); Pop(S,x); Push(S,’s’);

while(!StackEmpty(S)){ Pop(S,y);printf(y); }; Printf(x); }

答：输出为“stack”。

2. 【严题集3.12②】写出下列程序段的输出结果（队列中的元素类型QElem Type为char）。 void main( ){

Queue Q; Init Queue (Q); Char x=’e’; y=’c’;

EnQueue (Q,’h’); EnQueue (Q,’r’); EnQueue (Q, y); DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,’a’);

while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y); }; Printf(x); }

答：输出为“char”。

8

3. 简述以下算法的功能（栈和队列的元素类型均为int）。 void algo3(Queue &Q){ Stack S; int d; InitStack(S);

while(!QueueEmpty(Q)){ DeQueue (Q,d); Push(S,d); };

while(!StackEmpty(S)){ Pop(S,d); EnQueue (Q,d); } }

答：该算法的功能是：利用堆栈做辅助，将队列中的数据元素进行逆置。

六、算法设计（每小题5分，共15分。至少要写出思路）

1. 假设一个数组squ[m]存放循环队列的元素。若要使这m个分量都得到利用，则需另一个标志tag，以tag为0或1来区分尾指针和头指针值相同时队列的状态是“空”还是“满”。试编写相应的入队和出队的算法。

解：这就是解决队满队空的三种办法之① 设置一个布尔变量以区别队满还是队空（其他两种见简答题）；

思路：一开始队空，设tag=0，若从rear一端加到与front指针相同时，表示入队已满，则令

9

tag=1；

若从front一端加到与rear指针相同时，则令tag=0，表示出队已空。

2.试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。 答：编程如下：

int Palindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0 {

InitStack(S);InitQueue(Q); while((c=getchar())!='@') {

Push(S,c);EnQueue(Q,c); //同时使用栈和队列两种结构 }

while(!StackEmpty(S)) {

Pop(S,a);DeQueue(Q,b)); if(a!=b) return ERROR; }

return OK; }//Palindrome_Test

10