有4個問題和四個觀念確認 , 麻煩有空的版友回答了
(或是提供關鍵字也可以)
4題截取圖片 =>http://ppt.cc/5VHL
[NTUEE 103 1]
Horowitz有翻到BST的三個動作,不過不確定自己解讀正不正確....
threeWayJoin:給兩棵樹的root(small,big)和一個mid值 , 把它們合成BST
twoWayJoin:給兩棵樹的root(small,big),合出一顆BST
split:給你樹,k值, 依k把樹拆成small,mid,big
不過都沒圖例 =口=....我依自己估狗到的蔡老師投影片,做出下面的樹
s→3 b
／|＼ ↙
2 | 12
／ | ／|＼
1 4 | 13
|＼| ＼
| 11 16
|／| ／
7 | 15
／＼ /／
6 / 9/14
／ ／＼\
5 8 ↑10
mid
[NTUEE 102 3]
用queue , 又有stack pointer ... operation又是stack動作 , infix轉prefix..
不知道怎麼下手
(目前只知道利用stack做到: 1,中序轉前序或後序 2,計算前序或後序算式值
其實想法上是一樣的,只是由左至右還是由右至左的差別 , 不過這題也限制方向與次數
有請高手幫忙)
[NTUEE 97 19]
是從load factor下手嗎 ? 不清楚從哪個方向討論
[NTHU 103 5&6]
配分很重 , 有幾個答題上的問題
Q1 : storage mechanism 和 index structure是分開的嗎 ?
Q2 : 有實作王可以提供作答上的想法嗎?
[NTUEE 98 6(d)]
T or F :
Given the pointer to the node to be deleted , the node deleting operation
of a doubly-linked-list has lower complexity than that of a singly-linked-list.
如果給指定data值於 link-list刪除 , 兩者都要花O(n)
如果給定node指標於 link-list做刪除 , singly O(n) , doubly O(1)
固此敘述應該是T ?
[NTUEE 98 11(c)]
T or F :
Rehashing is a way to overcome primary clustering, which is when record begin
to accumulate in long string of adjacent positions instead of being uniformly
distributed throughout the table
Rehashing 和 double hash講的是同一件事情嗎 ?
還是rehashing只是廣義的collision Resolution的通稱?
i,e, linear probing , quadratic probing ....包含於 rehash?
[NTUEE 98 20(e)]
請問當在hash table中刪除key值通常是怎麼做 ?
e.g. 考慮hash table有5個bucket , 每個bucket皆只有一個slot , 發生collision採
linear probing , 依序插入 5,10,15,20 , 再刪除15應該會得到哪種hash table?
index content index content
0 5 0 5
1 10 1 10
2 x 2 20
3 20 3 x
4 x 4 x
主要想問的是刪除之後 , rehash path之後的key值會遞補上來嗎 ?
(如果是的話,越複雜的rehash機制會費很多功夫在修正上...)
[NTUEE 98 17]
討論Disjoint Sets的 Union & Find , Weighting Rule和Collapsing Rule是改善兩者
performance的方式 , 能讓 Find效率提升為 O(log n)
Q1:
討論類似的問題時 , 是否都是以一個set就是一個點做討論 ?
否則點數總共為n的Union & Find , 我取
T1: n1 T2: nth (第n個點獨立一個set)
↑
n2
.
.
.
第n-1個點
Union(T1,T2) 樹高是 n-1
即使採用上面的rule , 樹高也會是O(n)?
Q2: 做u次 Union ,f次 Find , 過程中皆遵守兩個Rule , 則複雜度是Θ(u+f)
原文書是寫 α(f) , 我自己的解讀是:
僅有幾個深度夠的點會花到O(logn) , 但會順便完成path compression , 可以讓
後續path上的find只要O(1)完成 , 分攤下來後幾乎只要常數就能完成find ?
這次積的有點多 , 先謝謝有看過der你