《数据结构 - 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*C/D+E↑F

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

序列2’模式的字符序列。其中序列1和序列2 中都不含字符’&’,且序列2 是序列1的逆序列。例如,‘a+b&b+a’是属该模式的字符序列,而‘1+3&3-1’则不是。 [提示]:

(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逆序。