《数据结构》习题集第3章 栈和队列.docx

《《数据结构》习题集第3章 栈和队列.docx》由会员分享，可在线阅读，更多相关《《数据结构》习题集第3章 栈和队列.docx（9页珍藏版）》请在三一办公上搜索。

1、数据结构习题集第3章 栈和队列第3章 栈和队列 一、 选择题 1. 栈结构通常采用的两种存储结构是。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2. 设栈ST 用顺序存储结构表示，则栈ST 为空的条件是 A、ST.top-ST.base0 B、ST.top-ST.base=0 C、ST.top-ST.basen D、ST.top-ST.base=n 3. 向一个栈顶指针为HS 的链栈中插入一个s 结点时，则执行 A、HS-next=s; B、s-next=HS-next；HS-next=s; C、s-next=HS；HS=s;

2、 D、s-next=HS；HS=HS-next; 4. 从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行 A 、x=HS；HS=HS-next; B 、HS=HS-next；x=HS-data; C 、x=HS-data；HS=HS-next; D 、s-next=Hs；Hs=HS-next; 5. 表达式a*(b+c)-d 的后缀表达式为 A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6. 中缀表达式A-*E 的后缀形式是 A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7. 一个队列

3、的入列序列是1，2，3，4， 则队列的输出序列是 A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 8. 循环队列SQ 采用数组空间SQ.base0,n-1存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为空的条件是 A、Q.rear-Q.front=n B、Q.rear-Q.front-1=n C、Q.front=Q.rear D、Q.front=Q.rear+1 9. 循环队列SQ 采用数组空间SQ.base0,n-1存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为满的条件是 A、Q.front=Q.rea

