Lesson4_栈和队列(习题)

1一个栈的入栈序列是A，B，C，D，E，则栈的不可能的输出序列是_。(A)EDCBA(B)DECBA(C)DCEAB(D)ABCDE2栈结构通常采用的两种存储结构是_。(A)顺序存储结构和链式存储结构(B)散列方式和索引方式(C)链式存储结构和数组(D)线性存储结构和非线性存储结构,一.单项选择题,3循环队列SQ采用数组空间SQ.data0，n-l存放其元素值，已知其头尾指标分别是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的数组上实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为()。A.1和5B.2和4C.4和2D.5和l,7用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指标指向队尾结点，则在进行出队运算时()。A.仅修改队头指针B.仅修改队尾指针C.对头、队尾指针都要修改D.对头、对尾指针都可能要修改8.若进栈序列为a，b，c，则通过入出栈运算可能得到的a，b，c的不同排列个数为()。A.4B.5C.6D.7,9设数组datam作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队运算后其头指针front值为()。A.front=front+lB.front=(front+l)%(m-l)C.front=(front-1)%mD.front=(front+l)%m10.在一个链队中，假定front和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个单元的顺序循环队列中，假定front和rear分别为队首指针和队尾指针，顺序表的下标下界从0开始，则判断队满的条件是()。A.(l+rear)%n=frontB.(l+rear)%(n-l)=frontC.l+rear%n=frontD.(l+front)%n=rear,二.填空题栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为。向栈中压入元素的操作是先，后。,从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。栈是一种线性表，它的特点是A。设用一维数组A1,n来表示一个栈，An为栈底，用整型变量T指示当前栈顶位置，AT为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值B；从栈中弹出（POP）一个元素时，变量T的值C。设栈空时，有输入序列a，b，c，经过PUSH，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个，做进栈运算时发生上溢，则说明该栈的最大容量为C。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的D分别设在这片内存空间的两端，这样，只有当E时，才产生上溢。供选择的答案：A，B：空满上溢下溢C：n-1nn+1n