版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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.一般的一维数组队列的尾指针已经到了数组的上
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 西京学院《建筑装饰材料及施工工艺》2023-2024学年第一学期期末试卷
- 第六首古诗《书湖阴先生壁》
- 西京学院《工程材料与热处理》2023-2024学年第一学期期末试卷
- 西华师范大学《中学数学教材分析》2022-2023学年第一学期期末试卷
- 西华师范大学《艺术思潮与流派》2023-2024学年第一学期期末试卷
- 西华师范大学《文化人类学》2023-2024学年第一学期期末试卷
- 西华师范大学《企业管理学》2022-2023学年第一学期期末试卷
- 西华师范大学《工程制图与打印》2022-2023学年第一学期期末试卷
- 西昌学院《影视戏剧鉴赏》2022-2023学年第一学期期末试卷
- 西昌学院《物联网工程实训》2022-2023学年期末试卷
- 检伤分类课件
- 柿单宁功能成效及其产品介绍综述
- (新版)重症专科护士考试题库(含答案)
- 监理情况汇报(模板)
- 《诗经》两首-完整版课件
- 缺铁性贫血 图文 优质课件
- 商务部绩效考核表
- 无犯罪记录证明书申请表模板(通用)
- 钢结构可行性分析报告
- 高中地理 选必一《自然环境的整体性》第二课时-教学设计
- 我的故乡-德江课件
评论
0/150
提交评论