若一个栈的输入序列是，，，，，其输出序列是1，2，3，，4，若=1，则的值（）。

若一个栈的输入序列是，，，，，其输出序列是1，2，3，，4，若=1，则的值（ ）。

A、可能是2

B、一定是2

C、不可能是2

D、不可能是3

设输入元素为1、2、3、P和A，输入次序为123PA，如图(编者略)。元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名?【中山大学1997】

算法5-5：有向无环图的拓扑排序【图】 Description 由某个集合上的一个偏序得到该集合上的一个全序，这个操作被称为拓扑排序。偏序和全序的定义分别如下： 若集合X上的关系R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。 设R是集合X上的偏序，如果对每个x,y∈X必有xRy或yRx，则称R是集合X上的全序关系。 由偏序定义得到拓扑有序的操作便是拓扑排序。 拓扑排序的流程如下： 1. 在有向图中选一个没有前驱的顶点并且输出之； 2. 从图中删除该顶点和所有以它为尾的弧。 重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。 采用邻接表存储有向图，并通过栈来暂存所有入度为零的顶点，描述拓扑排序的算法 在本题中，读入一个有向图的邻接矩阵（即数组表示），建立有向图并按照以上描述中的算法判断此图是否有回路，如果没有回路则输出拓扑有序的顶点序列。 Input 输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。 以后的n行中每行有n个用空格隔开的整数0或1，对于第i行的第j个整数，如果为1，则表示第i个顶点有指向第j个顶点的有向边，0表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为0。 Output 如果读入的有向图含有回路，请输出“ERROR”，不包括引号。 如果读入的有向图不含有回路，请按照题目描述中的算法依次输出图的拓扑有序序列，每个整数后输出一个空格。 请注意行尾输出换行。 Sample Input4 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0Sample Output3 0 1 2 HINT 在本题中，需要严格的按照题目描述中的算法进行拓扑排序，并在排序的过程中将顶点依次储存下来，直到最终能够判定有向图中不包含回路之后，才能够进行输出。 另外，为了避免重复检测入度为零的顶点，可以通过一个栈结构维护当前处理过程中入度为零的顶点。

已知程序段：

求当输入i=3时，本程序执行期间对运行栈的存储分配图。

基于Windows 2003操作系统的双协议栈主机的cmd窗口中，输入(5)命令可进行IPv6的路由跟踪，图7-12所示是使用该命令后系统的部分返回信息。根据图7-12所示的返回信息可知，(5)命令在传输层默认使用(6)协议，源端口使用32834，目的端口使用33434，中间路由器回送(7)报文，目的端回送(8)报文。

阅读以下说明和算法，完善算法并回答问题。

【说明】

假设以二维数组G[1..m，1..n)表示一幅图像各像素的颜色，则G[i，j]表示区域中点(i，j)处的颜色，颜色值为0～k的整数。

下面的算法将指定点(i0，j0)所在的同色邻接区域的颜色置换为给定的颜色值。约定所有与点(i0，j0)同色的上、下、左、右可连通的点组成同色邻接区域。

例如，一幅8×9像素的图像如图2-1所示。设用户指定点(3，5)，其颜色值为0，此时其上方(2，5)、下方(4，5)、右方(3，6)邻接点的颜色值都为0，因此这些点属于点(3，5)所在的同色邻接区域，再从上、下、左、右四个方向进行扩展，可得出该同色邻接区域的其他点(见图2-1中的阴影部分)。将上述同色区域的颜色替换为颜色值7所得的新图像如图2-2所示。

【算法】

输入：矩阵G，点的坐标(i0，j0)，新颜色值newcolor。

输出：点(i0，j0)所在同色邻接区域的颜色置换为newcolor之后的矩阵G。

算法步骤(为规范算法，规定该算法只在第七步后结束)如下。

第一步：若点(i0，j0)的颜色值与新颜色值newcolor相同，则(1)；

第二步：点(i0，j0)的颜色值→oldcolon创建栈S，并将点坐标(i0，j0)入栈；

第三步；若(2)，则转第七步；

第四步；栈顶元素出栈→(x,y)，并(3)；

第五步；1)若点(x，y-1)在图像中且G[x，y-1]等于oldcolor，则(x,y-1)入栈S；

2)若点(x，y+1)在图像中且GIx，y+1]等于oldeolor，则(x，y+1)入栈S；

3)若点(x-1，y)在图像中且G[x-1，y)等于oldcolor，则(x-1，y)入栈S；

4)若点(x+1，y)在图像中且G[x+1，y)等于oldcolor，则(x+1，y)入栈S；

第六步：转(4)；

第七步：算法结束。

【问题】

是否可以将算法中的栈换成队列?回答；(5) 。

