[理工] [資結] 98台大電機

看板Grad-ProbAsk作者 (code)時間14年前 (2011/12/14 19:24), 編輯推噓7(7推 0噓 7→)
留言14則, 3人參與, 最新討論串2/3 (看更多)
http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/098/098398.pdf 這份考卷我有很多小問題，希望版友不吝指教 6.(A) 如果有給插入或刪除的位置的話是O(1)若無則是O(n)這真不知道該不該選?! 11.(B)(E)不確定是true還是false? 13.(C)false top down的話是O(nlogn) bottom up O(n)所以C選項不能選?! (D)true 它用 extracting這字眼，所以代表不用調整，所以是O(1)是這樣嗎? 16.(E)false 請問這有相關定理嗎? 17.(E)是true還是false呢?!如果用union by height加上find with path compression 感覺就是true了?! 19.(A)fasle 應為O(n*m) (B)true (C)true (D)false 最多找O(n) (E)false 最多找O(n) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.116.58.22 ※ 編輯: TNC 來自: 122.116.58.22 (12/14 19:27) ※ 編輯: TNC 來自: 203.77.45.92 (12/14 19:31)
推
12/14 19:45, , 1F
11.(B) 是closed addressing
12/14 19:45, 1F
→
12/14 19:47, , 2F
11.(E)linear probing->primary cluster,quad->secondary
12/14 19:47, 2F
→
12/14 19:47, , 3F
16.是DS聖經上的一個證明喔~
12/14 19:47, 3F
推
12/14 19:58, , 4F
19.(A)應該是true沒錯
12/14 19:58, 4F
→
12/14 20:00, , 5F
19.(B)是theta(m/n),(C)是theta(m),(D)是theta(m/n)
12/14 20:00, 5F
→
12/14 20:00, , 6F
(E)是theta(n+m)
12/14 20:00, 6F
→
12/14 20:01, , 7F
17題我就有點忘了XDD"
12/14 20:01, 7F
推
12/14 21:23, , 8F
看錯題目19(A)應該是theta(n+m)..所以這一題我覺得沒答案
12/14 21:23, 8F
推
12/14 21:30, , 9F
19的E如果是n+m的話 就是m啦.. 因為n < m
12/14 21:30, 9F
→
12/14 21:31, , 10F
17題的話，他應該是少一個inverse Ackermann function
12/14 21:31, 10F
推
12/14 21:47, , 11F
所以19答案選(E)囉@口@?
12/14 21:47, 11F
推
12/14 22:29, , 12F
我覺得6(A)是對的
12/14 22:29, 12F
推
12/15 07:26, , 13F
6(A) 刪除一個node 除了要給定該node 還要給定該node之前
12/15 07:26, 13F
→
12/15 07:27, , 14F
的node 才有可能會是O(1) 因為是singly-linked-list
12/15 07:27, 14F
‣ 更多 TNC 的文章
文章代碼(AID): #1Ew8TO4O (Grad-ProbAsk)
‣ 更多 TNC 的文章
文章代碼(AID): #1Ew8TO4O (Grad-ProbAsk)