首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(n)处的字句写在对应栏内。 【说明】 一个印刷电路板的布线区域可分成n×m个方格,如图4-1(a)所示,现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(n)处的字句写在对应栏内。 【说明】 一个印刷电路板的布线区域可分成n×m个方格,如图4-1(a)所示,现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布
admin
2013-05-11
31
问题
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
采用脉码调制(PCM)方法对声音信号进行编码,若采样频率为8000Hz,量化级为256级,那么数据传输率要达到(10)。
不使用DNS和NIS进行地址解析时,为保证解析器能找到主机的IP地址,必须将所使用的主机名字写入(58)文件中。
某企业内部网段与Internet网互联的网络拓扑结构如图8-3所示,其防火墙结构属于(34)。
从信息资源管理的观点出发,信息系统的逻辑结构一般由4部分组成,其中(18)利用信息系统提供的信息进行决策和选择,是信息系统服务的对象。
SSL是一个介于(1)与TCP之间的一个可选层,当发送访问请求时,在SSL层,借助下层协议的安全信道(2),并用此来(3)。在TCP层,与服务器端口建立连接,传递SSL处理后的数据。接收端的操作与此发送端过程相反。SSL协议分为(4)和记录协议两部分。其中
子网过滤防火墙安装方法是把防火墙安装在一个由(1)控制边界的公共子网中,子网中有一台执行(2)的主机,对于多数应用入口,需要一个附加的(3)机制来控制、筛选入口与网络之间的信息流。这样可以有效地把该机制和(4)结合起来,达到多层屏障保护的目的。
下面关于曼彻斯特编码的叙述中,错误的是__________。(2010年下半年试题)
如果发现网络的数据传输很慢,服务质量也达不到要求,应该首先检查哪一个协议层工作情况?(70)
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的数字表示活动的持续时间(天)。由于某种原因,现在需要同一个开发人员完成BC和BD,则完成该项目的最少时间为_____________天。
汉字输入码有多种方案,区位码是属于数字编码。由于汉字数目较多,区位码采用两字节表示,区号占一个字节表示1~94区,位号占一个字节表示1~94位。区号、位号确定后,即可指定唯一的一个汉字。汉字内码也是两字节汉字,编号与区位码一一对应,其区别在于用(1)表示区
随机试题
我们已经是其他几家厂商的代理。
渗出性炎症时,炎灶局部最先渗出的蛋白成分是
急性左心衰吸氧需
如图所示,三棱柱A沿三棱柱B的光滑面滑动,三棱柱A重P,三棱柱B重Q,三棱柱B的斜面与水平成α角,初始系统静止,则三棱柱A沿斜面下滑时三棱柱B的加速度为()。
编制计划需要依据,属于施工成本计划编制依据的有()。
水利项目稽察组由()组成。
下列各项中,不属于机器组成部分的是()。
如图A、B为两种不同金属材料制成的导体,它们紧密接触且横截面积相同。已知A电阻率小于B,a、b分别为两种导体内部的点,在导体两端加一恒定电压U,导体内有恒定电流I通过,则下列关于a、b两点场强大小的判定正确的是()。
公安信息保障工作主要是为各项公安工作()
关于PGP的描述中,正确的是()。
最新回复
(
0
)