数据结构(栈和队列)习题与答案

一、单选题1、元素A、B、C、D依次进栈后，栈顶元素是_______。A.BB.DC.CD.A正确答案：B2、经过以下运算后，x的值是_______。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x)A.0B.bC.aD.1正确答案：C3、经过以下栈运算后，StackEmpty(s)的值是_______。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y)A.0B.bC.aD.1正确答案：D4、已知一个栈的进栈序列是ABC，出栈序列为CBA，经过栈的操作是_______。A.push,push,push,pop,pop,popB.push,pop,push,push,pop,popC.push,push,pop,pop,push,popD.push,pop,push,pop,push,pop正确答案：A5、若元素a、b、c、d、e、f依次进栈，允许进栈、退栈的操作交替进行，但不允许连续3次退栈工作，则不可能得到的出栈序列是_______。A.bcaefdB.afedcbC.cbdaefD.dcebfa正确答案：B6、设一个栈的输入序列为A、B、C、D，则借助一个栈所得的输出序列不可能是_______。A.DCBAB.DABCC.ACDBD.ABCD正确答案：B7、一个栈的进栈序列是abcde，则栈的不可能的输出序列是_______。A.decbaB.abcdeC.dceabD.edcba正确答案：C8、已知一个栈的进栈序列是1，2，3，…n，其输出序列的第一个元素是i（1≤i≤n），则第j（1≤j≤n）个出栈元素是_______。A.n-iB.j-i+1C.iD.不确定正确答案：D9、已知一个栈的进栈序列是1,2,3，…n，其输出序列是p1,p2,…pn，若p1=n,则pi的值是_______。A.不确定B.n-i+1C.n-iD.i正确答案：B10、设n个元素的进栈序列是p1,p2,…pn，其输出序列是1,2,3，…n，若pn=1，则pi（1≤i≤n-1）的值是_______。A.不确定B.iC.n-iD.n-i+1正确答案：D11、设n个元素的进栈序列是1,2,3，…n，其输出序列是p1,p2,…pn，若p1=3，则p2的值是_______。A.一定是1B.以上都不对C.不可能是1D.一定是2正确答案：C12、设n个元素的进栈序列是p1,p2,…pn，其输出序列是1,2,3，…n，若p3=1，则p1的值是_______。A.不可能是2B.不可能是3C.一定是2D.可能是2正确答案：A13、设n个元素的进栈序列是p1,p2,…pn，其输出序列是1,2,3，…n，若p3=3，则p1的值是_______。A.可能是2B.不可能是1C.一定是1D.一定是2正确答案：A14、设有5个元素的进栈序列是a，b，c，d，e，其输出序列是c，e，d，b，a，则该栈的容量至少是_______。A.2B.4C.1D.3正确答案：B15、在数据处理过程中常需要保存一些中间数据，如果后保存的数据先处理，则使用_______来保存这些数据。A.栈B.队列C.线性表D.单链表正确答案：A16、判定一个顺序栈st为（元素个数最多为MaxSize）空的条件为_______。A.st.top==MaxSizeB.st.top!=MaxSizeC.st.top!=-1D.st.top==-1正确答案：D17、判定一个顺序栈st为（元素个数最多为MaxSize）为栈满的条件为_______。A.st.top=-1B.st.top!=MaxSize-1C.st.top！==-1D.st.top==MaxSize-1正确答案：D18、表达式a*(b+c)-d的后缀表达式是_______。A.abcd*+-B.abc*+d-C.-+*abcdD.abc+*d-正确答案：D19、若一个栈用数组data[1..n]存储，初始栈顶指针top为n+1，则以下元素x进入栈的正确操作是_______。A.top--;data[top]=x;B.top++;data[top]=x;C.data[top]=x;top--;D.data[top]=x;top++;正确答案：A20、若一个栈用数组data[1..n]存储，初始栈顶指针top为n，则以下元素x进入栈的正确操作是_______。A.top--;data[top]=x;B.data[top]=x;top--;C.top++;data[top]=x;D.data[top]=x;top++;正确答案：B21、若一个栈用数组data[1..n]存储，初始栈顶指针top为0，则以下元素x进入栈的正确操作是_______。A.data[top]=x;top++;B.data[top]=x;top--;C.top--;data[top]=x;D.top++;data[top]=x;正确答案：D22、若一个栈用数组data[1..n]存储，初始栈顶指针top为1，则以下元素x进入栈的正确操作是_______。A.top--;data[top]=x;B.data[top]=x;top++;C.top++;data[top]=x;D.data[top]=x;top--;正确答案：B23、链栈与顺序栈相比有一个明显的优点，即_______。A.总是不会出现栈空的情况B.删除操作更加方便C.通常不会出现栈满的情况D.插入操作更方便正确答案：C24、以下各链表均不带有头节点，其中最不合适用作链栈的链表是_______。A.只有表头指针没有表尾指针的循环单链表B.只有表尾指针没有表头指针的循环双链表C.只有表尾指针没有表头指针的循环单链表D.只有表头指针没有表尾指针的循环双链表正确答案：A25、如果以链表作为栈的存储结构，则退栈操作时_______。A.判断链栈元素的类型B.对链栈不做任何判断C.必须判断链栈是否空D.必须判断链栈是否为满正确答案：C26、向一个不带头节点的栈顶指针为lst的链栈中插入一个s所指向节点时，则执行_______。A.s->next=lst->next;lst->next=s;B.lst->next=s;C.s->next=lst;lst=s;D.s->next=lst;lst->next=s;正确答案：C27、从一个不带头节点的栈顶指针为lst的栈链中删除一个节点时，用x保存被删节点的值，则执行_______。A.x=lst->data;lst=lst->next;B.x=lst;lst=lst->next;C.lst=lst->next;x=lst->data;D.x=lst->data正确答案：A28、栈和队列的不同点是_______。A.都不是线性表B.没有不同点C.都是线性表D.栈只能在一端进行插入删除操作，而队列在不同端进行插入删除操作正确答案：D29、经过下列运算后，队头的元素是_______。InitQueue(qu);Enqueue(qu,‘a’);EnQueue(qu,‘b’);EnQueue(qu,‘c’);DeQueue(qu);A.bB.aC.0D.1正确答案：A30、若某循环队列有队首指针front和队尾指针rear，在队不满时进队操作仅会改变_______。A.frontB.rearC.以上都不对D.front和rear正确答案：B31、循环队列qu的队满条件（front队首指针指向队首元素的前一位置，rear队尾指针指向队尾元素）是_______。A.(qu.rear+1)%maxsize==qu.front+1B.(qu.rear+1)%maxsize==qu.frontC.qu.rear==qu.frontD.(qu.rear+1)%maxsize==(qu.front+1)%maxsize正确答案：B32、设循环队列中数组的下标是0~N-1，其队头、队尾指针分别为f和r（f指向队首元素的前一位置，r指向队尾元素），则元素个数为_______。A.r-fB.r-f-1C.(r-f)%N+1D.(r-f+N)%N正确答案：D33、最适合用做链队列的不带表头节点的链表是_______。A.带首节点指针和尾节点指针的循环单链表B.只带尾节点指针的非循环单链表C.只带尾节点指针的循环单链表D.只带首节点指针的非循环单链表正确答案：C34、假设用一个不带表头节点的单链表表示队列，在进行删除操作时，_______。A.仅修改尾指针B.仅修改头指针C.头、尾指针可能都要修改D.头、尾指针都要修改正确答案：C35、假设用一个不带头节点的单链表表示队列，队头和队尾指针分别为front和rear，则判断队空的条件是_______。A.front==NULLB.rear!==NULLC.front==rearD.front!==NULL正确答案：A36、最不合适用做链队的不带头节点的链表是_______。A.只带队首节点指针的循环双链表B.以上都不合适C.只带队首节点指针的非循环单链表D.只带队尾节点指针的循环双链表正确答案：C37、假设用qu[0..M]实现循环队列，f、r分别为队首元素的前一个位置和队尾位置。若用“(r+1)%(M+1)==f”作为队满的标志，则_______。A.队列中最多可以有M+1个元素B.可用“f==r”作为队空的标志C.可用“(f+1)%(M+1)==r”作为队空的标志D.可用“f>r”作为队空的标志正确答案：B38、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别是0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是_______。A.4和2B.2和4C.1和5D.5和1正确答案：B二、判断题1、栈底元素是不能删除的元素。（×）2、顺序栈中元素值的大小是有序的。（×）3、n个元素依次进栈，它们的出栈顺序和进栈顺序一定正好相反。（×）4、栈顶元素和栈底有可能是同一元素。（√）5、若用s[0..m-1]表示顺序栈的存储空间，则对栈的进栈、出栈操作最多只能进行m次；（×）6、栈是一种对进栈、出