[理工] [DS]100台大電機丙

作者: winnie48 (winnie)   2015-01-09 09:25:34
100年題目連結:
http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/100/100412.pdf
1. 第10題的E 為什麼是對的 : B-tree的搜尋時間是O(h logm) , 當m增加時,雖然高度h
會變小,但是logm會變大,要怎麼保證時間一定變小呢?況且不管m是多少,space usage
都是O(n) (n是元素個數)?
2. 第16題的C為什麼是錯的:查到clique cover problem 是指圖中的點能被分成幾個cli
que。我畫出來是這樣:
http://i.imgur.com/kJQk5JQ.jpg
還是我哪裡誤會了?
謝謝大家!
作者: kather (Kather)   2015-01-09 11:35:00
1. 我覺得是access disk成本降低 影響遠大於在mem裡search2. 我畫出來也是3個 囧?edge clique cover=>每邊都要cover到vertex clique cover=>每點而題目沒說是哪種 假設是兩個都包含(所有邊 所有點)那就不只了
作者: winnie48 (winnie)   2015-01-09 12:16:00
原來clique cover 還分這兩種!謝謝!

Links booklink

Contact Us: admin [ a t ] ucptt.com