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

[TNC (code)]

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)
推 kiwidoit:11.(B) 是closed addressing
→ kiwidoit:11.(E)linear probing->primary cluster,quad->secondary
→ kiwidoit:16.是DS聖經上的一個證明喔~
推 kiwidoit:19.(A)應該是true沒錯
→ kiwidoit:19.(B)是theta(m/n),(C)是theta(m),(D)是theta(m/n)
→ kiwidoit:(E)是theta(n+m)
→ kiwidoit:17題我就有點忘了XDD"
推 kiwidoit:看錯題目19(A)應該是theta(n+m)..所以這一題我覺得沒答案
推 FRAXIS:19的E如果是n+m的話  就是m啦.. 因為n < m
→ FRAXIS:17題的話，他應該是少一個inverse Ackermann function
推 kiwidoit:所以19答案選(E)囉@口@?
推 show8822:我覺得6(A)是對的
推 FRAXIS:6(A) 刪除一個node 除了要給定該node 還要給定該node之前
→ FRAXIS:的node 才有可能會是O(1) 因為是singly-linked-list