高普考題庫
103 年 103年公務人員高等考試三級考試暨普通考試・資料結構
申論 5若處理的資料,其數值均不同且已知均為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 分)