Q192.
下列敘述何者正確？
電腦軟體設計共同科目 · 乙級 · Q192
難易度分析
3 / 5
本題要求對圖論多個核心基礎概念進行精確辨析，選項中包含容易混淆的資料結構對應關係與圖論基本定理，需準確掌握各定義之差異方能正確排除干擾項。
正確答案：④相鄰矩陣(Adjacency Matrix)可以表示有方向圖(Directed Graph)
④ 相鄰矩陣(Adjacency Matrix)可以表示有方向圖(Directed Graph):相鄰矩陣(Adjacency Matrix) 可有效表示有向圖，矩陣中 `A[i][j] = 1` 代表存在從頂點 i 指向頂點 j 的 有向邊，且 `A[i][j]` 與 `A[j][i]` 可獨立設定，符合有向圖特性。
錯誤選項解析
- ① 圖形採深度優先搜尋(Depth-First Search)追蹤是利用佇列結構:深度優先搜尋(DFS) 實際使用的是 堆疊(Stack) 結構（遞歸呼叫堆疊），而非佇列；使用佇列結構的是 廣度優先搜尋(BFS)。
- ② 最小展開樹(Minimum Spanning Tree)是唯一的:最小展開樹(MST) 並非唯一，當圖中存在 權重相同的邊 時，可能產生多棵不同的 MST；僅在所有邊權重皆不同時，MST 才唯一。
- ③ 一連通圖(Connected Graph)若有n 個頂點，則至少具有n 個邊:一連通圖若有 n 個頂點，至少需要 n-1 個邊 即可連通（如樹狀結構），而非 n 個邊；n 個邊會形成至少一個 環路(Cycle)。
Learning Tip
"本題核心考點為 圖的遍歷方式與資料結構對應關係（DFS→Stack、BFS→Queue）以及 圖的表示法（相鄰矩陣 vs 相鄰串列）。常考陷阱包括：混淆 DFS 與 BFS 使用的資料結構、誤認 MST 唯一性（需記住「邊權重全不同時才唯一」）、以及連通圖最少邊數為 n-1 而非 n。相鄰矩陣適合 稠密圖，相鄰串列適合 稀疏圖，此為實務上選擇資料結構的關鍵考量。"
學員答題分佈
①圖形採深度優先搜尋(Depth-First Search)追蹤是利用佇列結構0%
②最小展開樹(Minimum Spanning Tree)是唯一的0%
③一連通圖(Connected Graph)若有n 個頂點，則至少具有n 個邊0%
④相鄰矩陣(Adjacency Matrix)可以表示有方向圖(Directed Graph)0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！
相似類型題目
若一個圖形以下列相鄰矩陣(Adjacency Matrix)來表示，有關該圖形之特性，下列敘述何者是正確的？
以相鄰矩陣(Adjacency Matrix)儲存一個有向(Directed)權重圖(Weighted Graph)，下列敘述那些是正確的？（符號∞代表距離無限大）
以相鄰矩陣(Adjacency Matrix)儲存一個有向(Directed)權重圖(Weighted Graph)，下列敘述那些是正確的？（符號∞代表距離無限大）
以相鄰矩陣(Adjacency Matrix)儲存一個有向(Directed)權重圖(Weighted Graph)，下列敘述哪些是正確的？（符號∞代表距離無限大）
若一個圖形以下列相鄰串列(Adjacency List)來表示，有關該圖形之特性，下列敘述那些是正確的？