首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(n)处的字句写在对应栏内。 【说明】 一个印刷电路板的布线区域可分成n×m个方格,如图4-1(a)所示,现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(n)处的字句写在对应栏内。 【说明】 一个印刷电路板的布线区域可分成n×m个方格,如图4-1(a)所示,现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布
admin
2013-05-11
30
问题
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(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]i
4 [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://kaotiyun.com/show/kERZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
为了进行差错控制,必须对传送的数据帧进行校验,由接收方检测数据传输是否出现差错,常用的差错控制方法是(34)。要检测接收的数据是否有错,最常用的方法是(35)。海明码是一种纠错码,采用海明码纠正一位差错,若信息位为7bit,则冗余位至少应为(36),CRC
在面向对象方法中,把一组具有相同数据结构和相同操作的对象的集合定义为______ 。此定义包括一组数据属性和在数据上的一组合法操作。
采用脉码调制(PCM)方法对声音信号进行编码,若采样频率为8000Hz,量化级为256级,那么数据传输率要达到(10)。
使用ADSL拨号上网,需要在用户端安装(19)协议。
TheTCPprotocolisa(71)layerprotoc01.EachconnectionconnectstwoTCPsthatmaybejustonephysicalnetworkapartorlocate
TheTCPprotocolisa(71)layerprotoc01.EachconnectionconnectstwoTCPsthatmaybejustonephysicalnetworkapartorlocate
M软件公司的软件产品注册商标为M,为确保公司在市场竞争中占据优势,对员工进行了保密约束。此情形下该公司不享有__________。(2012年下半年试题)
采用UML进行软件设计时,可用()关系表示两类实体之间存在的特殊/一般关系,用聚集关系表示事物之间存在的整体/部分关系。
IIS6.0支持的身份验证安全机制有4种验证方法,其中安全级别最高的验证方法是__________。(2012年上半年试题)
SCSI是一种通用的系统级标准输入/输出接口,其中(65)标准的数据宽度16位,数据传送率达20MB/s。大容量的辅助存储器常采用RAID磁盘阵列。RAID的工业标准共有六级。其中,(66)是镜像磁盘阵列,具有最高的安全性;(67)是无独立校验盘的奇偶校验
随机试题
素质教育在本质上是一种()。
在建设工程项目施工风险管理中,针对项目风险而采取的相应对策,属于风险管理中的()。
金融监管包含哪些内容?
1956年4-5月,毛泽东先后在中央政治局扩大会议和最高国务会议上作的《论十大关系》报告中指出“最近苏联方面暴露了他们在建设社会主义过程中的一些缺点和错误,他们走过的弯路你还想走?过去,我们就是鉴于他们的经验教训,少走了一些弯路,现在当然更要引以为戒”,这
阴阳偏衰的治疗原则是
患者,男性,25岁,因车祸撞伤腹部,患者主诉疼痛难忍,伴恶心、呕吐,X线腹透可见膈下游离气体,拟诊断为胃肠道穿孔。为减少腹腔毒素吸收,可采取的体位是
给定线性方程组,正确的答案为( )。
对于不符合规定条件的建设项目所在地附近的气象台(站)资料,必须在与现场观测资料进行相关分析后方可考虑其使用价值,二级评价项目,相关系数γ不宜小于( )。
那位老人宁愿独居乡下,也不愿和儿子一起住在城里。
根据辩证唯物主义理论,关于物质和意识,下列说法正确的是()。
最新回复
(
0
)