首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(n)处的字句写在对应栏内。 【说明】 一个印刷电路板的布线区域可分成n×m个方格,如图4-1(a)所示,现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(n)处的字句写在对应栏内。 【说明】 一个印刷电路板的布线区域可分成n×m个方格,如图4-1(a)所示,现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布
admin
2013-05-11
56
问题
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
有关曼彻斯特码编码的正确叙述是(24)。
假定一条线路每1/16s采样一次,每个可能的信号变化都运载3bit的信息,则传输速率是(1)。
图3-5是虚拟主机示意图,图中“N”部分不可能是(63)。
IIS安装的硬盘分区最好选用NTFS格式,这是因为(1)和(2)。A.可以针对某个文件或文件夹给不同的用户分配不同的权限B.可以防止网页中的Applet程序访问硬盘中的文件C.可以使用系统自带的文件加密系统对文件或文件夹进行加
IIS安装的硬盘分区最好选用NTFS格式,这是因为(1)和(2)。A.可以针对某个文件或文件夹给不同的用户分配不同的权限B.可以防止网页中的Applet程序访问硬盘中的文件C.可以使用系统自带的文件加密系统对文件或文件夹进行加
ThedefactostandardApplicationProgramInterface(API)forTCP/IPapplicationsisthet•sockets”interface.AlthoughthisAPlwa
两个公司希望通过Internet传输大量敏感数据,从信息源到目的地之间的传输数据以密文形式出现,而且不希望由于在传输节点使用特殊的安全单元而增加开支,最合适的加密方式是(1),使用会话密钥算法效率最高的是(2)。(2009年上半年试题)(1)
Atransportlayerprotocolusuallyhasseveralresponsibilties.Oneistocreateaprocess—to—processcommunicationUDPuses(71)n
采用10Base一5的局域网表示(1)。采用特性阻抗为(2)Ω的粗同轴电缆。这种网络的收发器不在网卡上,而是直接与电缆相连,收发器电缆最长为(3),最大节点数限于(4)个工作站。(2)
阅读以下说明,回答问题,将解答填入对应的解答栏内。[说明]给出一个接收三个数a、b、c作为三角形边长并输出三角形的类型的程序。程序代码如下所示:结点源代码行Areada,b,cB
随机试题
设向量组α1,α2,α3线性无关,则下面向量组中线性无关的是()
学校文化由学校的物质文化、精神文化、组织文化和_______构成。
下列不属于系统性红蝴蝶疮临床表现的是
肥胖是指体重至少超过理想体重的
WWW网是()的简称。
合同变更应该从两方面人手,一是同意或拒绝变更要求的内部程序;二是修改合同以适应被批准的变化的机制。()
2009年春节前夕,A县公安局在治安检查中发现B公司在没有申领《卫生许可证》的情况下假冒C公司的商标生产香肠,A县公安局随即对没有销售的香肠进行了扣押。15日后,公安局将香肠移交给A县质监局,经质监局检验,该香肠质量不合格,大肠杆菌严重超标。A县质监局对于
(2006年真题)下列诸项表述中,能够成立的有
方程的根是___________.
[2002年]设A,B为同阶矩阵.当A,B均为实对称矩阵时,试证第一题的逆命题成立.
最新回复
(
0
)