数据结构第三章栈和队列练习及答案

一、选择题1、栈中存取数据的原则（）A、先进先出B、先进后出C、后进后出D、随意进出2、队列中存取数据的原则（）A、先进先出B、后进先出C、先进后出D、随意进出3、插入和删除只能在一端进行的线性表，称为（）A、队列B、循环队列C、栈D、循环栈4、在栈中，出栈操作的时间复杂度为（）A、O（1）B、O（log2n）C、O（n）D、O（n2）5、设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为（）A、O（1）B、O（log2n）C、O（n）D、O（n2）6、设长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为（）A、O（1）B、O（log2n）C、O（n）D、O（n2）7、一个线性表的第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（）A、110B、108C、100D、1208、一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（）A、edcbaB、decbaC、dceabD、abcde9、若已知一个栈的入栈序列是1，2，3，n，其输出序列是p1,p2,p3,pn，若p1=n，则pi为（）A、iB、n=iC、n-i+1D、不确定10、判断一个栈ST（最多元素m0）为空的条件是（）A、ST-top=0B、ST-top=-1C、ST-top!=m0D、ST-top=m011、判断一个栈ST（最多元素m0）为满的条件是（）A、ST-top!=0B、ST-top=0C、ST-top!=m0D、ST-top=m012、判断一个循环队列QU（最多元素为m0）为空的条件是（）A、QU.front=QU.rearB、QU.front!=QU.rearC、QU.front=(QU.rear+1)%m0D、QU.front!=(QU.rear+1)%m013、判断一个循环队列QU（最多元素为m0）为满的条件是（）A、QU.front=QU.rearB、QU.front!=QU.rearC、QU.front=(QU.rear+1)%m0D、QU.front!=(QU.rear+1)%m014、循环队列用数组存放其元素值A0，m-1，已知其头尾指针分别是rear和front，则当前队列的元素个数是（）A、(rear-front+m)%mB、rear-front+1C、rear-front-1D、rear-front15、栈和队列的共同特点是（）A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除 D、没有共同点二、填空题1、设长度为n的链队列用单循环链表表示，若只设头指针，则入队和出队操作的时间复杂度分别为（O(N)）和（O(1)）；若又设尾指针，则入队和出队操作的时间复杂度分别为（O(1)）和（O(1)）。2、线性表、栈和队列均是（线性）结构，可以在线性表的（N+1）位置上插入和删除元素；对于栈只能在（第N+1）插入和和在（第N）位置上删除元素；对于队列只能在（第N+1）位置上插入元素和在（第1）位置上删除元素。3、栈中存取数据遵从的原则是（后进先出）。4、队列中存取数据遵从的原则是（先进先出）。