測驗達人

susan
博一上
54270次
司法特考錄..
高二下
53569次
魯筱筱
研二下
44573次
(+35次)
Cyril..
研二上
38256次
(+6次)
錄事考試
小六下
25910次

公職◆資料結構題庫

【非選題】

五、若處理的資料,其數值均不同且已知均為 1 到 100 之間的整數或小數。若 K≦X<
K+1,集合 Lx 代表數值在[K,K-1]間全部資料,1≦K≦99, K 為整數,資料結構支援
下列功能。
Insert(X):增加 X,若 X 不存在 Lx 中。
Delete(X):移除 X,若 X 存在 Lx 中。
List(X):將 Lx 中的資料全部依序印出。
設計一資料結構滿足在最差情況的條件分析(Worst Case Analysis),每個功能的執
行時間要求為:Insert(X) and Delete(X)須在 O(log |Lx |)時間內完成,List(X)則須在
O(|Lx |)時間內完成。請說明設計的資料結構為何?並解釋其執行時間為何滿足需求?
(15 分)

#15577
編輯私有筆記