第三章栈和队列习题 - 数据结构
更新时间:2023-09-23 20:45:01 阅读量: IT计算机 文档下载
- 第三章栈和队列课后题答案推荐度:
- 相关推荐
习题三 栈和队列
一 单项选择题
1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。
①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2
2.若已知一个栈的进栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,...,pn,若p1=3,则p2为( )。
A 可能是2 B 一定是2 C 可能是1 D 一定是1
3. 有六个元素6,5,4,3,2,1 的顺序进栈,问下列哪一个不是合法的出栈序列?( )
A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素出栈的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是 ( )
A.2 B. 3 C. 5 D.6
5. 若栈采用顺序存储方式存储,现两栈共享空间V[1..m],top[i]代表第i个栈( i =1,2)栈顶,栈1的底在v[1],栈2的底在V[m],则栈满的条件是( )。
A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 6. 执行完下列语句段后,i值为:( )
int f(int x)
{ return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1));
A.2 B. 4 C. 8 D. 无限递归 7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时,对象栈和算符栈为( ),其中^为乘幂 。
A. 3,2,4,1,1;(*^(+*- B. 3,2,8;(*^- C. 3,2,4,2,2;(*^(- D. 3,2,8;(*^(- 8. 用链接方式存储的队列,在进行删除运算时( )。
A. 仅修改头指针 B. 仅修改尾指针
C. 头、尾指针都要修改 D. 头、尾指针可能都要修改
9. 递归过程或函数调用时,处理参数及返回地址,要用一种称为( )的数据结构。
A.队列 B.多维数组 C.栈 D. 线性表
10.设C语言数组Data[m+1]作为循环队列SQ的存储空间, front为队头指针,rear为队尾指针,则执行出队操作的语句为 ( )
A.front=front+1 B. front=(front+1)% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( )
A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front
12. 栈和队列的共同点是( )。
A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点
二、填空题
1.栈是_______的线性表,其运算遵循_______的原则。
2. 一个栈的输入序列是:1,2,3则不可能的栈输出序列是_______。
3.用S表示入栈操作,X表示出栈操作,若元素入栈的顺序为1234,为了得到1342出栈顺序,相应的S和X的操作串为_______。
4. 循环队列的引入,目的是为了克服_______。 5.队列是限制插入只能在表的一端,而删除在表的另一端进行的线性表,其特点是_______。
6. 已知链队列的头尾指针分别是f和r,则将值x入队的操作序列是_______。
7.表达式求值是_______应用的一个典型例子。
8.循环队列用数组A[0..m-1]存放其元素值,已知其头尾指针分别是front和rear ,则当前队列的元素个数是_______。
9. 以下运算实现在链栈上的初始化,请在________________处用请适当句子予以填充。
Void InitStacl(LstackTp *ls){ ________________;}
10.` 以下运算实现在链栈上的进栈,请在处用请适当句子予以填充。
Void Push(LStackTp *ls,DataType x)
{ LstackTp *p;p=malloc(sizeof(LstackTp)); ________________; p->next=ls;
________________; }
11.以下运算实现在链栈上的退栈,请在________________处用请适当句子予以填充。
Int Pop(LstackTp *ls,DataType *x) {LstackTp *p; if(ls!=NULL) { p=ls;
*x=________________; ls=ls->next;
________________; return(1); }else return(0);
}
12. 以下运算实现在链队上的入队列,请在________________处用适当句子予以填充。
Void EnQueue(QueptrTp *lq,DataType x) { LqueueTp *p;
p=(LqueueTp *)malloc(sizeof(LqueueTp)); ________________=x; p->next=NULL;
(lq->rear)->next=________________; ________________;
}
三、应用题
1.给出栈的两种存储结构形式名称,在这两种栈的存储结构中如何判别栈空与栈满?
2. 画出对算术表达式A-B*C/D-E↑F求值时操作数栈和运算符栈的变化过程。
3. 将两个栈存入数组V[1..m]应如何安排最好?这时栈空、栈满的条件是什么?
4. 怎样判定循环队列的空和满?
四、算法设计题
1.借助栈(可用栈的基本运算)来实现单链表的逆置运算。
2. 设表达式以字符形式已存入数组E[n]中,‘#’为表达式的结束符,试写出判断表达式中括号(‘(’和‘)’)是否配对的C语言描述算法:EXYX(E); (注:算法中可调用栈操作的基本算法。)
3. 假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和O组成的序列,称可以操作的序列为合法序列,否则称为非法序列。 (1)下面所示的序列中哪些是合法的?
A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO
(2)通过对(1)的分析,写出一个算法,判定所给的操作序列是否合法。若合法,返回
true,否则返回false(假定被判定的操作序列已存入一维数组中)。
4. 设有两个栈S1,S2都采用顺序栈方式,并且共享一个存储区[O..maxsize-1],为了尽量利用空间,减少溢出的可能,可采用栈顶相向,迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。
5. 请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下:PUSH(ST,x):元素x入ST栈;POP(ST,x):ST栈顶元素出栈,赋给变量x;Sempty(ST):判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算:enqueue:插入一个元素入队列; dequeue:删除一个元素出队列;queue_empty:判队列为空。(请写明算法的思想及必要的注释)
6. 要求循环队列不损失一个空间全部都能得到利用,设置一个标志tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满,请编写与此相应的入队与出队算法。
7. 已知Q是一个非空队列,S是一个空栈。仅用队列和栈的ADT函数和少量工作变量,编写一个算法,将队列Q中的所有元素逆置。栈的ADT函数有:
makeEmpty(s:stack); 置空栈
push(s:stack;value:datatype); 新元素value进栈 pop(s:stack):datatype; 出栈,返回栈顶值 isEmpty(s:stack):Boolean; 判栈空否 队列的 ADT函数有:
enqueue(q:queue:value:datatype); deQueue(q:queue):datatype; isEmpty(q:queue):boolean; 元素value进队 出队列,返回队头值 判队列空否
第3章 栈和队列
一 单项选择题 1. B A B 2. A 3. C 4.B 5. B 6. B 7. D 8. D 9. C 10.D 11.C 12. C
二、填空题
1.操作受限(或限定仅在表尾进行插入和删除操作) 后进先出 2. 3 1 2
3.S×SS×S××
4. 假溢出时大量移动数据元素 5.先进先出
6. s=(LinkedList)malloc(sizeof(LNode)); s->data=x;s->next=r->next;r->next=s;
r=s; 7.栈 8.(rear-front+m)% m; 9.ls=NULL
10. p->data=x, ls=p 11.p->data, free(p)
12. p->data, p, lq->rear=p
三、应用题 1.【解答】(1)顺序栈 (top用来存放栈顶元素的下标)
判断栈S空:如果S->top==-1表示栈空。
判断栈S满:如果S->top==Stack_Size-1表示栈满。
(2) 链栈(top为栈顶指针,指向当前栈顶元素前面的头结点) 判断栈空:如果top->next==NULL表示栈空。
判断栈满:当系统没有可用空间时,申请不到空间存放要进栈的元素,此时栈满。
2. 设操作数栈是opnd,操作符栈是optr,对算术表达式A-B*C/D-E↑F求值,过程如下: 步骤 opnd栈 初始 1 2 3 A A AB optr栈 输入字符 # # # - # - A-B*C/D-E↑F# A-B*C/D-E↑F# -B*C/D-E↑F# B*C/D-E↑F# 主要操作 PUSH(OPTR,’#’) PUSH(OPND,A) PUSH(OPTR,’-’) PUSH(OPND,B)
正在阅读:
第三章栈和队列习题 - 数据结构09-23
刑法学教学大纲- China-EU School of Law, CUPL10-26
2016安全生产月竞赛试题及答案09-15
phreeqc实例练习02-02
2011年国家级继续医学教育基地项目表04-16
大型游乐园项目可行性研究报告06-08
律师刑事诉讼格式文书修订版05-09
冲压模具毕业设计论文(级进模设计)07-19
- 供应商绩效评价考核程序
- 美国加州水资源开发管理历史与现状的启示
- 供应商主数据最终用户培训教材
- 交通安全科普体验教室施工方案
- 井架安装顺序
- 会员积分制度
- 互联网对美容连锁企业的推动作用
- 互联网发展先驱聚首香港
- 公司文档管理规则
- 机电一体化系统设计基础作业、、、参考答案
- 如何选择BI可视化工具
- 互联网产品经理必备文档技巧
- 居家装修风水的布置_家庭风水布局详解
- 全省基础教育信息化应用与发展情况调查问卷
- 中国石油--计算机网络应用基础第三阶段在线作业
- 【知识管理专题系列之五十八】知识管理中如何实现“场景化协同”
- 网络推广方案
- 中国石油--计算机网络应用基础第二阶段在线作业
- 汽车检测与维修技术专业人才培养方案
- 详解胎儿颈透明层
- 数据结构
- 队列
- 习题
- 第三章
- 人教版高中化学必修一高一上学期期中考试试题
- SAP之成本中心类型与功能范围
- 地理兴趣小组活动工作总结
- 教育心理学的试题和答案
- 华工2015企业战略管理平时作业
- 2012年橱柜十大品牌有哪些
- 法制宣传领导讲话稿4篇
- 学工部关于2013年暑期学生留宿的通知
- 湖南师范大学体育学院考研真题资料
- 安全技术措施(停送电2016)
- 获奖名师刘清珠年月日课堂实录
- 关于PT辅助开口三角电压的问题
- 拟建年产2万吨萘系高效减水剂建设项目可研报告
- 2016房地产估价师后续教育答案汇总
- 光明60KV变电所电气设计
- 汽油发动机台架试验常见故障及排除方法 - 图文
- 2019年中国烟草物流行业现状分析与发展趋势研究报告目录
- 初三语文三模试卷
- C语言答案
- 《有机化学》课程标准