《数据结构》第三章习题参考答案 殷人昆版
更新时间:2024-03-05 07:12:01 阅读量: 综合文库 文档下载
- 严蔚敏《数据结构》推荐度:
- 相关推荐
, 《数据结构》第三章习题参考答案
一、判断题(在正确说法的题后括号中打“√”,错误说法的题后括号中打“×”)
1、栈和队列都是线性表,只是在插入和删除时受到了一些限制。( √ ) 2、循环队列也存在空间溢出问题。( √ )
3、任何一个递归过程都可以转换成非递归过程。( √ ) 4、消除递归不一定需要使用栈。( √ )
5、有n个数顺序(依次)进栈,出栈序列有Cn种,Cn=(1/(n+1))*(2n)!/((n!)*(n!))。( √ )
6、循环队列方式能很好地解决队列的假溢出现象。( √ )
二、单项选择题
1、1.设有一个顺序栈S,元素P1,P2,P3,P4,P5,P6依次进栈,得到的出栈顺序P2,
P3,P4,P6,P5,P1,则顺序栈的容量至少为( B )。 A.2 B.3 C.4
D.无法确定
2.一个队列的输出序列是1,2,3,4,则队列的入队序列是( A )。
A.1,2,3,4 B.1,4,3,2 C.4,3,2,1 D.不确定
3、对于一个循环队列(最大元素个数为maxSize)进行入队操作时,对队列指针的修改
正确的语句是( C )。
A.rear = rear + 1 B.front = front + 1
C.rear = (rear + 1)% maxSize D.front = (front + 1)% maxSize
4、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear,则当前队列中的元素个数为( A )。
A.(rear-front+m)%m B.rear-front+1 C.(front-rear+m)%m D.(rear-front)%m
5、表达式a*(b+c)-d的后缀表达式是( B )。 A.abcd*+- 表达式[a-(c*d+b)] B. abc+*d- C. abc*+d- 表达式b*c+a-d D. -+*abcd
6、
若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3,当从队列中删除一个元素,再加入两个元素后,rear和front的值分
别为多少?( B )
A. 1和 5 B. 2和4 C. 4和2 D. 5和1
7、设abcdef以所给的次序进栈,若在进栈操作时,允许退栈操作,则下面得不到的序列为 ( D )。 A.fedcba B. bcafed C. dcefba D. cabdef
三、填空题
1、一个栈的输入序列是:1,2,3则不可能的栈输出序列是_3,1,2____。
2、用S表示入栈操作,X表示出栈操作,若元素入栈的顺序为1234,为了得到1342出栈顺序,相应的S和X的操作串为_SXSSXSXX_____。
3、循环队列的引入,目的是为了克服 假溢出时大量移动数据元素 。
4、顺序栈的类声明如下,试:
1、填空完成进栈(push)和出栈(pop)函数的代码。 2、填空完成利用栈编写一个将十进制数N转换为另一基为B的B进制数的算法。
template
class SeqStack{ void SeqStack
SeqStack(); if(__IsEmpty()==true__) return; ~SeqStack(){delete []elements;}
elements[_++top__]=x; void Push(const T& x) ; //进栈
bool Pop(T& x) ; //出栈
}
bool IsEmpty()const //判断栈空 {return (top==-1)?true:false;} template
bool SeqStack
{return (top==maxSize-1)?true:false;} private: if(_IsEmpty()==true __) return false; T* elements; //栈数组
x = _ elements[_top--__]__; int top; //栈顶指针
int maxSize; //栈最大可容纳元素个数 return true; };
}
//输入非负十进制整数,打印其B进制数 void ConversionData_10toB( ){
SeqStack
cout << “输入一个十进制数:”;
cin>>n;
while(n){
S.Push(__n%B___);
四、综合题
1、计算算术表达式的值时,可用两个栈作辅助工具。对于给出的一个表达式,从左向右扫描它的字符,并将操作数放入栈S1中,运算符放入栈S2中,但每次扫描到运算符时,要把它同S2的栈顶运算符进行优先级比较,当扫描到的运算符的优先级不高于栈顶运算符的优先级时,取出栈S1的栈顶和次栈顶的两个元素,以及栈S2的栈顶运算符进行运算将结果放入栈S1中(得到的结果依次用T1、T2等表示)。为方便比较,假设栈S2的初始栈顶为?(?运算符的优先级低于加、减、乘、除中任何一种运算)。现假设要计算表达式: A-B*C/D+E/F。写出栈S1和S2的变化过程。
【解答】
步骤 初始 1 2 3 4 5 6 7 8 栈S1 A A AB AB ABC AT1(注:T1=B*C) AT1D AT2(注:T2=T1/D) T3 (注:T3=A-T2) T3E T3E T3EF T3T4(注:T4=E/F) 栈S2 ???- ?- ?-* ?-* ?-/ ?-/ ?- 9 10 11 12 ?+ ?+ ?+/ ?+/ ?+ T5(注:T5= T3+ T4) ?
2、课本P131 3.1题
【解答】
(1)可能的不同出栈序列有
1 1?6C126=132种。(出栈序列为catalan数列)
(2)不能得到435612和154623这样的出栈序列。因为若在4, 3, 5, 6之后再将1, 2出栈,则1, 2必须一直在栈中,此时1先进栈,2后进栈,2应压在1上面,不可能1先于2出栈。154623也是这种情况。出栈序列325641和135426可以得到。
3、课本P131 3.2题
【解答】
因为借助栈由输入序列1, 2, 3, ?, n,可得到输出序列p1, p2, p3, ?, pn ,如果存在下标i, j, k,满足i < j < k,假设在输出序列中,出现pj < pk < pi的情形,则说明pj 出栈前pk 和 pi都已进栈,且留在栈中。由栈后进先出的性质可知,在栈中pk必然盖住pj,pk不出栈pj不可能出栈,pj出栈也不可能得到pj < pk的序列;
4、课本P131 3.3题
【解答】
由出栈序列可知栈中元素最多时有s1,s5,s6在栈中,所以栈的容量至少为3
5、课本P132 3.10题
【解答】
void List
ListNode
S.Push(p); p = p->link; }
ListNode
}
q->link = NULL; }
6、课本P132 3.12题
【解答】
void conversion( ){ //输入非负十进制整数,打印其B进制数 Stack S; int n,x;
cin>>n;
while(n){
S.Push(n%B); n=n/B; }
while(!S.IsEmpty()){ S.Pop(x);
cout< } } 7、课本P132 3.13题 【解答】 //括号匹配算法,匹配成功返回1,否则返回零;输入参数为字符串顺序表 int CheckPairofBracket (SeqList for(int i = 0; i < str.GetSize(); i++){ if(str [i]==’(’|| str [i]==’{’|| str [i]==’[’) s.Push(str [i]); else if(str [i]==’)’) { if(s.GetTop()==’(’) s.Pop(temp); else return 0; } else if( str [i]==’]’) { if(s.GetTop()==’ [ ’) s.Pop(temp); else return 0; } else if( str [i]==’ }’) { if( s.GetTop()==’ { ’) s.Pop(temp); else return 0; } } if(s.IsEmpty()) return 1; else return 0; } 8、课本P134 3.25题 【解答】 typedef Struct{ LinkNode void EnQueue(CycleQueue& Q, T & x){ LinkNode Q.p = s; Q.p->link =s; } else{ s->link = Q.p->link; Q.p->link = s; Q.p = s; } } 略……
正在阅读:
《数据结构》第三章习题参考答案 殷人昆版03-05
UML习题汇总11-09
斜井、平硐、巷道金属网、塑料网喷射混凝土支护工序质量验收记录表MKJ30404706-01
【百度云管家私密空间】关于如何使用手机管家对私密软件进行加密...02-16
中国_54021090_其他尼龙或聚酰胺纺制的高强力纱(2003-2013)进出口数据报告06-02
湖北省武汉市2015届高中毕业生五月模拟考试文综试题 - 图文03-17
公司财务工作计划201802-26
放射科质量与安全管理工作方案介绍09-18
医院监控方案11-30
- 清真菜谱
- 我国国民经济和社会发展十二五规划纲要(全文)
- 高三物理机械振动和机械波复习2
- 浙江省公路山岭隧道机械化装备应用指导手册 doc - 图文
- 2018届高三数学文科二轮复习:专题检测(九) 导数的简单应用
- 2015年上海市公务员录用考试《行政职业能力测验》试卷(B类)
- 七年级道德与法制下册
- 大班户外游戏教案
- 病虫害预警 - 图文
- 某养鱼场为了提高经营管理水平
- 汉中市勉县尧柏余热汽机规程 10
- 烹饪试卷
- 事业单位考试公共基础知识专项分类题库训练
- 语文:第2课 走一步,再走一步 课堂导学案(人教版 七上)
- 天汉使用手册
- 人教版小学三年级数学下册教学计划
- 房地产销售管理完全操作手册122页
- 2009年评审通过具有中学高级教师专业技术资格人员名单...
- 《15秋公共关系学》作业1
- 2017最新版监理公司三标一体管理手册
- 殷人
- 数据结构
- 习题
- 答案
- 参考
- 第三章
- 法院办公室主任竞聘演讲稿
- 教学设计(垃圾分类处理)
- C语言程序设计试卷2(含答案)
- XX老年之家项目可行性研究报告
- 2013年秋纳税基础与实务答案
- 合唱团兴趣小组活动记录
- 齿轮传动练习题
- 08级物理化学(上册)A
- 国赛电气安装与维修项目图纸
- 2015-2016学年度苏教版五年级上数学期末试卷及答案
- 外墙涂料施工技术交底
- 浅谈让学生乐学数学的方法
- 微型课题选题参考示例
- 西南交大-建筑施工技术B-第1-4次作业
- 2016呼和浩特职业学院语文单招试题测试版(附答案解析)
- 0128《教育科学研究方法》2013年6月期末考试指导
- 黄伯荣+廖序东《现代汉语》笔记整理
- (教案一第一章知识点)《原子结构与性质》
- 2015年度衢州双熊猫纸业有限公司销售收入与资产数据报告 - 图文
- 电子商务习题