第三章 栈和队列

一、选择题

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

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

2．若一个栈的输人序列是1，2，3，?，n，输出序列的第一个元素是n，则第k个输出元素是（ ）。

A．k B．n-k-1 C．n-k+1 D．不确定 3．判定一个栈S（最多有n个元素）为空的条件是（ ）。

A．S->top！＝0 B．S->top= =0 C．S->top!=n D．S->top= =n 4．判定一个栈S（最多有n个元素）为满的条件是（ ）。

A．S->top!=0 B．S->top= =0 C．S->top!=n D．S->top= =n 5．向一个栈顶指针为top的不带头结点的链栈中插人一个*S结点的时候，应当执行语句（ ）。 A．top->next=S； B．S->next=top；top=S；

C．S->next＝top->next；top->next＝S；D．S->next＝top；top＝S->next；

6．向一个带头结点、栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（ ）。 A．top->next=S； B．S->next=top；top=S；

C．S->next=top->next；top->next=S； D．S->next=top；top=S->next； 7．判定一个队列Q（最多有n个元素）为空的条件是（ ）。

A．Q->rear-Q->front= =n B．Q->rear-Q->front+1= =n C．Q->rear = = Q->front D．Q->rear +1= = Q->front 8．判定一个队列Q（最多有n个元素）为满的条件是（）。

A．Q->rear-Q->front= =n B．Q->rear-Q->front+1= =n C．Q->rear = = Q->front D．Q->rear +1= = Q->front 9．判定一个循环队列Q（最多有n个元素）为空的条件是（ ）。 A．Q->rear = = Q->front B．Q->rear = = Q->front＋l

C．Q->front= =(Q->rear +1)％n D．Q->front= =(Q->rear -1)％n 10．判定一个循环队列Q（最多有n个元素）为满的条件是（ ）。

A．Q->rear = = Q->front B．Q->rear = = Q->front＋l C．Q->front= =(Q->rear +1)％n D．Q->front= =(Q->rear -1)％n

11．在一个链队列中，假定front和rear分别为头指针和尾指针，则插入一个结点*S的操作是（ ）。

A．front＝front->next B．S->next=rear；rear=S C．rear->next=S；rear=S D．S->next=front；front＝S 12．在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（ ）。 A．front=front->next B．rear=rear->next C．rear->next=front D．front->next＝rear 13．栈与队列都是（ ）。

A．链式存储的线性结构 B．链式存储的非线性结构 C．限制存取点的线性结构 D．限制存取点的非线性结构 14．若进栈序列为l，2，3，4，则（ ）不可能是一个出栈序列。

A．3，2，4，1 B．l，2，3，4 C．4，2，3，1 D．4，3，2，l 15．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个

（ ）结构。

A．堆栈 B．队列 C．数组 D．线性表

1. C 2. C 3. B 4. D 5. B 6. C 7. C 8. A 9. A 10. C 11. C 12. A 13. C 14. C 15. B

二、填空回

1．栈（stack）是限定在________一端进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为__________，而另一端称为_________。不含元素的栈称为_______。

2．在栈的运算中，栈的插人操作称为________或________，栈的删除操作称为_________或__________。

3．根据栈的定义，每一次进栈的元素都在原___________之上，并成为新的__________；每一次出栈的元素总是当前的_____________，因此最后进栈的元素总是__________，所以栈也称为___________线性表，简称为____________表。

4．栈是一种操作受到限制的线性表，是一种特殊的线性表，因此栈也有__________和_________________两种存储结构，分别称为______________和____________。

5．当栈满的时候，再进行人栈操作就会产生____________，这种情况的溢出称为___________；当栈空的时候，如果再进行出栈操作，也会_____________，这种情况下的溢出称为__________________。

6．栈的链式存储结构简称为____________，是一种__________________。 7．人们日常计算用到的表达式都被称为____________，这是由于这种算术表达式的运算符被置于两个操作数中间。

8．计算机中通常使用___________，这是一种将运算符置于两个操作数后面的算术表达式。这种表达式是由波兰科学家谢维奇提出的，因此又称为__________________。

9．队列（Queue）也是一种___________，但它与栈不同，队列中所有的插人均限定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插人的一端称为_________，允许删除的一端称为_______________。

10．队列的特点是_________，因此队列又被称为_______________．的线性表，或称为_________________表。

