数据库系统l试题库及答案-第3章栈与队列(共12页).doc

《数据库系统l试题库及答案-第3章栈与队列(共12页).doc》由会员分享，可在线阅读，更多相关《数据库系统l试题库及答案-第3章栈与队列(共12页).doc（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上第3章 栈和队列3.1栈一、填空题1. 线性表、栈和队列都是 结构，可以在线性表的 位置插入和删除元素；对于栈只能 _插入和删除元素；对于队列只在_插入元素，并且只在_删除元素。2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 。不允许插入和删除运算的一端称为 。3. 向栈中压入元素的操作是先 ，后 。4. 从栈中弹出元素的操作是先 ，后 。二、选择题：1. （ ）栈中元素的进出原则是（ ）。A先进先出 B后进先出 C栈空则进 D栈满则出2. （ ）若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3， pn，若p1=n，则pi为（ ）。Ai

2、Bn=i Cn-i+1 D不确定3. （ ）判定一个栈ST（最多元素个数为m0）为空的条件是（ ）。AST-top0 BST-top=0 CST-topm0 DST-top=m04. （ ）有六个元素1,2,3,4,5,6 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）A. 1,2,3,4,5,6 B. 5,4,3,2,1,6 C. 4,3,2,1,5,6 D. 6,5,4,3,1,25. （ ）将递归算法转换成非递归算法时，通常要借助的数据结构是（ ）。A. 线性表 B. 栈 C. 队列 D. 树 6. （ ）若栈采用顺序存储方式存储，现两栈共享空间V1.m，topi代表第i个栈( i

3、=1,2)栈顶， 栈1的底在v1，栈2的底在Vm，则栈满的条件是（ ）。A. |top2-top1|=0 B. top1+1=top2 C. top1+top2=m D. top1=top27. （ ）一个递归算法必须包括（ ）。A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分8. （ ）从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷 对应栏内。 设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作。在进栈操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈初始状态都是空。现要进行的栈操作是进栈两次，出栈一次，再进

4、栈两次，出栈一次；这时，第一次出栈得到的元素是 A ，第二次出栈得到的元素是 B ；经操作后，最后在栈中的元素还有 C 个。 供选择的答案： AB：a1 a2 a3 a4 C： 1 2 3 09. （ ）从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷 的对应栏内。 在做进栈运算时，应先判别栈是否 A ；在做退栈运算时，应先判别栈是否 B 。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为 C 。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 D 分别设在这片内存空间的两端，这样，只有当 E 时，才产生上溢。

5、 供选择的答案： A，B：空 满 上溢 下溢C： n-1 n n+1 n/2 D： 长度 深度 栈顶 栈底 E：两个栈的栈顶同时到达栈空间的中心点 其中一个栈的栈顶到达栈空间的中心点 两个栈的栈顶在达栈空间的某一位置相遇 两个栈均不空，且一个栈的栈顶到达另一个栈的栈底10. 设n个元素进栈序列是1,2,3,n，其输出序列是p1,p2,pn，若p1=3，则p2的值( ) 。A. 一定是2B. 一定是1 C.不可能是1 D. 以上都不对11. 表达式a*(b+c)-d的后缀表达式是( )。 A.abcd*+- B.abc+*d- C.abc*+d- D.-+*abcd三、简答题1设有编号为1，2，

6、3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。2写出下列程序段的输出结果（栈的元素类型SElem Type为char）。void main( )Stack S;Char x,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假设一个算术表达式中包含圆括弧、方括弧和花括弧三种

7、类型的括弧，编写一个判别表达式中括弧是否正确配对的函数correct(exp,tag)；其中：exp为字符串类型的变量（可理解为每个字符占用一个数组元素），表示被判别的表达式，tag为布尔型变量。2试写一个算法判别读入的一个以为结束符的字符序列是否是“回文”。3. 假设表达式有单字母变量和双目四则运算算符构成，试写一个算符，将一个通常书写形式切书写正确的表达式转换成逆波兰式（即后缀表达式）。4. 如上题的假设条件，试写一个算法，对以逆波兰式表示的表达式求值。5. 用一个一维数组S（设大小为maxsize）作为两个栈的共享空间。请说明共享方法，栈满和栈空的判断条件，并设计初始化栈InitStac