试题一（共 15分）

阅读以下说明和算法，完善算法并回答问题，将解答写在答题纸的对应栏内。

[说明]

假设以二维数组G[1..m,1..n]表示一幅图像各像素的颜色，则G[i,j]表示区域中点(i,j)处的颜色，颜色值为0到k 的整数。下面的算法将指定点(i0,j0)所在的同色邻接区域的颜色置换为给定的颜色值。约定所有与点(i0,j0)同的上、下、左、右可连通的点组成同色邻接区域。

例如，一幅8×9 像素的图像如图1-1 所示。设用户指定点(3,5)，其颜色值为0，此时其上方(2,5)、下方 (4,5)、右方(3,6)邻接点的颜色值都为0，因此这些点属于点(3,5)所在的同色邻接区域，再从上、下、左、右四个方向进行扩展，可得出该同色邻接区域的其他点（见图1-1 中的阴影部分）。将上述同色区域的颜色替换为颜色值7所得的新图像如图1-2 所示。

[算法]

输入：矩阵 G，点的坐标(i0,j0)，新颜色值newcolor。

输出：点(i0,j0)所在同色邻接区域的颜色置换为newcolor之后的矩阵G。

算法步骤(为规范算法，规定该算法只在第七步后结束)：

第一步：若点(i0,j0)的颜色值与新颜色值newcolor相同,则(1) ；

第二步：点(i0,j0)的颜色值→oldcolor；创建栈S，并将点坐标(i0,j0)入栈；

第三步：若 (2) ，则转第七步；

第四步：栈顶元素出栈→(x,y)，并(3) ；

第五步：1) 若点(x,y-1)在图像中且G[x,y-1]等于oldcolor，则(x,y-1)入栈S；

2) 若点(x,y+1)在图像中且G[x,y+1]等于oldcolor，则(x,y+1)入栈S；

3) 若点(x-1,y)在图像中且G[x-1,y]等于oldcolor，则(x-1,y)入栈S；

4) 若点(x+1,y)在图像中且G[x+1,y]等于oldcolor，则(x+1,y)入栈S；

第六步：转 (4) ；

第七步：算法结束。

[问题]

是否可以将算法中的栈换成队列？回答： (5) 。

在一台安装Windows 2003操作系统的双协议栈主机的cmd窗口中，键入“netsh interface ipv6 show interface”可获得如图7-11所示的系统输出信息，请指出图7-11中“MTU”的含义。另外如想查看该主机IPv6路由表则需要输入什么命令?

阅读以下说明和算法，完善算法并回答问题，将解答写在对应栏内。

[说明]

假设以二维数组G[1..m,1..n]表示一幅图像各像素的颜色，则G[i,j]表示区域中点(i,j]处的颜色，颜色值为0到k的整数。

下面的算法将指定点(i0,j0)所在的同色邻接区域的颜色置换为给定的颜色值。约定所有与点(i0,j0)同色的上、下、左、右可连通的点组成同色邻接区域。

例如，一幅8×9像素的图像如图1-1所示。设用户指定点(3,5)，其颜色值为0，此时其上方(2,5)、下方(4,5)、右方(3,6)邻接点的颜色值都为0，因此这些点属于点(3,5)所在的同色邻接区域，再从上、下、左、右四个方向进行扩展，可得出该同色邻接区域的其他点(见图1-1中的阴影部分)。将上述同色区域的颜色替换为颜色值7所得的新图像如图1-2所示。

[算法]

输入：矩阵G，点的坐标(i0,j0)，新颜色值newcolor。

输出：点(i0,j0)所在同色邻接区域的颜色置换为newcolor之后的矩阵G。

算法步骤(为规范算法，规定该算法只在第七步后结束)：

第一步：若点(i0,j0)的颜色值与新颜色值newcolor相同，则(1)；

第二步：点(i0,j0)的颜色值→oldcolor；创建栈S，并将点坐标(i0,j0)入栈；

第三步：若(2)，则转第七步；

第四步：栈顶元素出栈→(x,y)，并(3)；

第五步：

1) 若点(x,y-1)在图像中且G[x,y-1]等于oldcolor,则(x,y-1)入栈S；

2) 若点(x,y+1)在图像中且G[x,y+1]等于oldcolor,则(x,y+1)入栈S；

3) 若点(x-1,y)在图像中且G[x-1,y]等于oldcolor,则(x-1,y)入栈S；

4) 若点(x+1,y)在图像中且G[x+1,y)等于oldcolor,则(x+1,y)入栈S：

第六步：转(4)；

第七步：算法结束。

[问题]

是否可以将算法中的栈换成队列?回答：(5)。

试题七（共 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;

}