试题七(共 15 分) 阅读以下说明和C程序,将应填入 (n) 处的字句写在答题纸的对应栏内。 【说明】 现

Question

试题七（共 15 分）

阅读以下说明和C程序，将应填入 （n） 处的字句写在答题纸的对应栏内。

【说明】

现有 n（n < 1000）节火车车厢，顺序编号为 1,2,3,...,n，按编号连续依次从 A方向的铁轨驶入，从 B 方向铁轨驶出，一旦车厢进入车站（Station）就不能再回到 A方向的铁轨上；一旦车厢驶入 B 方向铁轨就不能再回到车站，如图 7-1所示，其中 Station 为栈结构，初始为空且最多能停放 1000 节车厢。

下面的 C 程序判断能否从 B 方向驶出预先指定的车厢序列，程序中使用了栈类

STACK,关于栈基本操作的函数原型说明如下：

void InitStack(STACK *s)：初始化栈。

void Push(STACK *s,int e): 将一个整数压栈，栈中元素数目增 1。

void Pop(STACK *s)：栈顶元素出栈，栈中元素数目减 1。

int Top(STACK s)：返回非空栈的栈顶元素值，栈中元素数目不变。

int IsEmpty(STACK s)：若是空栈则返回 1，否则返回 0。

【C 程序】

include<stdio.h>

/*此处为栈类型及其基本操作的定义，省略*/

int main( ){

STACK station;

int state[1000];

int n; /*车厢数*/

int begin, i, j, maxNo; /*maxNo 为 A端正待入栈的车厢编号*/

printf("请输入车厢数： ");

scanf("%d",&n);

printf("请输入需要判断的车厢编号序列（以空格分隔） ： ");

if (n < 1) return -1;

for (i = 0; i<n; i++) /* 读入需要驶出的车厢编号序列,存入数组 state[] */

scanf("%d",&state[i]);

（1） ; /*初始化栈*/

maxNo = 1;

for(i = 0; i < n; ){/*检查输出序列中的每个车厢号 state[i]是否能从栈中获取*/

if ( （2） ){/*当栈不为空时*/

if (state[i] == Top(station)){ /*栈顶车厢号等于被检查车厢号*/

printf("%d ",Top(station));

Pop(&station); i++;

}

else

if ( （3） ){

printf("error\n");

return 1;

}

else {

begin = （4） ;

for(j = begin+1; j<=state[i]; j++) {

Push(&station, j);

}

}

}

else { /*当栈为空时*/

begin = maxNo;

for(j = begin; j<=state[i]; j++){

Push(&station, j);

}

maxNo = （5） ;

}

}

printf("OK");

return 0;

}

Answer 1

正确答案：

试题七 分析
　　本题考查栈数据结构的应用和C程序设计基本能力。
　　栈的运算特点是后进先出。在本题中，入栈序列为1、2、…、n-1、n，出栈序列保存在state[]数组中，state[0]记录出栈序列的第1个元素，state[1]记录出栈序列的第2个元素，依此类推。程序采用模拟元素入栈和出栈的操作过程来判断出栈序列是否恰当。需要注意的是，对于栈，应用时不一定是所有元素先入栈后，再逐个进行出栈操作，也不一定是进入一个元素紧接着就出来一个元素，而是栈不满且输入序列还有元素待进入就可以进栈，只要栈不空，栈顶元素就可以出栈，从而使得唯一的一个入栈序列可以得到多个出栈序列。当然，在栈中有多个元素时，只能让栈顶的元素先出栈，栈中其他的元素能从顶到底逐个出栈。本题中入栈序列和出栈序列的元素为车厢号。
　　空（1）处对栈进行初始化，根据题干中关于栈基本操作的说明，调用InitStack初始化栈，由于形参是指针参数，因此实参应为地址量，即应填入“Initstack(&station)”。
　　当栈不空时，就可以令栈顶车厢出栈，空（2）处应填入“!IsEmpty(station)”。
　　栈顶车厢号以Top(station)表示，若栈顶车厢号等于出栈序列的当前车厢号state[i]，说明截至到目前为止，出栈子序列state[0]～state[i]可经过栈运算获得。由于进栈时小编号的车厢先于大编号的车厢进入栈中，因此若栈顶车厢号大于出栈序列的当前车厢号state[i]，则对于state[i]记录的车厢，若它还在栈中，则此时无法出栈，因为它不在栈顶，所以出错，若它已先于当前的栈顶车厢出栈，则与目前的出栈序列不匹配，仍然出错，因此空（3）处应填入“state[i]<Top(station)”。
　　若栈顶车厢号小于出栈序列的当前车厢号state[i]，则说明state[i]记录的车厢还没有进入栈中，因此从入栈序列（A端）正待进入的车厢（即比栈顶车厢号正好大l）开始，直到state[i]记录的车厢号为止，这些车厢应依次进入栈中。程序中用以下代码实现此操作：
　　for(j=begin+1;j<=state[i];j++){
　　Push(&station,j);
　　}
　　显然，begin应获取栈顶车厢号的值，即空（4）处应填入“Top(station)”。
　　还有一种情况，就是待考查的出栈序列还没有结束而栈空了，则说明需要处理入栈序列，使其车厢入栈。程序中用maxNO表示A端正待入栈的车厢编号，相应的处理如下面代码所示：
　　begin=maxNO;
　　for(j=begin;j<=state[i];j++){
　　Push(&station,j);
　　}
　　接下来，A端正待入栈的车厢编号等于j或state[i]+1，即空（5）处应填入j或“state[i]+1”。
　　如果驶出的车厢编号序列是经由栈获得的，则程序运行时输出该序列及字符串“OK”否则输出“error”而结束。
试题七 参考答案（共15分，各3分）
（1）InitStack(&station)
（2）!IsEmpty(station)
（3）state[i]Top(station)
（4）Top(station)
（5）j