國中教甄｜資訊科技資訊科技108 年第 17 題單選題
圖形(Graph)為常見的資料結構，一般有兩種常用的表示法(representation)，相鄰矩陣(Adjacency Matrix)和相鄰串列(Adjacency List)，請問下列比較何者正確？
A就使用空間而言，邊(Edge)數量較多則適合使用 Adjacency List
B就存取資料而言，Adjacency Matrix 存取資料時會稍微快一些正確答案
C就新增邊的時間複雜度而言，Adjacency Matrix 中增加一條邊，需要 O(|E|)
D就刪除邊的時間複雜度而言，Adjacency Matrix 中刪除一條邊，需要 O(|E|)
B正確答案
相鄰矩陣透過陣列索引直接查詢邊的存在與否，時間複雜度為 O(1)，故存取資料較相鄰串列快速。
逐選項解析
A就使用空間而言，邊(Edge)數量較多則適合使用 Adjacency List✕ 錯誤
邊數量較多（密集圖）時，相鄰串列的節點與指標額外開銷較大，通常適合使用相鄰矩陣；邊數量較少（稀疏圖）才適合使用相鄰串列以節省空間。
B就存取資料而言，Adjacency Matrix 存取資料時會稍微快一些✓ 正確
相鄰矩陣可透過二維陣列索引直接確認兩頂點間是否有邊，時間複雜度為 O(1)；而相鄰串列需遍歷該頂點的串列，最壞情況為 O(|V|)，故相鄰矩陣存取（查詢）較快。
C就新增邊的時間複雜度而言，Adjacency Matrix 中增加一條邊，需要 O(|E|)✕ 錯誤
D就刪除邊的時間複雜度而言，Adjacency Matrix 中刪除一條邊，需要 O(|E|)✕ 錯誤
立即註冊,看完整詳解
這題的完整詳解,註冊就能看 · 每天 2 題免費
- 完整逐選項解析
- 秒殺解題技巧與破題關鍵
- 關鍵知識表整理
- 陷阱與易錯提醒
- 同考點歷屆題庫連續刷題與錯題本
