首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(n)处的字句写在对应栏内。 【说明】 一个印刷电路板的布线区域可分成n×m个方格,如图4-1(a)所示,现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(n)处的字句写在对应栏内。 【说明】 一个印刷电路板的布线区域可分成n×m个方格,如图4-1(a)所示,现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布
admin
2013-05-11
78
问题
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在软件开发过程中常用图作为描述工具。如DFD就是面向(6)分析方法的描述工具。在一套分层DFD中,如果某一张图中有N个加工(Process),则这张图允许有(7)张子图。在一张DFD图中,任意两个加工之间(8)。在画分层DFD时,应注意保持(9)之间的平
一般VLAN的划分的根据有端口,MAC地址,网络层,IP组播。请简要分析这几种方式的特点。在设定汇聚链接时,必须支持多大的传输速度?
Linux系统对普通文件默认的访问权限是(37)。
在软件生存期中,用户的参与主要在 ______ 。
软件开发中的瀑布模型典型地刻画了软件生存周期的阶段划分,与其最适应的软件开发方法是(13)。
对照ISO/OSI参考模型中的网络安全服务,在物理层可以采用(39)加强通信线路的安全;在数据链路层,可以采用(40)进行链路加密;在网络层可以采用(41)来处理信息内外网络边界流动和建立透明的安全加密信道;在传输层主要解决进程到进程间的加密,最常见的传输
在CPU执行一段程序的过程中,Cache的存取次数为4600次,由主存完成的存取次数为400次。若Cache的存取周期为5ns,主存的存取周期为25ns,则CPU的平均访问时间为(3)ns。
VLAN中继协议(VTP)的作用是(23)。按照VTP协议,交换机的运行模式有(24)。如果要启动VTP动态修剪,则(25)。(23)
入侵检测系统(IDS)是一类专门面向网络入侵检测的网络安全监测系统,其基本功能包括:检测出(1);发现攻击活动的范围和后果;诊断并发现攻击者的入侵方式和入侵地点,并给出解决建议;收集并记录(2)。IDS系统还可以(3)。IDS系统的服务功能
干兆以太网标准802.3z定义了一种帧突发方式(FrameBursting),这种方式是指__________。(2010年上半年试题)
随机试题
教育人事行政
即天意亦不欲长者之轻弃之也,幸宁心哉!
(2007年第173题)下肢动脉血栓栓塞最常来源与
小水泡音多出现在下列哪个时相和时期
以下关于防止基坑坍塌、淹埋应急措施的说法正确的是()。
对某企业的一条生产线进行评估,该生产线的设计生产能力为每天生产1000件产品,设备状况良好,技术上也很先进。由于市场竞争加剧,使该生产线开工不足,每天只生产500件产品。经评估,该生产线的重置成本为900万元,试估测该生产线的经济性贬值额(规模效益指数取
根据下面材料回答下列题。根据给定材料,下列说法正确的是()。
劳动生产率越高,生产一种物品所需要的劳动时间就越少,凝结在该物品中的劳动量就越小,该物品的价值就越小。相反地,劳动生产率越低,生产一种物品的必要劳动时间就越多,该物品的价值就越大。因此,为了增加单位商品的价值量,我们要尽量降低劳动生产率。这一观点
________ですが、あしたのパーティーには出られません。
Therearetwoaspectswhichdetermineanindividual’sintelligence.ThefirstistheDrainbeisborn【C1】______Humanbrainsdiff
最新回复
(
0
)