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

刺骨的言语ヽ痛彻心扉 2022-10-15 11:53 172阅读 0赞

第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＊Ｃ／Ｄ＋Ｅ↑Ｆ

5. 试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1 &

序列2’模式的字符序列。其中序列1和序列2 中都不含字符’&’，且序列2 是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。 \[提示\]：

(1) 边读边入栈，直到&

(2) 边读边出栈边比较，直到……

6. 假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形

式(中缀)且书写正确的表达式转换为逆波兰式(后缀)。 \[提示\]： 例：

中缀表达式：a+b 后缀表达式: ab+ 中缀表达式：a+b×c 后缀表达式: abc×+ 中缀表达式：a+b×c-d 后缀表达式: abc×+d- 中缀表达式：a+b×c-d/e 后缀表达式: abc×+de/- 中缀表达式：a+b×(c-d)-e/f 后缀表达式: abcd-×+ef/- ?

后缀表达式的计算过程：(简便)

顺序扫描表达式，

(1)如果是操作数，直接入栈；

(2)如果是操作符op，则连续退栈两次，得操作数X, Y，计算X op Y，并将结果入栈。 ?

如何将中缀表达式转换为后缀表达式？ 顺序扫描中缀表达式， (1)如果是操作数，直接输出；

(2)如果是操作符op2，则与栈顶操作符op1比较：

如果op2 > op1，则op2入栈； 如果op2 = op1，则脱括号； 如果op2 < op1，则输出op1；

7. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设

头指针)，试编写相应的队列初始化、入队列和出队列的算法。 \[提示\]： 参P.56 P.70 先画图. typedef LinkList CLQueue; int InitQueue(CLQueue \* Q)

int EnterQueue(CLQueue Q, QueueElementType x)

int DeleteQueue(CLQueue Q, QueueElementType \*x)

8. 要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或

1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。 \[提示\]：

初始状态：front==0, rear==0, tag==0 队空条件：front==rear, tag==0 队满条件：front==rear, tag==1

其它状态：front !=rear, tag==0(或1、2) 入队操作：

… …(入队)

if (front==rear) tag=1；(或直接tag=1) 出队操作： … …(出队) tag=0；

\[问题\]：如何明确区分队空、队满、非空非满三种情况？

9. 简述以下算法的功能(其中栈和队列的元素类型均为int)： (1)void proc\_1(Stack S)

\{ i

int i, n, A\[255\]; n=0;

while(!EmptyStack(S))

\{

n++;

Pop(&S, &A\[n\]); \}

for(i=1; i<=n; i++) Push(&S, A\[i\]);

\}

将栈S逆序。

(2)void proc\_2(Stack S, int e)

\{

Stack T; int d; InitStack(&T); while(!EmptyStack(S))

\{

Pop(&S, &d); if (d!=e) Push( &T, d); \}

while(!EmptyStack(T))

\{

Pop(&T, &d); Push( &S, d); \} \}

删除栈S中所有等于e的元素。

(3)void proc\_3(Queue \*Q)

\{

Stack S; int d; InitStack(&S);

while(!EmptyQueue(\*Q))

\{

DeleteQueue(Q, &d); Push( &S, d);

\}

while(!EmptyStack(S))

\{

Pop(&S, &d); EnterQueue(Q，d) \} \}

将队列Q逆序。

发表评论取消回复

表情：

评论列表（有 0 条评论，172人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构 c语言列车厢调度

1 ====== <--移动方向 / 3 ===== \ 2 ====

傷城~/ 2023年03月13日 13:22/ 0 赞/ 29 阅读

相关 c语言描述：数据结构【三.线性表】

连续存储【数组】前言 > 本知识总结来自于郝斌老师的数据结构大纲，故投转载。本人为大一计算机专业学生，自学过程中想借博客记录知识点，同时方便以后复习。 1

左手的ㄟ右手/ 2022年10月31日 12:16/ 0 赞/ 191 阅读

相关 c语言描述：数据结构【二.算法】

前言 > 本知识总结来自于书本《大话数据结构》，故投转载。本人为大一计算机专业学生，自学过程中想借博客记录知识点，同时方便以后复习。二.算法 1. 定义

约定不等于承诺〃/ 2022年10月31日 10:49/ 0 赞/ 211 阅读

相关 c语言描述：数据结构【一.数据结构绪论】

前言 > 本知识总结来自于书本《大话数据结构》，故投转载。本人为大一计算机专业学生，自学过程中想借博客记录知识点，同时方便以后复习。一.数据结构绪论 1.

我就是我/ 2022年10月31日 01:42/ 0 赞/ 239 阅读

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

第3章限定性线性表 — 栈和队列习题 1. 按图3.1(b)所示铁道(两侧铁道均为单向行驶道)进行车厢调度，回答： ⑴ 如进站的车厢序列为123，则可能得到的出站车

刺骨的言语ヽ痛彻心扉/ 2022年10月15日 11:53/ 0 赞/ 173 阅读

相关 c语言break习题,C语言循环结构练习题.doc

C语言循环结构练习题C语言循环结构练习题第5章循环结构程序设计 5.1 基本知识点 (while语句的使用格式和注意事项 (do-while语句的使用格式和注意事项

忘是亡心i/ 2022年10月14日 14:53/ 0 赞/ 257 阅读

相关用C语言描述数据结构

用C语言描述数据结构学好计算机，主要要从三个方面做起，其中，第一步就是要学好各种语言，这是第一步，对各种语言有一个大体的了解；然后就是数据结构了，它是计算机中的一门核心

àì夳堔傛蜴生んèń/ 2022年09月19日 12:04/ 0 赞/ 208 阅读

相关数据结构、算法与应用c++语言描述习题答案1

include <iostream> using namespace std; //1.2 / 问题1:使用实际函数调用发现，

╰半夏微凉°/ 2022年05月25日 06:41/ 0 赞/ 183 阅读

相关 Linux 进程调度算法c语言描述

进程调度分为：长程调度，又称作业调度，用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后，再将新创建的进程排在就绪队列上，准备执行。

末蓝、/ 2022年02月18日 17:30/ 0 赞/ 306 阅读

相关 Linux单处理器进程调度c语言描述

本次实现的是模拟在单处理器情况下的处理器调度，目的是设计一个按优先数调度算法实现处理器调度的程序。每一个进程用一个进程控制块PCB来代表，进程控制块的格式为：进程名——

àì夳堔傛蜴生んèń/ 2022年02月18日 17:06/ 0 赞/ 243 阅读