4、r B、Q.front!=Q.rear C、Q.front=(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 10. 若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为 A、1，5 B、2, 4 C、4，2 D、5，1 11. 用单链表表示的链式队列的队头在链表的位置 A、链头 B、链尾 C、链中 12. 判定一个链队列Q为空的条件是 A、Q.front=Q.rear B、Q.front!=Q.rear C、Q.front=(Q.rear+1)%n D、Q

5、.front!=(Q.rear+1)%n 13. 在链队列Q 中，插入s 所指结点需顺序执行的指令是 A 、Q.front-next=s；f=s; B 、Q.rear-next=s；Q.rear=s; C 、s-next=Q.rear；Q.rear=s; D 、s-next=Q.front；Q.front=s; 14. 在一个链队列Q 中，删除一个结点需要执行的指令是 A、Q.rear=Q.front-next; B、Q.rear-next=Q.rear-next-next; C、Q.front-next=Q.front-next-next; D、Q.front=Q.rear-next; 1/

6、5 15. 用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时 A、仅修改队头指针 B、仅修改队尾指针 C、队头尾指针都要修改 D、队头尾指针都可能要修改。 16. 栈和队列的共同点是 A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 17. 消除递归需要使用栈。 A、一定 B、不一定 18. 设有一顺序栈S，元素s1，s2，s3，s4，s5，s6 依次进栈，如果6 个元素出栈的顺序是s2，s3，s4，s6，s5，s1，则栈的容量至少应该是 A、2 B、3 C、 5 D、 6 19. 若一个栈的输入序列是a，b，c

7、，则通过入、出栈操作可能得到a,b,c 的不同排列个数为 A、 4 B、 5 C、 6 D、 7 20. 设有一顺序栈已经含有3 个元素，如图3.1 所示元素a4 正等待进栈。下列不可能出现的出栈序列是 A、a3,a1,a4,a2 B、 a3,a2,a4,a1 C、 a3,a4,a2,a1 D、 a4,a3,a2,a1 图3.1 21. 链栈和顺序栈相比，有一个比较明显的优势是 A、通常不会出现栈满的情况 B、通常不会出现栈空的情况 C、插入操作更容易实现 D、删除操作更加容易实现 22. 若一个栈的输入序列是1，2，3，4，n，输出序列的第一个元素是n，则第i 个输出元素是 A、不确定 B、

8、 n-i C、 n-i+1 D、n-i-1 二、 判断题 1. 在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。 2. 链栈与顺序栈相比的一个优点是链栈插入和删除操作更加方便。 3. 若一个栈的输入序列为 1，2，3，n，其输出序列的第一个元素为n，则其输出序列的每个元素一定满足ai=i+1(i=1,2, ,n)。X 4. 在链队列中，即使不设置尾指针也能进行入队操作。 5. 在对链队列做出队操作时，不会改变 front 指针的值。 6. 循环队列中元素个数为 rear-front。 7. 一个栈的输入序列是 1,2,3,4，则在栈的输出序列中可以得到4,3,1,2。 8. 一个栈的输

9、入序列是 1,2,3,4，则在栈的输出序列中可以得到1,2,3,4。 9. 若以链表作为栈的存储结构，则进栈需要判断栈是否满。 10. 若以链表作为栈的存储结构，则出栈需要判断栈是否空。 三、 填空题 1. 栈的特点是，队列的特点是。 2/5 2. 线性表、栈、队列都是结构，可以在线性表的位置插入和删除元素；对于栈只能在插入和删除元素；对于队列只能在插入元素和在位置删除元素。 3. 有程序如下，则此程序的输出结果是。 void main stack s; char x,y; initstack (s); x=c; y=k; push(s,x); push(s,a); push(s,y); po

10、p(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. 在栈顶指针为HS 的链栈中，判定栈空的条件是。 5. 向栈中压入元素的操作是先后。 6. 对栈进行退栈操作是先后。 7. 用循环单链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是和；若只设尾指针，则出队和入队的时间复杂度分别是和。 8. 从循环队列中删除一个元素时，其操作是。 9. 在一个循环队列中，队首指针指向队首元素的。 10. 在具有n 个单元的循环队列中，

11、队满时共有个元素。 11. 在HQ 的链队列中，判断只有一个结点的条件是。 12. 设栈S 和队列Q 的初始状态为空，元素a、b、c、d、e、f 依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b、d、c、f、e、a 则栈S 的容量至少应该是。 13. 有程序如下，则此程序的输出结果是。 void main char x=e,y=c; enqueue(q,h);enqueue(q,r);enqueue(q,y);dequeue(q,x);enqueue(q,x);degueue(q,x); enqueue(q,a); while(!queueempty(q) dequeue

12、(q,y);printf(y); printf(x); 14. 有如下递归函数： int dunno(int m) 3/5 int value; if(m=0) value=3; else value=dunno(m-1)+5; return(value); 执行语句printf(“%dn”,dunno(3);的结果是。 四、 简答题 1. 对于堆栈，给出三个输入项A，B，C，如果输入项序列为ABC，试给出全部可能的输出序列，并写 出每种序列对应的操作。例如：A 进B 进C 进C 出B 出A 出，产生的序列为CBA。 2. 简述以下算法的功能。 status algo1(stack s) in

13、t 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); 3. 内存中一片连续空间提供给两个栈s1 和s2 使用，怎样分配这部分存储空间，使得对任一栈仅当这部分空间全满时才发生溢出。 4.

14、 有递归过程如下： void print(int w) 4/5 int I; if(w!=0) print(w-1); for(I=1;I=w;I+) printf(“%3d”,w); printf(“n”); 问：调用语句print(4)的结果是什么？ 5. 简述以下算法的功能 void algo(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); 6. 假设 Q0，9是一个非循环线性队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的状态变化情况，如果不能入队，请指出其元素，并说明理由。 d,e,b,g,h 入队 d,e 出队 I,j,k,l,m入队 b 出队 n,o,p,q,r 入队。 7. 按照运算符优先数法，画出对下面算术表达式求值时，操作数栈和运算符栈的变化过程： 9-2*4+(8+1)/3。 5/5