首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(n)处的字句写在答题纸的对应栏内。 【说明】 一个印刷电路板的布线区域可分成n×m个方格,如图3-1(a)所示,现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(n)处的字句写在答题纸的对应栏内。 【说明】 一个印刷电路板的布线区域可分成n×m个方格,如图3-1(a)所示,现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直
admin
2006-03-15
42
问题
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(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
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】在某嵌入式智能服务机器人的软件设计中,为了更好地记录机器人的个体信息和机器人的工作信息,为智能服务机器人设计了信息数据库。数据库主要完成收集智能服务机器人反馈信息的作用,记录所有机器人的所有工
某一确定性有限自动机(DFA)的状态转换图如下图所示,令d=0|1|2|…|9,则以下字符串中,不能被该DFA接受的是(33),与该DFA等价的正规式是(34)。(其中,ε表示空字符)①3857②1.2E+5③-123.④.
在GB/T 17544中,软件包质量要求包括三部分,即产品描述要求、(53)、程序和数据要求。
多条件覆盖是一种逻辑覆盖,它的含义是设计足够的测试用例,使得每个判定中条件的各种可能组合都至少出现一次,满足多条件覆盖级别的测试用例也是满足(44)级别的;针对布尔表达式A&&(B‖C)执行逻辑覆盖测试,测试用例至少需要(45)种组合才能满足多条件覆盖的要
多条件覆盖是一种逻辑覆盖,它的含义是设计足够的测试用例,使得每个判定中条件的各种可能组合都至少出现一次,满足多条件覆盖级别的测试用例也是满足(44)级别的;针对布尔表达式A&&(B‖C)执行逻辑覆盖测试,测试用例至少需要(45)种组合才能满足多条件覆盖的要
两个同符号的数相加或异符号的数相减,所得结果的符号位SF和进位标志CF进行(1)运算为1时,表示运算的结果产生溢出。
请根据下面叙述的场景选用适当的设计模式。若某面向对象系统中的某些类有且只有一个实例,那么采用(30)设计模式能够有效达到该目的:该系统中的某子模块需要为其他模块捉供访问不同数据库系统(如 Oracle、SQL Server和DB2 UDB等)的功能,这些数
在“模型一视图一控制器(NVC)”模式中,(27)主要表现用户界面,(28)用来描述核心业务逻辑。
某供应商数据库中的供应关系为SPJ(供应商号,零件号,工担号,数量),如下命令查询某工程至少用了3家供应商(包含3家)供应的零件的平均数量,并按工程号的降序排列。SELECT工程号,(14)FROMSPJGROUPBY工程号(15)
在计算机体系结构中,CPU内部包括程序计数器PC、存储器数据寄存器MDR、指令寄存器IR和存储器地址寄存器MAR等。若CPU要执行的指令为:MOV R0,#100(即将数值100传送到寄存器R0中),则CPU首先要完成的操作是(1)。
随机试题
静息状态下,细胞膜对K+和Na+都具有通透性。()
患者,男性,58岁。在无明显外伤情况下,反复出现血尿,无痛。患者很焦虑,来到医院要求查明原因。根据该情况,优先考虑的疾病可能为
简述地役权的特征。
为什么必须依法治国,建设社会主义法制国家?
疼痛且有胀感者,称为
已知n阶可逆矩阵A的特征值为入0,则矩阵(2A)-1的特征值是()。[2012年真题]
城市道路系统规划中,符合规划要求的做法是()。
甲公司和乙公司均为增值税一般纳税人,适用的增值税税率均为17%,2×15年1月10日,甲公司销售一批商品给乙公司,货款为4863万元(含增值税税额)。合同约定,乙公司应于2×15年4月10日前支付上述货款。由于资金周转困难,乙公司到期不能偿付货款。经协商,
与设计测试用例无关的文档是______。
根据素材文件“百合花.docx”制作演示文稿,具体要求如下:采用由观众手动自行浏览方式放映演示文稿,动画效果要贴切,幻灯片切换效果要恰当、多样。
最新回复
(
0
)