8、k(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. （

9、 ）不允许对队列进行的操作有（ ）。A对队列中的元素遍历 B在队尾插入元素C在队列第一个元素之前插入元素 D删除队头元素3. （ ）若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ）。A1和5 B2和4 C4和2 D5和14. （ ）数组Qn用来表示一个循环队列，f为当前队列头元素的位置，r为尾元素的位置的下一个位置，假定队列中元素的个数小于n，计算队列中元素的公式为( ) A.rf B.（nfr）% n C.nrf D.（nrf）% n5. （ ）从供选择的答案中，选出应填入下面叙述

10、 内的最确切的解答，把相应编号写在答卷的对应栏内。 设有4个数据元素a1、a2、a3和a4，对他们分别进行队操作。在进队操作时，按a1、a2、a3、a4次序每次进入一个元素。假设队的初始状态都是空。考虑对这四个数据元素进行的队操作是进队两 次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 A ，第二次出队得到的元素是 B 。经操作后，最后在栈中或队中的元素还有 C 个。 供选择的答案： AB：a1 a2 a3 a4 C： 1 2 3 06.（ ）最大容量为n的循环队列，队尾是rear，队头是front，则队空的条件是 （ ）。A. (rear+1) MOD n=front B.

11、 rear=front Crear+1=front D. (rear-l) MOD n=front 7. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队满的条件是 （ ）。 A. (rear+1) MOD n=front B. rear=front C. （rear-l) MOD n=front D. rear=(front+1 )MOD n8. ( ) 栈和队列的共同点是( )。A. 都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除 D.没有共同点 9. （ ）最适合做链式队列的链表是( )。 A.带队首指针和队尾指针的循环单链表 B. 带队首指针和队尾指针的

