数据库系统l试题库及答案-第3章栈与队列

V:1.0精细整理，仅供参考日期：20xx年X月第3章栈和队列3.1栈一、填空题线性表、栈和队列都是结构，可以在线性表的位置插入和删除元素；对于栈只能___________插入和删除元素；对于队列只在__________插入元素，并且只在___________删除元素。栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为。向栈中压入元素的操作是先，后。从栈中弹出元素的操作是先，后。二、选择题：（）栈中元素的进出原则是（）。A．先进先出B．后进先出C．栈空则进D．栈满则出（）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。A．iB．n=iC．n-i+1D．不确定（）判定一个栈ST（最多元素个数为m0）为空的条件是（）。A．ST->top<>0B．ST->top=0C．ST->top<>m0D．ST->top=m0（）有六个元素1,2,3,4,5,6的顺序进栈，问下列哪一个不是合法的出栈序列（）A.1,2,3,4,5,6B.5,4,3,2,1,6C.4,3,2,1,5,6D.6,5,4,3,1,2（）将递归算法转换成非递归算法时，通常要借助的数据结构是（）。A.线性表B.栈C.队列D.树（）若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。A.|top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]（）一个递归算法必须包括（）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分（）从供选择的答案中，选出应填入下面叙述

内的最确切的解答，把相应编号写在答卷对应栏内。设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作。在进栈操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈初始状态都是空。现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是A，第二次出栈得到的元素是B；经操作后，最后在栈中的元素还有C个。供选择的答案：A～B：①a1②a2③a3④a4C：①1②2③3④0（）从供选择的答案中，选出应填入下面叙述

