試題詳解

在表示一個連通圖(connected graph)時，可以選用連結串列(linked list)或是矩陣 (array)的資料結構。若 n 表示連通圖上點的個數，則下列敘述何者不正確?
(A) 當一個連通圖不為完全圖 (complete graph)時，矩陣較 Linked-list 需較少的記憶體
(B) 使用矩陣資料結構，可在 O(1)時間內，確定圖上的兩點是否相鄰(adjacent nodes)
(C) 使用連結串列資料結構，最多需 O(n)時間內，確定圖上的兩點是否相鄰(adjacent nodes)
(D) 對一完全圖，矩陣與連結串列皆需 n2 的記憶體