2. 计算机
  3. 阅读以下说明和流程图，从供选择的答案中选出应填入流程图(n)处的字句写在对应栏内。 【说明】 一个印刷电路板的布线区域可分成n×m个方格，如图4-1(a)所示，现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布

阅读以下说明和流程图，从供选择的答案中选出应填入流程图(n)处的字句写在对应栏内。 【说明】 一个印刷电路板的布线区域可分成n×m个方格，如图4-1(a)所示，现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布

admin2013-05-11  36
问题 阅读以下说明和流程图，从供选择的答案中选出应填入流程图(n)处的字句写在对应栏内。
【说明】
   一个印刷电路板的布线区域可分成n×m个方格，如图4-1(a)所示，现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布线，如图4-1 (b)中虚线所示。为了避免线路相交，应将已布过线的方格做成封锁标记，其他线路不允许穿过被封锁的方格。
            
   设给定印刷电路板的起始方格x与目的方格y尚未布线，求这两个方格间最短布线方案的基本思路是：从起始方格x开始，考查与起始方格距离为k的某一个可达方格是目标方格y时为止，或者由于不存在从x到y的布线方案而终止。布线区域中的每一个方格与其相邻的上、下、左、右4个方格之间的距离为1，依次沿下、右、上、左这4个方向考查，并用一个队列记录可达方格的位置。表4-1给出了沿这4个方向前进1步时相对于当前方格的相对偏移量。

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

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

供选择的答案：
   [a]Found≠true    Found=true
   [c]T=EndPos    [d]Q.insert(T)
   [e]T←Q.delete()    [f]CurPos=EndPos
   [g]i4    [h]CurPos←Q.delete()
   Grid[T.row,T.col]=-1    [j]Grid[T.row,T.col]≠-1
选项
答案(1)[i]或i (2)[c]或c (3)[d]或d (4)[a]或a (5)[h]或h
解析 该流程实现的功能是为印刷电路板选择布线路径，路经中的每一小步都只能走垂直线或水平线，而且要求得到的路径是最短路径。
   图4-3是该算法的整体流程，包含了变量的初始化及输入输出，以及调用了子过程findPath。findPath子过程才是关键的处理(如图4-4所示)。
   findPath中，先设置offset数组的元素值，并创建空队列。然后将当前位置CurPos置为起始位置StartPos，并将标记Found置为false，表示当前还没找到路径，接着将当前方格置为0 (Grid数组中的对应元素)，表示起始点。进入循环，将i赋初值为0，从接着的判定的条件i＜ 4及offset.r可以断定，变量i就是表4-1中的“搜索顺序i”，所以紧接着的语句“T.row←CurPos.row+offset.r”和“T.col←CurPos.col+offset.c”就是求下一个要走的单元格(临时方格T)的行坐标和列坐标。然后是判定(1)，若不成立，则直接将i加1，向另一个方向继续搜索，意味着临时方格T不能布线(值为-9)或已经判断过(值大于等于0)；若成立，则将临时方格置为当前方格值加1，表示到起始方格的距离增加1，亦即可以布线且尚未判断过。根据题述，方格的初始值为-1表示可以布线，故判定(1)应为“Grid[T.row,T.col] =-1”，即选项i。
   接着是判定(2)，若成立则执行语句“Found←true”，意味着找到了解，即临时方格已经是目标方格。故判定(2)应为“T=EndPos”，即选项c。判定(2)不成立时，执行加工(3)，这里应该是入队操作，将临时方格入队，故加工(3)应为“Q.insert(T)”，即选项d。接着将i值加1，继续搜索。
   当判定“i＜4且Found=false”不成立时，有两种情况：一种是i＞=4，另一种是Found=true。判定(4)若不成立返回true，意味着找到了解，故判定(4)应为“Found≠true”，即选项a。这样，若判定(4)成立，意味着i＞=4，即4个方向均已搜索，接着判断队列是否为空，若非空，则出队继续查找，进程(5)自然是出队操作了，但是出队给哪个变量呢?是临时方格T还是当前方格CurPos?其实很容易判断，从最近的语句“T.row←CurPos.row+offset.r”和“T.col←CurPos.col+offset.c”可得应为当前方格CurPos，故应为“CurPos←Q.delete()”，即选项h。
转载请注明原文地址:https://jikaoti.com/ti/dvf7FFFM
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)