内的最确切的解答，把相应编号写在答卷的对应栏内。在做进栈运算时，应先判别栈是否A；在做退栈运算时，应先判别栈是否B。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为C。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的D分别设在这片内存空间的两端，这样，只有当E时，才产生上溢。供选择的答案：A，B：①空②满③上溢④下溢C：①n-1②n③n+1④n/2D：①长度②深度③栈顶④栈底E：①两个栈的栈顶同时到达栈空间的中心点②其中一个栈的栈顶到达栈空间的中心点③两个栈的栈顶在达栈空间的某一位置相遇④两个栈均不空，且一个栈的栈顶到达另一个栈的栈底10.设n个元素进栈序列是1,2,3,…,n，其输出序列是p1,p2,…,pn，若p1=3，则p2的值()。 A.一定是2 B.一定是1C.不可能是1 D.以上都不对表达式a*(b+c)-d的后缀表达式是()。A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd三、简答题1．设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。2．写出下列程序段的输出结果（栈的元素类型SElemType为char）。voidmain(){StackS;Charx,y;InitStack(S);X=’c’;y=’k’;Push(S,x);Push(S,’a’);Push(S,y);Pop(S,x);Push(S,’t’);Push(S,x);Pop(S,x);Push(S,’s’);while(!StackEmpty(S)){Pop(S,y);printf(y);};Printf(x);}五、算法设计题1．假设一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧，编写一个判别表达式中括弧是否正确配对的函数correct(exp,tag)；其中：exp为字符串类型的变量（可理解为每个字符占用一个数组元素），表示被判别的表达式，tag为布尔型变量。2．试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。假设表达式有单字母变量和双目四则运算算符构成，试写一个算符，将一个通常书写形式切书写正确的表达式转换成逆波兰式（即后缀表达式）。如上题的假设条件，试写一个算法，对以逆波兰式表示的表达式求值。用一个一维数组S（设大小为maxsize）作为两个栈的共享空间。请说明共享方法，栈满和栈空的判断条件，并设计初始化栈InitStack(st)、进栈Push(st,i,x)和出栈Pop(st,i,x)等算法，其中i为0表示第一个栈，i为1表示第二个栈。3.2队列一、填空题队列只能在插入和删除元素。是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。在具有n个单元的循环队列中，队满时共有个元素。循环队列的引入，目的是为了克服_______________。队列的特点是________________。二、选择题（）为解决计算机主机与打印机之间的速度不匹配问题，通常设计一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。A．栈B．队列C．树D．图（）不允许对队列进行的操作有（）。A．对队列中的元素遍历B．在队尾插入元素C．在队列第一个元素之前插入元素D．删除队头元素（）若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。A．1和5B．2和4C．4和2D．5和1（）数组Q［n］用来表示一个循环队列，f为当前队列头元素的位置，r为尾元素的位置的下一个位置，假定队列中元素的个数小于n，计算队列中元素的公式为()A.r－fB.（n＋f－r）%nC.n＋r－fD.（n＋r－f）%n（）从供选择的答案中，选出应填入下面叙述内的最确切的解答，把相应编号写在答卷的对应栏内。设有4个数据元素a1、a2、a3和a4，对他们分别进行队操作。在进队操作时，按a1、a2、a3、a4次序每次进入一个元素。假设队的初始状态都是空。考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是A，第二次出队得到的元素是B。经操作后，最后在栈中或队中的元素还有C个。供选择的答案：A～B：①a1②a2③a3④a4C：①1②2③3④06.（）最大容量为n的循环队列，队尾是rear，队头是front，则队空的条件是（）。(rear+1)MODn=frontB.rear=frontC．rear+1=frontD.(rear-l)MODn=front7.最大容量为n的循环队列，队尾指针是rear，队头是front，则队满的条件是（）。A.(rear+1)MODn=frontB.rear=frontC.（rear-l)MODn=frontD.rear=(front+1)MODn8.()栈和队列的共同点是()。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除D.没有共同点9.（）最适合做链式队列的链表是()。A.带队首指针和队尾指针的循环单链表B.带队首指针和队尾指针的非循环单链表C.只带队首指针的非循环单链表D.只带队尾指针的循环单链表判断题1.（）无论是循环队列还是链式队列，插入和删除运算的时间复杂度都是O(1)。2．（）对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。3．（）栈和队列是一种非线性数据结构。4．（）栈和队列的存储方式既可是顺序方式，也可是链接方式。5．（）队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。6．(）通常使用队列来处理函数或过程的调用。7.（）栈和队列都是线性表，只是在插入和删除时受到了一些限制。8.（）队列用于操作系统中的作业调度。四、简答题1.设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有①front=11，rear=19;②front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？

2.顺序队的“假溢出”是怎样产生的如何知道循环队列是空还是满

五、阅读理解1.写出下列程序段的输出结果（队列中的元素类型QElemType为char）。voidmain(){QueueQ;InitQueue(Q);Charx=’e’;y=’c’;EnQueue(Q,’h’);EnQueue(Q,’r’);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,’a’);while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);};Printf(x);}2.简述以下算法的功能（栈和队列的元素类型均为int）。voidalgo3(Queue&Q){StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Q,d);Push(S,d);};while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);}}算法设计题假设以带头结点的循环链单表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。第3章栈和队列3.1栈一、填空题1.线性任何栈顶表尾表头2.栈顶栈底3.存入元素移动栈顶指针4.移动栈顶指针栈顶元素出栈二、选择题1.B2.C3.B4.D5.B6.B7.B8.(2,4,2)9.(2,1,2,4,3)10.C11.B三、简答题1．至少有14种。①全进之后再出情况，只有1种：4，3，2，1②进3个之后再出的情况，有3种，3,4,2,13,2,4,13,2,1,4③进2个之后再出的情况，有5种，2,4,3,12,3,4,12,1,3,42,1,4,32,1,3,4④进1个之后再出的情况，有5种，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,32．输出为“stack”。五、算法设计题1．StatusAllBrackets_Test(char*str)//判别表达式中三种括号是否匹配{InitStack(s);for(p=str;*p;p++){if(*p=='('||*p=='['||*p=='{')push(s,*p);elseif(*p==')'||*p==']'||*p=='}'){if(StackEmpty(s))returnERROR;pop(s,c);if(*p==')'&&c!='(')returnERROR;if(*p==']'&&c!='[')returnERROR;if(*p=='}'&&c!='{')returnERROR;//必须与当前栈顶括号匹配}}//forif(!StackEmpty(s))returnERROR;returnOK;}//AllBrackets_Test2．intPalindrome_Test(){//判别输入的字符串是否回文序列,是则返回1,否则返回0

InitStack(S);InitQueue(Q);

