数据结构-C语言版-第二版(严蔚敏)-第3章--栈和队列-答案

第3章栈和队列1．选择题（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。A．5，4，3，2，1B．2，1，5，4，3C．4，3，1，2，5D．2，3，5，4，1答案：C解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。A．iB．n-iC．n-i+1D．不确定答案：C解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…，n，而输出序列的第一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，…，pi=n-i+1。（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。A．r-fB．(n+f-r)%nC．n+r-fD．（n+r-f)%n答案：D解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。（4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。A．x=top-data;top=top-link；B．top=top-link;x=top-link；C．x=top;top=top-link；D．x=top-link；答案：A解释：x=top-data将结点的值保存到x中，top=top-link栈顶指针指向栈顶下一结点，即摘除栈顶结点。（5）设有一个递归算法如下intfact(intn){//n大于等于0if(n=0)return1;elsereturnn*fact(n-1);}则计算fact(n)需要调用该函数的次数为（）。A．n+1B．n-1C．nD．n+2答案：A解释：特殊值法。设n=0，易知仅调用一次fact(n)函数，故选A。（6）栈在（）中有所应用。A．递归调用B．函数调用C．表达式求值D．前三个选项都有答案：D解释：递归调用、函数调用、表达式求值均用到了栈的后进先出性质。（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。A．队列B．栈C．线性表D．有序表答案：A解释：解决缓冲区问题应利用一种先进先出的线性表，而队列正是一种先进先出的线性表。（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。A．2B．3C．4D．6答案：B解释：元素出队的序列是e2、e4、e3、e6、e5和e1，可知元素入队的序列是e2、e4、e3、e6、e5和e1，即元素出栈的序列也是e2、e4、e3、e6、e5和e1，而元素e1、e2、e3、e4、e5和e6依次进入栈，易知栈S中最多同时存在3个元素，故栈S的容量至少为3。（9）若一个栈以向量V[1..n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是()。A．top++;V[top]=x;B．V[top]=x;top++;C．top--;V[top]=x;D．V[top]=x;top--;答案：C解释：初始栈顶指针top为n+1，说明元素从数组向量的高端地址进栈，又因为元素存储在向量空间V[1..n]中，所以进栈时top指针先下移变为n，之后将元素x存储在V[n]。（10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A．线性表的顺序存储结构B．队列C.线性表的链式存储结构D.栈答案：D解释：利用栈的后进先出原则。（11）用链接方式存储的队列，在进行删除运算时（）。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改答案：D解释：一般情况下只修改头指针，但是，当删除的是队列中最后一个元素时，队尾指针也丢失了，因此需对队尾指针重新赋值。（12）循环队列存储在数组A[0..m]中，则入队时的操作为（）。A.rear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)答案：D解释：数组A[0..m]中共含有m+1个元素，故在求模运算时应除以m+1。（13）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。A.(rear+1)%n==frontB.rear==frontC．rear+1==frontD.(rear-l)%n==front答案：B解释：最大容量为n的循环队列，队满条件是(rear+1)%n==front，队空条件是rear==front。（14）栈和队列的共同点是（）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点答案：C解释：栈只允许在栈顶处进行插入和删除元素，队列只允许在队尾插入元素和在队头删除元素。（15）一个递归算法必须包括（）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分答案：B2．算法设计题（1）将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长。试编写双栈初始化，判断栈空、栈满、进栈和出栈等算法的函数。双栈数据结构的定义如下：Typedefstruct{inttop[2],bot[2];//栈顶和栈底指针SElemType*V;//栈数组intm;//栈最大可容纳元素个数}DblStack[题目分析]两栈共享向量空间，将两栈栈底设在向量两端，初始时，左栈顶指针为-1，右栈顶为m。两栈顶指针相邻时为栈满。两栈顶相向、迎面增长，栈顶指针指向栈顶元素。[算法描述](1)栈初始化intInit(){S.top[0]=-1;S.top[1]=m;return1;//初始化成功}(2)入栈操作：intpush(stkS,inti,intx)∥i为栈号，i=0表示左栈，i=1为右栈，x是入栈元素。入栈成功返回1，失败返回0{if(i0||i1){cout“栈号输入不对”endl;exit(0);}if(S.top[1]-S.top[0]==1){cout“栈已满”endl;return(0);}switch(i){case0:S.V[++S.top[0]]=x;return(1);break;case1:S.V[--S.top[1]]=x;return(1);}}∥push(3)退栈操作ElemTypepop(stkS,inti)∥退栈。i代表栈号，i=0时为左栈，i=1时为右栈。退栈成功时返回退栈元素∥否则返回-1{if(i0||i1){cout“栈号输入错误”endl；exit(0);}switch(i){case0:if(S.top[0]==-1){cout“栈空”endl；return（-1）；}elsereturn(S.V[S.top[0]--]);case1:if(S.top[1]==m{cout“栈空”endl;return(-1);}elsereturn(S.V[S.top[1]++]);}∥switch}∥算法结束(4)判断栈空intEmpty();{return(S.top[0]==-1&&S.top[1]==m);}[算法讨论]请注意算法中两栈入栈和退栈时的栈顶指针的计算。左栈是通常意义下的栈，而右栈入栈操作时，其栈顶指针左移（减1），退栈时，栈顶指针右移（加1）。（2）回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)[题目分析]将字符串前一半入栈，然后，栈中元素和字符串后一半进行比较。即将第一个出栈元素和后一半串中第一个字符比较，若相等，则再出栈一个元素与后一个字符比较，……，直至栈空，结论为字符序列是回文。在出栈元素与串中字符比较不等时，结论字符序列不是回文。[算法描述]#defineStackSize100//假定预分配的栈空间最多为100个元素typedefcharDataType;//假定栈元素的数据类型为字符typedefstruct{DataTypedata[StackSize];inttop;}SeqStack;intIsHuiwen(char*t){//判断t字符向量是否为回文，若是，返回1，否则返回0SeqStacks;inti,len;chartemp;InitStack(&s);len=strlen(t);//求向量长度for(i=0;ilen/2;i++)//将一半字符入栈Push(&s,t[i]);while(!EmptyStack(&s)){//每弹出一个字符与相应字符比较temp=Pop(&s);if(temp!=S[i])return0;//不等则返回0elsei++;}return1;//比较完毕均相等则返回1}（3）设从键盘输入一整数的序列：a1,a2,a3，…，an，试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。[算法描述]#definemaxsize栈空间容量voidInOutS(ints[maxsize])//s是元素为整数的栈，本算法进行入栈和退栈操作。{inttop=0;//top为栈顶指针，定义top=0时为栈空。for(i=1;i=n;i++)//n个整数序列作处理。{cinx);//从键盘读入整数序列。if(x!=-1)//读入的整数不等于-1时入栈。｛if(top==maxsize-1){cout“栈满”endl;exit(0);}elses[++top]=x;//x入栈。｝else//读入的整数等于-1时退栈。{if(top==0){cout“栈空”endl;exit(0);}elsecout“出栈元素是”s[top--]endl;}}}//算法结束。（4）从键盘上输入一个后缀表达式，试编写算法计算表达式的值。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：23434+2*$。[题目分析]逆波兰表达式(即后缀表达式)求值规则如下：设立运算数栈OPND,对表达式从左到右扫描(读入)，当表达式中扫描到数时，压入OPND栈。当扫描到运算符时，从OPND退出两个数，进行相应运算，结果再压入OPND栈。这个过程一直进行到读出表达式结束符$，这时OPND栈中只有一个数，就是结果。[算法描述]floatexpr()//从键盘输入逆波兰表达式，以‘$’表示输入结束，本算法求逆波兰式表达式的值。｛floatOPND[30];//OPND是操作数栈。init(OPND);//两栈初始化。floatnum=0.0;//数字初始化。cinx;//x是字符型变量。while(x!=’$’){switch{case‘0’=x=’9’:while((x=’0’&&x=’9’)||x==’.’)//拼数if(x!=’.’)//处理整数{num=num*10+（ord(x)-ord(‘0’)）;cinx;}else//处理小数部分。{scale=10.0;cinx;while(x=’0’&&x=’9’){num