[考題] 資訊技師 資料結構 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的往前移動? 但是空間複雜度該怎麼算呢? 麻煩版上高手解惑 謝謝 -- ◆ From: 114.39.105.69
※ 批踢踢實業坊(ptt.cc)
※ 文章網址: https://www.ptt.cc/bbs/Examination/M.1368452362.A.B29.html

→ carterdunk:我想第一個問題應用disjoint set求解 05/13 23:36

→ asdd:恩恩 了解 謝謝~~ 05/14 00:06