資訊技師 資料結構 100年 - 考試

1.
一個大型社群網路（network）中可能包含多個興趣小社群（interest group），社群

網路常使用圖形（graph）為模型（modeling）。

請描述找出小社群（graph connected components）的方法。

請問這題是要用articulation point去解嗎?還是一般的相鄰串列 相鄰矩陣就可以了?


2.

雜湊表（Hash table）是根據索引鍵的雜湊函數（hashing function）組織而成的索引

鍵/值組集合。請說明運算（search, insert, delete）的時間複雜度及空間複雜度。

我覺得平均時間複雜度應該是O(n) search最佳是O(1) 最差是一路collision到底

insert 同search delete最佳O(1) 最差是不是要將之前collision的往前移動?

但是空間複雜度該怎麼算呢?

麻煩版上高手解惑 謝謝

--