数据结构域算法设计-第3章 桟和队列教案

《数据结构域算法设计-第3章 桟和队列教案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章桟和队列3.1　选择题1．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1≤i≤n）个元素是（　　）A）不确定B）n-i+1C）iD）n-i【答案】B【解析】根据栈的性质（LIFO），若输出的第一个元素是n，则表明所有的元素已经入栈，则出栈顺序为n，n-1，…，3，2，1。2．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是（　　）A）6B）4C）3D）2【答案】C【解析】根据栈的性质（LIFO）得，e2出栈前，

2、栈中存有e1和e2两个元素，e4出栈前，栈中存有e1、e3和e4三个元素，e4和e3出栈以后，e5和e6入栈，栈中同样存在e1、e5和e6三个元素，然后三个元素依次出栈，所以栈的容量至少应该为3。3．若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是（　　）A）top=top+1;V[top]=xB）V[top]=x;top=top+1C）top=top-1;V[top]=xD）V[top]=x;top=top-1【答案】C【解析】栈式运算受限的线性表，只允许在栈顶进行插入和删除操作。本题中栈顶指针为n+1，该数组将栈顶放在了下标大的一端，

3、所以在进行入栈操作时top指针应该进行减一操作。通常元素进栈的操作为：先移动栈顶指针后存入元素。4．如果我们用数组A[1..100]来实现一个大小为100的栈，并且用变量top来指示栈顶，top的初值为0，表示栈空。请问在top为100时，再进行入栈操作，会产生（）A）正常动作B）溢出C）下溢D）同步【答案】B【解析】当top为100时，表示栈已经满了，此时再进行入栈操作，则会造成溢出。5．栈在（　　）中应用。A）递归调用B）子程序调用C）表达式求值D）A，Ｂ，Ｃ【答案】D7．用链接方式存储的队列，在进行删除运算时（　　）A）仅修改头指针B）仅修改尾指针C）头、尾指针都要修改

4、D）头、尾指针可能都要修改【答案】D【解析】若队列中的元素多于一个，删除队列中的队尾元素，只需修改队尾指针；若队列中只有一个元素，删除该元素后，队头队尾指针都需要修改。8．循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是()A）(rear-front+m)%mB）rear-front+1C）rear-front-1D）rear-front【答案】A【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的求元素个数的运算可以利用求模运算。9．若用一个大小为6的数组来实现循环队列，且当前rear和fro

5、nt的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？()A）1和5B）2和4C）4和2D）5和1【答案】B【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的加1运算通常用求模运算来实现。所以入队和出队时的操作分别为：rear=(rear+1)%m，front=(front+1)%m。10．栈和队列的共同点是（　　）A）都是先进先出B）都是先进后出C）只允许在端点处插入和删除元素D）没有共同点【答案】C【解析】栈和队列都是运算受限的线性表，只允许在表端点处进行操作。11．在一个链队列中，假定front和

6、rear分别为队头和队尾指针，则插入*s结点的操作为（　　）A）front->next=s;front=s;B）s->next=rear;rear=s;C）rear->next=s;rear=s;D）s->next=front;front=s;【答案】C【解析】队列是运算受限的线性表（FIFO），插入元素只能插在队尾，所以需修改队尾指针。12．判定一个栈S（元素个数最多为MAXSIZE）为空和满的条件分别为（　　）A）S->top!=-1S->top!=MAXSIZE-1B）S->top=-1S->top=MAXSIZE-1C）S->top=-1S->top!=MAXSIZE

7、-1D）S->top!=-1S->top=MAXSIZE-1【答案】B3.2　填空题1．栈是_____________的线性表，其运算遵循_____________的原则。【答案】（1）操作受限（或限定仅在表尾进行插入和删除操作）（2）后进先出2．设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_____________，而栈顶指针值是_____________H。设栈为顺序栈，每个元素