推 qoojordon: 謝謝回答 12/19 22:20
※ 引述《kather (Kather)》之銘言：
: ※ 引述《qoojordon (穎川琦)》之銘言：
: : [NTUEE 97 19]
: : 是從load factor下手嗎 ? 不清楚從哪個方向討論
: (A)True
: (B)?
: (C)?
: (D)應該是O(n)?
: (E)該應不會是(1)吧..但也不知道是幾
題目沒有寫 average 是 average 什麼東西？ 是說h(key)是 uniform？
如果是，那(B)和(C)應該都是true。
: : [NTHU 103 5&6]
: : 配分很重 , 有幾個答題上的問題
: : Q1 : storage mechanism 和 index structure是分開的嗎 ?
: : Q2 : 有實作王可以提供作答上的想法嗎?
: 不知
(5)
說要 store 的話就猜 B-Tree，index就猜hash。
(6)
說要 store 的話就猜 B-Tree，index就猜binary trees，因為可以作range query。
: : [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則要兩次(一個往前一個往後)
這應該是只有簡單的系統才可以這樣作，因為搞不好系統有其他部分有指標指到
next node，你把next delete之後那些指標都錯了..
: : 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), 來自: 129.170.195.148
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1418913904.A.8E5.html