全國計算機技術與軟件專業技術資格(水平)考試
2005年上半年軟件設計師晨間試卷
(考試時間:9:00 ~ 11:30 * * * 150分)
●在計算機中，最適合數字加減法的數字編碼是_ _，最適合浮點數的數字編碼是_ _。
(1) A .原始碼b .反碼c .補碼d .碼移位
(2) A .原碼b .反碼c .補碼d .移碼
●如果主存容量為16M字節，以字節為單位尋址，則意味著主存地址至少需要_ _ _位。
(3) A.16 B，20 C.24 D.32
●操作數的位置可以決定指令的尋址模式。操作數包含在指令中，尋址方式為_ _；寄存器中的操作數，尋址方式是_ _；操作數的地址在寄存器中，尋址方式是_ _。
(4) A .立即處理B。直接定址
C.寄存器尋址d .寄存器間接尋址
(5) A .立即處理B。直接定址
C.寄存器尋址d .寄存器間接尋址
(6) A .相對尋址b .直接尋址
C.寄存器尋址d .寄存器間接尋址
●可靠性r為0.8的三個部件串聯成壹個系統，如下圖所示:
___ ___ ___ ___
那麽系統的可靠性是_ _。
(7)A、0.240 B、512 C、0.800 D、0.992
●在計算機系統中構建壹個虛擬內存。
(8) A .只需要壹定的硬件資源就可以實現B..只需要壹定的軟件就可以實現。
C.要實現d，軟件和硬件都需要，軟件和硬件都不需要。
壹家公司使用包過濾防火墻來控制進出公司局域網的數據。在不考慮使用代理服務器的情況下，下列描述是錯誤的:“防火墻可以_ _”。
(9) A .讓公司員工只能訪問互聯網和與他們有業務往來的公司的IP地址。
B.只允許HTTP協議通過。
C.使員工無法直接訪問端口號為21的FTP服務。
d .只有公司中具有特定IP地址的計算機才能訪問外部網絡。
●兩家公司希望通過互聯網進行安全通信，確保從住所源到目的地的數據傳輸以密文的形式出現，並且兩家公司不希望由於在傳輸節點使用特殊的安全單元而增加開支。最合適的加密方法是_ _，使用的會話密鑰算法應該是_ _。
(10) A .鏈路加密b .節點加密c .端到端加密d .混合加密
(11)A . RSA B . RC-5c . MD5 D . ECC
●在我國著作權法中，_ _ _指的是同壹個概念。
(12) A .出版權和著作權b .著作權c .作者權和專有權d .發行權和著作權
●由中國信息產業部批準發布，在信息產業部範圍內統壹使用的標準稱為_ _。
(13) A .地方標準b .部門標準c .行業標準d .企業標準
●軟件設計者將他人使用C編程語言開發的控制程序轉換成機器語言的控制程序，並在芯片中進行國產化的行為。
(14) A .不構成侵權，因為新的控制程序與原控制程序轉換成機器語言時使用的程序不同。
b不構成侵權，因為原控制程序經過了改造和固化，使用和表達方式不同。
C.把用壹種編程語言編寫的源程序轉換成另壹種編程語言，而不侵權，這是壹種“翻譯”行為。
D.構成侵權，因為他不享有原軟件作品的著作權。
●存儲在磁盤上的數據的排列會影響I/O服務的總時間。假設每個磁道分為10個物理塊，每個塊存儲1個邏輯記錄。邏輯記錄r！合乎邏輯的記錄。邏輯記錄R1，R2，R10存儲在同壹磁道上，記錄的排列順序如下表所示:
物理塊1234556789 10
邏輯記錄r 1r2r 3 R4 R5 R6 R7 R8 R9 r 10
假設磁盤轉速為20MS/周，磁頭目前在R1開頭。如果系統順序處理這些記錄並使用單個緩沖區，每條記錄的處理時間為4MS，那麽處理這10條記錄的最長時間為_ _。
(15)甲180毫秒乙200毫秒丙204毫秒丁220毫秒
(16)a . 40毫秒B. 60ms毫秒c . 100毫秒d . 160毫秒
●分頁存儲系統的邏輯地址由兩部分組成:頁號和頁中的地址。假設頁面大小是4K。地址轉換過程如下圖所示，邏輯地址用十進制表示。
(17)
圖中有效地址轉換後，十進制物理地址A應該是_ _。
下列說法中，與提高軟件可移植性有關的是_ _。
(18) A .選擇時間效率高的算法b .盡量減少評論c .選擇空間效率高的算法。
d盡量用高級語言寫系統中效率要求不高的部分。
在系統轉換過程中，舊系統和新系統並行工作壹段時間，然後新系統取代舊系統，稱為_ _；在新系統完全投入運行之前，壹部分壹部分替換舊系統的策略稱為_ _。
(19) A .直接轉換b .位置轉換c .段轉換d .並行轉換
(20) A .直接轉換b .位置轉換c .段轉換d .並行轉換
●在下列要素中，不屬於DFD的是_ _。當使用DFD建立薪資系統模型時，_ _ _可以被視為外部實體。
(21)答.處理b .數據流c .數據存儲d .聯系
(22) A .銀行接收工資單b .工資單系統源代碼程序c .工資單d .工資單數據庫的維護
●在系統驗收測試中，_ _ _是在模擬環境中用模擬數據運行系統；_ _ _是在真實的環境中用真實的數據運行系統。
(23) A .驗證測試b .審計測試c .確認測試d .模塊測試
(24) A .驗證測試b .審計測試c .確認測試d .模塊測試
●在使用瀑布模型進行系統開發的過程中，每個階段都會產生不同的文檔。在下面關於生成這些單據的描述中，正確的是_ _。
(25) A .外部設計評審報告在概要設計階段生成。
B.綜合評價計劃是在方案設計階段產生的。
C.系統計劃和需求陳述在詳細設計階段產生。
編碼時獨立設計單元測試計劃。
●在單CPU計算機系統中，有兩個外部設備R1和R2以及三個進程P1、P2和P3。系統采用優先級可分離的進程調度方案，所有進程可以並行使用I/O設備。三個進程的優先級、使用設備的順序以及設備的占用情況如下表所示:
進程優先級:使用設備的順序和設備占用的時間。
P1高R2(30毫秒)CPU(10毫秒)r 1(30毫秒)CPU(10毫秒)。
在P2，r 1(20毫秒)CPU(30毫秒)R2(40毫秒)
P3低CPU(40毫秒)r 1(10毫秒)
假設忽略操作系統的開銷，從投入運行到全部完成，三個進程的CPU利用率約為_ _%;R2的利用率約為_ _%(設備利用率是指設備的使用時間與工藝組完成全部所用時間的比值)。
(26)公元前60年至公元前67年
(27)公元前70年至公元前78年
●確定性有限自動機(DFA)的狀態轉移圖如下圖所示。設d = 0 | 1 | 2 |...| 9，那麽_ _是這個DFA不能接受的，等價於這個DFA的正規公式是_ _。(其中ε代表空字符)
①3875②1.2E+5③-123④. 576 e 10
(28)A.①、②、③ B. ①、②、④ C. ②、③、④ D. ①、②、③、④
(29)a .(-dld)d * E(-dld)d * |(-dld)d *。d*(ε|E(-dld)d*)
B.-(dld)dd*。|ε)d*(ε|E(-dld)d*)
C.(-ld)dd*E(-ld)d*|(-dld)dd*。d*(ε|E(-|E(-ld)d*)
D.(-dld)dd*E(-dld)d*l(-dld)dd*。d*(ε|E(-dd*ldd*))
●下列編號為①、②、③的正規表達式，正確的說法是_ _。
①(aa * lab)* b②(a/b)* b③((a/b)* laa)* b
(30) A .正規公式①和②的等價性b .正規公式①和③
C.正規公式②和③的等價性d .正規公式①、②和③
●在UML提供的圖中，_ _ _用於描述系統與外部系統和用戶之間的交互；_ _ _用於按時間順序描述對象之間的交互。
(31) A .用例圖b .類圖c .對象圖d .部署圖
(32) A .網絡圖b .狀態圖c .協作圖d .順序圖
●數據庫中有供應商關系S和零件關系P，其中供應商關系模式S(Sno，Sname，Szip，City)中的屬性分別表示為供應商代碼、供應商名稱、郵政編碼和供應商城市；零件號、零件名稱、顏色、重量和產地。要求壹個供應商可以供應多個零件，而壹個零件可以由多個供應商供應。請完成以下SQL語句的空白部分。
創建表SP(Sno CHAR(5)、
Pno CHAR(6)，
狀態字符(8)，
數量數字(9)，
___(Sno，Pno)，
___(Sno)，
_ _ _ _ _ _(Pno)；
查詢“紅色”零件的供應商號、零件號和數量(QTY)的元組演算表達式為:
{t|( u|？)(?v)(？w)(_ _ _ u[1]= v[1]v[2]= w[1]w[3]= ' red ' _ _)}
(33)A .外鍵b .主鍵C .外鍵(Sno)引用S
D.外鍵(Pno)引用
(34)A .外鍵b .主鍵C .外鍵(Sno)引用S
D.外鍵(Pno)引用
(35)A .外鍵b .主鍵C .外鍵(Sno)引用S
D.外鍵(Pno)引用
36)a.s(u)^s(p ^ sp(u)^s(v ^
C.P(U)^S(P) ^南(西)S(U)^P(V) ^ SP(西)
(37)a . t[1]= u[1]^ t[2]= w[2]^ t[3]= v[4]b . t[1]= v[1]^ t[2]= u[2]^ t[3]= u[4]
C.t[1]= w[1]^ t[2]= u[2]^ t[3]= v[4]d . t[1]= u[1]^ t[2]= v[2]^ t[3]= v[4]
●循環鏈表的主要優點是_ _ _ _ _ _。
(38)答:不需要磁頭指針。b .知道壹個節點的位置後，很容易找到它的直接前任節點。c .刪除後，鏈表可以保持打開。妳可以從表中的任何節點遍歷整個鏈表。
●表達式a*(b+c)-d的後綴表達式是_ _ _ _ _ _ _ _ _。
(39)a . ABCD *+-b . ABC+* d-c . ABC *+d-d .-+* ABCD
●如果二叉樹的前序遍歷序列是ABDECF，中序遍歷序列是DBEAFC，那麽後序遍歷序列是_ _ _ _ _ _ _ _ _ _。
(40)A . deb AFC B . def BCA C . deb CFA D . deb FCA
●無向圖中頂點的度數是指_ _ _ _ _ _ _ _ _ _ _。
(41) A .通過頂點的簡單路徑數b .通過頂點的回路數
C.與頂點d相鄰的頂點數。與該頂點相連的頂點數
●逐點插入建立序列(50，72，43，85，75，20，35，45，65，30)對應的二叉排序樹後，要將搜索元素30與_ _ _ _ _ _ _ _ _的子元素進行比較。
(42) A. 4 B.5 C. 6 D.7
已知三個類O、P和Q，在類O中定義了壹個私有方法F1和壹個公共方法F2；在類P中定義了公共方法F3。類P是類O的派生類，類Q是類P的派生類。它們的繼承方法如下:
P類:public O {…}；
Q類:private P {…}；
在對P類的描述中，正確的是_ _ _ _ _ _ _ _ _；關於Q類的描述中正確的是_ _ _ _ _ _。
(43) A .類P的對象可以訪問F1，但不能訪問F2。
B.類P的對象可以訪問F2，但不能訪問F1。
C.類p的對象可以訪問F1和F2。
D.類P的對象既不能訪問F1，也不能訪問F2。
(44)a . Q類的對象可以訪問F1、F2和F3。
b類q的對象可以訪問F2和F3，但是不能訪問F1。
c類q的成員可以訪問F2和F3，但不能訪問F1。
類q的d成員不能訪問F1，F2和F3。
●在類的實例化描述中，正確的是_ _ _ _ _ _。
(45) A .同壹類的對象有不同的靜態數據成員值。
不同類的對象有相同的靜態數據成員值。
C.同壹類的對象具有不同的對象自引用(this)值。
同壹類的d個對象具有不同的對象自引用(this)值。
●在某個系統中，有以下業務報表:①壹個客戶提交0個或0個以上訂單；②壹個訂單由壹個且只有壹個客戶提交。系統中有兩個類:客戶類和訂單類。對於Order類的每個實例，都有壹個Customer類的實例_ _ _ _ _ _ _ _ _；客戶類的每個實例都有壹個_ _ _ _ _ _ _ _ _客戶類的實例；
(46)A.0 B.1 C.1以上D.0以上。
(47)A.0 B.1 C.1以上D.0以上。
●在常用來描述二叉排序樹的存儲結構中，關鍵字值最大的節點是_ _ _ _ _ _ _ _。
(48) A .左指針必須為空b .右指針必須為空c .左右指針都為空d .左右指針都不為空。
壹個帶有n(n & gt；有0個頂點的連通無向圖至少有_ _ _ _ _ _ _ _ _條邊。
(49)a . n+1 b . n c . n/2d . n-1
●構造壹棵有4片葉子的霍夫曼樹，葉子的權重分別為9、2、5、7，樹的加權路徑長度為_ _ _ _ _ _ _ _ _。
(50)公元前23年至公元前37年
●在最好和最壞的情況下，時間復雜度為O(nlogn)，穩定排序方法為_ _ _ _ _ _ _ _。
(51) A .基數排序b .快速排序c .堆排序d .歸並排序
已知壹個線性表(38，25，74，63，52，48)，假設哈希函數h(key)=key%7用於計算哈希地址，哈希地址存儲在哈希表A[0..6].如果用線性檢測法解決沖突，在哈希表上等概率成功搜索的平均搜索長度為_ _ _ _ _。
(五十二)a . 1.5 b . 1.7 c . 2.0d . 2.3
●為了在狀態空間樹中_ _ _ _ _ _ _ _，可以使用LC- cost搜索快速找到壹個答案節點。在LC- retrieval中，為了避免算法過於偏向於深度檢查，應該是_ _ _ _。
(53) A .查找任意答案節點b .查找所有答案節點c .查找最佳答案節點d .遍歷。
(54) A .使用精確的成本函數c(。)進行LC-檢索b .使用廣度優先檢索。
C.使用深度優先搜索。
●基於比較的排序算法在最壞情況下的計算時間的下界是_ _ _ _ _ _ _ _ _。
(55)A . O(n)B . O(N2)C . O(logn)D . O(nlogn)
●用動態規劃法求解每對節點間的最短路徑問題時，有壹個有向圖G =
(56)A. Dk(I，j)=Dk-1(I，j)+C(I，j)
B.Dk (I，j)=min{ Dk-1 (I，j)，Dk-1 (I，j)+C(I，j)}
C.Dk (I，j)= Dk-1 (I，k)+ Dk-1 (k，j)
D.Dk (I，j)=min{ Dk-1 (I，j)，Dk-1 (I，k)+ Dk-1 (k，j) }
● PC處理人耳能聽到的音頻信號，其頻率範圍是_ _ _ _ _ _ _ _。
(57)a . 80-3400赫茲b . 300-3400赫茲c . 20-20千赫d . 22-44.1千赫
●在電視系統采用的色彩空間中，亮度信號和色度信號是分開的。下列色彩空間中，_ _ _ _ _ _色彩空間不屬於電視系統的色彩空間。
(58) A.YUV B.YIQ C.YcbCr D.HSL
●雙層雙面只讀DVD碟片的存儲容量可以達到_ _ _ _ _ _ _ _。
(59)a . 4.7 GB b . 8.5 GB c . 17 GB d . 6.6 GB
●靜止圖像壓縮標準JPEG2000中使用了_ _ _ _ _ _ _ _ _算法。
(60) A.K-L B .離散正弦變換c .離散余弦變換d .離散小波變換
●局域網中壹臺主機的IP地址為176 . 68 . 160 . 12，網絡地址為22位，所以局域網的子網掩碼為_ _ _ _ _ _ _ _，最多可以連接的主機數量為_ _ _ _ _ _ _ _。
(61)a . 255.255 . 255.0 b . 255.255.248.0 c . 255.255.252.0 d . 255.255.0
(62)a . 254 b . 512 c . 1022d . 1024
●在下列選項中，可用於遠程管理互聯網信息服務器的是_ _ _ _ _ _ _ _。
(63) A.Telnet B.RAS C.FTP D.SMTP
●在TCP/IP網絡中，為各種公共* * *服務保留的端口號範圍是_ _ _ _ _ _ _ _ _。
a . 1-255 b . 1-1023 c . 1-1024d . 1-65536
●下列網絡應用中，對帶寬要求最高的應用是_ _ _ _ _ _ _ _。
(65) A .可視電話b .數字電視c .撥號上網d .收發郵件
● DOM是壹種平臺-和語言-________API，允許程序和腳本動態訪問和更新WWW文檔的內容、結構和樣式(目前，HTML和XML文檔的定義是規範的壹部分)。可以對文檔進行進壹步處理，並且可以將處理的結果合並回所呈現的________。DOM是壹個基於_ _ _ _ _ _ _ _ _的文檔API，它要求在處理文檔時用_ _ _ _ _ _ _ _ _表示整個文檔。Dom的壹個更簡單的替代方法是基於事件的SAX，它可以用來處理不適合內存處理的非常大的_ _ _ _ _ _ _ _ _文檔。
(66) A .特定b .中性c .包含d .相關
(67) A .文字b .圖像c .頁面d .圖形
(68) A .表b .樹c .控制d .事件
(69) A .文件b .處理器c .光盤d .存儲器
(70)A . XML B.HTML c . script D . Web
●梅麗莎和洛夫萊特利用了朋友或同事之間存在的信任。想象壹下，收到朋友的壹封_ _ _ _ _ _信，要求妳打開它。這就是梅麗莎和其他幾封類似郵件的情況。壹旦運行，這些蠕蟲通常會將自己發送到受害者地址簿、以前的電子郵件、網頁中受害者的電子郵件地址。
由於管理員試圖通過識別眾所周知的__________來阻止危險的電子郵件附件，病毒編寫者使用其他擴展來繞過這種保護。可執行文件(。exe)文件被重命名為。蝙蝠和。cmd加上其他擴展的完整列表，仍然會運行並成功感染目標用戶。
通常，黑客試圖通過發送看起來像flash電影的附件來滲透網絡，該附件在顯示壹些可愛的動畫的同時，在後臺運行命令來竊取您的密碼，並讓_ _ _ _ _ _ _ _ _ _ _ _ _ _訪問您的網絡。
(71) A .附件b .數據包c .數據報d .消息
(72) A .虛擬b .病毒c .蠕蟲d .細菌
(73) A .內存b .高速緩存c .端口d .寄存器
(74) A .名稱B.cookies C .軟件d .擴展
(75) A .黑客b .用戶c .顧客d .客戶
下午試題
全國計算機技術與軟件專業技術資格(水平)考試
2005年上半年軟件設計師下午試卷
(考試時間:14:00 ~ 16:30 * * * 150分鐘)
請按照以下要求正確填寫答題卡。
1.在答題卡指定位置填寫妳所在省、自治區、直轄市和計劃單列市的名稱。
2.在答題卡指定位置填寫準考證號、出生日期、姓名。
3.答題卡上只能寫除上述內容以外的答案。
4.這份試卷有***7道題。問題1至4必答，問題5至7用1回答。每題15分，滿分75分。
5.回答的時候，字跡壹定要清晰。字跡不清的，針不評分。
6.仿照下面的例子，把答案寫在答題紙的相應欄裏。
例子
2005年上半年計算機技術與軟件全國技術資格(水平)考試日期為(1)月(2)。
因為正確答案是“5月29日”，所以在答題卡的相應欄目寫“5”和“29”(見下表)。
示例答案欄
(1) 5
(2) 29
問題1到4是必問的。
測試1 (15分)
閱讀下面的說明和數據流圖，回答問題1到3，會在題目紙相應的欄目中回答。
[描述]
學生住宿服務系統幫助學生在他們學習的城市找到他們需要的住房。系統管理和維護出租房信息、房主信息、需要租房的學生信息以及學生和房主的見面地點信息。
所有者信息包括姓名、地址、電話號碼以及系統分配的唯壹標識(ID)和密碼；房屋信息包括房屋地址、類型(單間/公寓)、適合住宿人數、租金、房主身份證以及現在是否可以出租(比如由於裝修，要等裝修後才能出租或者房子已經租出去)。每當房屋信息發生變化時，房主必須通知系統，系統會將房屋更新到檔案中，以便學生獲得可出租房屋的準確信息。業主在系統中添加可出租房屋信息時，要繳納壹定的費用，系統會自動給出費用信息。業主可以隨時更新房屋的各種屬性。
學生可以通過系統查詢現有的出租房，但必須先在系統中註冊。學生信息包括姓名、當前地址、電話號碼、出生日期、性別和系統分配的唯壹標識(ID)和密碼。如果學生想租房子，需要發出租房請求，裏面有房子的詳細信息。系統會安排學生和業主見面的時間和地點，並通知學生和業主見面信息，包括見面的時間和地點以及雙方的基本信息。系統將記錄會議信息。
學生住宿服務系統頂層框圖如圖1-1所示。學生住宿服務系統0層DFD圖如圖1-2，其中處理3的毛毛雨圖如圖1-3。
【問題1】(6分)
(1)數據流圖1-1缺少壹個數據流(圖1-2中也沒有給出)。請給出此數據流的起點和終點，並用描述中的文字給出此數據流的名稱。
(2)數據流圖1-2缺少“查詢房屋”處理相關的數據流。請指出這個數據流的起點和終點。
【問題2】(4分)
除了編寫會議文件，您還需要訪問哪些文件來進行“安排會議”處理？
【問題3】(5分)
請完成以下數據字典條目:
登錄信息=學號+密碼
註冊信息=
[數據流圖1-1]
測試二(15分)
閱讀下面的說明和表格，回答問題1到4，並將答案填入答題卡上相應的欄中。
[描述]
公司信息管理系統的需求分析和壹些關系模型的結果描述如下:
1.該公司有多個部門。每個部門都有壹個負責人，壹個辦公室，壹部電話，多名員工。每個員工最多壹個部門，負責人也是公司員工。
2.公司員工工資大於等於1000元，最低等於8000元。
3.數據庫的壹些關系模型設計如下:
員工(員工編號、員工姓名、月薪。部門編號、辦公室、電話號碼)
部門(部門編號、部門名稱、負責人代碼、工作時間)
4.“員工”和“部門”的關系示例分別見表2-1和表2-2。
[2-1]
“員工”關系
員工編號員工姓名月薪部門編號辦公室電話號碼
60801王郡華1000 1 A座201 6883122
60802楊小軍3200 1 A座201 6883122
王小華60803 4300 2 B座202 6883123
60804興2800座202 6883123
60805綠景苑5300座3 A 301 6883124
60806魯文鋒3200座3 A 301 6883124
60807牟雪松3座2800 A 301 6883124
高亞男60808號1200 4 B座302 6883125
60810李周3200 4 B座302 6883125
60820姚1200 4B座302 6883125
60821程文馳3200 5 B座303 6883126
60836徐俊坤0nu11...
[表2-2]
“部門”關系
部門編號，部門名稱，負責人代碼，工作時間
1財務部60802 2001-8-5
2市場部60803 2002年6月3日
3 R&D部門60805 2002年6月3日
4生產部1 60810 2003-8-1
5生產部2 60821 2004-6-3
【問題1】(4分)
根據說明，請給出
(1)雇員關系模式的主鍵和外鍵。
(2)“部門”關系模式的主鍵和外鍵。
【問題2】(4分)
(使用SQL定義“員工”關系模式，請在空白處填寫正確的內容。
創建雇員表(雇員號CHAR(5) (a)，
員工姓名字符(8)，
月薪是$ NUMBER美元，
部門編號CHAR(1)，
辦公室收費(20)
電話充電器(8)，
(b)(部門編號)，
檢查(月薪> = 1000且月薪< = 8000))；
(1)為有兩個或更多人的部門創建視圖D視圖(Dept，D)。
Num，D Totals，D Avgpay)，其中Dept為部門編號，D num為部門編號，D_Totals為部門編號，D_Avgpay為平均工資。請在空白處填寫正確的內容。
將視圖D_View(部門，數字，總計，費用)創建為
(選擇部門編號，(c)
來自員工
(d)計數(*)>=2，其中部門編號不為空):
【問題3】(3分)
對於表2-1和表2-2中顯示的“員工”和“部門”的關系，請在下面幾行中註明是否可以插入員工關系，為什麽？
60811
陸豐800 1 A座201 6883122
60802李瀟瀟3500街區2B 202 6883123
60812
高亞男2600
【問題4】(4分)
原來的“員工”關系模式有什麽問題？請給出修改後的“員工”和“關系模型”，不要添加新的關系模型。
測試三(15分)
閱讀下面的說明和流程圖，從可選答案中選擇應該填寫在流程圖(n)中的單詞，並將其寫在答題卡上相應的欄中。
[描述]
印刷電路板的布線區域可以分成n×m個正方形，如圖3-1(a)所示。現在朋友們需要確定電路板中兩個給定正方形的中心點之間最短的布線方案。電路只能在水平或垂直方向布線，如圖3-1(b)虛線所示。為了避免線的交叉，已經鋪好的方格要標記為被遮擋，不允許其他線穿過被遮擋的方格。
x
y
[圖3-1]
(a)布線區域應排列有列車(b)用於水平或垂直布線。
假設給定印刷電路板的起始網格X和目標網格Y沒有布線，尋找這兩個網格之間最短布線方案的基本思路是:從起始網格X開始，首先檢查壹個與起始網格距離為k的可達網格是否是目標網格Y，或者因為沒有起始網格X這個東西。