第三章 栈和队列

1、第三章 栈和队列一选择题1.在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针，则当做退栈处理时，top变化为 。Atop不变 Btoptop-n Ctoptop-1 Dtop=top+12.在一个顺序存储的循环队列中，队首指针指向队首元素的 。A前一个位置 B后一个位置 C队首元素位置 D队尾元素位置3.若进栈序列为1,2,3,4,栈过程中可以出栈，则 不可能是一个出栈序列。A3,4,2,1 B2,4,3,1 C1,4,2,3 D3,2,1,44.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是 。Afront

2、= =rear+1 Bfront+1= =rear Cfront= =rear Dfront= =05.向一个栈项指针为hs的链栈中插入一个*s结点时，则执行 。Ahs->next=s; Bs->next=hs->next;hs->next=s;Cs->next=hs;hs=s; Ds->next=hs;hs=hs->next;6.下列说法哪个正确：_A堆栈是在两端操作、先进后出的线性表B堆栈是在一端操作、先进先出的线性表C队列是在一端操作、先进先出的线性表D队列是在两端操作、先进先出的线性表7.栈和队列的共同点_A都是先进后出 B都是先进先出C只允许

3、在端点处插入和删除元素 D没有共同点8.以下数据结构中哪一个是非线性结构？_A队列 B栈 C线性表 D二叉树9.若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3 ，pn，若p1=n，则 pi 为_Ai Bn=i Cn-i+1 D不确定10.当利用大小为 N 的一维数组顺序存储一个栈时，假定用top=N 表示栈空，则向这个栈插入一个元素时，首先应执行_语句修改top指针。Atop+ Btop- Ctop=0 Dtop11.4个元素进S栈的顺序是 A,B,C,D,经运算 POP(S)后栈顶元素是_AA BB CC DD12.一个栈的输入序列是a,b,c,d,e,则栈的不可能的输

4、出序列是_A. edcba B.decba C.dceab D. abcde13设用链表作为栈的存储结构则退栈操作_。A必须判别栈是否为满 B必须判别栈是否为空C判别栈元素的类型 D对栈不作任何判别14设输入序列是 1、2、3、n，经过栈的作用后输出序列的第一个元素是 n，则输出序列中第i个输出元素是_。A n-i Bn-1-i Cn+1-i D不能确定15递归函数f(n)=f(n-1)十 n(n>1) 的递归出口是_。Af(1)=0 Bf(1)=1 Cf(0)=1 Df(n)=n16中缀表达式A-(B+CD)*E 的后缀形式是_。AABC+D*E- BABCD+E*- CAB-C+DE

5、* DABC-+D/E*17.字符 A、B、C、D 依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成_个不同的字符串？A.15 B.14 C.16 D.2118.字符 A 、B 、C 依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成_个不同的字符串？A.14 B.5 C.6 D.819判定一个循环队列QU(最多元素为 m0)为满队列的条件是_AQU->front=QU->rear BQU->front!=QU->rearCQU->front=(QU->rear+1)m0 DQU->front!=(QU->rear+1)

6、m020.以下哪一个不是队列的基本运算？_A. 在队列第 i 个元素之后插入一个元素 B.从队头删除一个元素C. 判断一个队列是否为空 D.读取队头元素的值21设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和 E6依次通过栈 S，一个元素出栈后即进入队列Q，若 6个元素出列的顺序为E2、E4、E3、E6、E5 和 E1，则栈S 的容量至少应该是_。A6 B4 C3 D222.用链接方式存储的队列，在进行插入运算时_。A. 仅修改头指针 B.头、尾指针都要修改C. 仅修改尾指针 D.头、尾指针可能都要修改23. 若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 fr

7、ont 的值分别为 0 和 3。当从队列中删除一个元素，再加入两个元素后，rear和front 的值分别为_？A. 1和5 B.2和4 C. 4和2 D. 5和124将一个递归算法改为对应的非递归算法时，通常需要使用_。A.栈 B.队列 C.循环队列 D.优先队列25在循环队列中用数组 A0.m-1 存放队列元素，其队头和队尾指针分别为 front和rear，则当前队列中的元素个数是_。A. (front-rear+1)%m B. (rear-front+1)%mC(front-rear+m)%m D. (rear-front+m)%m二填空题1. 栈和队列分别称为_的线性表。2. 栈结构允许

8、进行删除操作的一端为_。3. 向一个由HS指向的链栈中插入一个结点时p 时，需要执行的操作是_；删除一个结点时，需要执行的操作是_（假设栈不空而且无需回收被删除结点）。4. 向量、栈和队列都是_结构，可以在向量的_ 位置插入和删除元素；对于栈只能在_ 插入和删除元素；对于队列只能在 _插入和_ 删除元素。5. 栈是一种特殊的线性表，允许插入和删除运算的一端称为_ 。不允许插入和删除运算的一端称为_ 。6. 栈又称为_表，队列又称为_表。7. 当用长度为N 的数组顺序存储一个栈时，假定用top=N 表示栈空，则表示栈满的条件是_。8. 设输入序列为1、2、3，则经过栈的作用后可以得到_种不同的输

9、出序列。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

10、。 （ ）6. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （ ）7. 不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。 （ ）8. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （ ）9. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （ ）10. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 （ ）11. 高级语言中通常利用“递归工作栈”来处理递归。 （ ）四、简答题1.简述栈与队列的相同点与不同点。2.在顺序队列中，什么叫真溢出？什么叫假溢出？

11、为什么顺序队列常都采用循环队列结构？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)

12、int i,n,A255;n=0;while(!StackEmpty(S) n+; Pop(S,An); for(i=1;i<=n;i+) Push(S,Ai);(2) status algo2(Stack S,int e)Stack T; int d;InitStack(T);while(!StackEmpty(S)Pop(S,d);if(d!=e) Push(T,d);while(!StackEmpty(T)Pop(T,d);Push(S,d);五程序算法题1. 设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（不设头指针），试编写相应的入队列、出队列算法。2.设计一个输出如下形式数值的递归算法。4 4 4 43 3 32 23.试证明：若借助栈由输入序列12n得到的输出序列为(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i<j<k使<<。4.按照四则运算加、减、乘、除和幂运算()优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A-B×C/D+EF5.假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个函数decpair(exp,flag)；其中exp为表示算术表达式的字符串变量，flag用于返回是否匹配的结果。6.编写一个算法，利