资源描述：
《数据结构教学全套课件(李学刚)电子资源同步训练及参考答案 单元3 同步训练及答案.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、单元3同步训练及参考答案一、单项选择题1．栈操作数据的原则是（）。A．先进先出B．后进先出C．后进后出D．不分顺序2．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。A．不确定B．n-i+1C．iD．n-i3．若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。A．i-j-1B．i-jC．j-i+1D．不确定4．设一个栈的进栈序列是6，5，4，3，2，1，则不是合法的出栈序列为（）。A．543612B．453126C．346521D
2、．2341565．设一个栈的输入序列是1，2，3，4，5，则合法输出序列的是（）。A．51234B．45132C．43125D．321546．若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。A．
3、top[2]-top[1]
4、==0B．top[1]+1==top[2]C．top[1]+top[2]==mD．top[1]==top[2]7．栈在（）中应用。A．递归调用B．子程序调用C．表达式求值D．A，B，C8．
5、设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A．线性表的顺序存储结构B．队列C．线性表的链式存储结构D．栈9．栈与一般线性表的区别主要是()。A．元素个数B．逻辑结构C．元素类型D．插入和删除元素的位置10．在栈中，出栈操作的时间复杂度是()。A．O(1)B．O(log2n)C．O(n)D．O(n2)11．队列操作数据的原则是（）。A．先进先出B．后进先出C．先进后出D．不分顺序12．若以第（2）种方法（详见第69页）表示循环队列，循环队列的入队操作应为()。A．Q.rear=Q.rear+
6、1;sq.data[Q.rear]=x;B．Q.data[Q.rear]=x;Q.rear=Q.rear+1;C．Q.rear=(Q.rear+1)%QueueSize;Q.data[Q.rear]=x;D．Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%QueueSize;13．若以第（2）种方法（同第12题）表示循环队列，循环队列的出队操作为()。A．Q.fornt=(Q.front+1)%QueueSize;B．Q.fornt=Q.front+1;C．Q.rear=(Q.rear+1)%Qu
7、eueSize;D．Q.rear=Q.rear+1;14．若以第（2）种方法（同第12题）表示循环队列，循环队列的队满条件为()。A．(Q.rear+1)%QueueSize==(Q.front+1)%QueueSize;B．(Q.rear+1)%QueueSize==Q.front+1;C．(Q.rear+1)%QueueSize==Q.front;D．Q.rear==Q.front;15．若以第（2）种方法（同第12题）表示循环队列，循环队列的队空条件为()。A．(Q.rear+1)%QueueSize==(Q.f
8、ront+1)%QueueSize;B．(Q.rear+1)%QueueSize==Q.front+1;C．(Q.rear+1)%QueueSize==Q.front;D．Q.rear==Q.front;16．一个队列的入队序列是1,2,3,4,则队列的可能输出序列是()。A．4,3,2,1B．1,2,3,4C．1,4,3,2D．3,2,4,117．队和栈的主要区别是()。A．逻辑结构不同B．存储结构不同C．限定插入和删除的位置不同D．所包含的元素个数不同18．在链队列执行入队操作()。A．需要判别队列是否为空B．需要
9、判别队列是否满C．限制在链表头进行操作D．限制在链表尾进行操作19．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3时，当从队列中删除一个元素，再加上两个元素后，rear和front的值分别为()。A．1和5B．2和4C．4和2D．5和120．若进栈次序为a，b，c，且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是()。A．3B．5C．6D．7二、问题解答题1．设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若入
10、、出栈次序为Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop(),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop()表示出栈)?(2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。(3)请分析1，2，3，4的24种排列中，哪些序列是可以通
