[考題] 資訊技師 資料結構 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的往前移動?
但是空間複雜度該怎麼算呢?
麻煩版上高手解惑 謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.39.105.69
※ 編輯: asdd 來自: 114.39.105.69 (05/13 21:55)
※ 編輯: asdd 來自: 114.39.105.69 (05/13 21:57)
→
05/13 23:36, , 1F
05/13 23:36, 1F
→
05/14 00:06, , 2F
05/14 00:06, 2F