内容发布更新时间 : 2024/6/26 23:10:49星期一 下面是文章的全部内容请认真阅读。

第三章 栈和队列

一．选择题

1.在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针，则当做退栈处理时，top变化为 。

A．top不变 B．top＝top-n C．top＝top-1 D．top=top+1 2.在一个顺序存储的循环队列中，队首指针指向队首元素的 。

A．前一个位置 B．后一个位置 C．队首元素位置 D．队尾元素位置 3.若进栈序列为1,2,3,4,栈过程中可以出栈，则 不可能是一个出栈序列。 A．3,4,2,1 B．2,4,3,1 C．1,4,2,3 D．3,2,1,4

4.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是 。 A．front= =rear+1 B．front+1= =rear C．front= =rear D．front= =0 5.向一个栈项指针为hs的链栈中插入一个*s结点时，则执行 。 A．hs->next=s; B．s->next=hs->next;hs->next=s; C．s->next=hs;hs=s; D．s->next=hs;hs=hs->next; 6.下列说法哪个正确：_______

A．堆栈是在两端操作、先进后出的线性表 B．堆栈是在一端操作、先进先出的线性表 C．队列是在一端操作、先进先出的线性表 D．队列是在两端操作、先进先出的线性表 7.栈和队列的共同点_______

A．都是先进后出 B．都是先进先出 C．只允许在端点处插入和删除元素 D．没有共同点 8.以下数据结构中哪一个是非线性结构？_______

A．队列 B．栈 C．线性表 D．二叉树

9.若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3 ，?，pn，若p1=n，则 pi 为_______

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

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

11.4个元素进S栈的顺序是 A,B,C,D,经运算 POP(S)后栈顶元素是_______ A．A B．B C．C D．D

12.一个栈的输入序列是a,b,c,d,e,则栈的不可能的输出序列是_______ A. edcba B.decba C.dceab D. abcde 13．设用链表作为栈的存储结构则退栈操作_______。 A．必须判别栈是否为满 B．必须判别栈是否为空 C．判别栈元素的类型 D．对栈不作任何判别

14．设输入序列是 1、2、3、??、n，经过栈的作用后输出序列的第一个元素是 n，则输出序列中第i个输出元素是_______。

A． n-i B．n-1-i C．n+1-i D．不能确定 15．递归函数f(n)=f(n-1)十 n(n>1) 的递归出口是_______。

A．f(1)=0 B．f(1)=1 C．f(0)=1 D．f(n)=n 16．中缀表达式A-(B+C／D)*E 的后缀形式是_______。

A．ABC+D／*E- B．ABCD／+E*- C．AB-C+D／E* D．ABC-+D/E*

17.字符 A、B、C、D 依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成_______个不同的字符串？

A.15 B.14 C.16 D.21

18.字符 A 、B 、C 依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成_______个不同的字符串？

A.14 B.5 C.6 D.8

19．判定一个循环队列QU(最多元素为 m0)为满队列的条件是_______ A．QU->front==QU->rear B．QU->front!=QU->rear

C．QU->front==(QU->rear+1)％m0 D．QU->front!=(QU->rear+1)％m0 20.以下哪一个不是队列的基本运算？_______

A. 在队列第 i 个元素之后插入一个元素 B.从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值

21．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和 E6依次通过栈 S，一个元素出栈后即进入队列Q，若 6个元素出列的顺序为E2、E4、E3、E6、E5 和 E1，则栈S 的容量至少应该是_______。 A．6 B．4 C．3 D．2

22.用链接方式存储的队列，在进行插入运算时_______。 A. 仅修改头指针 B.头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 23. 若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0 和 3。当从队列中删除一个元素，再加入两个元素后，rear和front 的值分别为_______？

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

24．将一个递归算法改为对应的非递归算法时，通常需要使用_______。 A.栈 B.队列 C.循环队列 D.优先队列

25．在循环队列中用数组 A[0..m-1] 存放队列元素，其队头和队尾指针分别为 front和rear，则当前队列中的元素个数是_______。 A. (front-rear+1)%m B. (rear-front+1)%m C．(front-rear+m)%m D. (rear-front+m)%m 二．填空题

1. 栈和队列分别称为_____________的线性表。

2. 栈结构允许进行删除操作的一端为_____________。 3. 向一个由HS指向的链栈中插入一个结点时p 时，需要执行的操作是________；删除一个结点时，需要执行的操作是______________________________（假设栈不空而且无需回收被删除结点）。 4. 向量、栈和队列都是__________结构，可以在向量的__________ 位置插入和删除元素；对于栈只能在____________ 插入和删除元素；对于队列只能在 ________插入和_______ 删除元素。

5. 栈是一种特殊的线性表，允许插入和删除运算的一端称为___________ 。不允许插入和删除运算的一端称为_____________ 。

6. 栈又称为_______________表，队列又称为___________表。 7. 当用长度为N 的数组顺序存储一个栈时，假定用top==N 表示栈空，则表示栈满的条件是_____________________。

8. 设输入序列为1、2、3，则经过栈的作用后可以得到_____种不同的输出序列。 9. 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为____________。

10. (a+b)*c+(e*f-h)/(q+r)+3 的后缀表达式为__________________________。 11. 后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3 对应的后缀算式为_______________________________。 三．判断题

1. 栈是一种线性结构。 （ ） 2. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （ ） 3. 栈是一种插入和删除操作在表的一端进行的线性表。 （ ） 4. 出栈序列为abcd，则入栈序列可能是bcda。 （ ） 5. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 （ ） 6. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （ ） 7. 不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。 （ ） 8. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （ ） 9. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （ ） 10. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 （ ） 11. 高级语言中通常利用“递归工作栈”来处理递归。 （ ）

四、简答题

1.简述栈与队列的相同点与不同点。 2.在顺序队列中，什么叫真溢出？什么叫假溢出？为什么顺序队列常都采用循环队列结构？

3.写出下列程序段的输出结果（栈的元素类型SElemType为char）。 void main() { 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); }

4. 简述以下算法的功能（栈的元素类型SElemType为int）。 (1) status algo1(Stack S)