![](/assets/images/bg-loading.gif)
![](/assets/images/bg-loading.gif)
![](/assets/images/bg-loading.gif)
![](/assets/images/bg-loading.gif)
![](/assets/images/bg-loading.gif)
![](/assets/images/bg-loading.gif)
![](/assets/images/bg-loading.gif)
![](/assets/images/bg-loading.gif)
![](/assets/images/bg-loading.gif)
![](/assets/images/bg-loading.gif)
还剩11页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
第三章习题.按图
3.1b所示铁道〔两侧铁道均为单向行驶道进展车厢调度,答复⑴如进站的车厢序列为123则可能得到的出站车厢序列是什么⑵如进站的车厢序列为123456能否得到435612和135426的出站序列,并说明原因即写出以“S〃表示进栈、以“X〃表示出栈的栈操作序列.设队列中有A、B、C、D、E这5个元素,其中队首元素为A如果对这个队列重复执行以下4步操作:1输出队首元素;2把队首元素值插入到队尾;[3删除队首元素;4再次删除队首元素直到队列成为空队列为止,得到输出序列⑴A、C、E、C、C2A、C、E[3[A、C、E、C、C、C4A、C、E、C.给出栈的两种存储构造形式名称,在这两种栈的存储构造中若何判别栈空与栈满.按照四则运算加、减、乘、除和幕运算㈠优先关系的惯例,画出对以下算术表达式求值时操作数栈和运算符栈的变化过程A—B*C/D+EfF.试写一个算法,判断依次读入的一个以@为完毕符的字母序列,是否为形如序列1序列才模式的字符序列其中序列1和序列2中都不含字符且序列2是序列1的逆序列例如,匕+bb+a是属该模式的字符序列,而‘1+33—1则不是.假设表达式由单字母变量和双目四则运算算符构成试写一个算法,将一个通常书写形式且书写正确的表达式转换为逆波兰式.假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点注意不设头指针,试编写相应的队列初始化、入队列和出队列的算法.要求循环队列不损失一个空间全部都能得到利用,设置一个标志域tag以tag为0或1来区分头尾指针一样时的队列状态的空与满,请编写与此构造相应的入队与出队算法.简述以下算法的功能〔其中栈和队列的元素类型均为int.要求循环队列不损失一个空间全部都能得到利用,设置一个标志域tag以tag为或1来区分头尾指针一样时的队列状态的空与满,请编写与此构造相应的入队与出队算法[提示]:初始状态front==03rear==Otag==O队空条件front==rear5tag==O队满条件front==rear3tag==1其它状态:front!=reartag==0或
1、2入队操作…入队iffront==reartag=1;或直接tag=1出队操作…出队tag=0;[问题]:若何明确区分队空、队满、非空非满三种情况.简述以下算法的功能其中栈和队列的元素类型均为int voidproc_1StackS{inti5nA
[255];n=0;while!EmptyStackS{n++;PopS3A[n];}fori=1;i=n;i++PushS3A[i];将栈s逆序voidproc_2StackSinte{StackT;intd;lnitStackT;while!EmptyStackS{PopS5d;ifd!=ePushT3d;}while!EmptyStackT{PopTd;PushS5d;}删除栈s中所有等于e的元素voidproc_3Queue*Q{StackS;intd;lnitStackS;while!EmptyQueue*QDeleteQueueQd;PushS5d;}while!EmptyStackS{PopS5d;EnterQueueQd}将队列Q逆序实习题.回文判断称正读与反读都一样的字符序列为“回文〃序列试写一个算法,判断依次读入的一个以@为完毕符的字母序列,是否为形如序列1序列2模式的字符序列其中序列1和序列2中都不含字符且序列2是序列1的逆序列例如,a+bb+a是属该模式的字符序列,而1+33—1则不是.停车场管理设停车场是一个可停放n辆车的狭长通道,且只有一个大门可供汽车进出在停车场内,汽车按到达的先后次序,由北向南依次排列假设大门在最南端假设车场内已停满n辆车,则后来的汽车需在门外的便道上等候,当有车开走时,便道上的第一辆车即可开入当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门后,其它车辆再按原次序返回车场每辆车离开停车场时,应按其停留时间的长短交费在便道上停留的时间不收费试编写程序,模拟上述管理过程要求以顺序栈模拟停车场,以链队列模拟便道从终端读入汽车到达或离去的数据,每组数据包括三项
①是“到达还是“离去”;
②汽车牌照号码;
③“到达或离去的时亥!I与每组输入信息相应的输出信息为如果是到达的车辆,则输出其在停车场中或便道上的位置;如果是离去的车辆,则输出其在停车场中停留的时间和应交的费用(提示需另设一个栈,临时停放为让路而从车场退出的车).商品货架管理商品货架可以看成一个栈,栈顶商品的生产日期最早,栈底商品的生产日期最近上货时,需要倒货架,以保证生产日期较近的商品在较下的位置用队列和栈作为周转,实现上述管理过程voidproc_lStackS{intinA
[255];n=0;while!EmptyStackS{n++;PopSA[n];}fori=l;i=n;i++PushSA[i];}voidproc_2StackSinte{StackT;intd;InitStackT;while!EmptyStackS{PopSd;ifd!=ePushTd;}while!EmptyStackT{PopTd;PushSd;voidproc_3Queue*Q{StackS;intd;InitStackS;while!EmptyQueue*QDeleteQueueQd;PushSd;while!EmptyStackS{PopSd;EnterQueueQd实习题.回文判断称正读与反读都一样的字符序列为“回文〃序列试写一个算法,判断依次读入的一个以@为完毕符的字母序列,是否为形如序列1序列2,模式的字符序列其中序列1和序列2中都不含字符且序歹U2是序列1的逆序列例如,a+bb+a是属该模式的字符序列,而1+33—1则不是.停车场管理设停车场是一个可停放n辆车的狭长通道,且只有一个大门可供汽车进出在停车场内,汽车按到达的先后次序,由北向南依次排列〔假设大门在最南端)假设车场内已停满n辆车,则后来的汽车需在门外的便道上等候,当有车开走时,便道上的第一辆车即可开入当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门后,其它车辆再按原次序返回车场每辆车离开停车场时应按其停留时间的长短交费〔在便道上停留的时间不收费〕试编写程序,模拟上述管理过程要求以顺序栈模拟停车场,以链队列模拟便道从终端读入汽车到达或离去的数据,每组数据包括三项
①是“到达〃还是“离去〃;
②汽车牌照号码;
③“到达〃或“离去〃的时刻与每组输入信息相应的输出信息为如果是到达的车辆,则输出其在停车场中或便道上的位置;如果是离去的车辆,则输出其在停车场中停留的时间和应交的费用(提示:需另设一个栈,临时停放为让路而从车场退出的车).商品货架管理商品货架可以看成一个栈,栈顶商品的生产日期最早,栈底商品的生产日期最近上货时一,需要倒货架,以保证生产日期较近的商品在较下的位置用队列和栈作为周转,实现上述管理过程第三章答案按
3.1(b)所示铁道〔两侧铁道均为单向行驶道)进展车厢调度,答复:m如进站的车厢序列为123则可能得到的出站车厢序列是什么⑵如进站的车厢序列为123456能否得至!J435612和135426的出站序歹!J并说明原因即写出以“S〃表示进栈、“X〃表示出栈的栈序列操作【解答】1可能得到的出站车厢序列是
123、
132、
213、
231、321⑵不能得到435612的出站序列因为有S1S2S3S4X4X3S5X5S6S6此时按照“后进先出〃的原则,出栈的顺序必须为X2X1O能得到135426的出站序列因为有S1X1S2S3X3S4S5X5X4X2X10给出栈的两种存储构造形式名称,在这两种栈的存储构造中若何判别栈空与栈满【解答】1顺序栈[top用来存放栈顶元素的下标判断栈S空如果S-top==-1表示栈空判断栈S满如果S-top==Stack_Size-1表示栈满2链栈top为栈顶指针,指向当前栈顶元素前面的头结点判断栈空如果top-n6xt==NULL表示栈空判断栈满当系统没有可用空间时,申请不到空间存放要进栈的元素,此时栈满4照四则运算加、减、乘、除和塞运算的优先惯例,画出对以下表达式求值时操作数栈和运算符栈的变化过程A-B*C/D+EtF【解答】5写一个算法,判断依次读入的一个以@为完毕符的字母序列,是否形如序列1序列7的字符序列序列1和序列2中都不含,且序列2是序列1的逆序列例如,a+bb+a是属于该模式的字符序列,而1+33-1则不是【解答】算法如下intlsHuiWenStack*S;Charchtemp;lnitStackS;Printf“\n请输入字符序列〃;{returnFALSE;printf\nNO〃;}ifch==@lsEmptyS{returnTRUE;printf\nYES〃;}else{returnFALSE;printfK\nNOz;}}/*lsHuiWen
73.8要求循环队列不损失一个空间全部都能得到利用,设置一个标志tag以tag为0或1来区分头尾指针一样时的队列状态的空与满,请编写与此相应的入队与出队算法【解答】入队算法intEnterQueueSeqQueue*QQueueElementTypex{/*将元素x入队*/ifQ-front==Q-fronttag==1/*队满*/returnFALSE;ifQ-front==Q-fronttag==O/*x入队前队空,x入队后重新设置标志*/tag=1;Q-elememt[Q-rear]=x;Q-rear=Q-rear+1%MAXSIZE;/*设置队尾指针*/ReturnTRUE;出队算法intDeleteQueueSeqQueue*QQueueElementType*x{/*删除队头元素,用X返回其值*/ifQ-front==Q-reartag==O/*队空*/returnFALSE;*x=Q-element[Q-front];Q-front=Q-front+1%MAXSIZE;/*重新设置队头指针*/ifQ-front==Q-reartag=O;/*队头元素出队后队列为空,重新设置标志域*/ReturnTUUE;编写求解Hanoi问题的算法,并给出三个盘子搬动时的递归调用过程【解答】算法voidhanoiintncharxcharycharz{/*将塔座X上按直径由小到大且至上而下编号为1到n的n个圆盘按规则搬到塔座Z上,Y可用做辅助塔座*/ifn==1movex1z;else{Hanoin-15x3zy;movexnz;Hanoin-1yxz;}Hanoi3ABC的递归调用过程:moveA-C1号搬至UC2号搬到BmoveC-B1号搬至UB3号搬到CmoveB-A1号搬到A2号搬到CmoveA-C1号搬到C第3章限定性线性表一栈和队列习题.按图
3.1b所示铁道两侧铁道均为单向行驶道进展车厢调度,答复⑴如进站的车厢序列为123则可能得到的出站车厢序列是什么
123、
213、
132、23如321312⑵如进站的车厢序列为123456能否得到435612和135426的出站序列,并说明原因即写出以“S”表示进栈、以“X”表示出栈的栈操作序列SXSSXSSXXXSX或S1X1S2S3X3S4S5X5X4X2S6X
6.设队列中有A、B、C、D、E这5个元素,其中队首元素为A如果对这个队列重复执行以下4步操作:⑴输出队首元素;
(2)把队首元素值插入到队尾;
(3)删除队首元素;
(4)再次删除队首元素直到队列成为空队列为止,则是否可能得到输出序列A、C、E、C、C⑵A、C、E
(3)A、C、E、C、C、C
(4)A、C、E、C[提示]:A、B、C、D、E(输出队首元素A)A、B、C、D、E、A(把队首元素A插入到队尾)B、C、D、E、A(删除队首元素A)C、D、E、A(再次删除队首元素B)C、D、E、A(输出队首元素C)C、D、E、A、C(把队首元素C插入到队尾)D、E、A、C(删除队首元素C)E、A、C(再次删除队首元素D)
3.给出栈的两种存储构造形式名称,在这两种栈的存储构造中若何判别栈空与栈满4•按照四则运算加、减、乘、除和嘉运算(t)优先关系的惯例,画出对以下算术表达式求值时操作数栈和运算符栈的变化过程A-B*C/D+EtF.试写一个算法,判断依次读入的一个以@为完毕符的字母序列,是否为形如序列1序列2模式的字符序列其中序列1和序列2中都不含字符,,,且序列2是序列1的逆序列例如,a+bb+a是属该模式的字符序歹U而1+33—1’则不是[提示]:
(1)边读边入栈,直到
(2)边读边出栈边对比,直到…….假设表达式由单字母变量和双目四则运算算符构成试写一个算法,将一个通常书写形式(中缀)且书写正确的表达式转换为逆波兰式(后缀)偎示]:例中缀表达式a+b后缀表达式ab+中缀表达式a+bxc后缀表达式abcx+中缀表达式a+bxc-d后缀表达式abcx+d-中缀表达式a+bxc・d/e后缀表达式abcx+de/-中缀表达式a+b*c・d・e/f后缀表达式abcd-x+ef/-•后缀表达式的计算过程简便顺序扫描表达式,1如果是操作数,直接入栈;2如果是操作符op则连续退栈两次,得操作数XY计算XopY并将结果入栈•若何将中缀表达式转换为后缀表达式顺序扫描中缀表达式,1如果是操作数,直接输出;2如果是操作符OP2则与栈顶操作符6对比如果OP2AOP1则OP2入栈;如果OP2=OP1则脱括号;如果0P20P1则输出0P1;
7.假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点注意不设头指针,试编写相应的队列初始化、入队列和出队列的算法[提示]:参P.56P.70先画图.typedefLinkListCLQueue;intlnitQueueCLQueue*QintEnterQueueCLQueueQQueueElementTypexintDeleteQueueCLQueueQQueueElementType*x。
![贤阅信息](/assets/images/honor-2.png)
![贤阅信息](/assets/images/honor-3.png)
![贤阅信息](/assets/images/honor-4.png)