Lesson4_栈和队列(习题)(精品).ppt

《Lesson4_栈和队列(习题)(精品).ppt》由会员分享，可在线阅读，更多相关《Lesson4_栈和队列(习题)(精品).ppt（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1一个栈的入栈序列是一个栈的入栈序列是A，B，C，D，E，则栈的不可能的输出序列是，则栈的不可能的输出序列是_。(A)EDCBA(B)DECBA(C)DCEAB(D)ABCDE2栈结构通常采用的两种存储结构是栈结构通常采用的两种存储结构是_。(A)顺序存储结构和链式存储结构顺序存储结构和链式存储结构(B)散列散列方式和索引方式方式和索引方式(C)链式存储结构和数组链式存储结构和数组(D)线性存储结构和非线性存储结构线性存储结构和非线性存储结构一一.单项选择题单项选择题3循环队列循环队列SQ采用数组空间采用数组空间SQ.data0，n-l存存放其元素值，已知其头尾指标分别是放其元素值，已知其头尾

2、指标分别是front和和rear，则当前队列中的元素个数是则当前队列中的元素个数是()。A.(rear-front+n)%nB.rear-front+lC.rear-front-lD.rear-front4.中缀表达式中缀表达式A-(B+C/D)*E的后缀形式是的后缀形式是()。A.AB-C+DE*B.ABC+DE*C.ABCDE*+-D.ABCD+E*-5一个队列的入列序列是一个队列的入列序列是1，2，3，4，则队列的，则队列的输出序列是输出序列是()。A.4，3，2，1B1，2，3，4C1，4，3，2D3，2，4，16.若在一个大小为若在一个大小为6的数组上实现循环队列，且当前的数组上实现

3、循环队列，且当前rear和和front的值分别为的值分别为0和和3，当从队列中删除一，当从队列中删除一个元素，再加入两个元素后，个元素，再加入两个元素后，rear和和front的值分别的值分别为为()。A.1和和5B.2和和4C.4和和2D.5和和l7用不带头结点的单链表存储队列，其队头指针指用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指标指向队尾结点，则在进行出队向队头结点，队尾指标指向队尾结点，则在进行出队运算时运算时()。A.仅修改队头指针仅修改队头指针B.仅修改队尾指针仅修改队尾指针C.对头、队尾指针都要修改对头、队尾指针都要修改D.对头、对尾指对头、对尾指针都可能要修改

4、针都可能要修改8.若进栈序列为若进栈序列为a，b，c，则通过入出栈运算可能得，则通过入出栈运算可能得到的到的a，b，c的不同排列个数为的不同排列个数为()。A.4B.5C.6D.79设数组设数组datam作为循环队列作为循环队列SQ的存储空间，的存储空间，front为队头指针，为队头指针，rear为队尾指针，为队尾指针，则执行出队运算后其头指针则执行出队运算后其头指针front值为值为()。A.front=front+lB.front=(front+l)%(m-l)C.front=(front-1)%mD.front=(front+l)%m10.在一个链队中，假定在一个链队中，假定front和

5、和rear分别为队首指分别为队首指标和队尾指标，则删除一个结点的运标和队尾指标，则删除一个结点的运算应执行算应执行()。A.front=front-next；B.rear=rear-next;C.rear=front-next;D.front=rear-next;11向一个栈顶指标为向一个栈顶指标为hs的链栈中插入结点的链栈中插入结点*s时，时，应执行应执行()。A.hs-next=s；B.s-next=hs;hs=s;C.s-next=hs-next;hs-next=s;D.s-next=hs;hs=hs-next:12.在具有在具有n个单元的顺序循环队列中，假定个单元的顺序循环队列中，假定

6、front和和rear分别为队首指针和队尾指针，分别为队首指针和队尾指针，顺序表的下标下界从顺序表的下标下界从0开始，则判断队满的条件是开始，则判断队满的条件是()。A.(l+rear)%n=frontB.(l+rear)%(n-l)=frontC.l+rear%n=frontD.(l+front)%n=rear二二.填空题填空题1.栈是一种特殊的线性表，允许插入和删除栈是一种特殊的线性表，允许插入和删除运算的一端称为运算的一端称为。不允许插入和删。不允许插入和删除运算的一端称为除运算的一端称为。2.向栈中压入元素的操作是先向栈中压入元素的操作是先，后，后。从供选择的答案中，选出应填入下面叙述

7、从供选择的答案中，选出应填入下面叙述？内的最确切的解答，内的最确切的解答，把相应编号写在答卷的对应栏内。把相应编号写在答卷的对应栏内。栈是一种线性表，它的特点是栈是一种线性表，它的特点是A。设用一维数组。设用一维数组A1,n来来表示一个栈，表示一个栈，An为栈底，用整型变量为栈底，用整型变量T指示当前栈顶位置，指示当前栈顶位置，AT为栈顶元素。往栈中推入（为栈顶元素。往栈中推入（PUSH）一个新元素时，变量）一个新元素时，变量T的的值值B；从栈中弹出（；从栈中弹出（POP）一个元素时，变量）一个元素时，变量T的值的值C。设。设栈空时，有输入序列栈空时，有输入序列a，b，c，经过，经过PUSH，

8、POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是操作后，从栈中弹出的元素的序列是D，变量，变量T的值是的值是E。供选择的答案：供选择的答案：A：先进先出先进先出后进先出后进先出进优于出进优于出 出优于进出优于进随机进出随机进出B，C：加加1减减1不变不变清清0加加2减减2D：a,bb,cc,ab,ac,ba,cE：n+1n+2nn-1n-2在做进栈运算时，应先判别栈是否在做进栈运算时，应先判别栈是否A；在做退栈运算时，应先；在做退栈运算时，应先判别栈是否判别栈是否B。当栈中元素为。当栈中元素为n个，做进栈运算时发生上溢，则个，做进栈运算时发生上溢，则说明该栈的最大容量为说明该

9、栈的最大容量为C。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的片连续的内存空间时，应将两栈的D分别设在这片内存空间的分别设在这片内存空间的两端，这样，只有当两端，这样，只有当E时，才产生上溢。时，才产生上溢。供选择的答案：供选择的答案：A，B：空空满满上溢上溢下溢下溢C：n-1nn+1n/2D：长度长度深度深度栈顶栈顶栈底栈底E：两个栈的栈顶同时到达栈空间的中心点两个栈的栈顶同时到达栈空间的中心点其中一个栈的栈其中一个栈的栈顶到达栈空间的中心点顶到达栈空间的中心点两个栈的栈顶在达栈空间的某一位置相遇两个栈的栈顶在达栈空间的某一位置相遇两个栈均不空，两个栈均不空，且一个栈的栈顶到达另一个栈的栈底且一个栈的栈顶到达另一个栈的栈底