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

第3章栈和队列3.1栈一、填空题1.线性表、栈和队列都是结构，可以在线性表的位置插入和删除元素；对于栈只能___________插入和删除元素；对于队列只在__________插入元素，并且只在___________删除元素。2.栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为。3.向栈中压入元素的操作是先，后。4.从栈中弹出元素的操作是先，后。二、选择题：1.（）栈中元素的进出原则是（）。A．先进先出B．后进先出C．栈空则进D．栈满则出2.（）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。A．iB．n=iC．n-i+1D．不确定3.（）判定一个栈ST（最多元素个数为m0）为空的条件是（）。A．ST-top0B．ST-top=0C．ST-topm0D．ST-top=m04.（）有六个元素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,25.（）将递归算法转换成非递归算法时，通常要借助的数据结构是（）。A.线性表B.栈C.队列D.树6.（）若栈采用顺序存储方式存储，现两栈共享空间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]7.（）一个递归算法必须包括（）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分8.（）从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷对应栏内。设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作。在进栈操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈初始状态都是空。现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是A，第二次出栈得到的元素是B；经操作后，最后在栈中的元素还有C个。供选择的答案：A～B：①a1②a2③a3④a4C：①1②2③3④09.（）从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。在做进栈运算时，应先判别栈是否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.一定是2B.一定是1C.不可能是1D.以上都不对11.表达式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．试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。3.假设表达式有单字母变量和双目四则运算算符构成，试写一个算符，将一个通常书写形式切书写正确的表达式转换成逆波兰式（即后缀表达式）。4.如上题的假设条件，试写一个算法，对以逆波兰式表示的表达式求值。5.用一个一维数组S（设大小为maxsize）作为两个栈的共享空间。请说明共享方法，栈满和栈空的判断条件，并设计初始化栈InitStack(st)、进栈Push(st,i,x)和出栈Pop(st,i,x)等算法，其中i为0表示第一个栈，i为1表示第二个栈。3.2队列一、填空题1.队列只能在插入和删除元素。是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。2.在具有n个单元的循环队列中，队满时共有个元素。3.循环队列的引入，目的是为了克服_______________。4.队列的特点是________________。二、选择题1.（）为解决计算机主机与打印机之间的速度不匹配问题，通常设计一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。A．栈B．队列C．树D．图2.（）不允许对队列进行的操作有（）。A．对队列中的元素遍历B．在队尾插入元素C．在队列第一个元素之前插入元素D．删除队头元素3.（）若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。A．1和5B．2和4C．4和2D．5和14.（）数组Q［n］用来表示一个循环队列，f为当前队列头元素的位置，r为尾元素的位置的下一个位置，假定队列中元素的个数小于n，计算队列中元素的公式为()A.r－fB.（n＋f－r）%nC.n＋r－fD.（n＋r－f）%n5.（）从供选择的答案中，选出应填入下面叙述内的最确切的解答，把相应编号写在答卷的对应栏内。设有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，则队空的条件是（）。A.(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);}}六、算法设计题1.假设以带头结点的循环链单表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。第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,否则返回0InitStack(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)