[課程] 資料結構期末考重點整理
資料結構期末考重點整理 Exam at 9:30 on 2008/06/18
Hash
- 名詞解釋：collision 碰撞 同義字：Synonyn
h(x)=h(y)
Overflow 溢位
- Bucket的儲存空間滿了
- 對同一個Bucket的Collision數量超過slot的數量時
載入密度(Loading Factor)
- Loading Density
- α=N/(SB) i.e 總資料量/槽數*桶數
Perfect Hashing
- No collision，no overflow
P.8 (記)Hash：優缺點、設計原則
：方法 (Explain＆How)
-
- 折疊
- Digital Analysis
P.10 clustering of the keys 很多key 連在一起?
P.11 如何做
P.16 解釋或舉例子
P.19 如何拆
P.25
＊P.28 Overflow 怎麼辦?
＊P.29 常見的溢位處理方法
| ＊- Linear probing：資料刪除時怎麼處理
| - Quadratic probing
| - Rehashing
|
|
P.41 平方探測法
P.45 如何做 Double Hashing --作例子
2個Hashing Function
P.47 解決Overflow的方法
Chaining鏈結串列
CH.7
＊P.46 Heap Sort
- adjust
P.52 Sorting Several Keys 不同的Key
P.58
| front 271 串93，33，…9
P.60 如何串 個、十、百…
P.61 說明記起來
P.62
| External Sort
P.64 (應該必考) 了解How to do ---P.63---
步驟：利用記憶體750 merge(上課講的)
P.67 (可能會考) K-way K↗愈好？
P.68 可能會考
P.70 Huffman
先merge
P.78 P.79 O(1) 演算法步驟 write down
＊ | 必考 ＆跑例子
P.81
P.85以後不考
＊ 表示必考！！！
＊其他必考
＊ 上次沒考的AVL
＊ Order 1 Space(應該就是上面P.79吧)
＊ Shell Sort 元澤的講義有
p.s 對了，我記得我有看到學弟上課的時候邊聽重點邊po版，怎都沒看到阿...
然後以上重點整理是老師上課講的，如有錯誤請大家幫忙更正一下。
By RogerKao
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.134.226.214
推
06/17 17:47, , 1F
06/17 17:47, 1F
※ 編輯: RogerKao 來自: 220.134.226.214 (06/17 17:54)
→
06/17 17:55, , 2F
06/17 17:55, 2F
※ 編輯: RogerKao 來自: 220.134.226.214 (06/17 18:04)