while((c=getchar())!='@'&&c=getchar())!=''){

Push(S,c);EnQueue(Q,c);//同时使用栈和队列两种结构

}

while(!StackEmpty(S))

{

Pop(S,a);DeQueue(Q,b));

if(a!=b)returnERROR;

}

returnOK;

}//Palindrome_Test3.voidtrans(char*exp,charpostexp[])//将算术表达式exp转换成后缀表达式postexp{inti=0; //i作为postexp的下标InitStack(op)；//op为运算符栈Push（op，’=’）；//将'='进栈while(*exp!='\0') //exp表达式未扫描完时循环if(!InOp(*exp)) //为数字字符的情况 {postexp[i++]=*exp; exp++; }else //为运算符的情况 switch(Precede(op.data[op.top],*exp))//判断优先级 { case-1: //栈顶运算符的优先级低:进栈 Push(op,*exp); exp++; //继续扫描其他字符 break; case0: //只有括号满足这种情况 Pop(op,e); //将(退栈 exp++; //继续扫描其他字符 break; case1:Pop(op,e);//退栈并输出到postexp中 postexp[i++]=e; break; }}GetTop(op,e); while(e!='=')//此时exp扫描完毕,退栈到'='为止 { Pop(op,e); postexp[i++]=e; GetTop(op,e); } postexp[i]='\0'; //给postexp表达式添加结束标识4.floatcompvalue(char*postexp) //计算后缀表达式的值{OPNDStackOPND; //定义数值栈 InitStack_OPND(OPND); floatd,a,b,c,e; while(*postexp!=‘\0’) //postexp字符串未扫描完时循环 { switch(*postexp){ case'+': //判定为'+'号 Pop_OPND(OPND,a);//退栈取数值a Pop_OPND(OPND,b);//退栈取数值b c=a+b; //计算c Push_OPND(OPND,c);//将计算结果进栈break; case'-': //判定为'-'号 Pop_OPND(OPND,a);//退栈取数值a Pop_OPND(OPND,b);//退栈取数值b c=b-a; //计算c Push_OPND(OPND,c);//将计算结果进栈break;case'*': //判定为'*'号 Pop_OPND(OPND,a);//退栈取数值a Pop_OPND(OPND,b);//退栈取数值b c=a*b; //计算c Push_OPND(OPND,c);//将计算结果进栈 break; case'/': //判定为'/'号 Pop_OPND(OPND,a);//退栈取数值a Pop_OPND(OPND,b);//退栈取数值b if(a!=0) { c=b/a; //计算c Push_OPND(OPND,c);//将计算结果进栈 } else { printf("\n\t除零错误!\n"); exit(0); //异常退出 } break;default: //处理数字字符 Push_OPND(OPND,postexp++); break; }GetTop_OPND(OPND,e); return(e);}定义数据结构：typedefstruct{chardata[maxsize];inttop1,top2;}Stack;voidInitStack(Stack&S){ S.top1=0; S.top2=maxsize-1;}intPush(Stack&S,inti,ElemTypee){ if((S.top1+1)==S.top2)returnERRROR;//栈满了不能再进栈 if(i==0){//进第1个栈 S.data[S.top1]=e; S.top1++; } elseif(i==1)//进第2个栈 { S.data[S.top2]=e; S.top2--; } elsereturnERROR;//输入的i有误 returnOK;}intPop((Stack&S,inti,ElemType&e){if(((i==0)&&(S.top1==0))||((i==1)&&(S.top2==maxsize-1)))returnERROR;//栈空，不能出栈if(i==0){//从第1个栈出栈S.top1--; e=S.data[S.top1];}elseif(i==1){//从第2个栈出栈S.top2++; e=S.data[S.top2];}}3.2队列一、填空题1.队尾队首2.队列3.n-14.队列的假溢出5.先进先出二、选择题1.B2.C3.B4.D5.(1,2,2)6.B7.A8.D9.B三、判断题1.√2.√3.×4.√5.×6.×7.√8√四、简答题1.用队列长度计算公式：(N＋r－f)%N①L=（40＋19－11）%40=8②L=（40＋11－19）%40=322.一般的一维数组队列的尾指针已经到了数组的上