作者metalalive (想玩音樂)
看板Grad-ProbAsk
標題[理工] [DS] 台大電機
時間Mon Feb 6 20:52:33 2012
100台大電機
http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/100/100412.pdf
sorry ,問題/不確定的有點多,想請教...
單選題 :
2. O(h) 對嗎? 題目只說 abritrary B.T.
3. complexity是 p*K*n+(1-p)*K*lgn , 所以選e可以嗎
5. 漫花時間的一題 , collision 發生次數如下
a. 3
b. 3
c. 4
d. 2 .....選這個?
e. 5
6. 有查過wiki大概知道什麼是trie
但是還是不知道題目要問什麼情況下的 internal node 個數
複選題 :
7.我選CD
想問E , 我可以取 k=n 嗎? 題目沒說 k 是 constant的話...
8.我選BCD
想問 D , merge sort 用 singly/doube linked list 與 array
複雜度有什麼差別嗎?
9.我選 E
想問 D , 是不是錯在 O(2^n) ? 如果改成 O(2^h) (樹高) 那會對嗎?
10.我選CDE
想問 B , red-black tree 的樹高在什麼case 下, 會比 AVL tree 來的小?
想不到反例所以不敢選
想問 E , 這個敘述是對的嗎? 沒什麼概念
11.我選ABCD
想問 C ,D , 這樣的敘述是對的嗎
12.我選 ADE
想問 選項D的意思
以上
感激不盡 @O@
--
No time to pray....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.224.47.4
※ 編輯: metalalive 來自: 61.224.47.4 (02/06 21:00)
→ metalalive:哈,沒人回應 02/07 20:11
→ metalalive:還請各位高手幫個忙,感激不盡qq 02/07 20:12
推 bbhands:2. Yes 02/08 23:39
→ bbhands:3.(pK*O(n)+(1-p)K*O(log n))/K=O(pn+(1-p)logn)=O(pn) 02/08 23:42
→ bbhands:7. 題目這樣寫通常代表k是某個和n無關的值 02/08 23:44
→ bbhands:8. 我想是一樣的 都沒辦法direct access 02/08 23:46
推 bbhands:12. (D)interface function應該要能讓user使用 不該隱藏 02/08 23:52
推 bbhands:11. CD都對 02/08 23:56
推 bbhands:9. D的話，你寫O(2^h)和O(2^n)意思是一樣的 因為h=O(n) 02/08 23:58
→ bbhands: 比較好的答案我覺得是O(n) 02/08 23:59
→ metalalive:(3)跟 (9)我有點搞不太清楚,我先研究一下,感謝! 02/10 17:17