数据结构作业：第三章--栈和队列作业答案.docx

第三章栈和队列 一选择题对于栈操作数据的原则是（B ）。
A. 先进先出 B.后进先出C.后进后出 D.不分顺序在作进栈运算时，应先判别栈是否（①B ），在作退栈运算时应先判别栈是否（②A ）。 当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为（③B ）o为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应 将两栈的（④D ）分别设在这片内存空间的两端，这样，当（⑤C ）时，才产生上溢。
①，②：A.空
B.满
C.上溢
D.下溢
③：A. n-1
B. n
C. n+1
D. n/2
©: A,长度
B.深度
C.栈顶
D.栈底

⑤：A.两个栈的栈顶同时到达栈空间的中心点.
B. 其中一个栈的栈顶到达栈空间的中心点.
C. 两个栈的栈顶在栈空间的某一位置相遇.
D. 两个栈均不空，且一个栈的栈顶到达另一个栈的栈底.
1. 一个栈的输入序列为123...n,若输出序列的第一个元素是n,输出第i （l<=i<=n） 个元素是（B ） °不确定 B. n-i+1 C. i D. n-i若一个栈的输入序列为1,2,3,输出序列的第一个元素是i,则第j个输出元素是（D ）。
A. i-j-1 B. i-j C. j-i+1 D.不确定的若己知一个栈的入栈序列是l,2,3,...,n,其输出序列为pi,p2,P3,…，Pn,若Pn是n, 则pi是（D ）。
A. i B. n-i C. n-i+1 D.不确定有六个元素6, 5, 4, 3, 2, 1的顺序进栈，问下列哪一个不是合法的出栈序列？（C ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6设栈的输入序列是1, 2, 3, 4,则（D ）不可能是其出栈序列。
A. 1, 2, 4, 3,
B. 2, 1, 3, 4,
C. 1, 4, 3, 2,
4, 3, 1, 2, E. 3, 2, 1, 4,一个栈的输入序列为1 2 3 4 5,则下列序列中不可能是栈的输出序列的是（B ）。
A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2设一个栈的输入序列是1,2, 3, 4, 5,则下列序列中，是栈的合法输出序列的是（D ）。
A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4某堆栈的输入序列为a, b, c , d,下面的四个序列中，不可能是它的输出序列的是（D ）。
A. a, c, b, d B. b, c, d, a C. c, d, b, a D. d, c, a, b设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列 为（D ）。
A. fedcba B. bcafed C. dcefba D. cabdef设有三个元素X, Y, Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是（C ）。
A. XYZ B. YZX C. ZXY D. ZYX输入序列为ABC,可以变为CBA时，经过的栈操作为（B ）A.push,pop,push,pop,push,popB. push,push,push,pop,pop,pop
C. push,push,pop,pop, push,popD. push,pop,push,push,pop,pop若栈采用顺序存储方式存储，现两栈共享空间V[l.・m], top[i]代表第i个栈（i =1,2） 栈顶，栈1的底在v[l],栈2的底在V[m],则栈满的条件是（B ）。
A. |top[2]-top[l]|=0 B. top[l] + l=top[2] C.
top[l]+top[2] = m D.top[l]=top[2]设计一个判别表达式中左，右括号是否配对出现的算法，采用（D ）数据结构最佳。
A.线性表的顺序存储结构B.队列 C.线性表的链式存储结构D.栈用链接方式存储的队列，在进行删除运算时（D ）。
A.仅修改头指针 B.仅修改尾指针 C.头、尾指针都要修改 D.头、尾指针可能都 要修改用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结 点，则在进行删除操作时（D ）。
A.仅修改队头指针 B.仅修改队尾指针C.队头、队尾指针都要修改D,队头，队尾指针都可能要修改栈的特点是（①），队列的特点是（②），栈和队列都是（③）。若进栈序列 为1,2,3,4则（④）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列 的序列为1,2,3,4则（⑤）是一个出队列序列。BACCF①，②：A.先进先出B.后进先出 C.进优于出D.出优于进
③ ：A.顺序存储的线性结构B.链式存储的线性结构C.限制存取点的线性结构 D.限制存取点的非线性结构，⑤：A. 3,2,1,4B.3,2,4,1C. 4,2,3,1 D. 4,3,2,1 F. 1,2,3,4G.
1,324栈和队都是（C ）A.顺序存储的线性结构B,链式存储的非线性结构C.限制存取点的线性结构D.限制存取点的非线性结构
二判断题两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈 底分别设在这片内存空间的两端。（V ）即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得 的输出序列也一定相同。（x ）队列是•种插入与删除操作分别在表的两端进行的线性表，是•种先进后出型结构。
（x ）队列逻辑上是一个下端和上端既能增加又能减少的线性表。（V ）循环队列也存在空间溢出问题。（V ）队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（x ）
1. 栈和队列都是线性表，只是在插入和删除时受到了一些限制。（V ）栈和队列的存储方式，既可以是顺序方式，乂可以是链式方式。（V ）四应用题名词解释：栈、队列、循环队列？
栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈 底。最后插入的元素最先删除，故栈也称后进先出（LIFO）表。
队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端 叫队头。最先插入队的元素最先离开（删除），故队列也常称先进先出（FIFO）表。
循环队列：用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和 队头删除），容易造成''假溢出〃现象，即队尾已到达一维数组的高下标，不能再插入，然而 队中元素个数小于队列的长度（容量）。循环队列是解决''假溢出”的一种方法。通常把一维 数组看成首尾相接。在循环队列下，通常采用''牺牲一个存储单元''或''作标记''的方法解决''队 满''和''队空''的判定问题简述顺序存储队列的假溢出的避免方法及队列满和空的条件。
假溢出避免方法：采取循环队列的形式。
1. 怎样判定循环队列的空和满？
在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用''牺牲一 个单元"，即rear+l=front （准确记是（rear+1） %m=front, m是队列容量）时为队 满。另一种解法是''设标记"方法，如设标记tag, tag等于0情况下，若删除时导致 front=rear为队空；tag = 1情况下，若因插入导致front=rear则为队满。