民國115年 普通考試 統計 資料處理概要
第1題
某政府機關建置全國人口統計資料交換網路，各統計中心之連線關係： (A,B)、(A,C)、(B,D)、(C,F)、(D,E)、(F,D)，其中A 為中央統計中心，…
題目
某政府機關建置全國人口統計資料交換網路，各統計中心之連線關係： (A,B)、(A,C)、(B,D)、(C,F)、(D,E)、(F,D)，其中A 為中央統計中心，其 餘為各區域統計中心。中央統計中心A 需將最新人口統計資料傳送至各 區統計中心。請畫出連結圖，利用以下兩種搜尋法傳送資料，寫出資料 傳送順序：廣度優先搜尋法（Breadth First Search, BFS）、深度優先搜尋 法（Depth First Search, DFS），若有多個尚未拜訪的相鄰節點則依英文字 母順序選擇；並請利用BFS 說明由中央統計中心傳送資料到E 的最短 邊數路徑與其經過之節點。（30 分）
參考解答（AI 生成，非官方）
- 一、圖形結構：以A為根節點，邊為（A,B）、（A,C）、（B,D）、（C,F）、（D,E）、（F,D）。各節點相鄰情形為：A相鄰B、C；B相鄰A、D；C相鄰A、F；D相鄰B、E、F；E僅相鄰D；F相鄰C、D。全圖有6個節點、7條邊且連通，因C-F-D形成迴路，所以不是樹。繪圖時建議將A置於頂層，B、C置於第二層，D、F置於第三層，E置於第四層，並標明各邊方向與節點名稱；考生請依此描述自行繪製。
- 二、廣度優先搜尋（Breadth First Search, BFS）：使用佇列（Queue）先進先出。先拜訪A，並依字母順序將B、C入列；取出B，將尚未拜訪的D入列；取出C，將F入列；取出D，E入列（F已在列中）；再依序取出F、E，兩者均無新節點。資料傳送順序為A→B→C→D→F→E。
- 三、深度優先搜尋（Depth First Search, DFS）：使用堆疊（Stack）或遞迴，優先走字母最小的相鄰節點。由A走B，再由B走D；D的相鄰節點E、F中先選E，E無其他出路便回溯至D，再拜訪F；F的相鄰節點C尚未拜訪，故續走C後結束。資料傳送順序為A→B→D→E→F→C。
- 四、最短路徑：BFS依層次拜訪，A為第0層，B、C為第1層，D、F為第2層，E為第3層。A至E的最短邊數為3，路徑為A→B→D→E；另一條A→C→F→D→E需4條邊，較長。BFS首次抵達某節點時所走的路徑必為最短邊數路徑，此為其重要性質。
- 五、作答提醒：應完整標示佇列或堆疊的變化過程、已拜訪集合，以及同層依英文字母排序的規則，並註明最短路徑的邊數與經過節點，避免只寫順序而漏列推理過程。
AI 依官方試題文字產生的參考解答，非考選部公告答案，內容僅供備考參考。