軟件設(shè)計(jì)師案例分析當(dāng)天每日一練試題地址：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4

往期軟件設(shè)計(jì)師每日一練試題匯總：m.xiexiliangjiufa.com/class/27/e4_1.html

軟件設(shè)計(jì)師案例分析每日一練試題（2021/10/27）在線(xiàn)測(cè)試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2021/10/27

點(diǎn)擊查看：更多軟件設(shè)計(jì)師習(xí)題與指導(dǎo)

軟件設(shè)計(jì)師案例分析每日一練試題內(nèi)容（2021/10/27）

試題三
閱讀以下說(shuō)明和流程圖，從供選擇的答案中選出應(yīng)填入流程圖  (n)  處的字句寫(xiě)在答題紙的對(duì)應(yīng)欄內(nèi)。
【說(shuō)明】
一個(gè)印刷電路板的布線(xiàn)區(qū)域可分成n×m個(gè)方格，如圖3-1(a)所示，現(xiàn)在需要確定電路板中給定的兩個(gè)方格的中心點(diǎn)之間的最短布線(xiàn)方案。電路只能沿水平或垂直方向布線(xiàn)，如圖3-1(b)中虛線(xiàn)所示。為了避免線(xiàn)路相交，應(yīng)將已布過(guò)線(xiàn)的方格做封鎖標(biāo)記，其他線(xiàn)路不允許穿過(guò)被封鎖的方格。

設(shè)給定印刷電路板的起始方格x與目的方格y尚未布線(xiàn)，求這兩個(gè)方格間最短布線(xiàn)方案的基本思路是：從起始方格x開(kāi)始，先考查距離起始方格距離為1的可達(dá)方格并用一個(gè)路徑長(zhǎng)度值標(biāo)記，然后依次考查距離為2，3，…的可達(dá)方格，直到距離為k的某一個(gè)可達(dá)方格就是目標(biāo)方格y時(shí)為止，或者由于不存在從x到y(tǒng)的布線(xiàn)方案而終止。布線(xiàn)區(qū)域中的每一個(gè)方格與其相鄰的上、下、左、右四個(gè)方格之間的距離為1，依次沿下、右、上、左這四個(gè)方向考查，并用一個(gè)隊(duì)列記錄可達(dá)方格的位置。表3-1給出了沿這四個(gè)方向前進(jìn)1步時(shí)相對(duì)于當(dāng)前方格的相對(duì)偏移量。

例如，設(shè)印刷電路板的布線(xiàn)區(qū)域可劃分為一個(gè)6×8的方格陣列，如圖3-2(a)所示，其中陰影表示已封鎖方格。從起始方格x(位置[3，2]，標(biāo)記為0)出發(fā)，按照下、右、上、左的方向依次考查，所標(biāo)記的可達(dá)方格如圖3-2(a)所示，目標(biāo)方格為y(位置[4，7]，標(biāo)記為10)，相應(yīng)的最短布線(xiàn)路徑如圖3-2(b)虛線(xiàn)所示。 【圖3-2】


圖3-3和圖3-4所示的流程圖即利用上述思路，在電路板方格陣列中進(jìn)行標(biāo)記，圖【圖3-3】





中使用的主要符號(hào)如表3-2所示。在圖3-4中，設(shè)置電路板初始格局即將可布線(xiàn)方格置為數(shù)值-1、已布線(xiàn)方格(即封鎖方格)置為-9。設(shè)置方格陣列“圍墻”的目的是省略方格位置的邊界條件判定，方法是在四周附加方格，并將其標(biāo)記為-9(與封鎖標(biāo)記相同)。

供選擇的答案
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