习题课数据结构〔C语言版〕
习题课
1. 若教科书3.1.1节中图3.1(b)所示铁道进行车厢调度(注意:两侧铁道均为单向行驶道),则请回答:
(1) 如果进站的车厢序列为123,则可能得到的出站车厢序列是什么?
(2) 如果进站的车厢序列为123456,则能否得到435612和135426的出站序列,并请说明为什么不能得到或者如何得到(即写出以’S’表示进栈和以’X’表示出栈的栈操作序列).
2. 写出下列程序段的输出结果(栈的元素类型SElemType为char).
void main( )
{
Stack S;
char x,y;
InitStack(S);
x=’c’;
y=’k’;
Push(S,x);
Push(S,’a’) ;
Push(S,y) ;
Pop(S,x);
Push(S,’t’) ;
Push(S,x);
Pop(S,x) ;
Push(S,’s’);
while (!StackEmpty(S))
{
Pop(S,y);
printf(y);
};
print(x);
}
3. 简述以下算法的功能(栈的元素类型SElemType为int).
(1)
Status algol(Stack S)
{
int i, n, A[256];
n=0;
while(!StackEmpty(S))
{
n++;
Pop(S,A[n]);
};
for (i =1;i<=n: i ++ )
Push(S,A[i]);
}
(2)
Status algo2(Stack S, int e)
{
Stack T;
int d ;
InitStack(T);
while(!StackEmpty(S))
{
Pop(S,d);
if(d!=e)
Push(T,d);
}
while(!StackEmpty(T))
{
Pop(T,d);
Push(S,d);
}
}
4. 写出以下程序段的输出结果(队列中的元素类型QElemType为char).
void main( )
{
Queue Q;
InitQueue (Q);
char x=’e’,y=’c’;
EnQueue(Q,’h’);
EnQueue(Q,’r’);
EnQueue(Q,y);
DeQueue(Q,x);
EnQueue(Q,x);
DeQueue(Q,x);
EnQueue(Q,’a’);
While (!QueueEmpty(Q))
{
DeQueue(Q,y);
printf(y);
}
printf(x);
}
5. 简述以下算法的功能(栈和队列的元素类型均为int).
void algo3(Queue &Q)
{
Stack S;
int d;
while(!QueueEmpty(Q))
{
DeQueue(Q,d);
Push(S,d);
}
while(!StackEmpty(S))
{
Pop(S,d);
EnQueue(Q,d);
}
}
6. 若以1234作为双端队列的输入序列,试分别求出满足以下条件的输出序列;
(1) 能由输入受限的双端队列得到,但不能由输出受限的双端队列得到的输出序列;
(2) 能由输出受限的双端队列得到,但不能由输入受限的双端队列得到的输出序列;
(3) 既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列;