什麼是鏈結串列

正確答案：A. 若已知插入位置的前一個元素，只要改接指標就能插入，不必移動其他元素；但要讀取第 i 個元素，必須從開頭依序走訪

在鏈結串列中，只要知道插入或刪除的位置，改寫前後的指標即可，只需 O(1)。另一方面，要讀取第 i 個元素必須從開頭追蹤 i 次指標，需要 O(n)。陣列可由起始位址與元素大小算出第 i 個元素的位址，因此能以 O(1) 讀取，但在中間插入時需要把後面的元素往後挪，要花 O(n)。此外，陣列的元素連續排列，快取與預取容易發揮效果；鏈結串列的節點容易散落在記憶體各處，即使同樣是 O(n) 的走訪，也可能慢上許多。

正確答案：A. 鏈結法在負載因子超過1時也能存放，但開放定址法無法存放超過表大小的元素，且負載因子接近1時搜尋次數會急遽增加

鏈結法把相同位置的元素串成串列，因此元素數超過表的大小也能存放，但串列的平均長度與負載因子成正比增加，搜尋的工作量也隨之增加。開放定址法只存放在表中，元素數最多只能到表的大小，負載因子接近1時尋找空位的次數會急遽增加。無論哪種方法，負載因子超過設定值（例如約0.5～0.75）時，通常都會放大表格並重新放入所有元素（重新雜湊）。開放定址法也會發生碰撞，是靠尋找空位置來處理。