第3章 栈和队列.ppt

第3章 栈和队列一、判一、判 断断 题题 1、、 栈与队列是一种特殊操作的线性表栈与队列是一种特殊操作的线性表1、（、（ √√）） 2、、 栈和队列都是限制存取点的线性结构栈和队列都是限制存取点的线性结构2、（、（ √√ ）） 3、、 队列是一种插入与删除操作分别在表的两端进行的队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构线性表，是一种先进后出型结构3、（、（ × ））4、队列和栈都是运算受限的线性表，只允许在表的两、队列和栈都是运算受限的线性表，只允许在表的两端进行运算端进行运算4、（、（ × ））5、栈和队列都是线性表，只是在插入和删除时受到、栈和队列都是线性表，只是在插入和删除时受到了一些限制了一些限制5、（、（ √√））6、栈和队列的存储方式，既可以是顺序方式，又可、栈和队列的存储方式，既可以是顺序方式，又可以是链式方式以是链式方式6、（、（ √√ ）） 二、选择题二、选择题1、、一个栈的输入序列为一个栈的输入序列为1，，2，，3，，…，，n，若，若输出序列的第一个元素是输出序列的第一个元素是n，输出第，输出第i（（1<=i<=n）个元素是（）个元素是（ ）。

A. 不确定不确定 B. n-i+1 C. i D. n-i答案：答案：B 2、若一个栈的输入序列为、若一个栈的输入序列为1,2,3,…,n，输出序列的，输出序列的第一个元素是第一个元素是i，则第，则第j个输出元素是（个输出元素是（ ） A. i-j-1 B. i-j C. j-i+1 D. 不确定的不确定的答案：答案：D 3、设栈的输入序列是、设栈的输入序列是1，，2，，3，，4,则（则（ ）不可能）不可能是其出栈序列是其出栈序列 A. 1，，2，，4，，3 B. 2，，1，，3，，4 C. 1，，4，，3，，2 D. 4，，3，，1，，2答案：答案：D4、、一个栈的输入序列为一个栈的输入序列为1，， 2，， 3，， 4，， 5则下则下列序列中不可能是栈的输出序列的是（列序列中不可能是栈的输出序列的是（ ） A. 2，， 3，， 4，，1，， 5 B. 5，， 4，， 1 ，，3，， 2 C. 2，， 3，， 1，， 4，， 5 D. 1，， 5，， 4，， 3，， 2答案：答案：B 5、设有三个元素、设有三个元素X，，Y，，Z顺序进栈（进的过程中顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是允许出栈），下列得不到的出栈排列是( )。

A．．XYZ B. YZX C. ZXY D. ZYX答案：答案：C 6、输入序列为、输入序列为ABC，可以变为，可以变为CBA时，经过的栈时，经过的栈操作为（操作为（ ）） A. push，，pop，，push，，pop，，push，，pop B. push，，push，，push，，pop，，pop，，pop C. push，，push，，pop，，pop，，push，，pop D. push，，pop，，push，，push，，pop，，pop答案：答案：B7、用链接方式存储的队列，在进行删除运算时（、用链接方式存储的队列，在进行删除运算时（ ） A. 仅修改头指针仅修改头指针 B. 仅修改尾指针仅修改尾指针 C. 头、尾指针都要修改头、尾指针都要修改 D. 头、尾指针可能都要修改头、尾指针可能都要修改答案：答案：D8、假设存储空间、假设存储空间m来存储循环队列的元素来存储循环队列的元素,其头尾指针其头尾指针分别为分别为front和和rear，则当前队列中的元素个数为（，则当前队列中的元素个数为（ ）。

A．．(rear-front+m)%m B．．rear-front+1 C．．(front-rear+m)%m D．．(rear-front)%m答案：答案：A9、、若用一个大小为若用一个大小为6的数组来实现循环队列，的数组来实现循环队列，且当前且当前rear和和front的值分别为的值分别为0和和3，当从队，当从队列中删除一个元素，再加入两个元素后，列中删除一个元素，再加入两个元素后，rear和和front的值分别为多少？的值分别为多少？( ) A. 1和和 5 B. 2和和4 C. 4和和2 D. 5和和1 答案：答案：B10、、若以若以1,2,3,4作为双端队列的输入序列，则作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是输出受限的双端队列得到的输出序列是( ) A. 1234 B. 4132 C. 4231 D. 4213答案：答案：C11、、最大容量为最大容量为n的循环队列，队尾指针是的循环队列，队尾指针是rear，队头，队头是是front，若队空下面正确的是，若队空下面正确的是 （（ ）。

A. (rear+1) % n=front B. rear=front C．．rear+1=front D. (rear-l) % n=front答案：答案：B12、、栈和队列的共同点是（栈和队列的共同点是（ ） A. 都是先进先出都是先进先出 B. 都是先进后出都是先进后出 C. 只允许在端点处插入和删除元素只允许在端点处插入和删除元素 D. 没有共同点没有共同点答案：答案：C13、、设栈设栈S和队列和队列Q的初始状态为空，元素的初始状态为空，元素e1，，e2，，e3，，e4，，e5和和e6依次通过栈依次通过栈S，一个元，一个元素出栈后即进队列素出栈后即进队列Q，若，若6个元素出队的序列个元素出队的序列是是e2，，e4，，e3，，e6，，e5，，e1则栈则栈S的容量至的容量至少应该是少应该是( ) A．． 6 B. 4 C. 3 D. 2答案：答案：C。