3.8 本 章 小 结

 

3.8  本 章 小 结

本章主要介绍了两种运算受限的线性表：栈和队列。讨论了它们的基本概念、存储结构、基本运算的实现以及一些应用实例。

对于栈来说，它的插入和删除运算均在表的同一端进行，是一种“先进后出”的线性表，随着节点的进栈和出栈，用栈顶指针指示栈顶的变化。用顺序存储结构时，要注意栈满、栈空的条件；用链式存储结构时，要注意链的方向。

对于队列来说，它的插入运算在表的一端进行，而删除运算在表的另一端进行，是一种“先进先出”的线性表，分别用队头指针和队尾指针指示队列头节点和尾节点的变化。熟记队列中节点的插入、删除运算的算法及其溢出的条件。在顺序队列结构中，当节点不断插入、删除时，会很快移到队列末端而造成假溢出，用循环队列是一个好的解决方法。

3.9  练  习  题

1．选择题

（1）设有顺序栈S，元素s1，s2，s3，s4，s5，s6依次入栈，如果6个元素出栈的顺序是s2，s3，s4，s6，s5，s1，则栈的容量至少应该是      。

A．2                    B．3                     C．5                     D．6

（2）若有一个栈的输入序列是a、b、c，则通过入栈、出栈操作可能得到a、b、c的不同排列个数为      。

A．4                    B．5                     C．6                     D．7

（3）和顺序栈相比，链栈有一个比较明显的优势是      。

A．通常不会出现栈满的情况

B．通常不会出现栈空的情况

C．插入操作更容易实现

D．删除操作更容易实现

（4）若一个栈的输入序列是1，2，3，4，…，n，输出序列的第一个元素是n，则第i个输出元素是      。

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

（5）以下说法正确的是      。

A．因链接本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况

B．因顺序栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况

C．对于链栈而言，在栈满状态下，如果再进行入栈操作，则会发生“上溢”

D．对于顺序栈而言，在栈满状态下，如果再进行入栈操作，则会发生“下溢”

（6）顺序队列的入队操作为      。

A．sq.rear=sq.rear+1;sq.data[sq.rear]=x;

B．sq.rear=(sq.rear)=x;sq．rear=sq.rear+1;

C．sq.rear=(sq.rear+1)%maxsize;sq.data[sq.rear]=x;

D．sq.data=[sqrear]=x; sq.rear=(sq.rear+1)%maxsize;

（7）循环队列的入队操作为      。

A．sq.rear=sq.rear+1;sq.data[sq.rear]=x;

B．sq.data[sq.rear]=x; sq.rear=sq.rear+1;

C．sq.rear=(sq.rear+1)%maxsize;sq.data[sq．rear]=x;

D．sq.data[sq.rear]=x;sq.rear=(sq.rear+1)%maxsize;

（8）顺序队列的出队操作为      。

A．sq.front=(sq.front+1)%maxsize;

B．sq.front=sq.front+1;

C．sq.rear=(sq.rear+1)%maxsize;

D．sq.rear=sq.rear+1;

（9）循环队列的出队操作为      。

A．sq.front=(sq.front+1)%maxsize;

B．sq.front=sq.front+1;

C．sq.rear=(sq.rear+1)%maxsize;

D．sq.rear=sq.rear+1;

（10）循环队列的队满条件为      。

A．(sq.rear+1)maxsize= =(sq.front+1)%maxsize;

B．(sq.rear+1)maxsize= =sq.front+1;

C．(sq.rear+1)maxsize= =sq.front;

D．sq.rear= =sq.front;

（11）循环队列的队空条件为      。

A．(sq.rear+1)maxsize= =(sq.front+1)%maxsize;

B．(sq.rear+1)maxsize= =sq.front+1;

C．(sq.rear+1)maxsize= =sq.front;

D．sq.rear= =sq.front;

（12）如果以链表作为栈的存储结构，则出栈操作时      。

A．必须判别栈是否满

B．判别栈元素的类型

C．必须判别栈是否空

D．对栈不做任何判别

（13）向一个栈顶指针为Top的链栈中插入一个s所指节点时，其操作步骤为      。

A．Top->next=s;

B．s->next=Top->next;Top->next=s;

C．s->next=Top;Top=s;

D．s->next=Top;Top=top->next;

（14）从栈顶指针为Top的链栈中删除一个节点，并将被删节点的值保存到x中，其操作步骤为      。

A．x=Top->data;Top=Top->next;

B．Top=Top->next;x=Top->data;

C．x=Top;Top=Top->next;

D．x=Top->data;

（15）在一个链队中，若f、r分别为队头、队尾指针，则插入s所指节点的操作为     。

A．f->next=s;f=s;                                          B．r->next=s;r=s;

C．s->next=r;r=s;                                          D．s->next=f;f=s;

（16）一个栈的入栈序列是a，b，c，d，e，则栈不可能的输出序列是      。

A．e，d，c，b，a                                 B．d，e，c，b，a

C．d，c，e，a，b                                  D．a，b，c，d，e

（17）一个队列的入队序列是1，2，3，4，则队列可能的输出序列是      。

A．4，3，2，1                                      B．1，2，3，4

C．1，4，3，2                                      D．3，2，4，1

（18）设计一个判别表达式中左、右括号是否配对出现的算法，采用       数据结构最佳。

A．线性表的顺序存储结构                           B．栈

C．队列                                                 D．线性表的链式存储结构

（19）若以1，2，3，4作为双端队列的输入序列，则既不能由输入受限双端队列得到，也不能由输出受限双端队列得到的输出序列是      。

A．1，2，3，4                                      B．4，1，3，2

C．4，2，3，1                                      D．4，2，1，3

2．填空题

（1）向栈中压入元素的操作是               。

（2）对栈进行退栈时的操作是               。

（3）在一个循环队列中，队首指针指向队首元素的               。

（4）从循环队列中删除一个元素时，其操作是               。

（5）在具有n个单元的循环队列中，队满时共有            个元素。

（6）假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为               。

（7）栈的特点是               ，队列的特点是               。

（8）栈结构通常采用的两种存储结构是               和               。

3．问答题

（1）栈与队列可以利用C语言的哪一种数据结构来表示？请举出一些其性质类似于栈和队列的例子。

（2）叙述栈和队列之间的区别和联系。

（3）设有4个元素a，b，c，d进栈，给出它们所有可能的出栈次序。

（4）与一般队列相比，环形队列有什么优点？并给出环形队列队满和队空的判断条件。

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

4．上机操作题

（1）已知num为无符号十进制整数，请写一个非递归算法，依次输出num所对应的r进制数的各位数字。

（2）在一个顺序循环队列中，用count存放队列长度，要求充分利用循环队列中所有的存储空间，请设计循环队列的入队、出队算法。

（3）设用带表头节点的循环链表表示队列，且仅设一个尾指针，尾指针指向数据域值为队尾元素的节点，不设队首指针，请编写实现置空队列、入队和出队的算法。

（4）已知q是一个非空顺序队列，s是一个顺序栈，请设计一个算法，实现将队列q中所有元素逆置。