第二单元(栈和队列)(答案)

第二单元课后练习题知识点范围：第3章栈和队列一、选择题（每小题1分，共28分）1．栈的特点是B，简称C的线性表；队列的特点是A，简称D的线性表。A．先进先出B．后进先出C．LIFOD．FIFO2．栈和队列的共同点是C。A．都是先进后出B．都是先进先出C．只允许在端点处插入和删除元素D．没有共同点3．一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是C。A．edcbaB．decbaC．dceabD．abcde4．设有一个栈，元素依次进栈的顺序为A、B、C、D、E。下列B是可能的出栈序列。A．D,B,C,A,EB．B,C,D,E,AC．E,A,B,C,DD．E,D,C,A,B5．以下B不是队列的基本运算？A．从队尾插入一个新元素B．从队列中删除第i个元素C．判断一个队列是否为空D．读取队头元素的值6．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1＝n，则pi为C。A．iB．n－iC．n－i＋1D．不确定7．设计一个判别表达式中左、右括号是否配对出现的算法，采用D数据结构最佳。A．线性表的顺序存储结构B．队列C．线性表的链式存储结构D．栈8．判定一个顺序栈st（最多元素为MaxSize）为满的条件是D。A．st-top!=-1B．st-top==-1C．st-top!=MaxSizeD．st-top==MaxSize9．一个队列的入队序列是1，2，3，4，则队列的输出序列是B。A．4，3，2，1B．1，2，3，4C．1，4，3，2D．3，2，4，110．判定一个循环队列qu（最多元素为MaxSize）为空的条件是C。A．qu-rear–qu-front==MaxSizeB．qu-rear–qu-front-1==MaxSizeC．qu-rear==qu-frontD．qu-rear=qu-front-111．若用一个循环队列空间大小为6，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为B。A．1和5B．2和4C．4和2D．5和112．向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行D操作。A．h-next=s;B．s-next=h;C．s-next=h;h=s;D．s-next=h-next;h-next=s;13．输入序列为ABC，若用S表示入栈，X表示出栈操作，则得到CBA输出序列要经过的栈操作序列为B。A．SXSXSXB．SSSXXXC．SSXSXD．SXSSXX14．和顺序栈相比，链栈有一个比较明显的优势是A。A．通常不会出现栈满的情况B．通常不会出现栈空的情况C．插入操作更容易实现D．删除操作更容易实现15．若一个顺序栈中元素为n个,做进栈运算时发生上溢,则说明该栈的最大容量为(B)。A.n-1B.nC.n+1D.n/216．允许对队列进行的操作有D。A．对队列中的元素排序B．取出最近进队的元素C．在队头元素之前插入元素D．删除队头元素17．对于循环队列D。A．无法判断队列是否为空B．无法判断队列是否为满C．队列不可能满D．以上说法都不对18．若一个带头结点的链栈的栈顶指针用top表示，当p指向的结点进栈时，执行的操作是C。A．p-next=top;top=top-next;B．top=p-p;p-next=top;C．p-next=top-next;top-next=p;D．p-next=top;top=p;19．队列的“先进先出”特性是指D。A．最早插入队列中的元素总是最后被删除B．当同时进行插入、删除操作时，总是插入操作优先C．每当有删除操作时，总是要先做一次插入操作D．每次从队列中删除的总是最早插入的元素20．若一个循环队列，其最多元素个数为MAXSIZE，front为头指针，rear为尾指针，则判定满队列的条件是A。A．(rear+1)%MAXSIZE==frontB．rear+1==frontC．rear==frontD．(front+1)%MAXSIZE==rear21．队列是一种A的线性表。A．先进先出B．先进后出C．只能插入D．只能删除22．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为B。A．5，3，4，6，1，2B．3，2，5，6，4，1C．3，1，2，5，4，6D．1，5，4，6，2，323．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为C。A．R-FB．F-RC．(R-F+M)％MD．(F-R+M)％M24．设用链表作为栈的存储结构则退栈操作B。A．必须判别栈是否为满B．必须判别栈是否为空C．判别栈元素的类型D．对栈不作任何判别25．在链队列Q中，front指向链队列的头结点，rear指和队尾元素，若让s所指结点入队需执行的指令是（B）A．Q.front-next=s；f=s;B．Q.rear-next=s；Q.rear=s;C．s-next=Q.rear；Q.rear=s;D．s-next=Q.front；Q.front=s;26．设栈ST用顺序存储结构表示，若top、base分别为指向栈顶和栈底的指针，则栈ST为空的条件是BA、ST.top-ST.base0B、ST.top-ST.base==0C、ST.top-ST.basenD、ST.top-ST.base==n27．设有一顺序栈已经含有3个元素，如图2.1所示元素a4正等待进栈。下列不可能出现的出栈序列是AA、a3,a1,a4,a2B、a3,a2,a4,a1C、a3,a4,a2,a1D、a4,a3,a2,a1图2.128．设有一顺序栈S，若有6个元素按s1，s2，s3，s4，s5，s6的顺序依次进栈，如果6个元素出栈的顺序是s2，s3，s4，s6，s5，s1，则栈的容量至少需要的单元空间个数应该是BA、2B、3C、5D、6二、填空题（每空1分，共25分）1．栈是限定仅在表的一端进行插入或删除操作的线性表，其运算遵循后进先出的原则。2．下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。#defineMAXSIZE100typedefstruct{ints[MAXSIZE];inttop;}sqstack;voidpush(sqstack*stack,intx){if(stack-top==MAXSIZE)printf(“overflow”);else{stack-s[stack-top]=x;stack-top++;}}3．设输入序列为1、2、3，则经过栈的作用后可以得到5种不同的输出序列。4．不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为O(1)。5．设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储___M-1__个队列元素；当前实际存储(R-F+M)%M个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。6．栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__LIFO表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为___FIFO__表。7．设F和R分别表示顺序循环队列的头指针和尾指针，或F指向队头元素的前一个位置，R指向队尾元素则判断该循环队列为空的条件为F==R。8.栈是限定在表的一端进行插入或删除操作的线性表，其运算遵循后进先出的原则。9.若addQ(n)表示元素n入队列Q的入队运算，delQ()表示队列Q的出队运算，当前队列状态为空，则经过addQ(1)，addQ(2)，delQ()，addQ(5)，addQ(7)，delQ()，addQ(9)操作后，队头元素为5，队尾元素为9；若使队列中剩余元素全部出队，还需经过3次delQ()操作。10.栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。11.队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。12.设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则判断该循环队列满的条件为(R+1)%M==F。13.对于顺序存储结构的栈，在做入栈运算时应先判断栈是否栈满；在做出栈运算时应先判断栈是否空栈；当栈中元素为n个，做入栈运算时发生上溢，则说明该栈的最大容量为n个元素空间。三、判断题(每题1分，共12分)1．队列是一种插入和删除操作分别在表的两端进行的线性表，是一种先进后出的结构。（×）2．不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（√）3．在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。(√)4.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（√）5.循环队列中若front指向队头元素的前一个位置，rear指向队尾元素则元素个数为rear-front。（×）6.栈和链表是两种不同的数据结构。(×)错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。7.栈和队列是一种非线性数据结构。(×)错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。8.栈和队列的存储方式既可是顺序方式，也可是链接方式。（√）9.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（√）10.一个栈的输入序列是12345，则栈的输出序列不可能是12345。(×)11.若以链表作为栈的存储结构，则进栈需要判断栈是否满。(×)12.循环队列中元素个数为rear-front。(×)四、计算题(第1小题4分，第2小题3分，第3小题4分，共11分)铁道进行车厢调度，如下图2.2所示a,b二条铁道均为单向行驶，设有1~6编号的6节车厢，若进站的车厢序列为123456，则求解如下问题。(1)能否得到435612和135426的出站序列？(2)写出三种不可能的出站序列。(3)写出2种可能的出站序列及用S表示进栈、X表示出栈的栈操作序列。图2.2答：(1)可以得到135426出站序列，栈操作序列如下：入栈车厢号：123456栈操作：SXSSXSSXXXSX出栈车厢号：135426不能得到435612出站序列因为若4356出栈，说明12已在栈中，则1不可能在2之前出栈，(2)三种不可能的出站序列为：653412、312645、423615(3)二种可能的出站序列及栈操作序列如下：654321SSSSSSXXXXXX321456SSSXXXSXSXSX五、算法设计题(每题12分，共24分)1．应用顺序栈或链栈操作（栈初始化，入栈，出栈）实现进制转换。编程实现输入十进制数转换为八进制输出。例如，输入十进制数56，输出八进制数70#includestdio.h#defineMAXSIZE50#defineN8/*N为转换的进制*/typedefstructstack/*顺序栈类型定义*/{intd[MAXSIZE];inttop;}Seqstack;Seqstack*init()/*顺序栈初始化*/{Seqstack*s;s=(Seqstack*)malloc(sizeof(Seqstack));s-top=0;returns;}voidpush(Seqstack*s,intx)/*入栈操作*/{if(s-topMAXSIZE){s-d[s-top]=x;s-top++;}}intpop(Seqstack*s)/*出栈操作*/{intx;if(s-top0){s-top--;x=s-d[s-top];}returnx;}intmain(intargc,char*argv[])