首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(n)处的字句写在答题纸的对应栏内。 【说明】 一个印刷电路板的布线区域可分成n×m个方格,如图3-1(a)所示,现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(n)处的字句写在答题纸的对应栏内。 【说明】 一个印刷电路板的布线区域可分成n×m个方格,如图3-1(a)所示,现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直
admin
2006-03-15
59
问题
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(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
选项
答案
(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描述的上述处理过程中,满足条件i<4且Found=False时处理沿4个方向进行考查并扩展结点的操作,即
T.row=CurPos.row+offset
.r T.col=CurPos.col+offset
.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.insert<T)”。显然空(4)处表示找到目标方格时的结束条件,根据流程中的处理逻辑应填入“Found≠true”。当尚未找到目标位置结点而队列又不为空时,应从队列中取出一个新的结点作为当前结点进行考查和扩展,因此空(5)处填入“CurPos←O.delete()”。
转载请注明原文地址:https://kaotiyun.com/show/sfDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读下列C程序,回答问题,将解答填入答题纸的对应栏内。【C程序】intisbinary(constvoid*buf,constsizetbuf—fen){sizetsuspiciousbytes=0;sizettotal—by
阅读下列C程序,回答问题,将解答填入答题纸的对应栏内。【C程序】intisbinary(constvoid*buf,constsizetbuf—fen){sizetsuspiciousbytes=0;sizettotal—by
某数据库中有供应商关系S和零件关系P,其中,供应商关系模式S(Sno,Sname,SZip,City)中的属性分别表示;供应商代码、供应商名、邮编、供应商所在城市;零件关系模式P(Pno,Pname,Color,Weight,City)中的属性分别表示:
某一确定性有限自动机(DFA)的状态转换图如下图所示,令d=0|1|2|…|9,则以下字符串中,不能被该DFA接受的是(33),与该DFA等价的正规式是(34)。(其中,ε表示空字符)①3857②1.2E+5③-123.④.
数据存储在磁盘上的排列方式会影响I/O服务的总时间。假设每磁道划分成10个物理块,每块存放1个逻辑记录。逻辑记录R1,R2,…,R10存放在同一个磁道上,记录的安排顺序如下表所示:假定磁盘的旋转速度为20ms/周,磁头当前处在R1的开始处。若系统顺序处
两个公司希望通过Internet进行安全通信,保证从信息源到目的地之间的数据传输以密文形式出现,而且公司不希望由于在传输节点使用特殊的安全单元而增加开支,最合适的加密方式是(10),使用的会话密钥算法应该是(11)。
多条件覆盖是一种逻辑覆盖,它的含义是设计足够的测试用例,使得每个判定中条件的各种可能组合都至少出现一次,满足多条件覆盖级别的测试用例也是满足(44)级别的;针对布尔表达式A&&(B‖C)执行逻辑覆盖测试,测试用例至少需要(45)种组合才能满足多条件覆盖的要
针对下面程序段,边界值问题可以定位在(62)1:RemCregea10elementintegerarray2:RemInitializeeachelementto-13:Dimdata(10)As
某系统的进程状态转换如下图所示。图中1、2、3和4分别表示引起状态转换时的不同原因。原因4是由于(9);一个进程状态转换会引起另一个进程状态转换的是(10)。
随机试题
机会成本是指()
女,60岁,间歇性右上腹疼痛10年,疼痛向右肩放射,近一周再发右上腹疼痛。查体:右上腹可扪及10cm×8cm包块,张力高,局部压痛、反跳痛,腹肌紧张。行上腹部磁共振平扫及MRCP检查提示胆囊颈结石并胆囊炎。磁共振的禁忌证不包括下列
男性,26岁,农民,5天来发热、畏寒,1天来头痛、呕吐2次,于8月15入院,T39.6℃,球结膜充血,颈有抵抗,腹股沟淋巴结肿大,有压痛,腓肠肌有压痛,尿蛋白(++)。诊断应考虑
企业在确定组织结构类型时所需考虑的因素有()。
下列选项中,符合房地产经纪人执业资格考试报名条件的是()。
影子汇率换算系数越高,外汇的影子价格越高,产品是可外贸货物的项目效益较高,评价结论会()出口方案。同时外汇的影子价格较高时,项目引进投入物的方案费用较高,评价结论会()引进方案。
单位日常工作中,有些事情时间紧急但不是很重要,有些事情非常重要但不是很紧急。你处理这些事情时会怎么做?
对于一个长度为n的任意表进行排序,至少需要进行的比较次数是()。
加强网络文化建设和管理,充分发挥互联网在我国社会主义文化建设中的重要作用,有利于
Haveyouseenthismovie?Itisreallyworth(see)______.
最新回复
(
0
)