阅读以下说明和流程图,从供选择的答案中选出应填入流程图(n)处的字句写在答题纸的对应栏内。【说明

Question

阅读以下说明和流程图，从供选择的答案中选出应填入流程图(n)处的字句写在答题纸的对应栏内。

【说明】

一个印刷电路板的布线区域可分成n×m个方格，如图3-1(a)所示，现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布线，如图3-1(b)中虚线所示。为了避免线路相交，应将已布过线的方格做封锁标记，其他线路不允许穿过被封锁的方格。

设给定印刷电路板的起始方格x与目的方格y尚未布线，求这两个方格间最短布线方案的基本思路是：从起始方格x开始，先考查距离起始方格距离为1的可达方格并用一个路径长度值标记，然后依次考查距离为2，3，…的可达方格，直到距离为k的某一个可达方格就是目标方格y时为止，或者由于不存在从x到y的布线方案而终止。布线区域中的每一个方格与其相邻的上、下、左、右四个方格之间的距离为1，依次沿下、右、上、左这四个方向考查，并用一个队列记录可达方格的位置。表3-1给出了沿这四个方向前进1步时相对于当前方格的相对偏移量。

例如，设印刷电路板的布线区域可划分为一个6×8的方格阵列，如图3-2(a)所示，其中阴影表示已封锁方格。从起始方格x(位置[3，2]，标记为0)出发，按照下、右、上、左的方向依次考查，所标记的可达方格如图3-2(a)所示，目标方格为y(位置[4，7]，标记为10)，相应的最短布线路径如图3-2(b)虚线所示。

【图3-2】

图3-3和图3-4所示的流程图即利用上述思路，在电路板方格阵列中进行标记，图

中使用的主要符号如表3-2所示。在图3-4中，设置电路板初始格局即将可布线方格置为数值-1、已布线方格(即封锁方格)置为-9。设置方格阵列“围墙”的目的是省略方格位置的边界条件判定，方法是在四周附加方格，并将其标记为-9(与封锁标记相同)。

供选择的答案

A．Found≠true B．Found=true

C．T=EndPos D．Q．insert(T)

E．T←Q.delete() F．CurPos=EndPos

G．i≥4 H．CurPos←Q．delete()

I．Grid[T.row,T.col]=-1 J．Grid[T.row,T.col]≠-1

Answer 1

正确答案：(1)Grid[T.rowT.col]=-1 (2)T=EndPos (3)Q.insert(T) (4)Found≠true (5)CurPos→Q.delete()
(1)Grid[T.row,T.col]=-1 (2)T=EndPos (3)Q.insert(T) (4)Found≠true (5)CurPos→Q.delete() 解析：根据题目中的说明，设给定印刷电路板的起始方格x与目的方格y尚未布线，求这两个方格间最短布线方案的基本思路是：从起始方格x开始，先考查距离起始方格距离为1的可达方格并用一个路径长度值标记，然后依次考查距离为2、3、…的可达方格，直到距离为k的某一个可达方格就是目标方格y时为止，或者由于不存在从x到y的布线方案而终止。布线区域中的每一个方格与其相邻的上、下、左、右四个方格之间的距离为1，依次沿下、右、上、左这四个方向考查，并用一个队列记录可达方格的位置。该方法体现了广度优先搜索策略，以题中的图4-5为例，根结点表示起始方格的位置 ([3,2])，孩子结点表示一步可达的位置，其过程可用下图所示的树结构表示。
按照广度优先的策略，先将起始位置结点加入队列，此后在队列不为空的情况下，每次从队列中取出一个结点(元素出队列)，按照下、右、上、左的方向依次扩展并将扩展所得的结点加入队列，重复这个过程，直到目标位置结点出现，或队列为空还没有出现目标位置时为止。对于上例，根结点[3，2]出队列后，扩展出结点[4，2]、[3，3]、[2， 2]、[3，1)并依次加入队列，然后由14，2]扩展出[5，2]、[4，3]、[4，1)，[3，3]扩展出 [3，4)，[2，2]扩展出[2，1)、[1，2]，依次类推，当扩展出目标结点[4，7]时，路径长度为10。
在流程图3-4描述的上述处理过程中，满足条件i4且Found=False时处理沿4个方向进行考查并扩展结点的操作，即
T.row=CurPos.row+offset[i].rT.col=CurPos.col+offset[i].c)

但是方格位置[T.row,T.col]有可能已经封锁(标记为-9)，所以在对可扩展结点(标记为 -1)进行路径长度标记时应判断是否可以标记，因此空(1)处应对Grid[T.row,T.col]的标志进行判断，根据流程中的处理逻辑，显然应填入“Grid[T.row,T.col]=-1。当得到一个扩展结点时(Grid[T.row,T.col]←Grid[CurPos.row，CurPos.col+1)，应判断目标结点是否出现，即扩展出的结点T是否等于目标结点EndPos，若是，则可结束扩展操作 (Found=True)，否则，将结点T加入队列，因此空(2)处填入“T=EndPos'’、空(3)处填入“Q．insertT)”。显然空(4)处表示找到目标方格时的结束条件，根据流程中的处理逻辑应填入“Found≠true”。当尚未找到目标位置结点而队列又不为空时，应从队列中取出一个新的结点作为当前结点进行考查和扩展，因此空(5)处填入“CurPos←O.delete()”。