問題詳情
四、我們想設計一個動態資料結構儲存數字集合 S ={0, 1, 2, …, n – 1}的倆倆沒有交集，而且聯集等於 S 的子集合。初始時有 n 個元素，個數為 1 的子集合，分別為{0}, {1}, …, {n – 1}。我們希望這個資料結構可以支援以下兩個功能： union(x, y): x, y ∈ S。union(x, y)將包含 x 的子集合與包含 y 的子集合聯集得到一個新的子集合，原來的子集合不再存在。 equivalence(x, y): x, y ∈ S。equivalence(x, y)判斷 x 與 y 是否屬於同一個子集合，若屬於同一個子集合，則回傳 “TRUE”，否則回傳 “FALSE”。上述兩個函式必須能夠依任何順序交替執行。
【題組】⑴請描述一個可以達成上述需求而且 union (x, y)與 equivalence (x, y)的時間複雜度均為 O (log n)的資料結構。（15 分）
參考答案
答案：C
難度：簡單0.843973
統計：A(338),B(140),C(3424),D(155),E(0) #
個人：尚未作答書單：衡平原則、歐陸法系國家、成文法與不成文法
用户評論
【用戶】蘇同學
【年級】高三下
【評論內容】大陸=歐陸
【用戶】蘇同學
【年級】高三下
【評論內容】歐陸---成文
【用戶】張維之
【年級】大二上
【評論內容】C 英美法系