11．队列的_________又称为__________，是用一组地址连续的存储单元依次存放队列中的元素。 12．由于队列中的元素经常变化，对于队列的删除和插人分别在队头和队尾进行，因此需要设置两个指针分别指向__________和__________，这两个指针又称为__________和_____________。 13．循环顺序队列（Circular Sequence Queue）经常简称为___________，它是将存储顺序队列的存储区域看成是一个首尾相连的一个环，即将队首和队尾元素连接起来形成一个环形表。首尾相连的状态是通过数学上的_________________来实现的。

14．在算法或程序中，当一个函数直接调用自己或通过一系列语句间接调用自己的时候，则称这个函数为，也称为____________。函数直接调用自己，则称为__________；当一个函数通过另一个函数来调用自己则称为_________________。

15．在循环队列中规定：当Q->rear= =Q->front的时候循环队列为___________， 当（Q->rear+1）％MAXSIZE＝front的时候循环队列为____________________。 16．用链表方式表示的队列称为____________________。

17．已知栈的输人序列为1，2，3，?，n，输出序列为a1，a2，?，an，符合a2= =n的输出序列共有__________________。

18．一个栈的输人序列是12345，则栈的输出序列为43512是________（填是否可能）。

19．一个栈的输人序列是12345，则栈的输出序列为12345是_________（填是否可能）。 20．设sq[1．．maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，则作入栈操作的条件是______________。 21．设sq[1．．maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，如果把栈顶元素弹出并送到X中，则需执行语句______________。 22．栈的特性是__________________。

23．对栈进行退栈时的操作是先取出元素，后移动_________。 24．设s[1．．max]为一个顺序存储的栈，变量top指示栈顶位置，栈为满的条件是____。 25．设链栈的栈顶指针为top，则栈非空的条件是___________。

26．已知循环队列用数组data[1...n]存储元素值，用f，r分别作为头尾指针， 则当前元素个数为____________。

27．在一个循环队列中，队首指针指向队首元素的________位置。（前一个或后一个） 28．队列中允许进行删除的一端称为_______________。

29．链队列实际上是一个同时带有头指针和尾指针的单链表（1．．n），尾指针指向该单链表的第___________个元素。

30．设双向链表链列为lq，lq的头指针为lq.Front，尾指针为lq.Rear，则队列为空的条件是____________。

31．从循环队列中删除一个元素，其操作是先取出一个元素，后移动______________。 32．队列中允许进行插入的一端称为_________。

1. 表尾、栈顶、栈底、空栈 2. 进栈、入栈、退栈、出栈

3. 栈顶元素、栈顶元素、栈顶元素、最先出栈、后进先出、LIFO 4. 顺序、链式、顺序栈、链栈 5. 溢出、上溢、溢出、下溢 6. 链栈、特殊的单链表 7. 中缀表达式

8. 后缀表达式、波兰式

9. 特殊的线性表、队尾、队头 10. 先进先出、先进先出、FIFO 11. 顺序存储结构、顺序队列

12. 队头元素、队尾元素、队头指针、队尾指针 13. 循环队列、取模运算

14. 递归函数、自调用函数、直接递归调用、间接递归调用 15. 空、满 16. 链队列 17. n-1

18. 不可能的 19. 可能的

20. top!=maxsize

21. x=sq[top]; top=top-1 22. 先进后出 23. 栈顶指针 24. top==max 25. top!=nil

26. (n+r-f)mod n 27. 前一个 28. 队首 29. n

30. lq->front==lq->rear 31. 栈顶指针 32. 队尾

三、判断题

1．栈和队列都是限制存取点的线性结构。（ ） 2．不同的入栈和出栈组合可能得到相同输出序列。（ ） 3．消除递归一定要用栈。（ ） 4．循环队列是顺序存储结构。（ ） 5．循环队列不会产生溢出。（ ） 6．循环队列满的时候rear= =front。（ ）

7．在对链队列（带头结点）做出队操作时不会改变front指针的值。（）

1. 正确。

2. 错误：不同的入栈和出栈组合得到不同输出序列。 3. 错误：某些情况如尾递归可以转换为递推的形式。 4. 正确。

5. 错误：循环队列不会产生假溢出。 6. 错误。 7. 正确。

四、综合题

1．设有4个元素A、B、C和D进栈，给出它们所有可能的出栈秩序。 可能的出栈序列：（共14个）

ABCD ABDC ACBD ACDB ADCB BACD BADC BCAD BCDA BDCA CBAD CBDA CDBA DCBA

不可能的出栈序列：（共10个） ADBC BDAC

CABD CADB CDAB

DABC DACB DBAC DBCA DCAB