Examly題庫立即開始練習
國中教甄|資訊科技資訊科技114 年第 5 題單選題

一個無向圖(undirected graph)共有 6 個頂點(vertices),分別為 A,B,C,D,E,F,頂 點彼此間的連接關係以鄰近矩陣(adjacency matric)表示如下(0 表示不相連,1 表示有相 連): A B C D E F A 0 1 1 0 0 0 B 1 0 0 1 1 0 C 1 0 0 0 1 1 D 0 1 0 0 1 0 E 0 1 1 1 0 1 F 0 0 1 0 1 0 請以「廣度優先搜尋(Breath First Search,BFS)」方式,從 A 開始拜訪,並假設一旦需要 將多個相鄰頂點加入佇列(queue)時,會依照頂點英文字母排序(由前到後)的規則將其排 入佇列。請問最終 BFS 的拜訪次序為何?

AA → B → C → D → E → F正確答案
BA → B → D → C → E → F
CA → C → B → D → F → E
DA → C → B → E → D → F
答案與詳解
A
正確答案
根據鄰近矩陣與字母排序規則執行廣度優先搜尋,即可得出正確的拜訪順序。

為什麼答案是 A

從 A 開始,相鄰 B、C 依字母順序入列;接著取出 B,其未拜訪相鄰 D、E 入列;取出 C,其未拜訪相鄰 F 入列;最後依序取出 D、E、F,順序為 A-B-C-D-E-F。

載入中…

資訊科技 相關題目

想練更多資訊科技考古題?

Examly 收錄 38 萬+ 道歷屆題目,每題都有像這樣的精選詳解。免費下載,立即開練。

黑皮