《数据结构作业：第三章栈和队列作业答案》由会员分享，可在线阅读，更多相关《数据结构作业：第三章栈和队列作业答案（4页珍藏版）》请在装配图网上搜索。
1、第三章 栈和队列一 选择题1. 对于栈操作数据的原则是（ B ）。A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序2. 在作进栈运算时,应先判别栈是否( B ),在作退栈运算时应先判别栈是否( A)。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( B )。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( D)分别设在这片内存空间的两端,这样,当( C )时，才产生上溢。, : A. 空 B. 满 C. 上溢 D. 下溢 : A. n-1 B. n C. n+1 D.n/2 : A. 长度 B. 深度 C. 栈顶 D.
2、栈底 : A. 两个栈的栈顶同时到达栈空间的中心点.B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.3. 一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（ B ）。A. 不确定 B. n-i+1 C.i D. n-i4. 若一个栈的输入序列为1,2,3,n，输出序列的第一个元素是i，则第j个输出元素是（ D ）。A. i-j-1 B. i-j C. j-i+1 D. 不确定的5. 若已知一个栈的入栈序列是1,2,3,n，其输出序列为p1,p2,p3，pN,若pN
3、是n，则pi是( D )。 A. iB. n-i C. n-i+1 D. 不确定6. 有六个元素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 67. 设栈的输入序列是1，2，3，4,则（D ）不可能是其出栈序列。A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2，D. 4，3，1，2， E. 3，2，1，4，8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ B ）。 A. 2 3 4 1 5 B.
4、5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 29. 设一个栈的输入序列是 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 410. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ D ）。 A. a，c，b，dB. b, c，d，a C. c, d，b, a D. d, c，a，b11. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（D ）。Afedcba B. bcafed C
5、. dcefba D. cabdef12. 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( C )。AXYZ B. YZX C. ZXY D. ZYX13. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ B ）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,pop14. 若栈采用顺序存储方式存储，现两栈共享空间V1.m，topi代表第i个栈( i =1,2)栈顶，栈1的底在v1，
6、栈2的底在Vm，则栈满的条件是（B ）。A. |top2-top1|=0 B. top1+1=top2 C. top1+top2=m D.top1=top215. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结构最佳。A线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈16. 用链接方式存储的队列，在进行删除运算时（ D）。A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改17. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( D )。A仅修改队头指针
7、B. 仅修改队尾指针C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改18. 栈的特点是（ ）,队列的特点是（ ）,栈和队列都是（ ）。若进栈序列为1,2,3,4 则（ ）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4 则（ ）是一个出队列序列。BACCF, : A. 先进先出 B. 后进先出 C. 进优于出 D. 出优于进: A.顺序存储的线性结构 B.链式存储的线性结构C.限制存取点的线性结构 D.限制存取点的非线性结构, : A. 3,2,1,4 B.3,2,4,1 C. 4,2,3,1 D. 4,3,2,1F. 1,2,3,4 G. 1,3,
8、2,419. 栈和队都是（C ）A顺序存储的线性结构 B. 链式存储的非线性结构C. 限制存取点的线性结构 D. 限制存取点的非线性结构二 判断题1两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（ ）2. 即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（ ）3. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（ ）4. 队列逻辑上是一个下端和上端既能增加又能减少的线性表。（ ）5. 循环队列也存在空间溢出问题。（ ）6. 队列和栈都是运算受限的线性表，只允
9、许在表的两端进行运算。（ ）7. 栈和队列都是线性表，只是在插入和删除时受到了一些限制。（ ）8. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（ ）四 应用题1. 名词解释：栈、队列、循环队列？栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出（LIFO）表。队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开（删除），故队列也常称先进先出（FIFO）表。循环队列：用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和队头删除），容
10、易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度（容量）。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题2. 简述顺序存储队列的假溢出的避免方法及队列满和空的条件。假溢出避免方法：采取循环队列的形式。3. 怎样判定循环队列的空和满？在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1）%m=front，m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。
数据结构作业：第三章栈和队列作业答案
