推 qoojordon: 先謝過,第二題看到stack用兩個queue實作瞬間突破盲腸 12/18 22:40
※ 引述《qoojordon (穎川琦)》之銘言：
: 有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,計算前序或後序算式值
: 其實想法上是一樣的,只是由左至右還是由右至左的差別 , 不過這題也限制方向與次數
: 有請高手幫忙)
Java code:http://ideone.com/M6EF6f
應該是對的(吧)
: [NTUEE 97 19]
: 是從load factor下手嗎 ? 不清楚從哪個方向討論
(A)True
(B)?
(C)?
(D)應該是O(n)?
(E)該應不會是(1)吧..但也不知道是幾
: [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 ?
痾 false?
給定指標了
singly的操作:
now->data = now->next->data
node* temp = now->next->next
delete(now->next)
now->next = temp
doublly則要兩次(一個往前一個往後)
: [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?
覺得是false
Rehashing就是處理collision的方法
包含linear probing , quadratic probing , double hashing 等
double hashing可以避免 , 其他兩個則否
: [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你
cormen本有分析 但是太複雜了看不懂XD
只知道阿法很小 比lg(f)還小
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.237.38.26
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1418909616.A.C73.html