12、非循环单链表 C.只带队首指针的非循环单链表 D. 只带队尾指针的循环单链表 三、 判断题 1.（ ）无论是循环队列还是链式队列，插入和删除运算的时间复杂度都是O(1)。2（ ）对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 3（ ）栈和队列是一种非线性数据结构。 4（ ）栈和队列的存储方式既可是顺序方式，也可是链接方式。5（ ）队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。6( ）通常使用队列来处理函数或过程的调用。7.（ ）栈和队列都是线性表，只是在插入和删除时受到了一些限制。8.（ ）队列用于操作系统中的作业调度。四、简答题1.设循环队列

13、的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 front=11，rear=19; front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？2.顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？五、阅读理解1. 写出下列程序段的输出结果（队列中的元素类型QElem Type为char）。void main( )Queue Q; Init Queue (Q);Char x=e; y=c;EnQueue (Q,h); EnQueue (Q,r); EnQueue (Q, y);DeQueue (Q,x); EnQueue (Q,x); DeQue

14、ue (Q,x); EnQueue (Q,a); while(!QueueEmpty(Q) DeQueue (Q,y);printf(y); ;Printf(x); 2. 简述以下算法的功能（栈和队列的元素类型均为int）。void algo3(Queue &Q)Stack S; int d;InitStack(S);while(!QueueEmpty(Q) DeQueue (Q,d); Push(S,d);while(!StackEmpty(S) Pop(S,d); EnQueue (Q,d); 六、 算法设计题1. 假设以带头结点的循环链单表表示队列，并且只设一个指针指向队尾元素结点（注意

15、不设头指针），试编写相应的队列初始化、入队列和出队列的算法。第3章 栈和队列3.1栈一、填空题1.线性 任何 栈顶 表尾 表头 2.栈顶 栈底 3. 存入元素 移动栈顶指针 4.移动栈顶指针 栈顶元素出栈二、选择题1.B 2.C 3.B 4.D 5.B 6.B 7.B 8.( 2,4,2) 9.(2,1,2,4,3) 10.C 11.B三、简答题1至少有14种。 全进之后再出情况，只有1种：4，3，2，1 进3个之后再出的情况，有3种，3,4,2,1 3,2,4,1 3,2,1,4 进2个之后再出的情况，有5种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4

16、进1个之后再出的情况，有5种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,32输出为“stack”。五、算法设计题1Status AllBrackets_Test(char *str)/判别表达式中三种括号是否匹配 InitStack(s); for(p=str;*p;p+) if(*p=(|*p=|*p=) push(s,*p); else if(*p=)|*p=|*p=) if(StackEmpty(s) return ERROR; pop(s,c); if(*p=)&c!=() return ERROR; if(*p=&c!=) return ERROR

17、; if(*p=&c!=) return ERROR; /必须与当前栈顶括号匹配 /for if(!StackEmpty(s) return ERROR; return OK; /AllBrackets_Test 2int Palindrome_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

18、); if(a!=b) return ERROR; return OK;/Palindrome_Test3.void trans(char *exp,char postexp) /将算术表达式exp转换成后缀表达式postexp int i=0;/i作为postexp的下标 InitStack(op)；/op为运算符栈 Push（op，=）；/将=进栈 while (*exp!=0)/exp表达式未扫描完时循环 if (!InOp(*exp)/为数字字符的情况 postexpi+=*exp;exp+; else/为运算符的情况 switch(Precede(op.dataop.top,*exp

19、)/判断优先级 case -1: /栈顶运算符的优先级低:进栈Push(op,*exp);exp+; /继续扫描其他字符break; case 0: /只有括号满足这种情况Pop(op,e); /将(退栈exp+; /继续扫描其他字符break; case 1: Pop(op,e); /退栈并输出到postexp中postexpi+=e; break; GetTop(op,e);while (e!=) /此时exp扫描完毕,退栈到=为止Pop(op,e);postexpi+=e; GetTop(op,e);postexpi=0;/给postexp表达式添加结束标识4.float compval

20、ue(char *postexp )/计算后缀表达式的值 OPNDStack OPND;/定义数值栈InitStack_OPND(OPND);float d,a,b,c,e;while (*postexp!=0)/postexp字符串未扫描完时循环switch (*postexp)case +:/判定为+号 Pop_OPND(OPND,a); /退栈取数值a Pop_OPND(OPND,b); /退栈取数值b c=a+b;/计算cPush_OPND(OPND,c);/将计算结果进栈 break;case -:/判定为-号 Pop_OPND(OPND,a); /退栈取数值a Pop_OPND(O

21、PND,b); /退栈取数值b c=b-a;/计算c Push_OPND(OPND,c);/将计算结果进栈 break;case *:/判定为*号 Pop_OPND(OPND,a); /退栈取数值a Pop_OPND(OPND,b); /退栈取数值bc=a*b;/计算cPush_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(nt除零错误!n)

22、;exit(0);/异常退出break; default:/处理数字字符 Push_OPND(OPND,postexp+);break; GetTop_OPND(OPND,e);return(e);5. 定义数据结构：typedef structchar datamaxsize;int top1,top2;Stack;void InitStack(Stack &S)S.top1=0;S.top2=maxsize-1;int Push(Stack &S,int i, ElemType e)if(S.top1+1)=S.top2) return ERRROR;/栈满了不能再进栈if(i=0)/进第

23、1个栈S.dataS.top1=e;S.top1+;else if(i=1) /进第2个栈S.dataS.top2=e;S.top2-;else return ERROR;/输入的i有误return OK;int Pop(Stack &S,int i, ElemType &e) if(i=0)&(S.top1=0)|(i=1)&(S.top2=maxsize-1) return ERROR;/栈空，不能出栈 if(i=0) /从第1个栈出栈 S.top1-;e=S.dataS.top1; else if(i=1)/从第2个栈出栈 S.top2+;e=S.dataS.top2; 3.2队列一、填

24、空题1.队尾 队首 2. 队列 3.n-1 4.队列的假溢出 5.先进先出二、选择题1. B 2. C 3.B 4.D 5.(1,2,2) 6.B 7.A 8.D 9.B 三、判断题1. 2. 3. 4. 5. 6. 7. 8 四、简答题1.用队列长度计算公式： (Nrf)% N L=（401911）% 40=8 L=（401119）% 40=322.一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。采用循环队列是解决假溢出的途径。另外，解决队满队空的办法有三： 设置一个布尔变量以区别队满还是队空； 浪费一个元素的空间，用于区别队满还是队

25、空。 使用一个计数器记录队列中元素个数（即队列长度）。我们常采用法，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。判断循环队列队空标志是： f=rear 队满标志是：f=(r+1)%N五、阅读理解1.输出为“char”。2.该算法的功能是：利用堆栈做辅助，将队列中的数据元素进行逆置。六、算法设计题1.typedef int ElemType;typedef struct QNodeElemType data;QNode *next;QNode,*QPtr;typedef structQPtr rear;int size;Queue;Status InitQueue(Queue&

26、 q)Q.rear=(Qnode*) malloc(sizeof(QNode); if (!Q.rear) exit(OVERFLOW);q.rear-next=q.rear; /空的循环链表q.size=0;return OK; Status EnQueue(Queue& q,ElemType e)QPtr p;p=(Qnode*) malloc(sizeof(QNode);if(!p) return exit(OVERFLOW);p-data=e; /创建被插入结点pp-next=q.rear-next;q.rear-next=p;q.rear=p; /将p所指结点插入到q.rear的后面 q.size+;return OK; Status DeQueue(Queue& q,ElemType& e) QPtr p;if(q.size=0)return FALSE;p=q.rear-next-next; /p指向循环链表的第一个结点（即被删结点）e=p-data; q.rear-next-next=p-next; /删除p所指结点free(p); q.size-;return OK; 专心-专注-专业