车厢调度问题c语言,《数据结构 - C语言描述》习题及答案 耿国华

第3章 限定性线性表 — 栈和队列

习 题

1. 按图3.1(b)所示铁道(两侧铁道均为单向行驶道)进行车厢调度，回答：

⑴ 如进站的车厢序列为123，则可能得到的出站车厢序列是什么？ 123、213、132、231、321(312)

⑵ 如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。(即写出以“S”表示进栈、以“X”表示出栈的栈操作序列)。 SXSS XSSX XXSX 或 S1X1S2S3X3S4S5X5X4X2S6X6

2. 设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重复执

行下列4步操作： (1) 输出队首元素；

(2) 把队首元素值插入到队尾； (3) 删除队首元素； (4) 再次删除队首元素。

直到队列成为空队列为止，则是否可能得到输出序列： (1) A、C、E、C、C (2) 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. 按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例，画出对下列算术表达式

求值时操作数栈和运算符栈的变化过程： A－B＊&#x